Thursday, August 21, 2008 8:05 PM bart

How C# Array Initializers Work

Everyone knows array initializers; they’ve been part of the language since the very beginning. But do you know how this innocent looking construct really works?

var ints = new [] { 1, 2, 3 };

Before we continue, I should point out that the above sample uses a couple of C# 3.0 specific features, namely local variable type inference (var keyword) and implicitly typed arrays (new []). It’s exactly the same as:

int[] ints = new int[3] { 1, 2, 3 };

And actually you could also write:

int[] ints = { 1, 2, 3 };

You might expect the above to work just like:

int[] ints = new int[3];
ints[0] = 1;
ints[1] = 2;
ints[2] = 3;

Unfortunately, that’s not completely right. There’s a hidden subtlety that I’ll point out further on. Let’s put on our “IL freak” T-shirt and dive into the implementation details right now. Here’s what the translation of the original (and by equivalence the second and third, but not the fourth) code fragment results into:

image

Holy cow! What’s up with this <PrivateImplementationDetails>mumblemumble thing? Before I can reveal this, let’s take a look at Q::Main, where I’ve interleaved the stack state after every relevant line (left = top of stack):

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       20 (0x14)
  .maxstack  3
  .locals init (int32[] V_0)
  IL_0000:  nop
  // {}
  IL_0001:  ldc.i4.3
  // {3}
  IL_0002:  newarr     [mscorlib]System.Int32
  // {&int[3]}
  IL_0007:  dup
  // {&int[3], &int[3]}
  IL_0008:  ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
  // {&int[3], &int[3], #'$$method0x6000001-1'}
  IL_000d:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                                      valuetype [mscorlib]System.RuntimeFieldHandle)
  // {&int[3]}
  IL_0012:  stloc.0
  // {}
  IL_0013:  ret
} // end of method Q::Main

Let’s do a line-by-line analysis. On lines IL_0001 and IL_0002 we create a new array with element type System.Int32 and dimension 3. IL_0007 is a bit more surprising: the reference to the array is duplicated on the evaluation stack. Why? Blindly assume for a second that IL_0008 and IL_000d are two lines that initialize the array (we’ll come back to that in just a second). Now look one line further to IL_0012, where the value on top of the stack – again the array – is assigned to local variable with index 0, i.e. our “ints” variable. What would happen if we’d assign the array to the local variable already in line IL_0007, like this?

ldc.i4.3
newarr     [mscorlib]System.Int32
stloc.0
ldloc.0

ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                          valuetype [mscorlib]System.RuntimeFieldHandle)

Well, the assignment wouldn’t be atomic anymore: from that point on, an external observer watching the local variable would already be able to see the array but in a incompletely initialized state, i.e. the elements wouldn’t be there yet. And that initialization is precisely what IL_0008 and IL_000d are doing. So, the compiled code is not equivalent to:

int[] ints = new int[3];
ints[0] = 1;
ints[1] = 2;
ints[2] = 3;

It’s more accurate to say it’s semantically equivalent to:

int[] t = new int[3];
t[0] = 1;
t[1] = 2;
t[2] = 3;
int[] ints = t;

Although the implementation avoids the creation of two local variables as we can see in the IL code. This leaves us with two dark matter lines:

  IL_0008:  ldtoken    field valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'::'$$method0x6000001-1'
  IL_000d:  call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                                      valuetype [mscorlib]System.RuntimeFieldHandle)

No fears, this isn’t too hard either. Essentially we’re seeing a call to RuntimeHelpers.InitializeArray passing in our array (which is on the top of the stack after executing IL_0007) and a RuntimeFieldHandle, which is the representation of a “field” pointer referenced through an IL token which is loaded in IL_0008. That token corresponds to the line highlighted below:

image

Actually the indicated line a static field in some private class with an unspeakable, obviously compiler-generated, name. There are a few important things to notice here. First, this private class has a nested class called __StaticArrayInitTypeSize=12. This class represents any array with total native byte size (i.e. the sum of the sizes of all elements) of 12 bytes. How we come to 12 bytes is trivial: an Int32 is 32-bits, or 4 bytes, and we have three of those, hence 12 bytes. Notice this class extends System.ValueType. I guess the readers are familiar with the implications of value types with respect to stack allocation, so let’s not go there. How does the type actually get its 12 bytes? Just putting somewhere in the name isn’t enough for the CLR obviously, so if you take a look at the implementation (using ildasm.exe q.exe /out=q.il, opening the generated q.il file) you’d see:

.class private auto ansi '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'
       extends [mscorlib]System.Object
{
  .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 )
  .class explicit ansi sealed nested private '__StaticArrayInitTypeSize=12'
         extends [mscorlib]System.ValueType
  {
    .pack 1
    .size 12
  } // end of class '__StaticArrayInitTypeSize=12'

  .field static assembly valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '$$method0x6000001-1' at I_00002050
} // end of class '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'

The .size directive instructs the CLR that a memory block of the specified size (in bytes) should be allocated upon creation of an instance of the type. If you’re curious about the .pack directive, this one specifies that the fields within the class should be placed at addresses that are a multiple of the specified value (only powers of 2 up to 128 are supported). This is used primarily for COM interop to match up unmanaged data type layouts.

On to the field now:

.field static assembly valuetype '<PrivateImplementationDetails>{8C802ECE-B24C-4A20-AE34-9303FE2DD066}'/'__StaticArrayInitTypeSize=12' '$$method0x6000001-1' at I_00002050

Its type is straightforward, albeit a quite long name due to the nesting of classes (notice the separator for nested classes is /). The name is indicated in green but more interesting is the “at” part indicated in red. This is a reference to a so-called data label which is basically a pointer into the PE file itself. In the ILDASM output you’ll see the following:

.data cil I_00002050 = bytearray (
                 01 00 00 00 02 00 00 00 03 00 00 00)

This is the declaration of the data label and is set to a byte array with values (in little-endian) 01000000, 02000000 and 03000000 – or in readable terms: 1, 2 and 3. Now we should understand how the call to InitailizeArray works:

call       void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array,
                                                                                          valuetype [mscorlib]System.RuntimeFieldHandle)

Given the array object, which already has information about the size (we did ldc.i4.3; newarr [mscorlib]System.Int32 before), and a pointer to the field that just wraps the data at the specified ‘at’ offset, the runtime is capable of loading the calculated amount of bytes (3 x 4 = 12) from the specified location, resulting in an initialized array. I told you it was easy, or didn’t I? Actually for the real geeks, where does I_00002050 come from? It’s the so-called RVA or Relative Virtual Address, that is the relative offset to the start of the PE file. Using dumpbin we can dump the executable PE file (dumpbin /all q.exe) which shows this (click the image to admit you’re a geek):

image

A few more interesting things. The compiler reuses the __StaticArrayInitTypeSize class for all arrays that have the same size. So, writing the following:

int[]  ints  = { 1, 2, 3, 4, 5, 6, 7, 8 };
long[] longs = { 1, 2, 3, 4 };
byte[] bytes = { 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 };

causes the same type to be used since all of the types are 32 bytes:

.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-1' at I_00002050
.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-2' at I_00002070
.field static assembly valuetype '<PrivateImplementationDetails>{AA6C9D77-5FAD-47E0-8B55-1D8739074F1F}'/'__StaticArrayInitTypeSize=32' '$$method0x6000001-3' at I_00002090

.data cil I_00002050 = bytearray (
                 01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00
                 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00)
.data cil I_00002070 = bytearray (
                 01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00
                 03 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00)
.data cil I_00002090 = bytearray (
                 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10
                 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20)

Furthermore, for arrays with only 1 or 2 elements, a shortcut is taken:

int[] ints = { 1, 2 };

produces the following IL:

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       19 (0x13)
  .maxstack  3
  .locals init (int32[] V_0,
           int32[] V_1)
  IL_0000:  nop
  IL_0001:  ldc.i4.2
  IL_0002:  newarr     [mscorlib]System.Int32
  IL_0007:  stloc.1

  //
  // V_1[0] = 1
  //
  IL_0008:  ldloc.1
  IL_0009:  ldc.i4.0
  IL_000a:  ldc.i4.1
  IL_000b:  stelem.i4

  //
  // V_1[1] = 2
  //
  IL_000c:  ldloc.1
  IL_000d:  ldc.i4.1
  IL_000e:  ldc.i4.2
  IL_000f:  stelem.i4

  //
  // V_0 = V_1
  //

  IL_0010:  ldloc.1
  IL_0011:  stloc.0

  IL_0012:  ret
} // end of method Q::Main

Here the trick of two local variables is used, one (V_1) acting as a temporary variable for the “array under construction”, and another one (V_0) for the final destination variable (ints).

Finally, why was this implementation method (referring to the InitializeArray approach) chosen over a repetitive sequence of array assignment calls? A variety of reasons. First of all, code size. When using InitializeArray, the cost is constant, while for a naive implementation the cost would be 4 instructions (ldloc the array, ldc the index to be assigned to, ldc the value to be assigned, stelem to do the assignment) per element to be initialized. Secondly, the data to be assigned would be fragmented throughout the expanded code, so we can’t benefit from the fact that the data will be stored sequentially in memory (an array is ultimately just a starting address + an element size). So by trading instructions for data, we can gain a lot. Let’s do some kind of meta-programming to illustrate this:

using System;
using System.Text;

class G
{
    static void Main()
    {
        int N = 10000;

        StringBuilder sb = new StringBuilder();
        sb.AppendLine("using System;");
        sb.AppendLine("using System.Diagnostics;");
        sb.AppendLine("");
        sb.AppendLine("class Program");
        sb.AppendLine("{");
        sb.AppendLine("    static void Main()");
        sb.AppendLine("    {");
        sb.AppendLine("        Stopwatch watch = new Stopwatch();");
        sb.AppendLine("        watch.Start();");
        sb.Append    ("        var ints1 = new int[] { "); for (int i = 0; i < N; i++) sb.Append(i + ", "); sb.AppendLine(" };");
        sb.AppendLine("        watch.Stop();");
        sb.AppendLine("        Console.WriteLine(watch.Elapsed);");
        sb.AppendLine("");
        sb.AppendLine("        watch.Reset();");
        sb.AppendLine("        watch.Start();");
        sb.AppendLine("        var ints2_t = new int[" + N + "];");
        for (int i = 0; i < N; i++)
        sb.AppendLine("        ints2_t[" + i + "] = " + i + ";");
        sb.AppendLine("        var ints2 = ints2_t;")
        sb.AppendLine("        watch.Stop();");
        sb.AppendLine("        Console.WriteLine(watch.Elapsed);");
        sb.AppendLine("    }");
        sb.AppendLine("}");

        Console.WriteLine(sb);
    }
}

This generates code like this:

using System;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        Stopwatch watch = new Stopwatch();
        watch.Start();
        var ints1 = new int[] { 0, 1, …, N };
        Console.WriteLine(watch.Elapsed); 

        watch.Reset();
        watch.Start();
        var ints2_t = new int[N];
        ints2_t[0] = 0;
        ints2_t[1] = 1;
        …
        ints2_t[N] = N;
        var ints2 = ints2_t;
        watch.Stop();
        Console.WriteLine(watch.Elapsed);
    }
}

Compiling and executing the resulting program for N=10000 shows:

00:00:00.0000861
00:00:00.0004129

As you can see, the difference is substantial. Hope this post helps to eliminate some compiler obscurity!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# Reflective Perspective - Chris Alcock &raquo; The Morning Brew #164

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #164

# Dew Drop - August 22, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - August 22, 2008 | Alvin Ashcraft's Morning Dew

# Interesting Finds: 2008.08.22~2008.08.26

Monday, August 25, 2008 8:07 PM by gOODiDEA

DebugDebuggingSilverlightapplicationswithwindbgandsos.dllWebJavaScriptMemoryLeakDetec...

# Interesting Finds: 2008.08.22~2008.08.26

Monday, August 25, 2008 8:07 PM by gOODiDEA.NET

Debug Debugging Silverlight applications with windbg and sos.dll Web JavaScript Memory Leak Detector

# geeks com

Tuesday, September 09, 2008 4:48 PM by geeks com

Pingback from  geeks com

# ?????????PrivateImplementationDetails | Think Louder - ?????????

Pingback from  ?????????PrivateImplementationDetails | Think Louder - ?????????

# Recent Links Tagged With "array" - JabberTags

Friday, February 27, 2009 3:34 PM by Recent Links Tagged With "array" - JabberTags

Pingback from  Recent Links Tagged With "array" - JabberTags

# Ciekawostki | Wiadomo??ci o technologiach IT

Monday, February 07, 2011 9:30 PM by Ciekawostki | Wiadomo??ci o technologiach IT

Pingback from  Ciekawostki | Wiadomo??ci o technologiach IT

# How do I discern whether a Type is a static array initializer? - Programmers Goodies

Pingback from  How do I discern whether a Type is a static array initializer? - Programmers Goodies

# Tips For All

Monday, February 27, 2012 7:36 AM by Tips For All

Pingback from  Tips For All