I was reading some article by the Flash developers about the limit to software rendering.
In the article they say, "any memory access, especially random access ... is the most expensive operation."
http://www.kaourantin.net/2007/02/limits-of-software-rendering.html

I dont know why but this made me think about this Matrix library im writing for a graphics engine.
Having some extra time, I wrote up a test comparing Matrices implemented with double[][]
versus unwrapping them into double[]s.

The double[] implementation is almost twice as fast (40% consistently).
The code for matrix multiplication etc are all exactly the same (they all use 2 for loops)
except that instead of m[row][column] i use m[row * 4 column].

This seems like spooky voodoo to me. Should this be the case?

 

 

From what I've heard, Java does quite a bit of background bounds checking when arrays are indexed. As such, using a multi-dimensional array would cause (N-1)*M more such checks. I didn't think they would amount to 40% though, especially since the 1-D version needs to use extra math to calculate the index. Very interesting and good to know. Thanks for sharing.

 

 

No problem. Im glad someone was interested.
I'll post the code so you guys can keep me honest.

Forgive the ABYSMAL code.

My results:
Test 1: 700 v 400 (43%)
Test 2: 3650 v 1950 (46%)
Test 3: 1850 v 1250 (33%)


DOUBLE (ARRAY) MATRIX

import java.util.*;
 
public class DoubleMatrix{
 
public DoubleMatrix(){
 
	Random rand = new Random();
	m = new double[4][4];
 
	for(int r = 0; r < 4; r++){
	for(int c = 0; c < 4; c++){
 
	m[r][c] = rand.nextDouble();
 
	}
	}
 
}
 
public void op1(DoubleMatrix dm){
 
	for(int r = 0; r < 4; r++){
	for(int c = 0; c < 4; c++){
 
	m[r][c] *= dm.m[r][c];
 
	}
	}
 
}
 
public void mult(DoubleMatrix dm){
 
	double[][] result = new double[4][4];
 
	for(int row = 0; row < 4; row++){
	for(int column = 0; column < 4; column++){
 
	double value = 0;
 
	for(int i = 0; i < 4; i++){
	value += m[row][i] * dm.m[i][column];
	}
 
	result[row][column] = value;
 
	}
	}
 
	m = result;
 
}
 
	public double[][] m;
 
}
 

SINGLE (ARRAY) MATRIX

import java.util.*;
 
 
public class SingleMatrix{
 
public SingleMatrix(){
 
	Random rand = new Random();
	m = new double[16];
 
	for(int r = 0; r < 4; r++){
	for(int c = 0; c < 4; c++){
 
	m[(r * 4) + c] = rand.nextDouble();
 
	}
	}
 
}
 
public void op1(SingleMatrix sm){
 
	for(int i = 0; i < 16; i++){
 
	m[i] *= sm.m[i];
 
	}
 
}
 
public void mult(SingleMatrix sm){
 
	double[] result = new double[16];
 
	for(int row = 0; row < 4; row++){
	for(int column = 0; column < 4; column++){
 
	double value = 0;
 
	for(int i = 0; i < 4; i++){
	value += m[(row * 4) + i] * sm.m[(i * 4) + column];
	}
 
	result[(row * 4) + column] = value;
 
	}
	}
 
	m = result;
 
}
 
	public double[] m;
 
}
 

TEST CLASS

 
public class Test{
 
public static void main(String[] args){
 
	Test test = new Test();
 
	test.test01();
	test.test01();
 
	test.test02();
	test.test02();
	test.test02();
	test.test02();
 
	test.test03();
	test.test03();
	test.test03();
	test.test03();
 
}
 
public void test01(){
 
	System.out.println("\nTest 01: ");
 
	long start;
	long stop;
 
	start = System.currentTimeMillis();
	subtest01();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
 
	start = System.currentTimeMillis();
	subtest02();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
 
}
 
public void subtest01(){
 
	for(int i = 0; i < size1; i++){
	dms[i] = new DoubleMatrix();
	}
 
}
 
public void subtest02(){
 
	for(int i = 0; i < size1; i++){
	sms[i] = new SingleMatrix();
	}
 
}
 
public void test02(){
 
	System.out.println("\nTest 02: ");
 
	long start;
	long stop;
 
	start = System.currentTimeMillis();
	subtest03();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
 
	start = System.currentTimeMillis();
	subtest04();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
}
 
public void subtest03(){
 
	for(int q = 0; q < size3; q++){
	for(int i = 0; i < (size1 - 1); i++){
	dms[i].mult(dms[i+1]);
	}
	}
 
}
 
public void subtest04(){
 
	for(int q = 0; q < size3; q++){
	for(int i = 0; i < (size1 - 1); i++){
	sms[i].mult(sms[i+1]);
	}
	}
 
}
 
public void test03(){
 
	System.out.println("\nTest 03: ");
 
	long start;
	long stop;
 
	start = System.currentTimeMillis();
	subtest05();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
 
	start = System.currentTimeMillis();
	subtest06();
	stop = System.currentTimeMillis();
	System.out.println("Time: " + (stop - start));
 
}
 
public void subtest05(){
 
	for(int q = 0; q < size3 * 10; q++){
	for(int i = 0; i < (size1 - 1); i++){
	dms[i].op1(dms[i+1]);
	}
	}
 
}
 
public void subtest06(){
 
	for(int q = 0; q < size3 * 10; q++){
	for(int i = 0; i < (size1 - 1); i++){
	sms[i].op1a(sms[i+1]);
	}
	}
 
}
 
 
	int size1 = 100000;
	int size2 = 1000000;
	int size3 = 10;
 
	DoubleMatrix[] dms = new DoubleMatrix[size1];
	SingleMatrix[] sms = new SingleMatrix[size1];
 
}
 

 

 

I forgot to add, most importantly, transforming a vector (multiplying) takes 35% less time.
When rotating 1,000s of polygons that really adds up.

 

 

That is fascinating!

So why doesn't the JVM use a single array of objects for multi-dimensional arrays and simply use a dimension offset (e.g. realArray[x*d+y] is equivalent to declaredArray[x][y]) for their underlying implementation? Seems like a pretty good idea to me.

Edited by: the.maltese.falcon on Nov 8, 2007 3:28 PM
stupid italics tags

 

 

umm... because they defined multidimensional arrays as arrays of arrays so that you could have ragged non-homogeneous object oriented arrays.

 

 

I think thats only part of it. I think they might (???) see a speed up with ragged arrays too.
I think the actual reason is because you dont have to define the "subarrays" size at
creation.

double[4][3] ... create 12 entries
double[4][] ... create how many?

if we HAD to specify the sizes at creation time with something like:
double[4][{3, 7, 2, 5}] ... then they could do the offsets.

But yea, that would be an AWFUL way to implement multi-dim arrays, lol.

IMHO though, a 40% performance increase DEFINITELY warrants Java considering a new
rectangular multi-dim array language construct.

They could use a single array syntax utilizing commas:

double??? rectArray = new double[4, 3];
double value = rectArray[1, 3];

 

 

seems like even with that overhead and bounds checking they might still be faster than a 40% slowdown, since for memory management of objects you could allocate the array of object pointers in one spot and the actual objects somewhere else

and special thanks to forum.java.sun.com for suddenly not allowing me to edit my posts :(

 

 

Its not a 40% slowdown.
The single array is 40% faster meaning the multidim is 66% slower.

 

 

One thought: a 4x4 matrix is pretty small, and your test appears to be including initialization in its timings. If you're just looking to compare access time, it's probably worthwhile to create single instances of the arrays, and pass those prebuilt instances into the test methods. Would also eliminate garbage collection overhead.

 

 

Its not. Test 1 is. Test 1 times how long it takes to fill an array of Matrices.
All subsequent tests use the Matrix objects that were already created and
that populate that array.

 

 

So I implemented a test with larger matrices :) My results did not show nearly a 66% slowdown...I would actually hesitate to make any conclusions based on the data I collected.

size := length of a side of the two-dim array. So the actual array size is size^2^
one-dim := time (in ms) to perform 5000000 operations of the type

array1[random] += array1[random]

two-dim := time (in ms) to perform 5000000 operations of the type

array2[random][random] += array2[random][random]

slowdown := how much longer it took (in ms) to execute operations on the two-dim array

size	one-dim	two-dim	slowdown
1	1500	1515	15
2	1218	1281	63
3	1359	1406	47
4	1266	1296	30
5	1375	1421	46
6	1359	1453	94
7	1453	1437	-16
8	1250	1312	62
9	1422	1421	-1
10	1375	1421	46
11	1375	1531	156
12	1375	1546	171
13	1406	1453	47
14	1515	1656	141
15	1546	1687	141
16	1531	1500	-31
17	1422	1702	280
18	1562	1422	-140
19	1375	1484	109
20	1609	1734	125
21	1406	1484	78
22	1499	1781	282
23	1671	1500	-171
24	1390	1422	32
25	1375	1421	46
26	1375	1749	374
27	1688	1749	61
28	1390	1688	298
29	1405	1438	33
30	1359	1437	78
31	1359	1421	62
32	1359	1313	-46
33	1452	1438	-14
34	1374	1422	48
35	1359	1437	78
36	1359	1406	47
37	1359	1421	62
38	1437	1484	47
39	1375	1593	218
40	1391	1468	77
41	1390	1438	48
42	1437	1624	187
43	1375	1406	31
44	1359	1422	63
45	1405	1438	33
46	1374	1422	48
47	1374	1422	48
48	1375	1406	31
49	1390	1640	250

Statistics (of the slowdown column):
Mean:77.8
Median: 48
Mode: 47
Min: -171
Max: 374
Standard Deviation: 101.53

So, based on these results, I am very hesitant to make any solid conclusions. It seems, that in general, the two-dimensional array tends to be slower. However, if indeed it is slower to use a multiple-dimension array, it seems that the slowdown is miniscule. Consider even the largest difference, of 374 milliseconds - this is the difference in time for 5000000 iterations of a command. That translates to 74.8 microseconds (which, I suppose is a long time in the realm of clock cycles on a GHz processor; but is nothing to a lowly human such as myself).

I guess my point is that, based on my results, I don't care, and will continue to use multi-dimensional arrays. I'll post my code if anyone wants to see it...I'll hold off for now though cause I don't want to make this post any longer...

 

 

Some thoughts. I agree that random memory accesses might be costly since the OS might have to page in and page out memory pages, and caches can get invalidated. An array that is 1d is allocated using contiguous memory so it has speed advantages in that way, but there's more to it. Accessing the 1d array is just an offset to a pointer, but accessing a 2d array means adding the offset to a pointer, get another pointer, add an offset to that pointer and then get the data. That together with bounds checks sounds expensive in comparison to the 1d array.

Kaj

 

 

(Do also note that row * 4 + column is pretty cheap since it can be optimized to a shift and add, i.e no multiplication)

 

 

No, this is what the MARC finite element software that I used to work with did it. They had one massive 1D array that held everything.

Of course, that was FORTRAN, but the idea applies. They didn't give a d@mn about 2D arrays mapping better to matricies.

%