Hello. How can I make a large tilemap (ie. 128x128x10) without using too much memory? I was wondering if I could just have something like this
Tile[][][] tiles = new Tile[128][128][10];
Would this take up a lot of memory even though they’re only null references?
I really need help since I want this to work with computers with more than or equal to 500 megs of ram… Please help!
IIRC overhead (on heap) is about 34 (update: 20) bytes per array.
128x128 x 34 = 557056 bytes = 0,53MB overhead
~~
Update:
I did measure this code:
System.gc();
System.gc();
System.gc();
System.gc();
for (int i = 0; i < 4; i++)
{
Object[][][] a;
long m0 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
a = new Object[128][128][10];
long m1 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
a[0] = null;
a = null;
System.gc();
long m2 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
System.out.println("alloc=" + (m1 - m0) / 1024 + "k ... freed=" + (m1 - m2) / 1024 + "k");
}
Output:
alloc=973k ... freed=968k
alloc=953k ... freed=966k
alloc=956k ... freed=967k
alloc=956k ... freed=967k
Thank you very much for the reply! I really apprechiate the code snippet! I typed your program and I found out after playing around with the variables and setting the third one to 1000 the jvm only allows (in eclipse) around 65 megs of ram to be used on 1 gig of memory, however the maximum number of layers I’ll have is probably around 32 (around 2 megs for 128x128). This is slightly unexpected for me since you said that each array takes about 34 bytes, so I thought 12812832*34 = 17825792 bytes -> (17 megs) but it is actually around 2.3 megs in the program?. Thank you very much for the help!
Well:
float[] x = new float[10]; // 1 array, not 10 arrays
float[] xy = new float[10][11]; // 10 arrays, not 10x11 arrays
float[] xyz = new float[10][11][12]; // 10x11 arrays, not 10x11x12 arrays
So your assumption of 128x128x10x34 should be:
128x128x{array-overhead}+128x128x10x4* = 990200 bytes
16384x{array-overhead}+655360 = 990200 bytes
16384x{array-overhead}= 334840 bytes
{array-overhead} = 20 bytes
So:
heap allocation for array-objects: 128x128x20b = 327.680
heap allocated for array-data: 128x128x32x4* = 2.097.152
total heap allocation: 327.680 + 2.097.152 = 2.424.832 = 2,31MB
* reference size (on 32bit cpu) = 1 int = 4 bytes
About the 65MB limit, that’s probably 64MB and can be increased by setting
“-mx{n}” as vm-argument, like:
-mx64M, -mx128M, -mx1G, etc etc.
Note:
Keep in mind that using multi-dimensional arrays in this way in this case might be a sign of bad design. You should try something like this:
int xDim = 128;
int yDim = 128;
int zDim = 10;
Tile[] tiles = new Tile[xDim * yDim * zDim];
// get tile at: x y z
tiles[((z * yDim) + y) * xDim) + x];
Or something like that if the (sub) array-sizes are not going to change.
This not only reduces overhead, but also makes tile-lookup significantly faster.
Thanks for posting again!
I tried your program again with different variables and it seems this approach saves the most memory of them all. I also see I could use some bit shifting for faster array accesses. Thank you so much for the help. Should I be careful about changing the maximum memory? For example if the max memory on a computer is 256 and I set the jvms heap size to 256 will the jvm overwrite memory used by the operating system?
No, the OS handles everything. You might get swapping which is so slow it’s pretty much unusable if you have to access everything in your array in a short amount of time. So be wise: only keep in RAM what you need, and dump/retrieve everything else at/from the harddisk if you are working with datasets larger than expected heap-size.
Is it really faster to calculate the index in a one dimension array than to look it up directly in a 3-dimensional one?
I would have thought the calculation you’d perform at the java level would be the same as the one that would have been performed at the VM level.
So, I’m suprised if it is.
Kev
But with an N-dimensional array the VM will be doing N bounds checks, if you do the index calculation the VM only has to do one bound checked access so it should be faster. Whether this is actually a noticable difference is another matter.
Also the two are not directly comparable - you are effectivly tossing out the safety of those extra bounds checks and a particularly big x/y coord which would otherwise have been valid becomes a ‘valid’ location for an entirely different tile. Basically you end up back in happy-fun C land where you can stomp around memory without any indication that you’re doing something wrong.
Incidentally, big 3d arrays tend to be the wrong way to go about this. Either a 2d array with a bunch of linked lists hanging off each cell or a set of Layers, each with a 2d array in them tends to work out nicer.
And one (minor) optimisation if you’re worried about array-object overhead: be careful about the dimension ordering. As all arrays are ragged (or rather, potentially ragged) with 1d arrays hanging off of 1d arrays then a 2x200 array (3 objects) ends up with many less objects than a 200x2 array (201 objects).
It occurs to me that you could use a ragged 3d array instead of a 2d array + linked lists, but that just makes me cringe even thinking about managing that nicely without going insane(er).
On Client VM it really is but you sacrifice safety, like OrangyTang said.
On Server VM it doesn’t matter that much anymore.
Ahh, that makes sense.
Kev
Would it really be that hard? Couldn’t you just increase the z dimension by 1 when you want another layer?
Is it really faster to calculate the index in a one dimension array than to look it up directly in a 3-dimensional one?
Yes. First it’s industry standard for some reason.
Second
int something = array[l * j + k*j2 + j3];
translates into
mov ebx, array
mov edx, l
mov eax, j
mul edx
add ebx, eax
mov edx, j2
mov eax, k
mul edx
add ebx, eax
mov edx, j3
add ebx, edx
possibly do array boundary checks
mov eax, [ebx]
int something = array[j][j2][j3];
converts to this
mov eax, array
mov ebx, j
add eax, ebx
mov eax, [eax]
mov ebx, j2
add eax, ebx
mov eax, [eax]
mov ebx, j3
add eax, ebx
mov eax, [eax]
In optimal case.
or into this
mov eax, array
mov ebx, j
add eax, ebx
possibly do array boundary checks
mov eax, [eax]
mov ebx, j2
add eax, ebx
possibly do array boundary checks
mov eax, [eax]
add eax, j3
possibly do array boundary checks
mov eax, [eax]
or into this
call retrieveArray, array (boundary checks might be in this inlineable function)
mov ebx, j
add eax, ebx
call retrieveArray, eax
mov ebx, j2
add eax, ebx
call retrieveArray, eax
mov ebx, j3
add eax, ebx
mov eax, [eax]
Another differences are
One random memory access vs three random memory accesses.
Has higher pointer overhead. Array of refferences is 24 bytes + a * 8 bytes on 64 bit computer. (12 + a * 4 on 32 bit)
BTW if this[quote]new Tile[128][128][10];
[/quote]
was supposed to hold 10 different tiles, it was done wrongly
Tile ti = new Tile[10]
ti[0] = new Tile(128, 128);
Would work much better.
It’s not hard for an individual case, but the syntax is ugly and non-intuitive and the whole process is very error prone. I’d rather not be tracking down awkward bugs when I can avoid the whole mess (and have a nicer design) from the outset. Especially for something that smells like a micro optimisation.
+1 on Orangy’s feelings.
Early micro-optimisation is generally as bad idea as explained as far back as Abrash’s Xen of Optimization.
Doubly so in Java where, assuming you are using a modern VM, htinsg like getters/setters are optized away.
Write clean, celar well encapsulated code first, that is the easiest to tune in the long run.
Then profile.
The tun.