How to optimize performance of sequential condition checks in Java?

Question

I am writing a program that looks for a solution of a diophantine equation. The program is cycling

for (int d = 0; d <= max; d++) {
    for (int c = 0; c < d; c++) {
        boolean possibleSolution = true;  
        possibleSolution =test1(c,d);
        if(possibleSolution) {possibleSolution =test2(c,d);}
        ...
        if(possibleSolution) {possibleSolution =test30(c,d);}
        if(possibleSolution) solutionFound(c,d);
    }
}

My testN methods are reasonably optimized. Most solutions are removed by a simple test1, but program has to run 30 pointless if(possibleSolution) checks. Is there a way to directly go to a new cycle of the testN yields false. Can a try ... catch block or some similar structure be adopted for this purposes?

Answer 1

Based on your question break; will NOT work for you. You want to skip all further steps in this cycle, do c++ and go for a new round. This is done using continue. Break will end inner cycle do d++ and start inner cycle from 0.

Answer 2

Measure first instead of making assumptions.

The sequence of 30 tests "if (possibleSolution)" is something that a good compiler should be able to optimise away. At the first "if (possibleSolution)" a good compiler would generate code that doesn't only skip one call, but figures out immediately that the second, third, and so on if are also going to fail, so it would generate code that jumps right past the call to solutionFound ().

An ugly but effective way of doing this by hand is using good old goto if your language / coding standards support it.

if (! test1 (c, d)) goto nosolution;
if (! test2 (c, d)) goto nosolution;
...
if (! test30 (c, d)) goto nosolution;
solutionfound (c, d);
nosolution: ;

An almost equally ugly way avoiding goto is this:

do {
    if (! test1 (c, d)) break;
    if (! test2 (c, d)) break;
    ...
    if (! test30 (c, d)) break;
    solutionfound (c, d);
} while (0);

But to make it fast, you want to minimise the total running time of all the test you are doing. To do this, measure for each test how long it runs, and how much the probability is that it is decisive, that is it determines there is no solution. Then you sort the test, doing the one with the smallest ratio of execution time divided by probability that the test decides the outcome. If one test takes 5 microseconds and has a 10% chance of failing, and another takes 7 microseconds with a 20% chance of failing, we do the second one first. (This has little effect if it is highly likely that all 30 tests pass).

This gets more complicated if the tests are not independent.

Answer 3

Replace

 If(pass) pass=testN(c,d);

With

  If(!testN(c,d)) {break;}

This way you get to a new cycle right away.

Answer 4

I'm not sure if this is what you mean, but you can do such a thing with a labeled break/continue (http://docs.oracle.com/javase/tutorial/java/nutsandbolts/branch.html):

main: for (int d = 0; d <= max; d++) {
    subMain: for (int c = 0; c < d; c++) {
        boolean possibleSolution = test1(c,d);
        if(!possibleSolution)
            continue main;
        possibleSolution = test2(c,d);
        ...
        if(possibleSolution)
            break main;
        else continue subMain;
        ...etc.
    }
}

Answer 5

You could use java 8's Streams, which will do short-circuiting under the hood for you.

To get around some boxing/unboxing you can define this internal interface :

private interface SolutionTest {
    boolean test(int a, int b);
}

With this in place you can introduce these helper methods :

private boolean isPossibleSolution(int c, int d) {
    return allTests().anyMatch(solutionTest -> solutionTest.test(c, d));
}

private Stream<SolutionTest> allTests() {
    return Stream.of(
                this::test1,
                this::test2,
                //...

                this::test30
        );
}

Which will allow the main code to be as simple as :

IntStream.rangeClosed(0, max)
        .forEach(d -> IntStream.range(0, d)
                .filter(c -> isPossibleSolution(c, d))
                .findFirst()
                .ifPresent(c -> solutionFound(c, d)));

anyMatch() and findFirst() are the methods that do all the short circuiting for you. And as a bonus it's all a lot less verbose, and way more readable.