Rayvolution
|
 |
«
Posted
2014-05-04 21:16:05 » |
|
I'm working on my Pathfinding in my game attempting to come up with my own version of A*, and I've found it massively less complicated to use a 2D array to gather data, and it seems plenty fast enough to suit my needs. But, a lot of other coders seem to want to cram the X/Y coordinates into a single array. I was curious what your guy's input is on these 2 methods of storing X/Y coordinate values, and if there's any reason I shouldn't just go with a 2D array? I can't even find a real performance difference, and it's a lot easier to code with an int[xCord][yCord] array. Storing the daya in a small 2D array: 1 2 3
| int[][] array = new int[mapHeight][mapWidth];
array[x][y] = value; |
Storing the same data in a large 1D array: 1 2 3
| int[] array = new int[mapHeight * mapWidth];
array[y + (x * mapWidth)] = value; |
the 1D array is probably technically less memory intensive, but it's a pain in the arse to work with.  Main reason I bring this up is I don't want to get all the way into the final product of my pathfinding to find out there's some legitimate serious flaw with using a 2D array.
|
|
|
|
jonjava
|
 |
«
Reply #1 - Posted
2014-05-04 21:45:05 » |
|
the 1D array is probably technically less memory intensive, but it's a pain in the arse to work with.  Main reason I bring this up is I don't want to get all the way into the final product of my pathfinding to find out there's some legitimate serious flaw with using a 2D array. There isn't and it's not. Don't worry about it.
|
|
|
|
Rayvolution
|
 |
«
Reply #2 - Posted
2014-05-04 21:52:49 » |
|
There isn't and it's not. Don't worry about it.
Good to know, because I can't find any justified way why I'd want a huge 1D array that's hard to work with over a 2D array that's basically just 2 small 1D arrays. That brings an interesting functionality question to mind though, this array is for a 256x256 tile map, technically speaking is int[65536] (aka: 256x256) and int[256][256] the same size, or is int[256][256]'s total size actually 512? If the 1D array's total size is larger than the 2D's, I can't imagine any way that a 1D array would be better at all. EDIT: I am assuming here that a int[256][256] array is 256 arrays of 256 arrays, meaning it's the same size as int[65536]
|
|
|
|
Games published by our own members! Check 'em out!
|
|
CodeHead
|
 |
«
Reply #3 - Posted
2014-05-04 22:06:11 » |
|
That brings an interesting functionality question to mind though, this array is for a 256x256 tile map, technically speaking is int[65536] (aka: 256x256) and int[256][256] the same size, or is int[256][256]'s total size actually 512?
If the 1D array's total size is larger than the 2D's, I can't imagine any way that a 1D array would be better at all.
They are the same size. The memory footprint is the product of the individual dimensions times the object size. I would venture to guess that everything is stored in a single dimension array behind the scenes with the [] operator handling the offset math for the developer. I remember hearing the advice to use singe dimension arrays many years ago, but have considered it outdated wisdom for general programming for a while now.
|
Arthur: Are all men from the future loud-mouthed braggarts? Ash: Nope. Just me baby...Just me.
|
|
|
BurntPizza
|
 |
«
Reply #4 - Posted
2014-05-04 22:10:16 » |
|
Yeah, don't worry about it. If it's easier to use, then it's probably better for you. I myself have simply gotten used to using a 1D array from various projects where it was actually necessary, so in that case the 1D is easier for me. The only real performance benefits I can think of are: less memory usage (minimal to decent, depending on circumstances), and better data locatity and thus cache friendliness (again ranges from minimal to algorithm-breaking). Also less indirection due to only having to make 1 lookup. (Also a cache-related issue) That brings an interesting functionality question to mind though, this array is for a 256x256 tile map, technically speaking is int[65536] (aka: 256x256) and int[256][256] the same size, or is int[256][256]'s total size actually 512?
If the 1D array's total size is larger than the 2D's, I can't imagine any way that a 1D array would be better at all.
http://www.javamex.com/tutorials/memory/array_memory_usage.shtmlThe uses 16 + 4n bytes, where n is the length of the array. For n = 65536, size = 262,160 bytes The uses 16 + 4j + j(16 + 4k) bytes, where j and k are the dimensions of the outer and inner arrays, respectively. For j,k= 256, size = 267,280 bytes, or 5 kb more. They are the same size. The memory footprint is the product of the individual dimensions times the object size. I would venture to guess that everything is stored in a single dimension array behind the scenes with the [] operator handling the offset math for the developer. I remember hearing the advice to use singe dimension arrays many years ago, but have considered it outdated wisdom for general programming for a while now.
This is false. "Multidimensional" arrays in java are nested arrays, you might be thinking of C where MD arrays are more or less syntax sugar over a 1D array.
|
|
|
|
CodeHead
|
 |
«
Reply #5 - Posted
2014-05-04 22:22:03 » |
|
This is false. "Multidimensional" arrays in java are nested arrays, you might be thinking of C where MD arrays are more or less syntax sugar over a 1D array.
Indeed, I am pulling the information out of my C recollections. Could you elaborate on the "nested array" comment? It would seem to me that a contiguous memory allocation would be the most efficient way to approach a fixed size array no matter the number of dimensions, so I'm curious as to how/why Java would stray from that type of arrangement. (Not questioning your answer, just genuinely curious.) 
|
Arthur: Are all men from the future loud-mouthed braggarts? Ash: Nope. Just me baby...Just me.
|
|
|
BurntPizza
|
 |
«
Reply #6 - Posted
2014-05-04 22:31:30 » |
|
A 1D array is as such: int[] i = new int[] { 1, 3, 5, 7 }; |
and sits in memory as such: As with any object array (in objects the header is 8 bytes) the header is 12 bytes and the total size is rounded up to the nearest 8 bytes. Since s are divisible by 8 I just round up the header to 16 from the get-go for calculations. A 2D array is as such: 1 2 3 4
| int[][] i = new int[][] { { 1, 3 } { 5, 7 } }; |
and sits in memory as such: Outer array: (rowRef x are pointers to the sub-arrays) Row 0: Row 1: EDIT: As for contiguity, I don't believe the JVM makes any guarantees, but it's likely the allocator attempts to make it as contiguous as possible. The pointer indirection is still there however, and each "element" in the outer arrays is an object in it's own right and may be anywhere in the heap. You can see how this coupled with the memory usage increase can quickly get out of hand at higher dimensions.
|
|
|
|
CodeHead
|
 |
«
Reply #7 - Posted
2014-05-04 22:41:49 » |
|
That just seems inefficient to me, at least in the case of primitive types. I appreciate the clarification though. 
|
Arthur: Are all men from the future loud-mouthed braggarts? Ash: Nope. Just me baby...Just me.
|
|
|
BurntPizza
|
 |
«
Reply #8 - Posted
2014-05-04 22:47:58 » |
|
That just seems inefficient to me, at least in the case of primitive types. I appreciate the clarification though.  It is inefficient, and why people continue to use 1D arrays to represent higher-dimensional structures. It's not nearly as bad as this example with s when the objects stored in the array are large however. (Although then each is a equally large 32 bit pointer to the object you are storing, leading to more indirection and inefficiency) Pretty much the worse case however is using s. Each 1-bit is rounded up to a full byte. This is terrible at higher dimensions. Use a instead. (Exception is when speed is absolutely critical, an array lookup is still usually faster than a BitSet lookup even with the indirection and poor locality) Edit for quick example: In terms of % of total space "wasted," small, multidimensional arrays of small items are the worst. Consider an array of 4 booleans vs. a 2x2 array of booleans: : 12 + 1 * 4 = 16 bytes. (note that this is still 32x as much information as the booleans are storing) : (12 + 4 * 2 + 4 rounding) + 2(12 + 1 * 2 + 2 rounding) = 56 bytes. 3.5x more, and 112x times as much information as the array is actually storing. >99% of the memory is "wasted."
|
|
|
|
Rayvolution
|
 |
«
Reply #9 - Posted
2014-05-05 01:42:14 » |
|
So what I'm getting out of this is since I am dealing in such a large array, the ratio of wasted memory is so negligibly small I shouldn't care? (Unless I am loading thousands of these, and I'm not anyway). ..but on the other hand, if I was loading a int[2][2] over a int[4] I should care, because the ratio of wasted memory is much larger. (Not that I could think of many logical reasons I would load a int[2][2] array, but for arguments sake.  )
|
|
|
|
Games published by our own members! Check 'em out!
|
|
BurntPizza
|
 |
«
Reply #10 - Posted
2014-05-05 03:31:42 » |
|
So what I'm getting out of this is since I am dealing in such a large array, the ratio of wasted memory is so negligibly small I shouldn't care? (Unless I am loading thousands of these, and I'm not anyway). ..but on the other hand, if I was loading a int[2][2] over a int[4] I should care, because the ratio of wasted memory is much larger. (Not that I could think of many logical reasons I would load a int[2][2] array, but for arguments sake.  ) No, you still shouldn't really care because looping over a 4 element array takes nanoseconds either way the array is structured.
|
|
|
|
Rayvolution
|
 |
«
Reply #11 - Posted
2014-05-05 03:42:40 » |
|
No, you still shouldn't really care because looping over a 4 element array takes nanoseconds either way the array is structured.
Even better. 
|
|
|
|
Gibbo3771
|
 |
«
Reply #12 - Posted
2014-05-05 03:43:20 » |
|
I doubt the difference if noticeable, I use 2D arrays for all my tiles, can't imagine using 1D array.
Just do whatever is easier, stop worrying about performance/efficiency unless you hit a problem IMO.
Code code code, refactor later.
Also my A* algorithm does not iterate over an array of tiles for movement values or anything, that would be pointless and expensive IMO. Instead when the map loads, generate a 2D array of ints that can be passed to the A* NodeMap to identify node values when doing a search.
That means if you happen to alter the map, all you do is fetch the x y of that tile and alter the array of ints in the NodeMap, if that makes sense Lol.
|
"This code works flawlessly first time and exactly how I wanted it" Said no programmer ever
|
|
|
BurntPizza
|
 |
«
Reply #13 - Posted
2014-05-05 03:48:37 » |
|
Indeed, do not worry about performance until you have documented reason to worry.
That said, there can be legitimate reasons to worry. In one of my cellular automation-related projects a long time ago I remember using a 2D array for the main data structure was the main performance bottleneck. Replacing it with a 1D array and using it effectively got me from tens of updates per second (intolerable in that particular case) to hundreds.
|
|
|
|
Cero
|
 |
«
Reply #14 - Posted
2014-05-05 05:04:50 » |
|
well how much memory are you using ?
|
|
|
|
ikovrigin
Senior Newbie 
|
 |
«
Reply #15 - Posted
2014-05-05 05:17:31 » |
|
1D vs 2D is not about memorty consumation but about access time (reads count). 2D case: using row offset read rowRef using column offset read data
1D case: calculate offset and read
|
|
|
|
Roquen
|
 |
«
Reply #16 - Posted
2014-05-05 05:21:09 » |
|
Since this is posted in " Performance Tuning" then answer is: There's a huge difference between n-D arrays and 1D arrays.
1) In n-D arrays you walk random memory (insanely slow) everywhere except linear access in the deepest. 2) The math above is all wrong...all except the lowest are arrays of objects per entry. Much fatter and more GC overhead. 3) The compiler will frequently not be able to determine if an array object has been changed between accesses and will need to walk the chain of arrays to get to the element.
EDIT: Personally the only time I use an N-D is for time unimportant sparse datasets. Use a getter/setter method.
|
|
|
|
Rayvolution
|
 |
«
Reply #17 - Posted
2014-05-05 05:24:05 » |
|
well how much memory are you using ?
Hardly anything really; I can't even identify a memory usage change when I completely disable the entire pathfinding class.  Oddly enough I can't even see the different in my memory usage with a profiler either, go figure.
|
|
|
|
Gibbo3771
|
 |
«
Reply #18 - Posted
2014-05-05 07:53:11 » |
|
well how much memory are you using ?
Hardly anything really; I can't even identify a memory usage change when I completely disable the entire pathfinding class.  Oddly enough I can't even see the different in my memory usage with a profiler either, go figure. Soooo0000000... /thread ? :p
|
"This code works flawlessly first time and exactly how I wanted it" Said no programmer ever
|
|
|
Roquen
|
 |
«
Reply #19 - Posted
2014-05-05 08:05:51 » |
|
I'd say the point is: vs. vs. so it's reasonable to get into the habit of flattening arrays. Maybe they'll get around to adding this to the language at some point.
|
|
|
|
Riven
|
 |
«
Reply #20 - Posted
2014-05-05 09:20:41 » |
|
Some surprising results... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| public class CacheGrid { private static final int dim = (1 << 12); private static final int[] grid = new int[dim * dim]; private static final int[][] rows = new int[dim][dim];
public static void main(String[] args) { System.out.println(System.getProperty("java.version")); System.out.println(System.getProperty("java.vm.version"));
for(int i = 0; i < 10; i++) { System.out.println(); { long t0 = System.nanoTime(); fill_1d_XY(); long t1 = System.nanoTime(); System.out.println("fill_1d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_YX(); long t1 = System.nanoTime(); System.out.println("fill_1d_YX took: " + (t1 - t0) / 1000000 + "ms"); }
{ long t0 = System.nanoTime(); fill_2d_XY(); long t1 = System.nanoTime(); System.out.println("fill_2d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_YX(); long t1 = System.nanoTime(); System.out.println("fill_2d_YX took: " + (t1 - t0) / 1000000 + "ms"); } } }
public static void fill_1d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) grid[(y << 12) | x] = y * dim + x; }
public static void fill_1d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) grid[(y << 12) | x] = y * dim + x; }
public static void fill_2d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) rows[y][x] = y * dim + x; }
public static void fill_2d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) rows[y][x] = y * dim + x; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| 1.7.0_45 24.45-b08
fill_1d_XY took: 1229ms fill_1d_YX took: 20ms fill_2d_XY took: 545ms fill_2d_YX took: 20ms
fill_1d_XY took: 1227ms fill_1d_YX took: 16ms fill_2d_XY took: 539ms fill_2d_YX took: 15ms
fill_1d_XY took: 1225ms fill_1d_YX took: 17ms fill_2d_XY took: 539ms fill_2d_YX took: 15ms
fill_1d_XY took: 1225ms fill_1d_YX took: 17ms fill_2d_XY took: 539ms fill_2d_YX took: 15ms
fill_1d_XY took: 1229ms fill_1d_YX took: 17ms fill_2d_XY took: 538ms fill_2d_YX took: 15ms
fill_1d_XY took: 1223ms fill_1d_YX took: 17ms fill_2d_XY took: 538ms fill_2d_YX took: 15ms |
In this micro-benchmark, int[w][h] is always faster than int[w*h], who would-a-thunk! (Probably due to HotSpot not able to remove bounds-checks in the 1D version)
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
princec
|
 |
«
Reply #21 - Posted
2014-05-05 10:37:28 » |
|
Try adding a random-access and "psuedo-random" access couple of benchmarks and see how it compares. Cas 
|
|
|
|
BurntPizza
|
 |
«
Reply #22 - Posted
2014-05-05 15:13:18 » |
|
I made a quick attempt at the random fill, not sure if precalculating the random indices kills the bench, but I don't see much of a better way. EDIT: accounted for extra lookups by adding linearX and linearY, also fixed "<< dim" 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
| import java.util.*;
public class CacheGrid { private static final int dim = (1 << 12); private static final int[] grid = new int[dim * dim]; private static final int[][] rows = new int[dim][dim]; private static int[] randX = new int[dim], randY = new int[dim], linearX = new int[dim], linearY = new int[dim]; static { Random rand = new Random(35682457L); Set<Integer> set = new HashSet<Integer>(); while(set.size() < dim) set.add(rand.nextInt(dim)); Integer[] ints = set.toArray(new Integer[0]); for (int i = 0; i < dim; i++) randX[i] = ints[i]; set.clear(); while(set.size() < dim) set.add(rand.nextInt(dim)); ints = set.toArray(new Integer[0]); for (int i = 0; i < dim; i++) randY[i] = ints[i]; for(int i = 0; i < dim; i++) { linearX[i] = i; linearY[i] = i; } }
public static void main(String[] args) { System.out.println(System.getProperty("java.version")); System.out.println(System.getProperty("java.vm.version"));
for(int i = 0; i < 10; i++) { System.out.println(); { long t0 = System.nanoTime(); fill_1d_XY(); long t1 = System.nanoTime(); System.out.println("fill_1d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_YX(); long t1 = System.nanoTime(); System.out.println("fill_1d_YX took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_XY(); long t1 = System.nanoTime(); System.out.println("fill_2d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_YX(); long t1 = System.nanoTime(); System.out.println("fill_2d_YX took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_random(); long t1 = System.nanoTime(); System.out.println("fill_1d_random took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_random(); long t1 = System.nanoTime(); System.out.println("fill_2d_random took: " + (t1 - t0) / 1000000 + "ms"); } } } public static void fill_1d_random() { for(int x = 0; x < dim; x++) { for(int y = 0; y < dim; y++) { int xi = randX[x]; int yi = randY[y]; grid[(yi << 12) | xi] = yi * dim + xi; } } } public static void fill_2d_random() { for(int x = 0; x < dim; x++) { for(int y = 0; y < dim; y++) { int xi = randX[x]; int yi = randY[y]; rows[yi][xi] = yi * dim + xi; } } }
public static void fill_1d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) { int xi = linearX[x]; int yi = linearY[y]; grid[(yi << 12) | xi] = yi * dim + xi; } }
public static void fill_1d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) { int xi = linearX[x]; int yi = linearY[y]; grid[(yi << 12) | xi] = yi * dim + xi; } }
public static void fill_2d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) { int xi = linearX[x]; int yi = linearY[y]; rows[yi][xi] = yi * dim + xi; } }
public static void fill_2d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) { int xi = linearX[x]; int yi = linearY[y]; rows[yi][xi] = yi * dim + xi; } } } |
Results: (last 6 sets) 1.7.0_25 1.7.0_25 23.25-b01
fill_1d_XY took: 674ms fill_1d_YX took: 64ms fill_2d_XY took: 188ms fill_2d_YX took: 67ms fill_1d_random took: 673ms fill_2d_random took: 198ms
fill_1d_XY took: 673ms fill_1d_YX took: 65ms fill_2d_XY took: 189ms fill_2d_YX took: 68ms fill_1d_random took: 673ms fill_2d_random took: 196ms
fill_1d_XY took: 674ms fill_1d_YX took: 66ms fill_2d_XY took: 189ms fill_2d_YX took: 68ms fill_1d_random took: 671ms fill_2d_random took: 198ms
fill_1d_XY took: 673ms fill_1d_YX took: 64ms fill_2d_XY took: 191ms fill_2d_YX took: 67ms fill_1d_random took: 686ms fill_2d_random took: 197ms
fill_1d_XY took: 672ms fill_1d_YX took: 64ms fill_2d_XY took: 187ms fill_2d_YX took: 68ms fill_1d_random took: 674ms fill_2d_random took: 199ms
fill_1d_XY took: 672ms fill_1d_YX took: 63ms fill_2d_XY took: 189ms fill_2d_YX took: 67ms fill_1d_random took: 673ms fill_2d_random took: 198ms
|
|
|
|
Riven
|
 |
«
Reply #23 - Posted
2014-05-05 15:23:12 » |
|
You are shifting 'yi' by 4096 bits! This means you are actually shifting it by 4096&31 = 0 bits, which means you're mostly touching the first 'row' of your grid. Suddenly everything first in cache, skewing the results tremendously 
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
BurntPizza
|
 |
«
Reply #24 - Posted
2014-05-05 15:25:14 » |
|
Whoops, fixing...
|
|
|
|
Riven
|
 |
«
Reply #25 - Posted
2014-05-05 16:46:26 » |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
| import java.util.*;
public class CacheGrid { private static final int dim = (1 << 12); private static final int[] grid = new int[dim * dim]; private static final int[][] rows = new int[dim][dim];
private static int[] randX = new int[dim], randY = new int[dim], randL = new int[dim * dim], linearX = new int[dim], linearY = new int[dim], linearL = new int[dim * dim];
static { for(int i = 0; i < dim; i++) linearX[i] = randX[i] = i; for(int i = 0; i < dim; i++) linearY[i] = randY[i] = i; for(int i = 0; i < dim * dim; i++) linearL[i] = randL[i] = i;
shuffle(randX, new Random(293856L)); shuffle(randY, new Random(293856L)); shuffle(randL, new Random(293856L)); }
public static void shuffle(int[] arr, Random rndm) { for(int i = 0; i < arr.length; i++) { int idx1 = rndm.nextInt(arr.length - i); int idx2 = arr.length - 1 - i;
int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; } }
public static void main(String[] args) { System.out.println(System.getProperty("java.version")); System.out.println(System.getProperty("java.vm.version"));
for(int i = 0; i < 10; i++) { System.out.println(); { long t0 = System.nanoTime(); fill_1d_LI(); long t1 = System.nanoTime(); System.out.println("fill_1d_LI took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_LL(); long t1 = System.nanoTime(); System.out.println("fill_1d_LL took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_LR(); long t1 = System.nanoTime(); System.out.println("fill_1d_LR took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_XY(); long t1 = System.nanoTime(); System.out.println("fill_1d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_YX(); long t1 = System.nanoTime(); System.out.println("fill_1d_YX took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_XY(); long t1 = System.nanoTime(); System.out.println("fill_2d_XY took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_YX(); long t1 = System.nanoTime(); System.out.println("fill_2d_YX took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_1d_random(); long t1 = System.nanoTime(); System.out.println("fill_1d_random took: " + (t1 - t0) / 1000000 + "ms"); } { long t0 = System.nanoTime(); fill_2d_random(); long t1 = System.nanoTime(); System.out.println("fill_2d_random took: " + (t1 - t0) / 1000000 + "ms"); } } }
public static void fill_1d_random() { for(int x = 0; x < dim; x++) { for(int y = 0; y < dim; y++) { int xi = randX[x]; int yi = randY[y];
grid[(yi << 12) | xi] = yi * dim + xi; } } }
public static void fill_2d_random() { for(int x = 0; x < dim; x++) { for(int y = 0; y < dim; y++) { int xi = randX[x]; int yi = randY[y];
rows[yi][xi] = yi * dim + xi; } } }
public static void fill_1d_LI() { for(int i = 0; i < dim * dim; i++) { grid[i] = i; } }
public static void fill_1d_LL() { for(int i = 0; i < dim * dim; i++) { grid[linearL[i]] = i; } }
public static void fill_1d_LR() { for(int i = 0; i < dim * dim; i++) { grid[randL[i]] = i; } }
public static void fill_1d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) { int xi = linearX[x]; int yi = linearY[y]; grid[(yi << 12) | xi] = yi * dim + xi; } }
public static void fill_1d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) { int xi = linearX[x]; int yi = linearY[y]; grid[(yi << 12) | xi] = yi * dim + xi; } }
public static void fill_2d_XY() { for(int x = 0; x < dim; x++) for(int y = 0; y < dim; y++) { int xi = linearX[x]; int yi = linearY[y]; rows[yi][xi] = yi * dim + xi; } }
public static void fill_2d_YX() { for(int y = 0; y < dim; y++) for(int x = 0; x < dim; x++) { int xi = linearX[x]; int yi = linearY[y]; rows[yi][xi] = yi * dim + xi; } } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| 1.7.0_45 24.45-b08
fill_1d_LI took: 22ms fill_1d_LL took: 43ms fill_1d_LR took: 1266ms fill_1d_XY took: 1425ms fill_1d_YX took: 50ms fill_2d_XY took: 920ms fill_2d_YX took: 45ms fill_1d_random took: 1476ms fill_2d_random took: 2010ms
fill_1d_LI took: 19ms fill_1d_LL took: 41ms fill_1d_LR took: 1158ms fill_1d_XY took: 1312ms fill_1d_YX took: 41ms fill_2d_XY took: 1037ms fill_2d_YX took: 39ms fill_1d_random took: 1457ms fill_2d_random took: 2010ms
fill_1d_LI took: 18ms fill_1d_LL took: 37ms fill_1d_LR took: 1418ms fill_1d_XY took: 1319ms fill_1d_YX took: 41ms fill_2d_XY took: 1048ms fill_2d_YX took: 41ms fill_1d_random took: 1417ms fill_2d_random took: 1850ms |
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings!
|
|
|
BurntPizza
|
 |
«
Reply #26 - Posted
2014-05-05 19:03:26 » |
|
Nice, I was going to add some of those other comparisons, also realized that shuffling would be better than brute forcing a set, but class was ending so I didn't have time. Looks about like I expected. Also comparing 1d_LI to 1d_YX without the linearX, linearY lookups: (AMD Phenom II 955) 1.7.0_51 24.51-b03
fill_1d_LI took: 18ms fill_1d_LL took: 30ms fill_1d_LR took: 420ms fill_1d_YX took: 20ms fill_1d_random took: 1296ms Interestingly, LI is slightly faster (barely, but measurable) than YX, indicating that the loops where not flattened to equal code as the single loop. This is a consistent result. Bounds checking?
|
|
|
|
GoToLoop
|
 |
«
Reply #27 - Posted
2014-05-06 11:06:28 » |
|
Some cache optimization ideas for the random fill functions: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| private static final int POW = 10, DIM = 1 << POW;
private static final int[] grid = new int[DIM*DIM]; private static final int[][] rows = new int[DIM][DIM];
private static int[] randX = new int[DIM], randY = new int[DIM], linearX = new int[DIM], linearY = new int[DIM];
public static void fill_1d_random() { for (int y = 0; y != DIM;) { int yi = randY[y++], x = 0;
while (x != DIM) { int xi = randX[x++]; grid[yi<<POW | xi] = yi^xi; } } }
public static void fill_2d_random() { for (int y = 0; y != DIM;) { int yi = randX[y++], ry[] = rows[yi], x = 0;
while (x != DIM) { int xi = randX[x++]; ry[xi] = yi^xi; } } } |
|
|
|
|
GoToLoop
|
 |
«
Reply #28 - Posted
2014-05-06 11:18:23 » |
|
And for the non-random 2D fill too: 1 2 3 4 5 6 7 8 9 10
| public static void fill_2d_YX() { for (int y = 0; y != DIM;) { int yi = linearY[y++], ry[] = rows[yi], x = 0;
while (x != DIM) { int xi = linearX[x++]; ry[xi] = yi*DIM + xi; } } } |
|
|
|
|
Oskuro
|
 |
«
Reply #29 - Posted
2014-05-06 11:21:50 » |
|
*looks up*  I personally like 1D arrays because the may situations I have where it is easier to reference objects by their (pre-computed) index value directly. Silly example off the top of my head: 1 2 3 4 5 6 7 8 9 10
| Object[] all_objects_there_are_in_2d_world = new Object[]{ ... }; int[] selected_objects = new int[]{ ... };
void doSomethingForAll() { for(int index : selected_objects) { all_objects_there_are_in_2d_world [index].DoSomething(); } } |
But it is certainly situation specific. *looks back down* 
|
|
|
|
|