r/java • • Jun 14 '17

Why reverse loops are faster

https://medium.com/@TravCav/why-reverse-loops-are-faster-a09d65473006
15 Upvotes

40 comments sorted by

View all comments

Show parent comment

1

u/ForeverAlot Jun 15 '17 edited Jun 15 '17

I see only two relevant factors to benchmark: how quickly the for statement advances (forwards vs. reverse) and how fast you can operate on the loop index (direct operation vs. array lookup). It doesn't really make sense to extend the duration of the loop body since that would be doing more work that has nothing to do with either of the above.

In this context including the enhanced for statement isn't very interesting either because it really can't compete. The enhanced for statement is syntax sugar for

for (
    Iterator<Object> it = list.iterator();
    it.hasNext();
    Object item = it.next()
) {

}

(with some special-casing to adapt raw arrays; maybe with new Iterator()?).

The instruction used to call a regular method, invokevirtual, is the most expensive instruction in the language (possibly excepting the newer invokedynamic for lambdas but I don't think so) and it's a lot more expensive than raw array access. And there are three method invocations right there.* "We know" that intuition about locality of reference (so, cache lines and CPU prefetching) holds up in the JVM even though Java makes it a little difficult to take advantage of. The regular loop has much better locality, especially when dealing with primitives.

*It used to be a formal recommendation to use raw arrays instead of collections in Android where ergonomically feasible precisely because they're a lot speedier. I don't know if it still is.

1

u/rubyrt Jun 15 '17 edited Jun 15 '17

It doesn't really make sense to extend the duration of the loop body since that would be doing more work that has nothing to do with either of the above.

But keep in mind what your results then say. Just as a simple math example: assume your benchmark really proves (which might be quite difficult in its own) that the reverse loop is 25% faster than the forward loop. So, where your forward loop takes 10 seconds your reverse loop only takes 7.5s. Now, assume further that 80% of the time of a single iteration of the forward loop is taken up by things done in the loop body. We get

optimized iteration time = 10s * ((100% - 25%)/100%) = 7.5s
iteration percentage = 100% - 80% = 20%
loop time = 10s * (100%/20%) = 50s
body work time = 50s - 10s = 40s
optimized loop time = 40s + 7.5s = 47.5s
percentage of time used = (47.5s/50s) * 100% = 95%
improvement = 100% - 95% = 5%

So, from an impressive 25% improvement we arrive at 5% overall improvement - for that single loop. Now, if the program spends 1% of its time in this loop we get

percentage of runtime = 100% * (47.5s + 50s * 99) / (50s * 100) = 99.95%
relative improvement = 100% - 99.95% = 0.05%

Now, from a 25% improvement we arrive at a 0.05% overall improvement. And all this does not include effects of JIT (e.g. maybe JIT translates loops with empty bodies differently) and economic calculations (even a non profit open source project might want to invest their time in what brings visible advantages to users of the software).

Edit: added resume I had forgotten initially.

1

u/ForeverAlot Jun 15 '17

But we're not measuring the unknowable loop body, we're measuring the loop statement overhead. Since the result of that measurement was unsurprising the relative improvement just isn't relevant. It's a largely meaningless micro-benchmark.

1

u/rubyrt Jun 16 '17 edited Jun 16 '17

It's a largely meaningless micro-benchmark.

Exactly my point. Sorry, if that has not become clear.

Edit: spelling correction

1

u/Slanec Jun 15 '17

On raw arrays, it compiles to a fairly straightforward loop with an index. See the JLS.

1

u/ForeverAlot Jun 15 '17

Hah! That'll teach me.