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

« JGO Spiffy Duke »


Medals: 249
Projects: 2
Exp: 1 year


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

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 - Survival Sim/Builder/Roguelike!
LIVE-STREAMING DEVELOPMENT: http://www.twitch.tv/SG_Rayvolution
Offline 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. Shocked

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.

Offline Rayvolution

« JGO Spiffy Duke »


Medals: 249
Projects: 2
Exp: 1 year


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 - Survival Sim/Builder/Roguelike!
LIVE-STREAMING DEVELOPMENT: http://www.twitch.tv/SG_Rayvolution
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CodeHead

JGO Knight


Medals: 41


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.
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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.
Offline CodeHead

JGO Knight


Medals: 41


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

Arthur: Are all men from the future loud-mouthed braggarts?
Ash: Nope. Just me baby...Just me.
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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:

header1357
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)
headerrowRef0rowRef1

Row 0:
header13

Row 1:
header57

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.
Offline CodeHead

JGO Knight


Medals: 41


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

Arthur: Are all men from the future loud-mouthed braggarts?
Ash: Nope. Just me baby...Just me.
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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. Smiley

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."
Offline Rayvolution

« JGO Spiffy Duke »


Medals: 249
Projects: 2
Exp: 1 year


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

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Survival Sim/Builder/Roguelike!
LIVE-STREAMING DEVELOPMENT: http://www.twitch.tv/SG_Rayvolution
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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. Tongue )

No, you still shouldn't really care because looping over a 4 element array takes nanoseconds either way the array is structured.
Offline Rayvolution

« JGO Spiffy Duke »


Medals: 249
Projects: 2
Exp: 1 year


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

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Survival Sim/Builder/Roguelike!
LIVE-STREAMING DEVELOPMENT: http://www.twitch.tv/SG_Rayvolution
Online 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
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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.
Offline Cero
« Reply #14 - Posted 2014-05-05 05:04:50 »

well how much memory are you using ?

Offline 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
Offline 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.
Offline Rayvolution

« JGO Spiffy Duke »


Medals: 249
Projects: 2
Exp: 1 year


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

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 - Survival Sim/Builder/Roguelike!
LIVE-STREAMING DEVELOPMENT: http://www.twitch.tv/SG_Rayvolution
Online 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. Tongue

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
Offline 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.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline princec

« JGO Spiffy Duke »


Medals: 430
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 Smiley

Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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<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)

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

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 years



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

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

« JGO Overlord »


Medals: 840
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 289
Exp: 5 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.

Looks about like I expected.

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?
Offline 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:   Roll Eyes  

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;
    }
  }
}
Offline 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:   Cool  

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;
    }
  }
}
Offline Oskuro

JGO Knight


Medals: 40
Exp: 6 years


Coding in Style


« Reply #29 - Posted 2014-05-06 11:21:50 »

*looks up*  Cranky

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*  Emo

Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (30 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (42 views)
2014-12-09 22:41:13

BurntPizza (76 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (50 views)
2014-12-03 16:27:13

CopyableCougar4 (48 views)
2014-11-29 21:32:03

toopeicgaming1999 (114 views)
2014-11-26 15:22:04

toopeicgaming1999 (102 views)
2014-11-26 15:20:36

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!