What's the fastest way to loop through data?

[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):

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?

[princec]

Premature optimisation is the root of all evil

Cas

[bobjob]

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.

[VeAr]

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.

for (int i = 0, mi = length; i < mi; i++) {
}

[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:

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:

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:

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.....

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:

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.

[VeAr]

Can you try the same benchmarks with looping over arrays?

Something like this:

void addArrays(float[] source1, float[] source2, float[] result) {
for(int i=0; i<source1.length; i++) {
result[i] = source1[i] + source2[i];
}
}

[bobjob]

tests forward and backward

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

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:

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

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