2

I found this topic on a similar Stack Overflow thread.

In c++, when you make an array int[i][j] you get row major order, so iterating by row will give you caches which contain more useful data.

In java, there is no 2d array, but it still creates something similar enough in terms of caches. My question is, does it create the arrays of actual data in the size of row, or does it create the array of pointers in size of row?

Or, as the top answer on the similar Stack Over thread said, does it do something entirely different where int[5][8] would be an array of 5 pointers to arrays of any size that all add up to (5*8)?

It said java makes jagged arrays, and I can't think of any good reason for this to be true.

Community
  • 1
  • 1
Thumbz
  • 347
  • 3
  • 11
  • http://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html – Brian Roach Jan 29 '13 at 20:56
  • As far as I know, Java has 2d arrays the same as C/C++ does, arrays of 1 dimensional arrays. If someone has a resource that says otherwise, please post it. – Alex DiCarlo Jan 29 '13 at 20:57
  • 1
    @AlexDiCarlo To quote the link: _"In the Java programming language, a multidimensional array is simply an array whose components are themselves arrays. This is unlike arrays in C or Fortran."_ – keyser Jan 29 '13 at 20:59
  • @Keyser Every resource I've quickly looked at just now with a simple google search say arrays in C/C++ work the same way. See [here](http://www.cplusplus.com/doc/tutorial/arrays/) for example. – Alex DiCarlo Jan 29 '13 at 21:03
  • @AlexDiCarlo The quote said `C`, your link is about `C++`. And I'm simply quoting the official documentation. – keyser Jan 29 '13 at 21:06
  • @Keyser I realize you were just quoting, and I'm replying because quoting official documentation doesn't necessarily mean it is correct information. Also, I didn't link a source for C because I didn't want to link a bunch of easily googleable things, for example the [first result](http://www.eskimo.com/~scs/cclass/int/sx9.html) for the search "multi-dimensional arrays in C". – Alex DiCarlo Jan 29 '13 at 21:08
  • @Keyser P.S. Not trying to attack you, just trying to figure out if this is just a common misconception or I'm missing something. – Alex DiCarlo Jan 29 '13 at 21:09
  • @AlexDiCarlo Not sure if the "easily googable" thing was applicable there :p Not feeling attacked though. I think the difference can be illustrated with the fact that the "rows" can vary in length in Java. – keyser Jan 29 '13 at 21:16
  • If your main concern is performance, and if by "caches which contain more useful data" you're referring to *cache performance* then I think a Java array of arrays will have performance characteristics similar to C++ 2d arrays. Reading both in row-major order will yield the best spacial locality, since elements of a given row will be close to each other in memory. The only difference is that C++ 2d arrays have the additional property that the end of one row will also be next to the first element of the next row in memory. – Chris Rice Jan 30 '13 at 05:08

1 Answers1

2

In java, there is no 2d array, but it still creates something similar enough in terms of caches

I don't know about the C++ behaviour, but it sounds like you're expecting something in the Java behaviour which may very well not be the case. If you write:

int[][] x = new int[5][8];

then that's equivalent to:

int[][] x = new int[5][];
x[0] = new int[8];
x[1] = new int[8];
x[2] = new int[8];
x[3] = new int[8];
x[4] = new int[8];

There are 6 separate arrays here. At any point, you could write:

x[2] = new int[10000];

It's just an array of arrays - jagged by definition. There's nothing to say it'll stay rectangular forever, or even that all the elements of the "top-level" array will be non-null.

I'd expect the values to start off close to each other in memory, but there's no guarantee that they'd stay that way.

If you really want to make sure you have a contiguous block of memory, you should use int[] x = new int[40]; instead.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • Is this not the same as C/C++? – Alex DiCarlo Jan 29 '13 at 20:58
  • @AlexDiCarlo: I'm not sure, but I'm pretty sure it's not what the OP is expecting. I'll edit to clarify that. – Jon Skeet Jan 29 '13 at 20:59
  • Most definitely not the same as C/C++. There the 2D arrays are real arrays, not arrays of array-references. – Jim Garrison Jan 29 '13 at 21:09
  • @JimGarrison Can you link a source? This source for [C++](http://www.cplusplus.com/doc/tutorial/arrays/) and this one for [C](http://www.eskimo.com/~scs/cclass/int/sx9.html) claim otherwise. (Or a short explanation would do) – Alex DiCarlo Jan 29 '13 at 21:17
  • I'm not positive, but I think the difference is that in C++ the arrays are next to each other, basically like one big array. This makes sense to me because the point of using an array rather than list is to localize data. – Thumbz Jan 29 '13 at 21:31
  • Also, thank you Jon. I think you got it. It would be best to iterate through the 5 rows by col, rather than 8 col by row. Especially because there might not even be 8 col. I've actually been messing this up in my code some, doing it arbitrarily and probably costing myself A LOT of speed. – Thumbz Jan 29 '13 at 21:33
  • @Thumbz: Yes, iterating over the whole of a single array is probably better... but I doubt that it's been costing you a *lot* of speed. I would still recommend writing the most *readable*, natural code first - and benchmark to find whether the performance is adequate. – Jon Skeet Jan 29 '13 at 22:10