Hello Guest

What's the fastest way to loop through data?

  • 9 Replies
  • 13170 Views
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[0]=x, float[1]=y, float[2]=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

*

Offline princec

  • *****
  • 1929
    • Puppygames
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 :)

*

Offline 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 »

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

*

Offline 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++) {
}


*

Offline princec

  • *****
  • 1929
    • Puppygames
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 :)

*

Offline 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 »

*

Offline 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  :P.
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 »

*

Offline 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];
}
}

*

Offline 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 »