13

In C# there are 2 ways to create mutlidimensional arrays.

int[,] array1 = new int[32,32];

int[][] array2 = new int[32][];
for(int i=0;i<32;i++) array2[i] = new int[32];

I know that the first method creates a 1-dimensional array internally, and that the second method creates an array of arrays (slower access).

However in Java, there is no such thing as [,], and I see multidimensional arrays declared like this:

int[][] array3 = new int[32][32];

Since such syntax is illegal in C#, and Java has no int[,], I'm wondering if this is equivilant to array1? Or is it still an array of arrays?

Hannesh
  • 7,256
  • 7
  • 46
  • 80
  • Also see http://stackoverflow.com/questions/168897/whats-better-in-regards-to-performance-type-or-type – nawfal Apr 25 '13 at 14:14
  • No, in c# there is one way to create a multidimensional array. And another to create a *jagged* array. They are two different things. – arkon Aug 05 '16 at 06:26

6 Answers6

10

It's still an array of arrays. It's just that in C# you'd have to create each subarray in a loop. So this Java:

// Java
int[][] array3 = new int[32][32];

is equivalent to this C#:

// C#
int[][] array3 = new int[32][];
for (int i = 0; i < array3.Length; i++)
{
    array3[i] = new int[32];
}

(As Slaks says, jagged arrays are generally faster in .NET than rectangular arrays. They're less efficient in terms of memory though.)

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
9

You are incorrect; jagged (nested) arrays are faster. (the CLR is optimized for them)

Java does not support true multi-dimensional arrays; that's a jagged array.
The Java syntax automatically creates all of the inner arrays; in C#, that would need a separate loop.

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • 2
    Nested arrays are fundamentally slower than true multi-dimensional arrays. There is a level of indirection for each level of nesting (an extra pointer to follow), and in most cases suboptimal memory locality. – rlibby Mar 15 '11 at 15:26
  • 2
    @rlibby: You're right that they're slower than 1d arrays. However, .Net 2d arrays are less efficient. (Note that I haven't measured that) – SLaks Mar 15 '11 at 15:28
  • I just did a quick benchmark, and in C# it looks like iterating through a 2D array (e.g. `int[x, y]`) takes roughly twice as long as iterating through a same-size 1D array. Good thing 18 months of Moore's Law fixes this. :) I did not compare 2D arrays with jagged arrays. – MusiGenesis Mar 15 '11 at 15:45
  • @SLaks, thanks, I didn't know .NET's multi-dimensional array implementation was so idiotic. It takes a special kind of stupid to make single memory reference perform worse than recursively following a chain of memory references, but I guess they managed it. Why did they even bother including multidimensional arrays if they weren't going to implement them right to ensure they perform well? – rlibby Mar 15 '11 at 15:56
  • 1
    @rlibby: There are two types of arrays in the CLR: *vectors* (which always zero-based and single-dimensional) and *arrays* (which are potentially multi-dimensional and potentially don't have a zero base). I *suspect* that it's the additional "it might not have a zero base" arithmetic that makes the difference here. Just a guess though. – Jon Skeet Mar 15 '11 at 17:58
  • Maybe there is a reason that Java doesn't implement 2D arrays, if they are slower than jagged arrays. – Hannesh Mar 17 '11 at 07:08
  • 1
    @Hannesh: They're slower in .Net's implementation. They're not intrinsically slower. The reason they're slower/not support is that they're not used much. – SLaks Mar 17 '11 at 12:47
  • This is blatant misinformation. Jagged arrays are ALWAYS slower due to the way they are allocated, and the extra JMPs in memory caused be this. – Engineer Dec 22 '18 at 13:44
  • @ArcaneEngineer: Yes, but the .Net implementation for multi-dimensional arrays is much slower, negating that benefit. – SLaks Dec 23 '18 at 16:46
7

Because people were concerned about the performance of multi-dimension vs staggered arrays in .NET, I implemented a few tests and benchmarked the results on 8k by 8k elements:

The tests were:

  1. Multi-dimensional 2D array
  2. Multi-dimensional with indices backwards (y first)
  3. Multi-dimensional with GetLength(x) instead of integer bound
  4. Staggered with backwards indicies
  5. Staggered
  6. One dimensional (size x size) with multiplication in index
  7. One dimensional with increment index

And the results:

one <> Elapsed Time: 0.543558s
two <> Elapsed Time: 0.8911516s
three <> Elapsed Time: 0.8908123s
four <> Elapsed Time: 1.1367238s
five <> Elapsed Time: 0.3039648s
six <> Elapsed Time: 0.8110969s
seven <> Elapsed Time: 0.2629394s

For fun I ran them on the WP7 emulator as well, and got similar numbers.

Code of the test function is here.

nullspace
  • 1,279
  • 13
  • 13
  • Your sixth test is incorrect (according to your test description), as you use x + y*size as offset and thereby jumping around in the array. The offset should of course be x*size + y. – Jonas Nyrup Oct 22 '14 at 09:29
3

In Java you are declaring an array of arrays.

You can see this by the following code:

int[][] arrOfArr = new int[5][];
arrOfArr[0] = new int[5];
arrOfArr[1] = new int[1];
arrOfArr[2] = new int[9];
...

int[][] arr = new int[3][3]; is just shorthand for:

int[][] arr = new int[3][];
arr[0] = new int[3];
arr[1] = new int[3];
arr[2] = new int[3];
jjnguy
  • 136,852
  • 53
  • 295
  • 323
1

I was translating some Java code to C# - here is how I did the Jagged array

    //Java
    private static int grad3[][] = {{1,1,0},{-1,1,0},{1,-1,0},{-1,-1,0},{1,0,1},{-1,0,1},{1,0,-1},{-1,0,-1},{0,1,1},{0,-1,1},{0,1,-1},{0,-1,-1}};

    //C#
    private static int[,] grad3setup = { { 1, 1, 0 }, { -1, 1, 0 }, { 1, -1, 0 }, { -1, -1, 0 }, { 1, 0, 1 }, { -1, 0, 1 }, { 1, 0, -1 }, { -1, 0, -1 }, 
                                  { 0, 1, 1 }, { 0, -1, 1 }, { 0, 1, -1 }, { 0, -1, -1 } };

    private static int[][] grad3
    {
        get
        {
            int[][] grad3 = new int[12][];
            for (int i = 0; i < grad3.Length; i++)
            {
                grad3[i] = new int[3] { grad3setup[i, 0], grad3setup[i, 1], grad3setup[i, 2] };
            }
            return grad3;
        }
    }
Bixel
  • 75
  • 6
0

It is an array of arrays with the same performance tradeoffs as in C#. If you know that your array of arrays is not going to be jagged, then you can wrap it in a class to get 2-d indexing on a 1-d backing array.

Mike Samuel
  • 118,113
  • 30
  • 216
  • 245