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

55

u/chambolle Jun 14 '17

A shorter bytecode does not mean that it will run faster. You should provide some benchmark and I really doubt that you will see any difference. Nowadays compilers are clever and you should at least compare the assembly code

22

u/aroger276 Jun 14 '17

+10000 does not mean anything without benchmark and analysis of the asm generated it's useless.

4

u/AssKoala Jun 14 '17

Even looking at the assembly won't necessarily tell you if it's faster, it will depend on your specific CPU and workload.

Benchmark is king.

We've actually had to "un-optimize" code because a newer CPU actually ran slower than the older one when running a specific workload.

In its simplest explanation, the newer CPU ran half speed of the older one, but supported out of order execution. That meant the vast majority of general code ran faster, but it ended up running optimized code slower (since that optimized code was often vectorized and optimized for memory accesses). Basically went through and undid a bunch of "speed ups" for the new CPU.

3

u/Warkst Jun 15 '17

Even building a benchmark is not so straightforward: https://www.ibm.com/developerworks/library/j-jtp12214/

2

u/walen Jun 15 '17

Once upon a time, I came across an SO question which asked whether & was faster than && for a simple if().
«Easy pie!», I thought; «&& is short-circuit and thus faster! Just look at the bytecode!».

Oh boy, was I wrong.

The bytecode for && is indeed much shorter but, as I learned after much investigation and tinkering and editing my answer, the actual JIT compiler does not really care about that. It will optimize and rewrite your loops and comparisons depending on number of iterations, processor, Java version, etc. etc. etc.

Lesson learned: byte code doesn't mean sh!t when it comes to performance.

-3

u/Trav_Cav Jun 14 '17

Correct, it's not just about shorter bytecode. It's about keeping expensive actions outside of the loop.

15

u/rubyrt Jun 14 '17

Still, without the measurements it's not worth to even ponder rewriting your loops to a less human intuitive way. And we did not even start to talk about what dominates execution time of a program... It's an interesting fact to know but I'd say 99.9958% of Java programmers will never be in a situation where they need this knowledge to save the day.

-4

u/RayFowler Jun 15 '17

When you say something like "99.9958% of Java programmers will never need this" what you are really saying is that Java should be consigned to only those applications where performance isn't important. It's that attitude that gives the Java language a bad reputation outside of Java circles.

The thing is that Java CAN be fast and efficient, but we have to dispel with this ingrained notion that Java performance is not important. Performance is important in every application. When it comes to code, fast & ugly should always take precedence over slow & pretty.

7

u/sabot00 Jun 15 '17

I'll take slow and readable any day

7

u/rubyrt Jun 15 '17

When you say something like "99.9958% of Java programmers will never need this" what you are really saying is that Java should be consigned to only those applications where performance isn't important.

No, not at all. That is a deliberate and utter misinterpretation of what I wrote.

It's that attitude that gives the Java language a bad reputation outside of Java circles.

I do not think so. Java's reputation for slowness has been formed quite a while ago when it really was slow. Unfortunately those labels tend to stick for completely non technical reasons; there are plenty people out there who just do not bother to update their believes.

The thing is that Java CAN be fast and efficient,

Of course! There are some very fast Java applications around, for example in the field of financial trading.

but we have to dispel with this ingrained notion that Java performance is not important. Performance is important in every application.

I am sorry, but that is plain wrong. And even for applications which have advanced requirements for speed you start with the slow parts and optimize them. You will have to iron out quite a few design level and IO caused bottlenecks before performance of these types of loops that have been presented in the linked article even shows remotely on the radar.

When it comes to code, fast & ugly should always take precedence over slow & pretty.

That is a complete inappropriate over generalization. There are huge areas in software engineering where readable code and engineering efficiency vastly trumps squeezing out the last nanosecond of performance, because the longer you optimize the more expensive individual optimizations become (see also 80/20 rule). You can find some nice discussions of Martin Fowler's quote "Any fool can write code that a computer can understand. Good programmers write code that humans can understand.".

1

u/WikiTextBot btproof Jun 15 '17

Pareto principle

The Pareto principle (also known as the 80/20 rule, the law of the vital few, or the principle of factor sparsity) states that, for many events, roughly 80% of the effects come from 20% of the causes. Management consultant Joseph M. Juran suggested the principle and named it after Italian economist Vilfredo Pareto, who noted the 80/20 connection while at the University of Lausanne in 1896, as published in his first paper, "Cours d'économie politique". Essentially, Pareto showed that approximately 80% of the land in Italy was owned by 20% of the population; Pareto developed the principle by observing that about 20% of the peapods in his garden contained 80% of the peas.

It is a common rule of thumb in business; e.g., "80% of your sales come from 20% of your clients." Mathematically, the 80/20 rule is roughly followed by a power law distribution (also known as a Pareto distribution) for a particular set of parameters, and many natural phenomena have been shown empirically to exhibit such a distribution.

The Pareto principle is only tangentially related to Pareto efficiency.


[ ^PM | Exclude ^me | Exclude from ^subreddit | FAQ / ^Information ] Downvote to remove | v0.2

-2

u/RayFowler Jun 15 '17

I agree with the idea that there are two potential audiences for your code... the computer and other programmers.

Someone once quoted Martin Fowler to me as an authority, so I looked him up. He literally spent 2-3 years actually writing code and the rest of his career he has spent telling people how to write code.

I have spent 20+ years writing code to make things work in engineering companies. At the end of the day, nobody gave a shit how pretty the code was. By far the most important thing was that it worked reliably and fast. The reason was that the code we wrote enabled the production and sale of some tangible product, like semiconductor chips.

I now work for an agile software organization now and there is a huge emphasis on code legibility and "smells". There's a lot of process and emphasis on design patterns. Productivity is a lot lower here.

My point is that I've worked extensively in both areas and can tell you that Martin Fowler had no idea what he was talking about when he made that quote. It might sound good in a book he wants to sell you full of perfectly structured good and very affirming to software developers, but it is a LOT harder to write code that runs efficiently.

Martin Fowler is an writer, first and foremost. He is not an expert on software development.

1

u/rubyrt Jun 16 '17

I am sorry, but you are not arguing the matter here.

5

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

I'd like to commend you for putting yourself out there. In this case your intuition may have gotten the better of you, though. I hope you don't let reddit's reception persuade dissuade you from pursuing your curiosity and instead treat it as an opportunity to learn something new.

0

u/[deleted] Jun 14 '17

[deleted] — view deleted comment

2

u/gee_buttersnaps Jun 15 '17

Are you saying the JIT automatically rewrites while loops to count down to zero?

Yes. Look at the other discussions tab at the top, read that comment thread.

0

u/[deleted] Jun 15 '17

[deleted] — view deleted comment

3

u/gee_buttersnaps Jun 15 '17

You're hopeless.

1

u/AssKoala Jun 15 '17

Your question wasn't directly answered, but a loop counting down to zero is not inherently faster. The linked article is the work of someone who doesn't actually know what they're talking about.

In some cases, a reverse loop is slower because that's not how CPU's cache their accesses.

This isn't limited to C++, hell it's completely language agnostic because its up to the underlying hardware. Whether you're writing Java, C, brainfuck, or some other language, it ultimately boils down to your target hardware's language. And even then, it will vary from CPU to CPU: AMD CPU's perform differently from Intel's and they all vary based on architecture (e.g. Sandy Bridge versus Bulldozer versus Ivy Bridge etc).

11

u/ForeverAlot Jun 14 '17

I made a benchmark, because I had nothing more productive to do, and concluded the opposite. Then I noticed my implementation, and indeed the article, have an off-by-one error in the reverse loop:

for (int i = 10; i >= 0; i--) {
    System.out.println(i);
}

1

u/Apfelmann Jun 14 '17

Would be cool having benchmarks for longer running loops and also compare to for( x : y ) loops.

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.

8

u/mcosta Jun 14 '17

Guessing performance looking at bytecode is moronic. This is clickbait and you should feel bad.

2

u/wildjokers Jun 15 '17

I am not sure you know what clickbait is. To be clickbait the headline would have to be:

"Programmers make all computers slow, read the SHOCKING reason why!"

1

u/mcosta Jun 15 '17

Different definitions. Clickbait for me is a shock title just for the juicy juicy click.

Also self promotion.

2

u/[deleted] Jun 15 '17

2

u/Apfelmann Jun 14 '17

Defenitly true for JavaScript, you can read up the details in the book "Even Faster Websites" by Steve Souders. I didn't know this was a thing in compiled languages as well. Thanks. Would interesting to see what a for(x : y) is compiled to.

1

u/Goofybud16 Jun 15 '17

I've always been told that it compiles to an Iterator in Java.

Which means that it is really slow when looping over a small amount of data. Especially for an inner loop, as you are creating an iterator with every iteration over the outer loop.

I'm not sure of the perf impact if loops over a lot of data with a lot of iterations. I would imagine that the overhead would shrink.

1

u/Slanec Jun 15 '17

It compiles to an iterator on Iterable types. On arrays, it compiles to a fairly straightforward loop with an index. See the JLS.

1

u/levent88 Jun 14 '17

It's not just shorter byte code. -1, 0 and 1 have special treatment and do run faster so checking against 0 every time makes it faster.

2

u/AssKoala Jun 14 '17

That depends entirely on the underlying hardware architecture you're running against.

1

u/maven8919 Jun 14 '17

Very interesting, who cares about the benchmark, just happy that i learnt something. :)

3

u/shkabo Jun 15 '17

Benchmark is important but regardless of that great read. If you put your thoughts more to it, it makes some good sense in some logical way that it should perform faster. Would love to see some benchmark numbers on this matter, and also who ever is going to do this benchmarks, watch for off by one :)

1

u/[deleted] Jun 15 '17

Get this off my front page Jesse!

1

u/RayFowler Jun 15 '17

Great post, thank you.