CODEWITHSUNDEEP
java
aprilsky
aprilsky

Reputation: 131

Nested if-statement in loop vs two separate loops

Here is the source code:

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
        }
    }
    return -1;
}

Why doesn't one this: have only one loop and the if-statement. 

public int indexOf(Object o) {

   for (int i = 0; i < size; i++){
       if (o == null) {
             if (elementData[i]==null)
                return i;
        else {
             if (o.equals(elementData[i]))
                return i;
        }
    }

    return -1;
}

The first snippet has to have two loops, but some say the above code performance is good. Why?

Upvotes: 10

Views: 4403

Answers (4)

Jon Hanna
Jon Hanna

Reputation: 113392

The second form checks whether o == null or not, size - 1 fewer times.

Assuming that such an optimisation isn't done for you anyway. Which wouldn't be something to assume without trying it.

There can also be advantages sometimes in having less instructions in the final machine code in the loop, though it's very unlikely to make any difference.

Reducing the number of possible branches can improve performance too, because it's less likely that the wrong instructions where prefetched. (thanks Andreas Henning).

In all, the idea of moving things outside of loops is a reasonable enough thing to do when you need to optimise something, but probably not likely to matter in this case.

Just seeing your comment. Considering how much code out there hits into ArrayList.indexOf, it's a reasonable place to do every little squeeze you can think of.

Upvotes: 0

ronalchn
ronalchn

Reputation: 12335

With a single loop, you have to recheck the condition on each iteration - hence more work.

With the first example, you only check the condition once.

If compiled without optimization (in a literal way), then the 2nd example will be slower.

However, most compilers do have tricks, and can convert the code in the 2nd example to machine code equivalent to that of the first example. However, this heavily depends on compiler optimization flags (ie. what is optimized - running time or code size)

Upvotes: 0

David Schwartz
David Schwartz

Reputation: 182883

The thinking is that the first one only has to compare o to null once while the second one has to compare it each pass in the loop.

Upvotes: 0

Andreas Grapentin
Andreas Grapentin

Reputation: 5796

effectively, both snippets do the same. However, the second snippet could perform worse because the comparison statement is evaluated multiple times, as opposed to only a single comparison in the first snippet. The number of loop iterations each code snippet goes through are the same, but the number of comparisons needed differs. simple as that.

Upvotes: 4

Related Questions