I've heard this quite a few times. Are JavaScript loops really faster when counting backward? If so, why? I've seen a few test suite examples showing that reversed loops are quicker, but I can't find any explanation as to why!
I'm assuming it's because the loop no longer has to evaluate a property each time it checks to see if it's finished and it just checks against the final numeric value.
I.e.
for (var i = count - 1; i >= 0; i--)
{
// count is only evaluated once and then the comparison is always on 0.
}
This question is related to
javascript
performance
loops
for-loop
while-loop
The answer is
Love it, lots of marks up but no answer :D
Simply put a comparison against zero is always the fastest comparison
So (a==0) is actually quicker at returning True than (a==5)
It's small and insignificant and with 100 million rows in a collection it's measurable.
i.e on a loop up you might be saying where i <= array.length and be incrementing i
on a down loop you might be saying where i >= 0 and be decrementing i instead.
The comparison is quicker. Not the 'direction' of the loop.
I don't think that it makes sense to say that i-- is faster that i++ in JavaScript.
First of all, it totally depends on JavaScript engine implementation.
Secondly, provided that simplest constructs JIT'ed and translated to native instructions, then i++ vs i-- will totally depend on the CPU that executes it. That is, on ARMs (mobile phones) it's faster to go down to 0 since decrement and compare to zero are executed in a single instruction.
Probably, you thought that one was waster than the other because suggested way is
for(var i = array.length; i--; )
but suggested way is not because one faster then the other, but simply because if you write
for(var i = 0; i < array.length; i++)
then on every iteration array.length had to be evaluated (smarter JavaScript engine perhaps could figure out that loop won't change length of the array). Even though it looks like a simple statement, it's actually some function that gets called under the hood by the JavaScript engine.
The other reason, why i-- could be considered "faster" is because JavaScript engine needs to allocate only one internal variable to control the loop (variable to the var i). If you compared to array.length or to some other variable then there had to be more than one internal variable to control the loop, and the number of internal variables are limited asset of a JavaScript engine. The less variables are used in a loop the more chance JIT has for optimization. That's why i-- could be considered faster...
Not a lot of time is consumed by i-- or i++. If you go deep inside the CPU architecture the ++ is more speedy than the --, since the -- operation will do the 2's complement, but it happend inside the hardware so this will make it speedy and no major difference between the ++ and -- also these operations are considered of the least time consumed in the CPU.
The for loop runs like this:
- Initialize the variable once at the start.
- Check the constraint in the second operand of the loop,
<,>,<=, etc. - Then apply the loop.
- Increment the loop and loop again throw these processes again.
So,
for (var i = Things.length - 1; i >= 0; i--) {
Things[i]
};
will calculate the array length only once at the start and this is not a lot of time, but
for(var i = array.length; i--; )
will calculate the length at each loop, so it will consume a lot of time.
It depends on placement of your array in memory and the hit ratio of memory pages while you are accessing that array.
In some cases accessing array members in column order is faster than row order because of the increase in hit ratio.
This is just a guess, but maybe it's because it's easier for the processor to compare something with 0 ( i >= 0 ) instead of with another value ( i < Things.length).
I've seen the same recommendation in Sublime Text 2.
Like it was already said, the main improvement is not evaluating the array's length at each iteration in the for loop. This a well-known optimization technique and particularly efficient in JavaScript when the array is part of the HTML document (doing a for for the all the li elements).
For example,
for (var i = 0; i < document.getElementsByTagName('li').length; i++)
is much slower than
for (var i = 0, len = document.getElementsByTagName('li').length; i < len; i++)
From where I'm standing, the main improvement in the form in your question is the fact that it doesn't declare an extra variable (len in my example)
But if you ask me, the whole point is not about the i++ vs i-- optimization, but about not having to evaluate the length of the array at each iteration (you can see a benchmark test on jsperf).
To cut it short: There is absolutely no difference in doing this in JavaScript.
First of all, you can test it yourself:
Not only can you test and run any script in any JavaScript library, but you also have access to the whole bunch of previously written scripts, as well as the abilty to see differences between execution time in different browsers on different platforms.
So as far as you can see, there is no difference between performance in any environment.
If you want to improve performance of your script, things you can try to do:
- Have a
var a = array.length;statement so that you will not be calculating its value each time in the loop - Do loop unrolling http://en.wikipedia.org/wiki/Loop_unwinding
But you have to understand that the improvement you can gain will be so insignificant, that mostly you should not even care about it.
My own opinion why such a misconception (Dec vs Inc) appeared
A long, long time ago there was a common machine instruction, DSZ (Decrement and Skip on Zero). People who programmed in assembly language used this instruction to implement loops in order to save a register. Now this ancient facts are obsolete, and I am pretty sure you will not get any performance improvement in any language using this pseudo improvement.
I think the only way such knowledge can propagate in our time is when you read another's person code. See such a construction and ask why was it implemented and here the answer: "it improves performance because it compares to zero". You became bewildered of higher knowledge of your colleague and think to use it to be much smarter :-)
Since, you are interested in the subject, take a look at Greg Reimer's weblog post about a JavaScript loop benchmark, What's the Fastest Way to Code a Loop in JavaScript?:
I built a loop benchmarking test suite for different ways of coding loops in JavaScript. There are a few of these out there already, but I didn't find any that acknowledged the difference between native arrays and HTML collections.
You can also do a performance test on a loop by opening https://blogs.oracle.com/greimer/resource/loop-test.html (does not work if JavaScript is blocked in the browser by, for example, NoScript).
EDIT:
A more recent benchmark created by Milan Adamovsky can be performed in run-time here for different browsers.
For a Testing in Firefox 17.0 on Mac OS X 10.6 I got the following loop:
I try to give a broad picture with this answer.
The following thoughts in brackets was my belief until I have just recently tested the issue:
[[In terms of low level languages like C/C++, the code is compiled so that the processor has a special conditional jump command when a variable is zero (or non-zero).
Also, if you care about this much optimization, you could go ++i instead of i++, because ++i is a single processor command whereas i++ means j=i+1, i=j.]]
Really fast loops can be done by unrolling them:
for(i=800000;i>0;--i)
do_it(i);
It can be way slower than
for(i=800000;i>0;i-=8)
{
do_it(i); do_it(i-1); do_it(i-2); ... do_it(i-7);
}
but the reasons for this can be quite complicated (just to mention, there are the issues of processor command preprocessing and cache handling in the game).
In terms of high level languages, like JavaScript as you asked, you can optimize things if you rely on libraries, built-in functions for looping. Let them decide how it is best done.
Consequently, in JavaScript, I would suggest using something like
array.forEach(function(i) {
do_it(i);
});
It is also less error-prone and browsers have a chance to optimize your code.
[REMARK: not only the browsers, but you too have a space to optimize easily, just redefine the forEach function (browser dependently) so that it uses the latest best trickery! :) @A.M.K. says in special cases it is worth rather using array.pop or array.shift. If you do that, put it behind the curtain. The utmost overkill is to add options to forEach to select the looping algorithm.]
Moreover, also for low level languages, the best practice is to use some smart library function for complex, looped operations if it is possible.
Those libraries can also put things (multi-threaded) behind your back and also specialized programmers keep them up-to-date.
I did a bit more scrutiny and it turns out that in C/C++,
even for 5e9 = (50,000x100,000) operations, there is no difference between going up and down if the testing is done against a constant like @alestanis says. (JsPerf results are sometimes inconsistent but by and large say the same: you can't make a big difference.)
So --i happens to be rather a "posh" thing. It only makes you look like a better programmer. :)
On the other hand, for-unrolling in this 5e9 situation, it has brought me down from 12 sec to 2.5 sec when I went by 10s, and to 2.1 sec when I went by 20s. It was without optimization, and optimization has brought things down to unmeasureable little time. :) (Unrolling can be done in my way above or using i++, but that does not bring things ahead in JavaScript. )
All in all: keep i--/i++ and ++i/i++ differences to the job interviews, stick to array.forEach or other complex library functions when available. ;)
I want to contribute to this thread the fastest loop in JavaScript that is cross-browser ! This loop yields over 500% improvement compared to the reverse while loop.
It's not the -- or ++, it is the compare operation. With -- you can use a compare with 0, while with ++ you need to compare it with the length. On the processor, compare with zero is normally available, while compare with a finite integer requires a subtraction.
a++ < length
is actually compiled as
a++
test (a-length)
So it takes longer on the processor when compiled.
Using the prefix increment operator is somewhat faster. With the postfix, the compiler must retain the previous value as the result of the expression.
for (var i = 0; i < n; ++i) {
do_stuff();
}
A smart interpreter or compiler will see that the result of i++ is not used and not store the result of the expression, but not all js engines do.
for(var i = array.length; i--; ) is not much faster. But when you replace array.length with super_puper_function(), that may be significantly faster (since it's called in every iteration). That's the difference.
If you are going to change it in 2014, you don't need to think about optimization. If you are going to change it with "Search & Replace", you don't need to think about optimization. If you have no time, you don't need to think about optimization. But now, you've got time to think about it.
P.S.: i-- is not faster than i++.
In very simple words
"i-- and i++. Actually, they're both takes the same time".
but in this case when you have incremental operation.. processor evaluate the .length every time variable is incremented by 1 and in case of decrement.. particularly in this case, it will evaluate .length only once till we get 0.
i-- is as fast as i++
This code below is as fast as yours, but uses an extra variable:
var up = Things.length;
for (var i = 0; i < up; i++) {
Things[i]
};
The recommendation is to NOT evaluate the size of the array each time. For big arrays one can see the performance degradation.
HELP OTHERS AVOID A HEADACHE --- VOTE THIS UP!!!
The most popular answer on this page does not work for Firefox 14 and does not pass the jsLinter. "while" loops need a comparison operator, not an assignment. It does work on chrome, safari, and even ie. But dies in firefox.
THIS IS BROKEN!
var i = arr.length; //or 10
while(i--)
{
//...
}
THIS WILL WORK! (works on firefox, passes the jsLinter)
var i = arr.length; //or 10
while(i>-1)
{
//...
i = i - 1;
}
Well, I don't know about JavaScript, it should really be just a matter of re-evaluation array length and maybe something to do with the associative arrays (if you only decrement, it is unlikely new entries would need to be allocated - if the array is dense, that is. someone may optimize for that).
In low-level assembly, there is a looping instruction, called DJNZ (decrement and jump if non-zero). So the decrement and jump is all in one instruction, making it possibly ever-so-slightly faster than INC and JL / JB (increment, jump if less than / jump if below). Also, comparing against zero is simpler than comparing against another number. But all that is really marginal and also depends on target architecture (could make difference e.g. on Arm in a smartphone).
I wouldn't expect this low-level differences to have so great impact on interpreted languages, I just haven't seen DJNZ among the responses so I thought I would share an interesting thought.
The way you're doing it now isn't faster (apart from it being an indefinite loop, I guess you meant to do i--.
If you want to make it faster do:
for (i = 10; i--;) {
//super fast loop
}
of course you wouldn't notice it on such a small loop. The reason it's faster is because you're decrementing i while checking that it's "true" (it evaluates to "false" when it reaches 0)
The last time I bothered about it was when writing 6502 assembly (8-bit, yeah!). The big gain is that most arithmetic operations (especially decrements) updated a set of flags, one of them was Z, the 'reached zero' indicator.
So, at the end of the loop you just did two instructions: DEC (decrement) and JNZ (jump if not zero), no comparison needed!
It used to be said that --i was faster (in C++) because there is only one result, the decremented value. i-- needs to store the decremented value back to i and also retain the original value as the result (j = i--;). In most compilers this used up two registers rather than one which could cause another variable to have to be written to memory rather than retained as a register variable.
I agree with those others that have said it makes no difference these days.
This is not dependent on the -- or ++ sign, but it depends on conditions you apply in the loop.
For example: Your loop is faster if the variable has a static value than if your loop check conditions every time, like the length of an array or other conditions.
But don't worry about this optimization, because this time its effect is measured in nanoseconds.
++ vs. -- does not matter because JavaScript is an interpreted language, not a compiled language. Each instruction translates to more than one machine language and you should not care about the gory details.
People who are talking about using -- (or ++) to make efficient use of assembly instructions are wrong. These instruction apply to integer arithmetic and there are no integers in JavaScript, just numbers.
You should write readable code.
Short answer
For normal code, especially in a high level language like JavaScript, there is no performance difference in i++ and i--.
The performance criteria is the use in the for loop and the compare statement.
This applies to all high level languages and is mostly independent from the use of JavaScript. The explanation is the resulting assembler code at the bottom line.
Detailed explanation
A performance difference may occur in a loop. The background is that on the assembler code level you can see that a compare with 0 is just one statement which doesn't need an additional register.
This compare is issued on every pass of the loop and may result in a measurable performance improvement.
for(var i = array.length; i--; )
will be evaluated to a pseudo code like this:
i=array.length
:LOOP_START
decrement i
if [ i = 0 ] goto :LOOP_END
... BODY_CODE
:LOOP_END
Note that 0 is a literal, or in other words, a constant value.
for(var i = 0 ; i < array.length; i++ )
will be evaluated to a pseudo code like this (normal interpreter optimisation supposed):
end=array.length
i=0
:LOOP_START
if [ i < end ] goto :LOOP_END
increment i
... BODY_CODE
:LOOP_END
Note that end is a variable which needs a CPU register. This may invoke an additional register swapping in the code and needs a more expensive compare statement in the if statement.
Just my 5 cents
For a high level language, readability, which facilitates maintainability, is more important as a minor performance improvement.
Normally the classic iteration from array start to end is better.
The quicker iteration from array end to start results in the possibly unwanted reversed sequence.
Post scriptum
As asked in a comment: The difference of --i and i-- is in the evaluation of i before or after the decrementing.
The best explanation is to try it out ;-) Here is a Bash example.
% i=10; echo "$((--i)) --> $i"
9 --> 9
% i=10; echo "$((i--)) --> $i"
10 --> 9
Sometimes making some very minor changes to the way that we write our code can make a big difference to how quickly our code actually runs. One area where a minor code change can make a big difference to execution times is where we have a for loop that is processing an array. Where the array is of elements on the web page (such as radio buttons) the change has the biggest effect but it is still worth applying this change even where the array is internal to the Javascript code.
The conventional way of coding a for loop to process an array lis like this:
for (var i = 0; i < myArray.length; i++) {...
The problem with this is that evaluating the length of the array using myArray.length takes time and the way that we have coded the loop means that this evaluation has to be performed every time around the loop. If the array contains 1000 elements then the length of the array will be evaluated 1001 times. If we were looking at radio buttons and had myForm.myButtons.length then it will take even longer to evaluate since the appropriate group of buttons within the specified form must first be located before the length can be evaluated each time around the loop.
Obviously we don't expect the length of the array to change while we are processing it so all of these recalculations of the length are just adding unnecessarily to the processing time. (Of course if you have code inside the loop that adds or removes array entries then the array size can change between iterations and so we can't change the code that tests for it)
What we can do to correct this for a loop where the size is fixed is to evaluate the length once at the start of the loop and save it in a variable. We can then test the variable to decide when to terminate the loop. This is much faster than evaluating the array length each time particularly when the array contains more than just a few entries or is part of the web page.
The code to do this is:
for (var i = 0, var j = myArray.length; i < j; i++) {...
So now we only evaluate the size of the array once and test our loop counter against the variable that holds that value each time around the loop. This extra variable can be accessed much faster than evaluating the size of the array and so our code will run much faster than before. We just have one extra variable in our script.
Often it doesn't matter what order we process the array in as long as all of the entries in the array get processed. Where this is the case we can make our code slightly faster by doing away with the extra variable that we just added and processing the array in reverse order.
The final code that processes our array in the most efficient way possible is:
for (var i = myArray.length-1; i > -1; i--) {...
This code still only evaluates the size of the array once at the start but instead of comparing the loop counter with a variable we compare it with a constant. Since a constant is even more effective to access than a variable and since we have one fewer assignment statement than before our third version of the code is now slightly more efficient than the second version and vastly more efficient than the first.
First, i++ and i-- take exactly the same time on any programming language, including JavaScript.
The following code take much different time.
Fast:
for (var i = 0, len = Things.length - 1; i <= len; i++) { Things[i] };
Slow:
for (var i = 0; i <= Things.length - 1; i++) { Things[i] };
Therefore the following code take different time too.
Fast:
for (var i = Things.length - 1; i >= 0; i--) { Things[i] };
Slow:
for (var i = 0; i <= Things.length - 1; i++) { Things[i] };
P.S. Slow is slow only for a few languages (JavaScript engines) because of compiler's optimization. The best way is to use '<' instead '<=' (or '=') and '--i' instead 'i--'.
Since none of the other answers seem to answer your specific question (more than half of them show C examples and discuss lower-level languages, your question is for JavaScript) I decided to write my own.
So, here you go:
Simple answer: i-- is generally faster because it doesn't have to run a comparison to 0 each time it runs, test results on various methods are below:
Test results: As "proven" by this jsPerf, arr.pop() is actually the fastest loop by far. But, focusing on --i, i--, i++ and ++i as you asked in your question, here are jsPerf (they are from multiple jsPerf's, please see sources below) results summarized:
--i and i-- are the same in Firefox while i-- is faster in Chrome.
In Chrome a basic for loop (for (var i = 0; i < arr.length; i++)) is faster than i-- and --i while in Firefox it's slower.
In Both Chrome and Firefox a cached arr.length is significantly faster with Chrome ahead by about 170,000 ops/sec.
Without a significant difference, ++i is faster than i++ in most browsers, AFAIK, it's never the other way around in any browser.
Shorter summary: arr.pop() is the fastest loop by far; for the specifically mentioned loops, i-- is the fastest loop.
Sources: http://jsperf.com/fastest-array-loops-in-javascript/15, http://jsperf.com/ipp-vs-ppi-2
I hope this answers your question.
In many cases, this has essentially nothing to do with the fact that processors can compare to zero faster than other comparisons.
This is because only a few Javascript engines (the ones in the JIT list) actually generate machine language code.
Most Javascript engines build an internal representation of the source code which they then interpret (to get an idea of what this is like, have a look near the bottom of this page on Firefox's SpiderMonkey). Generally if a piece of code does practically the same thing but leads to a simpler internal representation, it will run faster.
Bear in mind that with simple tasks like adding/subtracting one from a variable, or comparing a variable to something, the overhead of the interpreter moving from one internal "instruction" to the next is quite high, so the less "instructions" that are used internally by the JS engine, the better.
This guy compared a lot of loops in javascript, in a lot of browsers. He also has a test suite so you can run them yourself.
In all cases (unless I missed one in my read) the fastest loop was:
var i = arr.length; //or 10
while(i--)
{
//...
}
The fastest way for decrement mode:
var iteration = 10000000;
while(iteration > 0){
iteration--;
}
FASTER THAN:
var iteration = 10000000;
while(iteration--);
I made a comparison on jsbench.
As alestani pointed out, one thing that takes time in ascending loops, is to evaluate, for each iteration, the size of your array. In this loop:
for ( var i = 1; i <= array.length; i++ )
you evaluate .length each time you increment i. In this one:
for ( var i = 1, l = array.length; i <= l; i++ )
you evaluate .length only once, when you declare i. In this one:
for ( var i = array.length; i--; )
the comparison is implicit, it happens just before decrementing i, and the code is very readable. However, what can make a terrific difference, is what you put inside the loop.
Loop with call to function (defined elsewhere):
for (i = values.length; i-- ;) {
add( values[i] );
}
Loop with inlined code:
var sum = 0;
for ( i = values.length; i-- ;) {
sum += values[i];
}
If you can inline your code, instead of calling a function, without sacrificing legibility, you can have a loop an order of magnitude faster!
Note: as browser are becoming good at inlining simple functions, it really depends on how complex your code is. So, profile before optimizing, because
- The bottleneck may be elsewhere (ajax, reflow, ...)
- You may choose a better algorithm
- You may choose a better data structure
But remember:
Code is written for people to read, and only incidentally for machines to execute.
Wouldn't the compiler cache .length, and therefore it makes no difference if you are comparing 0 or .length? I guess this is very specific to the compiler or interpreter you are dealing with.
I would say if you are using a well optimised compiler or interpreter then you shouldn't worry about this, it is for the language developers to worry about.
The best approach to answering this sort of question is to actually try it. Set up a loop that counts a million iterations or whatever, and do it both ways. Time both loops, and compare the results.
The answer will probably depend on which browser you are using. Some will have different results than others.
It can be explained by JavaScript (and all languages) eventually being turned into opcodes to run on the CPU. CPUs always have a single instruction for comparing against zero, which is damn fast.
As an aside, if you can guarantee count is always >= 0, you could simplify to:
for (var i = count; i--;)
{
// whatever
}Source: Stackoverflow.com