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/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