Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (624) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1] 2
 ignore  |  Print
 Is there a logical reason to stuff 2D array data into one?  (Read 5722 times) 0 Members and 1 Guest are viewing this topic.
Rayvolution

« JGO Spiffy Duke »

Medals: 313
Projects: 2
Exp: 2 years

Resident Crazyman

 « 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]; // 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.

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution
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

« JGO Spiffy Duke »

Medals: 313
Projects: 2
Exp: 2 years

Resident Crazyman

 « 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]

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution

JGO Knight

Medals: 45

From rags to riches...to rags.

 « 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

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

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

JGO Knight

Medals: 45

From rags to riches...to rags.

 « 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

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « 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
 `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)

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.

JGO Knight

Medals: 45

From rags to riches...to rags.

 « 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

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « 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
 `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 + 4rounding) + 2(12 + 1 * 2 + 2rounding) = 56 bytes. 3.5x more, and 112x times as much information as the array is actually storing. >99% of the memory is "wasted."
Rayvolution

« JGO Spiffy Duke »

Medals: 313
Projects: 2
Exp: 2 years

Resident Crazyman

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

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution
BurntPizza

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « 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

« JGO Spiffy Duke »

Medals: 313
Projects: 2
Exp: 2 years

Resident Crazyman

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

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution
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

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « 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 »

2D case:

1D case:
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

« JGO Spiffy Duke »

Medals: 313
Projects: 2
Exp: 2 years

Resident Crazyman

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

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution
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.

"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:

 `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
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « 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_4524.45-b08fill_1d_XY took: 1229msfill_1d_YX took: 20msfill_2d_XY took: 545msfill_2d_YX took: 20msfill_1d_XY took: 1227msfill_1d_YX took: 16msfill_2d_XY took: 539msfill_2d_YX took: 15msfill_1d_XY took: 1225msfill_1d_YX took: 17msfill_2d_XY took: 539msfill_2d_YX took: 15msfill_1d_XY took: 1225msfill_1d_YX took: 17msfill_2d_XY took: 539msfill_2d_YX took: 15msfill_1d_XY took: 1229msfill_1d_YX took: 17msfill_2d_XY took: 538msfill_2d_YX took: 15msfill_1d_XY took: 1223msfill_1d_YX took: 17msfill_2d_XY took: 538msfill_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

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « 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

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « 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 set = new HashSet();     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)

Quote
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
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #23 - Posted 2014-05-05 15:23:12 »

 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

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
BurntPizza

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

 « Reply #24 - Posted 2014-05-05 15:25:14 »

Whoops, fixing...
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « 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_4524.45-b08fill_1d_LI took: 22msfill_1d_LL took: 43msfill_1d_LR took: 1266msfill_1d_XY took: 1425msfill_1d_YX took: 50msfill_2d_XY took: 920msfill_2d_YX took: 45msfill_1d_random took: 1476msfill_2d_random took: 2010msfill_1d_LI took: 19msfill_1d_LL took: 41msfill_1d_LR took: 1158msfill_1d_XY took: 1312msfill_1d_YX took: 41msfill_2d_XY took: 1037msfill_2d_YX took: 39msfill_1d_random took: 1457msfill_2d_random took: 2010msfill_1d_LI took: 18msfill_1d_LL took: 37msfill_1d_LR took: 1418msfill_1d_XY took: 1319msfill_1d_YX took: 41msfill_2d_XY took: 1048msfill_2d_YX took: 41msfill_1d_random took: 1417msfill_2d_random took: 1850ms`

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
BurntPizza

« JGO Bitwise Duke »

Medals: 373
Exp: 6 years

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

Also comparing 1d_LI to 1d_YX without the linearX, linearY lookups:

Quote
(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

Junior Devvie

Medals: 2
Exp: 1 year

 « 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<
GoToLoop

Junior Devvie

Medals: 2
Exp: 1 year

 « 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

JGO Knight

Medals: 44
Exp: 6 years

Coding in Style

 « 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[]{ ... }; //Indices of specific objectsvoid doSomethingForAll(){   for(int index : selected_objects)   {        all_objects_there_are_in_2d_world [index].DoSomething();   }}`

But it is certainly situation specific.

*looks back down*

Pages: [1] 2
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 ClaasJG (25 views) 2015-04-27 13:36:51 BurntPizza (33 views) 2015-04-23 03:42:11 theagentd (36 views) 2015-04-22 16:23:07 Riven (50 views) 2015-04-16 10:48:47 Duke0200 (59 views) 2015-04-16 01:59:01 Fairy Tailz (42 views) 2015-04-14 20:13:12 Riven (46 views) 2015-04-12 21:36:37 bus hotdog (61 views) 2015-04-10 02:39:32 CopyableCougar4 (66 views) 2015-04-10 00:51:04 BurntPizza (71 views) 2015-04-06 22:06:58
 theagentd 23x BurntPizza 17x wessles 15x kingroka123 11x alwex 11x Spasi 11x 65K 11x kevglass 8x Hanksha 7x Riven 7x chrislo27 7x Olo 7x Ecumene 7x ra4king 7x Rayvolution 7x KevinWorkman 6x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org