Which of these pieces of code is faster in Java?
https://stackoverflow.com/questions/1656506
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
a) for(int i = 100000; i > 0; i--) {}
b) for(int i = 1; i < 100001; i++) {}
The answer is there on this website (question 3). I just can't figure out why? From website:
3. a
Solution
When you get down to the lowest level (machine code but I'll use assembly since it maps one-to-one mostly), the difference between an empty loop decrementing to 0 and one incrementing to 50 (for example) is often along the lines of:
ld a,50 ld a,0
loop: dec a loop: inc a
jnz loop cmp a,50
jnz loop
That's because the zero flag in most sane CPUs is set by the decrement instruction when you reach zero. The same can't usually be said for the increment instruction when it reaches 50 (since there's nothing special about that value, unlike zero). So you need to compare the register with 50 to set the zero flag.
However, asking which of the two loops:
for(int i = 100000; i > 0; i--) {}
for(int i = 1; i < 100001; i++) {}
is faster (in pretty much any environment, Java or otherwise) is useless since neither of them does anything useful. The fastest version of both those loops no loop at all. I challenge anyone to come up with a faster version than that :-)
They'll only become useful when you start doing some useful work inside the braces and, at that point, the work will dictate which order you should use.
For example if you need to count from 1 to 100,000, you should use the second loop. That's because the advantage of counting down (if any) is likely to be swamped by the fact that you have to evaluate 100000-i inside the loop every time you need to use it. In assembly terms, that would be the difference between:
ld b,100000 dsw a
sub b,a
dsw b
(dsw is, of course, the infamous do something with assembler mnemonic).
Since you'll only be taking the hit for an incrementing loop once per iteration, and you'll be taking the hit for the subtraction at least once per iteration (assuming you'll be using i, otherwise there's little need for the loop at all), you should just go with the more natural version.
If you need to count up, count up. If you need to count down, count down.
OTHER TIPS
On many compilers, the machine instructions emitted for a loop going backwards, are more efficient, because testing for zero (and therefore zero'ing a register) is faster than a load immediate of a constant value.
On the other hand, a good optimising compiler should be able to inspect the loop inner and determine that going backwards won't cause any side effects...
BTW, that is a terrible interview question in my opinion. Unless you are talking about a loop which runs 10 millions of times AND you have ascertained that the slight gain is not outweighed by many instances of recreating the forward loop value (n - i), any performance gain will be minimal.
As always, don't micro-optimise without performance benchmarking and at the expense of harder to understand code.
These kinds of questions are largely an irrelevant distraction that some people get obsessed with it. Call it the Cult of Micro-optimization or whatever you like but is it faster to loop up or down? Seriously? You use whichever is appropriate for what you're doing. You don't write your code around saving two clock cycles or whatever it is.
Let the compiler do what it's for and make you intent clear (both to the compiler and the reader). Another common Java pessimization is:
public final static String BLAH = new StringBuilder().append("This is ").append(3).append(' text").toString();
because excessive concatenation does result in memory fragmentation but for a constant the compiler can (and will) optimize this:
public final static String BLAH = "This is a " + 3 + " test";
where it won't optimize the first and the second is easier to read.
And how about (a>b)?a:b vs Math.max(a,b)? I know I'd rather read the second so I don't really care that the first doesn't incur a function call overhead.
There are a couple of useful things in this list like knowing that a finally block isn't called on System.exit() is potentially useful. Knowing that dividing a float by 0.0 doesn't throw an exception is useful.
But don't bother second-guessing the compiler unless it really matters (and I bet you that 99.99% of the time it doesn't).
A better question is;
Which is easier to understand/work with?
This is far more important than a notional difference in performance. Personally, I would point out that performance shouldn't be the criteria for determining the difference here. If they didn't like me challenging their assumption on this, I wouldn't be unhappy about not getting the job. ;)
On a modern Java implementation this is not true. Summing up the numbers up to one billion as a benchmark:
Java(TM) SE Runtime Environment 1.6.0_05-b13 Java HotSpot(TM) Server VM 10.0-b19 up 1000000000: 1817ms 1.817ns/iteration (sum 499999999500000000) up 1000000000: 1786ms 1.786ns/iteration (sum 499999999500000000) up 1000000000: 1778ms 1.778ns/iteration (sum 499999999500000000) up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000) up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000) up 1000000000: 1766ms 1.766ns/iteration (sum 499999999500000000) up 1000000000: 1776ms 1.776ns/iteration (sum 499999999500000000) up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000) up 1000000000: 1771ms 1.771ns/iteration (sum 499999999500000000) up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000) down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000) down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1832ms 1.832ns/iteration (sum 499999999500000000) down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000) down 1000000000: 1839ms 1.839ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
Note that the time differences are brittle, small changes somewhere near the loops can turn them around.
Edit: The benchmark loops are
long sum = 0;
for (int i = 0; i < limit; i++)
{
sum += i;
}
and
long sum = 0;
for (int i = limit - 1; i >= 0; i--)
{
sum += i;
}
Using a sum of type int is about three times faster, but then sum overflows. With BigInteger it is more than 50 times slower:
BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)
Typically real code will run faster counting upwards. There are a few reasons for this:
- Processors are optimised for reading memory forwards.
- HotSpot (and presumably other bytecode->native compilers) heavily optimise forward loops, but don't bother with backward loops because they happen so infrequently.
- Upwards is usually more obvious, and cleaner code is often faster.
So happily doing the right thing will usually be faster. Unnecessary micro-optimisation is evil. I haven't purposefully written backward loops since programming 6502 assembler.
There are really only two ways to answer this question.
To tell you that it really, really doesn't matter, and you're wasting your time even wondering.
To tell you that the only way to know is to run a trustworthy benchmark on your actual production hardware, OS and JRE installation that you care about.
So, I made you a runnable benchmark you could use to try that out here:
http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java
This Caliper framework is not really ready for prime time yet, so it may not be totally obvious what to do with this, but if you really care enough you can figure it out. Here are the results it gave on my linux box:
max benchmark ns
2 Forwards 4
2 Backwards 3
20 Forwards 9
20 Backwards 20
2000 Forwards 1007
2000 Backwards 1011
20000000 Forwards 9757363
20000000 Backwards 10303707
Does looping backwards look like a win to anyone?
Are you sure that the interviewer who asks such a question expects a straight answer ("number one is faster" or "number two is faster"), or if this question is asked to provoke a discussion, as is happening in the answers people are giving here?
In general, it's impossible to say which one is faster, because it heavily depends on the Java compiler, JRE, CPU and other factors. Using one or the other in your program just because you think that one of the two is faster without understanding the details to the lowest level is superstitious programming. And even if one version is faster than the other on your particular environment, then the difference is most likely so small that it's irrelevant.
Write clear code instead of trying to be clever.
Such questions have their base on old best-practice recommendations. It's all about comparison: comparing to 0 is known to be faster. Years ago this might have been seen as quite important. Nowadays, especially with Java, I'd rather let the compiler and the VM do their job and I'd focus on writing code that is easies to maintain and understand.
Unless there are reasons for doing it otherwise. Remember that Java apps don't always run on HotSpot and/or fast hardware.
With regards for testing for zero in the JVM: it can apparently be done with ifeq whereas testing for anything else requires if_icmpeq which also involves putting an extra value on the stack.
Testing for > 0, as in the question, might be done with ifgt, whereas testing for < 100001 would need if_icmplt.
This is about the dumbest question I have ever seen. The loop body is empty. If the compiler is any good it will just emit no code at all. It doesn't do anything, can't throw an exception and doesn't modify anything outside of its scope.
Assuming your compiler isn't that smart, or that you actually didn't have an empty loop body: The "backwards loop counter" argument makes sense for some assembly languages (it may make sense to the java byte code too, I don't know it specifically). However, the compiler will very often have the ability to transform your loop to use decrementing counters. Unless you have loop body in which the value of i is explicitly used, the compiler can do this transformation. So again you often see no difference.
I decided to bite and necro back the thread.
both of the loops are ignored by the JVM as no-ops. so essentially even one of the loops were till 10 and the other till 10000000, there would have been no difference.
Looping back to zero is another thing (for jne instruction but again, it's not compiled like that), the linked site is plain weird (and wrong).
This type of a question doesn't fit any JVM (nor any other compiler that can optimize).
The loops are identical, except for one critical part:
i > 0; and i < 100001;
The greater than zero check is done by checking the NZP (Commonly known as condition code or Negative Zero or Positive bit) bit of the computer.
The NZP bit is set whenever operation such as load, AND, addition ect. are performed.
The greater than check cannot directly utilize this bit (and therefore takes a bit longer...) The general solution is to make one of the values negative (by doing a bitwise NOT and then adding 1) and then adding it to the compared value. If the result is zero, then they're equal. Positive, then the second value (not the neg) is greater. Negative, then the first value (neg) is greater. This check takes a slightly longer than the direct nzp check.
I'm not 100% certain that this is the reason behind it though, but it seems like a possible reason...
The answer is a (as you probably found out on the website)
I think the reason is that the i > 0 condition for terminating the loop is faster to test.
The bottom line is that for any non-performance critical application, the difference is probably irrelevant. As others have pointed out there are times when using ++i instead of i++ could be faster, however, especially in for loops any modern compiler should optimize that distinction away.
That said, the difference probably has to do with the underlying instructions that get generated for the comparison. Testing if a value is equal to 0 is simply a NAND NOR gate. Whereas testing if a value is equal to an arbitrary constant requires loading that constant into a register, and then comparing the two registers. (This probably would require an extra gate delay or two.) That said, with pipelining and modern ALUs I'd be surprised if the distinction was significant to begin with.
I've been making tests for about 15 minutes now, with nothing running other than eclipse just in case, and I saw a real difference, you can try it out.
When I tried timing how long java takes to do "nothing" and it took around 500 nanoseconds just to have an idea.
Then I tested how long it takes to run a for statement where it increases:
for(i=0;i<100;i++){}
Then five minutes later I tried the "backwards" one:
for(i=100;i>0;i--)
And I've got a huge difference (in a tinny tiny level) of 16% between the first and the second for statements, the latter being 16% faster.
Average time for running the "increasing" for statement during 2000 tests: 1838 n/s
Average time for running the "decreasing" for statement during 2000 tests: 1555 n/s
Code used for such tests:
public static void main(String[] args) {
long time = 0;
for(int j=0; j<100; j++){
long startTime = System.nanoTime();
int i;
/*for(i=0;i<100;i++){
}*/
for(i=100;i>0;i--){
}
long endTime = System.nanoTime();
time += ((endTime-startTime));
}
time = time/100;
System.out.print("Time: "+time);
}
Conclusion:
The difference is basically nothing, it already takes a significant amount of "nothing" to do "nothing" in relation to the for statement tests, making the difference between them negligible, just the time taken for importing a library such as java.util.Scanner takes way more to load than running a for statement, it will not improve your application's performance significantly, but it's still really cool to know.
