Nested if-statement in loop vs two separate loops

Question

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?

Not an array list, a bit unclear as to what you're asking. To answer the question directly, yes the code has two loops, but only one can ever be executed. The second piece of code has one loop but checks the boolean condition every time through, which degrades performance. Most of the time though, you don't need to do unnecessary optimization like this, so it's okay to do either approach (unless speed is critical). — Makoto
– Makoto, Commented Sep 1, 2012 at 1:16
by the way, I don't think this question deserves downvotes. It's covering some very basic ground in software engineering, but it's still a valid question and could be a helpful reference to others. — Andreas Grapentin
– Andreas Grapentin, Commented Sep 1, 2012 at 1:28
thank you ,this code is ArrayList #indexOf() method , and when i look the source code ,i found this. — aprilsky
– aprilsky, Commented Sep 1, 2012 at 1:29

Andreas Grapentin · Accepted Answer · 2012-09-01 01:26:17Z

5

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.

answered Sep 1, 2012 at 1:26

Andreas Grapentin

5,8265 gold badges42 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

David Schwartz · Accepted Answer · 2012-09-01 01:26:19Z

0

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.

answered Sep 1, 2012 at 1:26

David Schwartz

184k18 gold badges229 silver badges293 bronze badges

Comments

ronalchn · Accepted Answer · 2012-09-01 01:26:49Z

0

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)

answered Sep 1, 2012 at 1:26

ronalchn

12.4k10 gold badges53 silver badges61 bronze badges

3 Comments

Andreas Grapentin Over a year ago

looks like java to me. is the jvm able to optimize stuff like this? I mean, it's basically just horrible and inefficient style, that noone should ever think of writing.

Jon Hanna Over a year ago

@AndreasHenning I haven't read anything about JVM optimisations in a long time, but the sort of things being talked about when I did went much beyond hosting a check against a local, like this does.

ronalchn Over a year ago

I don't know exactly what is optimized, but there is an -O flag for javac, which might do some optimizations. Many optimizations are actually done with the JIT compiler at runtime.

Jon Hanna · Accepted Answer · 2012-09-01 01:37:08Z

0

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.

edited Sep 1, 2012 at 1:37

answered Sep 1, 2012 at 1:30

Jon Hanna

114k10 gold badges151 silver badges258 bronze badges

2 Comments

Andreas Grapentin Over a year ago

depends. there's not much else in the loop. if the code is compiled/interpreted literally, and size is large, then the surprisingly expensive conditioned branches could have a major impact on the performance.

Jon Hanna Over a year ago

@AndreasHenning I completely forgot about branching costs. Good call.

Collectives™ on Stack Overflow

Nested if-statement in loop vs two separate loops

4 Answers 4

Comments

Comments

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related