 |
Author |
Topic: array nitty gritty (Read 2538 times) |
|
benelek
 
 
|
array nitty gritty
« on: Jan 22nd, 2003, 11:20am » |
|
this's a general java/programming question that applies to proce55ing by inheritance.
does a 2D array use more memory than a 1D array with the same number of variables in it?
eg, would the following arrays use the same amount of memory as each other?
Code:
int[][] arrA = new int[5][5];
int[] arrB = new int[25];
|
|
also, would accessing a variable in one be any faster than in the other?
thanks,
-jacob
|
|
|
|
|
REAS
|
Re: array nitty gritty
« Reply #1 on: Jan 22nd, 2003, 12:47pm » |
|
Jacob,
I'm playing devil's advocate and taking the risk in annoying many people by saying this, but why do you feel this is important at this stage in computer evolution? Compilers write very efficient machine code and we have memory to spare. And were talking about Java code which is inherently slow.
+ Casey
|
|
|
|
|
benelek
|
Re: array nitty gritty
« Reply #2 on: Jan 22nd, 2003, 1:45pm » |
|
hehe, that's fair enough with the example i've given. but it might be easier to access, say, the pixels array if it were a 2D array, than the 1D array it is right now. no one would have to fuss about with any modulo or equations.
|
|
|
|
|
fry
|
Re: array nitty gritty
« Reply #3 on: Jan 22nd, 2003, 5:13pm » |
|
casey is right re: memory requirements. java uses a lot, not matter what 
the single [] is faster than [][], and non-array variables are even faster than that. for instance, all the 4x4 matrix math inside the p5 graphics engine is done with floats like m00, m01, m02, m03 instead of m[0][0], m[0][1], etc because the former is much faster.
the reason is that inside an array, the vm is doing extra de-referencing and bounds checking.
all that said, i personally recommend 1D arrays for things like image data (especially if accessing it sequentially is what youre doing mostly); however as a learning device, and way to teach others, the 2D array can be much more understandable.
i *do not* encourage using lists of floats instead of small arrays, this is only done inside the graphics engine because those numbers are used very heavily inside very tight/small loops. much more advanced than almost any p5 app.
|
|
|
|
|
Martin
   
|
Re: array nitty gritty
« Reply #4 on: Jan 22nd, 2003, 6:16pm » |
|
if code elegance tweaked for speed was to be shun away for the mean time, may i recommend the use of vectors and hash tables? or, is that a real overkill?
|
|
|
|
|
fry
|
Re: array nitty gritty
« Reply #5 on: Jan 22nd, 2003, 7:29pm » |
|
vectors and hashtables are useful for different things than elemental types like int/float/color/char.
vectors are useful for storing variable length lists of Objects (not basic datatypes); hashtables are useful for a sort of dictionary style lookup. ie. looking up an object based on a 'String' object which is its name.
for instance, a Vector might store a list of BImage objects that are used in a project. a Hashtable of BImage objects might be based around Strings that are keys such as:
Code:BImage catImage = loadImage("cat.jpg");
BImage potatoImage = loadImage("potato.jpg");
BImage bearImage = loadImage("bear.jpg");
Hashtable table = new Hashtable();
table.put("cat", catImage);
table.put("potato", potatoImage);
table.put("bear", bearImage);
// then, to retrieve the image based on its name:
BImage theOneIWant = (Bimage) table.get("potato"); |
|
vectors are slower than arrays, but useful while learning to deal with lists of objects. they're too cumbersome for non-objects, however (int/float/char/color).
|
|
|
|
|
Glen Murphy
|
Re: array nitty gritty
« Reply #6 on: Jan 23rd, 2003, 12:18am » |
|
To address the issue of how relevant this all is, I think minor speed tweaks like this are extremely important in a lot of P5 apps where you can have thousands of objects all running the same code, and so the smallest improvement in efficiency is amplified thousands of times.
(eg the Grid4 example I recently posted kept running out of memory until I changed the size of one array from 500 to 300 [but that may have more to do with me being a suckhead]).
|
|
|
|
|
benelek
|
Re: array nitty gritty
« Reply #7 on: Jan 23rd, 2003, 3:08pm » |
|
actually, glen's hit the point i was asking about. a lot more people are interested in "ai"/"simulation"/etc, than there used to be. a trend in this direction is lots of small (tiny) "quantasized" operations that become something interesting on a more grand scale. to this end, knowing the nitty gritty of simple operations should be of huge importance.
all too often i find myself designing large operations to perform seemingly complex transformations, only to find a built-in function that does a similar process using a fundamental function of the language, weeks later.
as an interesting sidenote, the same problem occurs in normal language usage. people will use large paragraphs to describe something that pretty much has a word or short phrase for it already
|
| « Last Edit: Jan 23rd, 2003, 3:11pm by benelek » |
|
|
|
|
REAS
|
Re: array nitty gritty
« Reply #8 on: Jan 23rd, 2003, 4:37pm » |
|
I think someone should make a simple performance test to settle this once and for all.
At high noon.
|
|
|
|
|
Glen Murphy
|
Re: array nitty gritty
« Reply #9 on: Jan 24th, 2003, 12:18am » |
|
Done
Single-dimensional (test2) below runs faster for all test values of c > 200. Below that, test1 runs faster.
However, test2 has to perform more arithmetic operations than test1 so it has the disadvantage, but since we're likely talking about this in the context of pixel buffers, those operations (i+u*250) would be required anyway.
I suspect that when c < 200, it hasn't properly optimised the i+u*250 arithmetic yet.
Gosh I'm tired.
Code:
int[][] testarray1 = new int[250][250];
int[] testarray2 = new int[250*250];
int c = 0;
void setup() {
size(100,100);
for(int i = 0; i < 250; i++) {
for(int u = 0; u < 250; u++) {
testarray1[i][u] = i*u;
testarray2[i+u*250] = i*u;
}
}
}
void loop() {
int woka;
/*
// test1
for(int i = 0; i < 250; i++) {
for(int u = 0; u < 250; u++) {
woka = testarray1[i][u];
}
}
*/
// test2
for(int i = 0; i < 250; i++) {
for(int u = 0; u < 250; u++) {
woka = testarray2[i+u*250];
}
}
if(c == 2000) {
println(millis());
}
c++;
}
|
|
|
|
|
|
|
benelek
|
Re: array nitty gritty
« Reply #10 on: Jan 24th, 2003, 3:02am » |
|
mm, fair enough. but i modified the testing so that we can tell how much of a difference an interation method makes on the whole thing. btw, im getting test1 faster than test2 for ur testing, glen.
below, the different iteration methods used for 1D and 2D array accessing are tested (minus the arrays). on my computer (P4, 256meg, win2k), the two ran just as fast as each other on average, but the repeated results of test1 varied a bit more than the repeated results of test2 did. strange.
anywho, it has a bearing on glen's tests because the calculation (i+u*250) is unnecessary (correct me if im wrong), and may therefore be the deciding factor in his results.
Code:
// iteration speed testing.
int c=0;
void setup() {
size(200,200);
}
void loop() {
int woka=0;
//test 1.
for(int i=0; i<40000; i++) {
woka++;
}
/*
//test 2.
for(int i=0; i<200; i++) {
for(int j=0; j<200; j++) {
woka++;
}
}
*/
if(c==2000) { println(millis()); }
c++;
}
|
|
|
| « Last Edit: Jan 24th, 2003, 3:20am by benelek » |
|
|
|
|
benelek
|
Re: array nitty gritty
« Reply #11 on: Jan 24th, 2003, 5:14am » |
|
okay guys (and gals), the whole issue hereby simplifies itself: iteration by incrementing by the width, removes the need for the seperate (x+y*width) calculation. now we can actually find out which type of array is faster.
essentially, we're doing the same calculation, but incremental calculation for the process of iteration costs us less in processor power than normal calculation! see here for the test:
Code:
// iteration speed testing.
int c=0;
void setup() {
size(200,200);
}
void loop() {
int woka=0;
/*
//test 1. -- 1D array indexing.
for(int i=0; i<40000; i++) {
woka++;
}
//test 2.0 -- 2D array indexing
for(int i=0; i<200; i++) {
for(int j=0; j<200; j++) {
woka++;
}
}
*/
//test 2.1 -- 1D array indexing using 2D iteration.
for(int i=0; i<200; i++) {
for(int u=i*200; u<i*200+1; u++) {
for(int j=0; j<200; j++) {
for(int k=j+u; k<j+u+1; k++) {
woka++;
// NOTE: (i=y), (u=y*width), (j=x), (k=x+y*width)
}
}
}
}
if(c==2000) { println(millis()); }
c++;
}
|
|
|
| « Last Edit: Jan 24th, 2003, 6:20am by benelek » |
|
|
|
|
benelek
|
Re: array nitty gritty
« Reply #12 on: Jan 24th, 2003, 12:55pm » |
|
hrm, after a while playing with the above code, i have some questions.
but before i go into anything else - with the above code, try each of the tests. does everyone else get a similar time for each?
|
|
|
|
|
fry
|
Re: array nitty gritty
« Reply #13 on: Jan 24th, 2003, 4:57pm » |
|
as a side note about the array processing.. when using a single dimensional array for images and the like, it's important to try and avoid the y*width+x calculation, otherwise you're blowing all the speed that you gain by using a single array.
the way to do this depends on your code. for instance, if you can do everything sequentially, use an index:
Code:int index = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
pixels[index++] = // something here based on x and y
}
} |
|
or maybe even just looping over index if y and x aren't needed in the computation. that way a single loop is used.
also to note, doing an addition at each increment in the loop will be faster than a multiply. something like the following is an improvement:
Code:int offset = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
pixels[offset + x] = // something fancy
}
offset += width; // to prevent the multiply
} |
|
as for the specifics and running timing tests, your mileage will vary. the stuff i'm talking about here is more general comp sci nuts and bolts and less specific to java, though it will still apply. it'll apply even moreso in c, and to a fuller extent as you get into using more low powered processors (embedded microcontrollers, etc). it's just good practice as you get into more advanced things like glen's aggressive pixel hacking contraptions.
|
|
|
|
|
|
