Topic awaiting preservation: Better for loops and Java/Javascript optimisation

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

it looks to me like it might be the i<data.length which is the bottleneck ...

perhaps you could re-evaluate the original for loop but assign data.length to a variable before the loop, then use i<variablename to compare the performance difference. Calling the .length function through every iteration of the loop seems a big overhead to me ...

personally I'd sacrifice a small overhead (the separating of the initial, terminal and step conditions) as a trade-off for maintaining readability, but I wouldn't want to give up all those cycles calling a function if I could avoid it.


Bug-free software only exisits in two places
In programmer's mind and on a salesman's lips

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

I'm not sure how Javascript holds it's datastructures, but 3 things struck me about that loop.

One, moving a constant into a register is always faster than moving a variable there. So not needing to access that variable each iteration is a big speedup (not to mention, I notice that nested data structures in Javascript are VERY slow... JS is probably bad at copying pointers?).

A while back, I did some i686 tests on speeds of operators in ASM. As expected, integer subtraction is just a teeny bit slower the adding, but the floating point subtraction was faster (it was something like 120%). If Javascript stores all it's variables as floats, that may also accound for it.

Not to mention, it's faster to only access a variable once (via the --i) as opposed to twice (once for comparison and once for updating).

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

quote:

---

t's not called through every iteration:

---

I beg to differ. In any loop, the terminal condition is tested at each iteration, and if that terminal condition is a fuction, then the function is executed at each iteration too. Try it - set up a for loop on astring of 18 characters, get it to print out the current character at position i, and every second iteration add a new character to the end - it won't run 18 times.

... hence, in order for changes in terminal condition to be detected and acted upon, it must test the condition on each iteration, and so, if the condition includes a function, it must execute that function.


Bug-free software only exisits in two places
In programmer's mind and on a salesman's lips

I just talked about that on ICQ with InI, so I'll try to make it short:

I think the speculations about how Javascript should behave in regard of assembly tricks is pure and useless theory considering the amount of layers until the script language is finally interpreted in assembly opcodes by the processor. And those who know assembly and a bit of processor architecture ( I mainly think to the U and V pipelines on Pentium class processors and thus instructions pairing and AGI stalls, and how the caches works and the impact of a CACHE MISS ) knows that it needs an extremely small change in the assembly code to alter significantly the execution speed of a routine.

Add to that, that the browsers and OS are really differents from one computer to another. The JavaScript engine in IE is not the same as the one in Mozilla, Opera, Netscape, Safari ... and once you manipulate the DOM and some stylistic aspects of the pages that's another box of pandora that you open. The rendering engines also differs in many ways and have a huge impact on the performance of DHTML. ( That's the only reason for which 3D TOMB II is not playable in Mozilla. Mozilla's rendering engine crawls when it has many elements to manipulate )

That's why, when optimizing a script for speed, I stick to basic rules like.

• doing the very minimum : it includes JavaScript only aspects, but more precisely the DHTML aspects that is altering the DOM and rendering of the page.
• avoiding to do repeated accesses to members of members of members of ... an object by using a temporary variable pointing directly to the right member.

Basically I agree with those depicted in the link given by InI, at the slight exception of the example "Integer Arithmetic" which makes no sense in JavaScript.

NB: I think I failled in making it short.

[edit] Trib is true, the expression in the terminal condition is evaluated at every iteration. [/edit]



(Edited by poi on 06-09-2004 15:56)

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

That should probably be 'Trib is right...' - but yeah, what would happen if you changed the list within the for() loop - length could turn out something else - it needs to be evaluated each turn.

document.write("Trib is "+(trib.statement?"true":"false"));

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Tyberius Prime: You're _right_

InI: For the same reason that it's not possible to expect assembly tricks to be used once our scripts are interpreted by the processor, it's really hard to be sure how JavaScript engines really store the numerical values. All the more that JavaScript only have the Number object without explicit distinction between doubles and integers. And we don't know if the Numbers are stored by default in doubles or integers.

Nonetheless you're right, it seems that JS makes a difference between doubles and integers at times notably when using parseInt() or any binary operator. Otherwise it's really hard to know how the numerical variables are handled when you use them, and casting them all the time to make sure we use integer arithmetic is a waste of time.

That's why I think it's useless to try to use integer operations at all costs. In the very example of Integer Arithmetic on the page you gave, they do 3 extra operations. It makes sense in Java since that language have some explicitely typed ints and floats but not in Javascript.

Another thing that might irks you, is that it is quite likely ( though absolutely not proved ) that a JavaScript engine could work only with floats and temporary cast them when needed to perform a parseInt() or a binary operator and immediatly cast the result back to float. ( /me can't help thinking to "And the robot floats back to you" when writing this. )

Also, it's been a while since the FPUs perform the basic operations ( + - * / ) as fast ( if not faster in certain cases ) as the CPUs do with integers on both Motorala and Intel based computers.



(Edited by poi on 06-09-2004 17:14)

n=s.length;

260ms for(i=0;i<s.length;i++)
231ms for(i=0;i<n;i++)
220ms for(i=s.length;--i>-1
250ms i=0; while(j<s.length) j++;
230ms i=0; while(j<n) j++;

270ms i=0.1
250ms i=0.1
241ms s.length+.1
270ms i=0.1
250ms i=0.1


Not Enough Is Better Than Too Much

what about : i=s.length; while( --i ); on your computer ? Have your repeated the loops severals times and averaged the results ? I did that kind of benchmark on Mozilla, IE, and Netscape a while ago for http://www.javascript-games.org the great website holded by Scott Porter but he left his domain name go ashtray



(Edited by poi on 06-09-2004 17:44)

Averaging. no... visual. when I see the same set of values over and over I take it to be about right. I've not employed any really scientific methodology, guestimation mostly.


two new ones *

n=s.length;
260ms for(i=0;i<s.length;i++)
231ms for(i=0;i<n;i++)
220ms for(i=s.length;--i>-1
210ms for(i=n;--i>1;) *
250ms i=0; while(j<s.length) j++;
230ms i=0; while(j<n) j++;
210ms i=n; while(--i); *


Not Enough Is Better Than Too Much

for(i=data.length;--i>0;)

Shouldn't that be

for(i=data.length;--i>=0

?

Which, unfortunately, wouldn't work for an unsigned integer in C++.


 

Well, you also have to be careful, since

for(i=data.length;--i>0;) is not the same as for(i=data.length;i-->0;), so you can abuse it either way, heh. ;)

for(i=data.length;--i>-1;) == for(i=data.length;i-->=0;) == for(i=data.length;i-->0;) but I doubt any is really too much different in speed (the last one is probably the slowest due to the postfix).

Edit: disabled slimies, they screw stuff up

(Edited by Iron Wallaby on 06-09-2004 20:36)

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

InI: I sent you 2 files listing the number of clock cycles taken by the CPU and FPU instructions on a Pentium class processor. You'll see by yourself.

Obviously, like I said, there's so much layers between our JS scripts and their interpretation by the CPU that using either integer or floating point arithmetic makes little difference ( unless you stuff your script with type casting and useless calculations ), if any.

As I've never coded in Java I don't know if there's a real difference of execution speed between integer and floating point arithmetic. But I'd be surprised to see a real difference for similar calculations.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

InI: check you email @beyondwonderland.com

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

I didn't read all the way through this thread, but I am sure if you guys really want to find about data types for the javascript interpreter, you could dig around here if you haven't already. I am sure it has some pretty useful information.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Thank you for bringing it back.
The Key Points sound really obvious. They can be summed up by : go straight to the problem and minimize every, possibly, redundant bits of your algo. Anyhow, that's a good thing to give some examples of little things to think of to optimize a routine.



(Edited by poi on 07-20-2004 22:04)

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

quote:

---

InI said:

Key point 7 and 8 didn't sound so obvious

---

to you maybe, Sugar Bunny But once you thought about it a bit, it is pretty obvious.
Key 1 backs up your point for the use of integers in Java. If such a difference exists in JavaScript, I think it'd require a lot a iterations ( read more than what we have generally in our inner loops ) to see a noticeable difference.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

I did.

quote:

---

InI said:

So why didn't you do it before

---

I did. I always try to arrange my conditions in the optimal order. It's so obvious I didn't even thought it was necessary to talk about the optimization of condition expressions.

Oh, and if you wanna chat, I've installed ICQ at work

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

sorry if my tone sounded lame and egocentric.
You know, I'm the kind of man that need challenges to be boosted and move my ass, otherwise I work quietly and fall in boredom. And honestly my work provides almost no challenge these days.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Awww, how sweet. :3

I looked through the article you posted. Lots of it had already been brought up in the thread, and a little of it is obvious, but it is a well-put-together generalization on for loop optimizations.

Particularly interesting is that Java typecasts shorts and bytes to ints in comparisons. I hadn't known that. Of course, I'm not much of a fan of Java...

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

http://search.cpan.org/~ilyaz/OpenGL-0.54/OpenGL.pod
http://search.cpan.org/~jchin/OpenGL-Simple-0.01/Simple.pm
http://search.cpan.org/~dgoehrig/SDL_Perl-2.1.0/lib/SDL/OpenGL.pm

I am still trying to think of a practical reason to use OpenGL with an interpreted language... give me a minute... I'm sure something will come to me, heh...

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

If my memory serves me right, ECMAScript specifies the behavior for numbers to a pretty good level. Generally, numbers are handled as IEEE 754 floating point double precisions numbers, giving a 53 bit precision representation for most handling. The only mathematical operators that cast into 32 bit integers are the bitshifting ones. As for the built in functions they are a few: parseInt and those native methods that take indices, precisions or radices, all of them of the nature that couldn't possibly accept non-integers.

What is most important in ECMAScript performance optimisation is actually to have an idea about the memory handling. In ECMAScript you have a memory handling that means everything is an object. All variables and all properties are instances of a container object type, the structure of which is irrelevant just now, except that it has a value field and a type. The type is either primitive (undefined, null, string, boolean, number) or compound (object, array, function, regex, collections (from the DOM perhaps), other). If it's compound the value field contains a pointer to the value object. If it on the other hand is a primitive the value field may contain a string, a double precision floating point number or a boolean in the implementation language.

All ECMAScript implementations are differently optimised at different areas. JScript excells at looping. It just blows SpiderMonkey, KJS and {whatever the name is for the Opera JavaScript engine} away. SpiderMonkey and Opera on the other hand excells at identifier resolution and scope traversal - object handling. This means that you may optimise for one or the other, but seldom all.


Tricks for optimisation:
Some are the old usual, some are unique. Comparison to zero is faster than comparison to any other number, so reversing a loop speeds up those badly optimised at looping.

var

    i=obj.length;

while(i-->0)

    dosomething;

is thus better optimised than

var

    i=0,

    l=obj.length

while(l>i++)

    dosomething;

Caching a primitive instead of accessing it's container is in most cases prefereable.

var

    i=0,

    l=obj.length

while(l>i++)

    dosomething[;

is faster than

var

    i=0

while(obj.length>i++)

    dosomething;

If you feel crafty, the best way to performance optimise SpiderMonkey is to unroll loops. This is a bit of a cludge, but if performance is critical you might consider it.

var

    n=8,

    i=obj.length%n,

    j=obj.length/n-i;

while(i-->0)

    dosomething;

while(j-->0)

    dosomething,

    dosomething,

    dosomething,

    dosomething,

    dosomething,

    dosomething,

    dosomething,

    dosomething;

Of course, there are other problems when you take the browser into count. A couple of generic tips would be as follows:

Except for code already in the global scope (not inside a function body), ALWAYS use the window identifier when accessing an object in the global scope. Browsers are optimised for this and won't have to try identifier resolution in all scopes on the way.

For JScript and Opera, it's much faster to use just [b]window[b].elementnameorid than to use the document or docuemnt.* identifiers. The downside is that it's not standards compliant.

When using the DOM, avoid caching anything that is not a node reference. For example, never cache the dynamic objects that are of the type HTMLCollection, HTMLOptionsCollection, NodeList or NamedNodeMap.

var

    i=0,

    elm;

while(elm=document.getElementsByTagName(string).item(i++))

    dosomething;

is actually faster than

var

    i=0,

    c=document.getElementsByTagName(string),

    elm;

while(elm=c.item(i++))

    dosomething;

The reason for this is that each time a propertiy in the collection is accessed, the browser (re)creates a temporary array which it fills with all elements it can find in the document that fills the criteria put by the collection. If you instead access a single element in the collection, the browser is optimised so as to never create the array, it just finds and accesses the element without building an array.

When looping through a collection, cache the element in question.

var

    i=0,

    elm;

while(elm=coll.item(i++))

    dosomethingwithelm;

is faster than

var

    i=0,

    lenght=coll.length;

while(l<++i)

    dosomethingwithcoll[i];

When you loop through the elements of a collection, use the coll.item(index) method instead of the coll[index] syntax. This means that you don't have to know the length of the collection, since the item method returns null when the index is too big, instead of throwing a parsing error as it would using the hash syntax.

(Edited by liorean on 09-04-2004 07:14)

Liorean: Welcome in the Asylum. For one of your first posts, that's a monster/master piece. Kudos.

Many of the simple loop optimization tricks covered here are also explained in "Speed up you site" by Andrew B. King ( ISBN: 0-7357-1324-3 ) ( though I've always found his resulting numbers were weird, but afair he tested his routines on a Mac ).

That's great to have the view of someone that really know how the JavaScript engines are implemented, all the more that you explanations are clear.

I didn't knew that the JavaScript engine(s) created a temporary array for the HTMLCollection, HTMLOptionsCollection, NodeList or NamedNodeMap. On the other hand I'm not surprised about how the variables are handled and by the fact that the numbers are stored in IEEE 754 in priority. Actually the way the variables are handled reminds me the way GFA basic handled them.

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Welcome, Liorean!

I had speculated as much concerning numbers being stored as floating point... the speed of number operations (divide especially) seemed such to me that it couldn't natively store everything as an integer.

The optimations are good to know, especially the one with caching getElementById etc., I was not aware of this behavior, personally.

Anyway, have a good stay at the Asylum!

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

Actually, I have to correct myself about the DOMCollections. JavaScript has in difference to Java no threading support and as a single threaded language doesn't need to recreate the temporary arrays when accessing them in a loop. So,

var

    i=0,

    elm;

while(elm=document.getElementsByTagName(string).item(i++))

    dosomething;

is not at all faster than

var

    i=0,

    c=document.getElementsByTagName(string),

    elm;

while(elm=c.item(i++))

    dosomething;

Quite the opposite, actually, the latter example takes between five and ten or even a hundred times the amount of time to complete. (Opera has lousy preformance sometimes...)


I just put up a DOMCollection performance test that displays this. Especially Opera and MSN/OSX seems to benefit from caching the collections.



However, the rest of the optimisations are correct. Especially the last one mentioned is important. Comparing the counter to the collection length and accessing the element through the collection cancels out the benefit of caching the collection. So, the most important DOM optimisation for JavaScript (as opposed to Java) would be to use

var

    i=0,

    elm;

while(elm=coll.item(i++))

    dosomethingwithelm;

to traverse the collection instead of doing something like

var

    i=0,

    lenght=coll.length;

while(i++>l)

    dosomethingwithcoll[i];

or even worse

var

    i,

for(i=0;i<coll.length;i++)

    dosomethingwithcoll[i];

The short of it, cache everything you can, don't access an element by index in the collection if you can avoid it by caching it in the loop condition.
--
var Liorean = {
prototype: JavaScriptGuru.prototype,
abode: "http://liorean.web-graphics.com/",
profile: "http://codingforums.com/member.php?u=5798"};

(Edited by liorean on 09-15-2004 01:59)