Topic: Optimising JavaScript loops

Hi all,

I've been trying to find a thread that I saw a long while back on optimising loops and other code in JavaScript. I remember it contained discussion on whether looping forward (x++) or backwards (x--) was faster and / or more efficient.

I've looked through this forum, and used the search facility, but can't find it.

Can any inmates point me in the right direction?

Thanks,
Dan

can't find it either. I remember that thread, and am sure it involved the usual suspects : InI, Petskull, BitDamaged, and yours truly.

Most of the time it is faster to do loops in reverse. Another thing that might speed up a bit is to unwind the loops or use a "Duff device". Check on the net and Wikipedia for "loop unwinding" and "Duff optimization".

Here are a few links on the subject:

Wikipedia: Loop optimization/transformation ( some really interresting bits there )
Wikipedia: Loop unwinding
JavaScript Optimization
WebSiteOptimization: Chapter 10: Optimizing JavaScript for Execution Speed ( nice book if you're not a hardcore optimizer )


HTH

are you talking about Better for loops and Java/Javascript optimisation?

->Tyberius Prime

Yes. At least that's the one I had in mind.
InI posted a link to a site giving hints to optimize Java code.


Note to self: Next time, try searching with EN and US spelling.

Thanks guys... clearly my memory isn't what it used to be. Signs of a mis-spent youth playing too many computer games, probably

Dan

Might as well take a chance to jump in, so hello, world.

I think it all deserves a few updates - clearly, the tips are good (well, the ones which haven't been removed), but all things evolve.

Language independent trick (1) for optimisation, get your algorithms rights. Eg. look them up.
Some fields of algorithm research are broadly open, like 3d compression and the likes. Some have been explored in and out, and (almost) all recipes exposed.
Get the available ones, and the fastest ones. look up stuff you want to do and append " algorithm" at the end of your query.

For "lower level languages", like Cpp or Assembler, then, there are some truths to be used : comparisons to 0 always are faster (hence the --x > 0 kind of loop).
Most architectures like integer based operations, some are optimised for floats. MOD operator is slow. Divide is quite slow too. Mult, plus, minus, are fast, in floating point or integer.

Numbers that are powers of two are useful when coding, because they allow easy bit shifting. Instead of number / 2, you can do number >> 1 (bit shift that right).

Part of this, actually, most of what is arithmetic optimisation and what affects loops and comparisons, remains true for higher level languages, like Java or Javascript, semi-interpreted and interpreted

But for both Java and Javascript, other kinds of optimisations must be considered, which are HIGHLY dependent on the implementation. See poi's 3d Tomb II about that.

The underlying memory management, namely, matters a lot : the case of closures in javascript is a dangerous example. It is easy, in js, to create cyclic references
that mess up garbage collection. This impacts speed also because a lot of adressed memory is more difficult to manage to a given runtime environment (than only a few kbs or megs).

And then there is size optimisation, a whole different topic altogether, yet tightly related... less instructions seemingly lead to faster results,
but this is not a rule of thumb, it is a general condition with exceptions.

Sample exception : if you create lookup tables for sine and cosine operations,
sine and cosine operations will be faster, but creating lookup tables may result in a larger executable. Faster, but larger.

For Javascript only, you can :

1) safely apply the maths and conditions and loops tricks.
2) safely apply many size optimisations, like variables obfuscation.

And you should :

3) Watch out for the structure of the target documents, large dom, small dom? Inline CSS? (that is the devil) Can you alter classes at once, or should you focus on named elements?
It all depends on what you want to do.

Hey,

To add a quick personal note to this, I like to do this method of reversed loops in JS:

for (var i=something.length; i--;) {
// something[i] ..
}

There's some "duff" method of optimization I read about which sounds pretty good if I recall correctly, check Poi's links for reference.

For the most part, I suspect the core of JS efficiency comes from optimizing JS-DOM interaction and "expensive" computation functions, etc. However, always good to be thinking about all aspects of performance.

(Edited by Scott on 07-23-2007 20:27)

There are in general two kinds of optimisation in computer science: Either you don't do the work at all (or at least, you don't do *as much* work...) or you do the work ahead of time, and just recall the result when you need it instead of calculate it when you need it.

The key to optimising any language is figuring out when and how you can do less work, or do the work ahead of time. JavaScript can't optimise in a lot of ways that lower level languages do - there is no integer type, there are no hard arrays, there are no pointer manipulations etc. One example is that bitshifting is commonly faster than multiplication for factors of 2 in most languages. JavaScript has only floating point numbers, but it does have bitshifting. So, in order to perform a bitshift JavaScript has to convert a floating point number to an integer, then perform the bitshift, and then convert it back again. Doing all those conversions means that bitshifting is an example of an optimisation that rarely, if ever, leads to any speedup of script. (The JavaScript version of Duff's device is one example where bitshifting actually improves performance in JavaScript, in some browsers.)

A JavaScript version of Duff's device can speed up JavaScript, but really, it's seldom JavaScript that is the problem. Most often, JavaScript performance problems come from the DOM side, with a few exceptions such as string concatenations with huge amounts of strings. The general tip I'd give is: test doing things in different ways in different browsers. For example, the only way make string concatenation really fast in iew is rather slow compared to the other ways of concatenating strings in moz.



What always works, however:
- Cache everything you can when you first use it. Even if that use is for example in the condition of a for loop, and use the cached variable instead of doing the work of getting it again.
- Do less work, use better algorithms etc. Maybe even change the HTML code a bit, that can sometimes really speed up DOM scripting.

--
var Liorean = {
abode: "http://codingforums.com/",
profile: "http://codingforums.com/member.php?u=5798"};