Accessing elements efficiently

Why not:

for(i = 0; i < vertices.length; )
{
x = vertices[i++];
y = vertices[i++];
z = vertices[i++];
}

Voila - 3 adds per loop iteration, plus the cost of indexing into the array itself which is unavoidable. Considering you're using Javascript, that's probably about as fast as you'll get (I don't know how optimized object field accesses are in most JS runtimes).

This gets repeated a lot here but it's important. Premature optimization is the root of all evil. Write clean code and use good algorithms where appropriate. Let the compiler (or interpreter) take care of the micro optimizations. If profiling shows that the compiler isn't doing a good enough job, THEN look at tuning it by hand.

For example, do you know if your Javascript engine is compiled at all, or is it simply interpreted? Does it optimize? How exactly are objects stored in memory? What are the costs involved allocating and destroying a vertex object as opposed to extending your array? What sort of cache access patterns does each allocation method have? These are only a few things you will need to know to answer your question meaningfully, and the best thing is that they will be different for each browser you run this in, if you're even running in a browser at all.

So stop worrying about it. Rewrite that sucker to use vertex objects. You are dealing with vertices, so using a packed array with all that access math is just plain confusing, a potential source of bugs and will make maintenance much harder.

Thanks for the posts guys. I've thought a lot about what both of you have said.

I did a little bit of benchmark testing (only for google chrome)

Heres the code incase anyone wants to repeat the test:

var intNow;


var Vertex = function()
{
this.x = 0;
this.y = 0;
this.z = 0;
}

var numVertices = new Array(500000*3);
for(var i=0; i<numVertices.length/3; i++)
{
numVertices[0 + (i*3)] = 0
numVertices[1 + (i*3)] = 0
numVertices[2 + (i*3)] = 0
}

var vertices = new Array(500000);
for(var i=0; i<vertices.length; i++)
{
vertices = new Vertex();
}

var x;
var y;
var z;

intNow = (new Date()).getTime();
for(var i=0; i<500000; i++)
{
x = numVertices[0 + (i*3)];
y = numVertices[1 + (i*3)];
z = numVertices[2 + (i*3)];
}
console.log((new Date()).getTime() - intNow);


intNow = (new Date()).getTime();
for(var i=0; i<500000; i++)
{
x = vertices.x;
y = vertices.y;
z = vertices.z;
}
console.log((new Date()).getTime() - intNow);


Summary:
Direct accessing the objects member variables was on average about 25% faster than the math hack.

I Also reran the test using Apoch's suggestion (I don't know why I never thought of that, I feel stupid. Thanks for point that out to me!)

Summary:
Using the post increment after each access is about 30% faster than direct accessing through vertex objects.

Kuro makes a great point though, I have had more than a few headaches debugging arrays and it would be much more readable to have objects. He also makes a great point about all of the other factors to consider.

Summary:
Direct accessing the objects member variables was on average about 25% faster than the math hack.

I Also reran the test using Apoch's suggestion (I don't know why I never thought of that, I feel stupid. Thanks for point that out to me!)

Summary:
Using the post increment after each access is about 30% faster than direct accessing through vertex objects.

Kuro makes a great point though, I have had more than a few headaches debugging arrays and it would be much more readable to have objects. He also makes a great point about all of the other factors to consider.

Here's one more to try:

for(var vertex in vertices)
{
x = vertex.x;
y = vertex.y;
z = vertex.z;
}


It might not end up being faster than Apoch's suggestion, but I would still go with objects as they will be much easier to work with. Once you actually do some sort of math on the values in real code, that 400-500% performance difference in the access will most likely become insignificant. If the access is 10% of the function time (a very generous estimate), making the access 500% faster will only speed your function up by about 8% overall.

Yeah, as soon as i posted that i edited, but you caught it before I could submit my edit =)

I had made a mistake in not adjusting my <50000 once i was incrementing i 3 times per loop.

I'll try your suggestion as well, thanks!

Yeah, as soon as i posted that i edited, but you caught it before I could submit my edit =)

I had made a mistake in not adjusting my <50000 once i was incrementing i 3 times per loop.

I'll try your suggestion as well, thanks!

Cool. I must admit I'm curious if using array access would have any impact on performance, so when you try it, if you don't mind posting the result it would be awesome .

[quote name='Darkbouncer4689' timestamp='1314924359' post='4856540']
Yeah, as soon as i posted that i edited, but you caught it before I could submit my edit =)

I had made a mistake in not adjusting my <50000 once i was incrementing i 3 times per loop.

I'll try your suggestion as well, thanks!

Cool. I must admit I'm curious if using array access would have any impact on performance, so when you try it, if you don't mind posting the result it would be awesome .
[/quote]

It would seem that a for in loop on an array will default to the number of elements in the array and not a reference to each object in the array. Thus to get the code to work I had to do

for(var vertex in vertices)
{
x = vertices[vertex].x;
y = vertices[vertex].y;
z = vertices[vertex].z;
}

Which is substantially slower as I believe the "in" keyword involves more complicated type checking than a simple less than comparison.

I don't use for/in very much, if I am messing something up please let me know =)

It would seem that a for in loop on an array will default to the number of elements in the array and not a reference to each object in the array. Thus to get the code to work I had to do

for(var vertex in vertices)
{
x = vertices[vertex].x;
y = vertices[vertex].y;
z = vertices[vertex].z;
}

Which is substantially slower as I believe the "in" keyword involves more complicated type checking than a simple less than comparison.

I don't use for/in very much, if I am messing something up please let me know =)

Ah, so it does, you are right. Thanks for trying it, though .

No problem!

Whenever possible, use the following in Java:
for ( int I = numVertices.length; --I >= 0; )





That is, start from the end of the loop and go towards 0.
There are many ways to check against 0 and regardless of optimizations you are guarantee never to reload numVertices.length into RAM and check against it for each iteration.
Additionally, this generates smaller code.

While this is also faster in C/C++, it helps Java even more.

Perform your own benchmarks with it.


L. Spiro

These sandbox timing tests are all fine and dandy, but in a real world project, what you actually do with those values once assigned is likely to be far more time-consuming than these trivial assignments and likely to make these tiny optimisations irrelevant.

Really one needs to write real-world code and profile before optimising.

That is, start from the end of the loop and go towards 0.
There are many ways to check against 0 and regardless of optimizations you are guarantee never to reload numVertices.length into RAM and check against it for each iteration.
Additionally, this generates smaller code.

While this is also faster in C/C++, it helps Java even more.

Perform your own benchmarks with it.[/quote]

Going backwards is problematic in c++ because the size() methods return unsigned types. The code will infinite loop as the counter never drops below zero. Alternatives are:

for(std::size_t i = container.size(); i-- > 0;){


}

Which is not the most readable of code, but a great solution if you can't use iterators and actually have to loop backwards.

So the simplest and fastest way to iterate is to just store the counter.

for(std::size_t i = 0, num = container.size(); i < num; ++i){

}

Or for iterators

for(auto i = container.begin(), end = container.end(); i != end; ++i){

}

The auto keyword in c++0x is a godsend...

Whenever possible, use the following in Java:
for ( int I = numVertices.length; --I >= 0; )

That is, start from the end of the loop and go towards 0.
There are many ways to check against 0 and regardless of optimizations you are guarantee never to reload numVertices.length into RAM and check against it for each iteration.
Additionally, this generates smaller code.

While this is also faster in C/C++, it helps Java even more.

Perform your own benchmarks with it.

Yes, definitely perform benchmarks.

Because iterating memory backwards is the exact opposite of CPU heuristics, meaning that for any set spanning multiple cache lines the hidden penalty will be high since prefetching, one of most crucial performance mechanisms will be rendered ineffective.

The canonical way remains this:final/const int n = container.size();
for (int i = 0; i < n; i++) {
}

If we are worrying about small code, then in C and C++, the following saves one register and simplifies iteration:T * curr = ...;
T * end = ...;
while (curr < end) {
...
curr++;
}


Reverse loops have many other problems as well, from signed types, to reverse iteration which may not be suitable for many algorithms to violating the principle of least surprise.