Initializing a large jagged array takes over 1 GB of RAM and crashes with StackOverflowException

Question

When I compile this piece of C# code (full text) and run the ArrayTest.exe, the process hangs for a few seconds, consumes 1 GB of RAM, and crashes with StackOverflowException. Why?

public struct Point { }

public class ArrayTest {
    public static void Main(string[] args) {
        Point[][] array = {
            new Point[]{new Point(), new Point(), /* ... 296 omitted ... */, new Point(), new Point()},
            new Point[]{new Point(), new Point(), /* ... 296 omitted ... */, new Point(), new Point()},
            /* ... 296 omitted ... */
            new Point[]{new Point(), new Point(), /* ... 296 omitted ... */, new Point(), new Point()},
            new Point[]{new Point(), new Point(), /* ... 296 omitted ... */, new Point(), new Point()},
        };
        /* Do nothing and return */
    }
}

I am using Microsoft (R) Visual C# Compiler version 4.0.30319.33440 for Microsoft (R) .NET Framework 4.5. I'm just calling csc.exe on the command line and executing the compiled EXE. The problem disappears when I add the csc /optimize flag. The snippet above is indeed the entire code I am testing with - there is no useful work being performed in Main() after the array is initialized.

---

Problem context: I was trying to hard-code a set of numerical test cases into a program. In Java, JavaScript, or Python, the code would innocently look like this and work properly:

class Point { int x; int y; }

Point[][] data = {  // About 1000 entries
    {new Point(1, 2)},
    {new Point(5, 3), new Point(0, 6), new Point(1, 8)},  // Different length
    ... et cetera ...
};
for (Point[] thing : data):
    test(thing);

But when I tried to compiled code like this in C#, the array initialization took a noticeable amount of time (~5 seconds), even before the for-loop with the test() could start to execute.

My actual code has been reduced to the MVCE above, where struct Point contains no fields, and Main() contains just the array initialization and no useful work.

Answer 1

Okay, I started compiling debug/release versions of your class file. With the VS 2015 compiler found in the 14.0 version of tools, the output for the IL is identical. This covers the reason people weren't noticing issues.

Debug vs release in the previous compiler used in VS 2013 is pretty immediately damning. Output the the executable in debug mode is 2,091 kb. IL from the release version indicates it just ignores the actual object since it's never utilized. Okay, fine. I'll compare VS 2015 Debug IL to the VS 2013 Debug IL.

I've changed the array size to 3x3 for brevity.

Here is the output from the 2015 IL:

  .method public hidebysig static void  Main() cil managed
  {
    .entrypoint
    // Code size       45 (0x2d)
    .maxstack  4
    .locals init (valuetype Point[][] V_0)
    IL_0000:  nop
    IL_0001:  ldc.i4.4
    IL_0002:  newarr     valuetype Point[]
    IL_0007:  dup
    IL_0008:  ldc.i4.0
    IL_0009:  ldc.i4.3
    IL_000a:  newarr     Point
    IL_000f:  stelem.ref
    IL_0010:  dup
    IL_0011:  ldc.i4.1
    IL_0012:  ldc.i4.3
    IL_0013:  newarr     Point
    IL_0018:  stelem.ref
    IL_0019:  dup
    IL_001a:  ldc.i4.2
    IL_001b:  ldc.i4.3
    IL_001c:  newarr     Point
    IL_0021:  stelem.ref
    IL_0022:  dup
    IL_0023:  ldc.i4.3
    IL_0024:  ldc.i4.3
    IL_0025:  newarr     Point
    IL_002a:  stelem.ref
    IL_002b:  stloc.0
    IL_002c:  ret
  } // end of method ArrayTest::Main

The main difference between this and the release mode code is the additional nop instruction.

Here is the output for the 2012/2013 version of the compiler:

  .method public hidebysig static void  Main() cil managed
  {
    .entrypoint
    // Code size       307 (0x133)
    .maxstack  4
    .locals init (valuetype Point[][] V_0,
             valuetype Point[][] V_1,
             valuetype Point[] V_2,
             valuetype Point V_3)
    IL_0000:  nop
    IL_0001:  ldc.i4.4
    IL_0002:  newarr     valuetype Point[]
    IL_0007:  stloc.1
    IL_0008:  ldloc.1
    IL_0009:  ldc.i4.0
    IL_000a:  ldc.i4.3
    IL_000b:  newarr     Point
    IL_0010:  stloc.2
    IL_0011:  ldloc.2
    IL_0012:  ldc.i4.0
    IL_0013:  ldelema    Point
    IL_0018:  ldloca.s   V_3
    IL_001a:  initobj    Point
    IL_0020:  ldloc.3
    IL_0021:  stobj      Point
    IL_0026:  ldloc.2
    IL_0027:  ldc.i4.1
    IL_0028:  ldelema    Point
    IL_002d:  ldloca.s   V_3
    IL_002f:  initobj    Point
    IL_0035:  ldloc.3
    IL_0036:  stobj      Point
    IL_003b:  ldloc.2
    IL_003c:  ldc.i4.2
    IL_003d:  ldelema    Point
    IL_0042:  ldloca.s   V_3
    IL_0044:  initobj    Point
    IL_004a:  ldloc.3
    IL_004b:  stobj      Point
    IL_0050:  ldloc.2
    IL_0051:  stelem.ref
    IL_0052:  ldloc.1
    IL_0053:  ldc.i4.1
    IL_0054:  ldc.i4.3
    IL_0055:  newarr     Point
    IL_005a:  stloc.2
    IL_005b:  ldloc.2
    IL_005c:  ldc.i4.0
    IL_005d:  ldelema    Point
    IL_0062:  ldloca.s   V_3
    IL_0064:  initobj    Point
    IL_006a:  ldloc.3
    IL_006b:  stobj      Point
    IL_0070:  ldloc.2
    IL_0071:  ldc.i4.1
    IL_0072:  ldelema    Point
    IL_0077:  ldloca.s   V_3
    IL_0079:  initobj    Point
    IL_007f:  ldloc.3
    IL_0080:  stobj      Point
    IL_0085:  ldloc.2
    IL_0086:  ldc.i4.2
    IL_0087:  ldelema    Point
    IL_008c:  ldloca.s   V_3
    IL_008e:  initobj    Point
    IL_0094:  ldloc.3
    IL_0095:  stobj      Point
    IL_009a:  ldloc.2
    IL_009b:  stelem.ref
    IL_009c:  ldloc.1
    IL_009d:  ldc.i4.2
    IL_009e:  ldc.i4.3
    IL_009f:  newarr     Point
    IL_00a4:  stloc.2
    IL_00a5:  ldloc.2
    IL_00a6:  ldc.i4.0
    IL_00a7:  ldelema    Point
    IL_00ac:  ldloca.s   V_3
    IL_00ae:  initobj    Point
    IL_00b4:  ldloc.3
    IL_00b5:  stobj      Point
    IL_00ba:  ldloc.2
    IL_00bb:  ldc.i4.1
    IL_00bc:  ldelema    Point
    IL_00c1:  ldloca.s   V_3
    IL_00c3:  initobj    Point
    IL_00c9:  ldloc.3
    IL_00ca:  stobj      Point
    IL_00cf:  ldloc.2
    IL_00d0:  ldc.i4.2
    IL_00d1:  ldelema    Point
    IL_00d6:  ldloca.s   V_3
    IL_00d8:  initobj    Point
    IL_00de:  ldloc.3
    IL_00df:  stobj      Point
    IL_00e4:  ldloc.2
    IL_00e5:  stelem.ref
    IL_00e6:  ldloc.1
    IL_00e7:  ldc.i4.3
    IL_00e8:  ldc.i4.3
    IL_00e9:  newarr     Point
    IL_00ee:  stloc.2
    IL_00ef:  ldloc.2
    IL_00f0:  ldc.i4.0
    IL_00f1:  ldelema    Point
    IL_00f6:  ldloca.s   V_3
    IL_00f8:  initobj    Point
    IL_00fe:  ldloc.3
    IL_00ff:  stobj      Point
    IL_0104:  ldloc.2
    IL_0105:  ldc.i4.1
    IL_0106:  ldelema    Point
    IL_010b:  ldloca.s   V_3
    IL_010d:  initobj    Point
    IL_0113:  ldloc.3
    IL_0114:  stobj      Point
    IL_0119:  ldloc.2
    IL_011a:  ldc.i4.2
    IL_011b:  ldelema    Point
    IL_0120:  ldloca.s   V_3
    IL_0122:  initobj    Point
    IL_0128:  ldloc.3
    IL_0129:  stobj      Point
    IL_012e:  ldloc.2
    IL_012f:  stelem.ref
    IL_0130:  ldloc.1
    IL_0131:  stloc.0
    IL_0132:  ret
  } // end of method ArrayTest::Main

So, in the 2012/2013 compiler you're using, debug mode is doing a very large number of stack allocations, likely so that you can intellisense the entire jagged array structure during edit and continue, or possibly so that you might step into each individual object construction. I'm not sure about this at all.

I am no expert on IL, but it appears to me that it's allocating for each Point, then again for each Array, then again for the jagged array, leading to way too many allocations.