## What's the fastest way to loop through data?

Started by elias4444, October 31, 2008, 19:43:05

#### elias4444

Ok, now that I'm interpolating my animations, I have to loops through every vertice every frame and calculate it's new position. The biggest speed killer seems to be the looping. Here's what I have now:

An ArrayList<float[]> to hold each frame of the animation (and each float[] is a list of coordinates so that float[0]=x, float[1]=y, float[2]=z, loop ad infinitum). So, to loop through, I do this (note, pseudo code):

My question is, is there a faster method to reference, store, and loop through these long lists of coordinates? Or am I doing it the most optimized way?
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

#### princec

Premature optimisation is the root of all evil

Cas

#### bobjob

Quote from: princec on October 31, 2008, 21:06:13
Premature optimisation is the root of all evil
Cas
so true!

nun the less heres my 5cents.
The answer would be something like

for (int i = length-1; i >= 0; i--) {
}

as its faster to compare with '0'

oh i almost forgot, because you know your dealing with "triangles" (I assume you are)
then you can just make the code longer and change...;i -= 3) {
that way you dont loop as much

#### elias4444

Well, Bob, you gave me an idea. I took the animationFrames.get(currentFrame).length out of the condition. I realized that it'd be pulling that on every loop. I also now set a float[] array on each currentFrame and nextFrame increment, rather than polling for it every frame with .get(). In the end, I got about a 75% increase in the loop speed. It looks like the ArrayList.get() command is the most costly, so I'm avoiding that now.

I'm also not sure the i-=3 will give me anymore, as now the most expensive operation (as far as I can tell) is the calculation of the newpoint (one minus and a multiply). I may try the i-- method, but it may cost me just as much to either put things back in order when I'm finished with the loop or to perform a simple subtraction to fetch the points from front to back.

=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

#### VeAr

Quote from: bobjob on October 31, 2008, 23:01:18
for (int i = length-1; i >= 0; i--) {
}

Looping backwards on arrays has negative impact on the cache. Caches are designed to cache data in forward direction. When looping on arrays always loop forward.

#### princec

Aye, and these days it's no more expensive to compare with non-zero numbers as well. Clever things these processors, now.

Cas

#### bobjob

ok well i guess there is a bit that has changed in java.

what i ment with the i -= 3; was that you would do the same code three times
but after the first call to i, the next two would use i+1, i+2, that way you loop 3 times as less, but your code is 3 times longer.

#### bobjob

ok here are some loops i used and here are the results
Windows XP, Intel Pentium - dual core, dont know what else is relavent  .
warning: I dont know how accurate Sys.getTime() is
1:

results:
3484, 3515, 3500

2:

results:
3515, 3515, 3516

3:

results:
4109, 4093, 4078

The winner is.....

results:
2546, 2531, 2547

because you refer to 'i' more than once, so make sure to just use --i before calling the next point in the triangle.

#### VeAr

Can you try the same benchmarks with looping over arrays?

Something like this:

#### bobjob

tests forward and backward

results:
13344, 13312, 13343

results:
13796, 13765, 13735

unrolled loops are as follows:

12844, 12813, 12813

results:
13484, 13468, 13453

would be cool if someone else could run the tests on there own comps, Just make sure to include lwjgl, as it uses the org.lwjgl.Sys class