Is there a logical reason to stuff 2D array data into one?

[Rayvolution]

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]; // or, [x][y] really //then store data by: array[x][y] = value;

Storing the same data in a large 1D array:

1   2   3

int[] array = new int[mapHeight * mapWidth]; //then store data by; 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]

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]

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]

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.

[BurntPizza]

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

The

int[]

uses 16 + 4n bytes, where n is the length of the array. For n = 65536, size = 262,160 bytes
The

int[][]

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]

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

[BurntPizza]

A 1D array is as such:

int[] i = new int[] { 1, 3, 5, 7 };

and sits in memory as such:

header

1

3

5

7

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

int

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: (rowRefx are pointers to the sub-arrays)

header

rowRef0

rowRef1

Row 0:

header

1

3

Row 1:

header

5

7

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]

That just seems inefficient to me, at least in the case of primitive types. I appreciate the clarification though.

[BurntPizza]

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

int

s when the objects stored in the array are large however. (Although then each

int

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

boolean[]

s. Each 1-bit

boolean

is rounded up to a full byte. This is terrible at higher dimensions. Use a

BitSet

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:

boolean[4]

: 12 + 1 * 4 = 16 bytes. (note that this is still 32x as much information as the booleans are storing)

boolean[2][2]

: (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]

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]

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]

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]

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.

[BurntPizza]

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]

well how much memory are you using ?

[ikovrigin]

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]

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]

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]

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

[Roquen]

I'd say the point is:

val = data[x][y]

vs.

val = get(x,y)

data[x][y] = val

vs.

set(x,y,val)

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]

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)

[princec]

Try adding a random-access and "psuedo-random" access couple of benchmarks and see how it compares.

Cas

[BurntPizza]

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]

1	(yi << dim) | xi

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

[BurntPizza]

Whoops, fixing...

[Riven]

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

[BurntPizza]

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]

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]

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]

*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[]{ ... }; //Indices of specific objects 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*