Hello Guest

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

• 9 Replies
• 17688 Views #### elias4444

•     • 636 ##### What's the fastest way to loop through data?
« on: October 31, 2008, 19:43:05 »
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=x, float=y, float=z, loop ad infinitum). So, to loop through, I do this (note, pseudo code):

Code: [Select]
`animationFrames = ArrayList<float[]>;for (int i=0;i<animationFrames.get(currentFrame).length;i++) {     currentPoint = animationFrames.get(currentFrame)[i];     nextPoint = animationFrames.get(nextFrame)[i];     newpoint = (calculate interpolation of points);     currentGeometryFloatBuffer.put(newpoint);}`
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?
« Last Edit: October 31, 2008, 19:45:17 by elias4444 »
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com #### princec

•     • 1933 ##### Re: What's the fastest way to loop through data?
« Reply #1 on: October 31, 2008, 21:06:13 »
Premature optimisation is the root of all evil Cas  #### bobjob

•    • 394
• LWJGL: WOW SO GOOD ##### Re: What's the fastest way to loop through data?
« Reply #2 on: October 31, 2008, 23:01:18 »
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
« Last Edit: October 31, 2008, 23:08:36 by bobjob » #### elias4444

•     • 636 ##### Re: What's the fastest way to loop through data?
« Reply #3 on: November 01, 2008, 03:59:15 »
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

• • 18 ##### Re: What's the fastest way to loop through data?
« Reply #4 on: November 01, 2008, 08:32:34 »
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.

Code: [Select]
`for (int i = 0, mi = length; i < mi; i++) {}` #### princec

•     • 1933 ##### Re: What's the fastest way to loop through data?
« Reply #5 on: November 01, 2008, 09:34:00 »
Aye, and these days it's no more expensive to compare with non-zero numbers as well. Clever things these processors, now.

Cas  #### bobjob

•    • 394
• LWJGL: WOW SO GOOD ##### Re: What's the fastest way to loop through data?
« Reply #6 on: November 01, 2008, 17:56:06 »
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.

« Last Edit: November 01, 2008, 18:42:59 by bobjob » #### bobjob

•    • 394
• LWJGL: WOW SO GOOD ##### Re: What's the fastest way to loop through data?
« Reply #7 on: November 01, 2008, 18:28:59 »
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:
Code: [Select]
` int length = 1000000000; long total = 0; long time = Sys.getTime(); for (int i = length; --i >= 0;) { total += i; } long result = Sys.getTime() - time; System.out.println(result);`results:
3484, 3515, 3500

2:
Code: [Select]
` int length = 1000000000; long total = 0; long time = Sys.getTime(); for (int i = length-1; i >= 0; i--) { total += i; } long result = Sys.getTime() - time; System.out.println(result);`results:
3515, 3515, 3516

3:
Code: [Select]
` int length = 1000000000; long total = 0; long time = Sys.getTime(); for (int i = 0; i < length; i++) { total += i; } long result = Sys.getTime() - time; System.out.println(result);`results:
4109, 4093, 4078

The winner is.....
Code: [Select]
` int length = 1000000000; long total = 0; long time = Sys.getTime(); for (int i = length-1; i >= 0; i -= 2) { total += i; total += i-1; } long result = Sys.getTime() - time; System.out.println(result);`results:
2546, 2531, 2547

but what your after is:
Code: [Select]
` for (int i = length-1; i >= 0; i--) { total += i; total += --i; }`because you refer to 'i' more than once, so make sure to just use --i before calling the next point in the triangle.
« Last Edit: November 01, 2008, 18:52:49 by bobjob » #### VeAr

• • 18 ##### Re: What's the fastest way to loop through data?
« Reply #8 on: November 01, 2008, 20:31:16 »
Can you try the same benchmarks with looping over arrays?

Something like this:

Code: [Select]
`void addArrays(float[] source1, float[] source2, float[] result) {for(int i=0; i<source1.length; i++) {result[i] = source1[i] + source2[i];}}` #### bobjob

•    • 394
• LWJGL: WOW SO GOOD ##### Re: What's the fastest way to loop through data?
« Reply #9 on: November 01, 2008, 21:23:22 »
tests forward and backward

Code: [Select]
` long total = 0; int length = 1000000; int array[] = new int[length]; int loopLength = length * 1000; for (int i = 0; i < array.length; i++) { array[i] = i; } int i = 0; long time = Sys.getTime(); for (int z = loopLength-1; z >= 0; z--) { i = z % length; total += array[i] + array[i]; } long result = Sys.getTime() - time; System.out.println(result);`results:
13344, 13312, 13343

Code: [Select]
` long total = 0; int length = 1000000; int array[] = new int[length]; int loopLength = length * 1000; for (int i = 0; i < array.length; i++) { array[i] = i; } int i = 0; long time = Sys.getTime(); for (int z = 0; z < loopLength; z++) { i = z % length; total += array[i] + array[i]; } long result = Sys.getTime() - time; System.out.println(result);`results:
13796, 13765, 13735

unrolled loops are as follows:

Code: [Select]
` long total = 0; int length = 1000000; int array[] = new int[length]; int loopLength = length * 1000; for (int i = 0; i < array.length; i++) { array[i] = i; } int i = 0; long time = Sys.getTime(); for (int z = loopLength-1; z >= 0; z--) { i = z % length; total += array[i] + array[i]; i = --z % length; total += array[i] + array[i]; } long result = Sys.getTime() - time; System.out.println(result);`12844, 12813, 12813

Code: [Select]
` long total = 0; int length = 1000000; int array[] = new int[length]; int loopLength = length * 1000; for (int i = 0; i < array.length; i++) { array[i] = i; } int i = 0; long time = Sys.getTime(); for (int z = 0; z < loopLength; z++) { i = z % length; total += array[i] + array[i]; i = ++z % length; total += array[i] + array[i]; } long result = Sys.getTime() - time; System.out.println(result);`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
« Last Edit: November 01, 2008, 21:42:05 by bobjob »