28

Sometimes I need a hardcoded lookup table for a single method.

I can create such an array either

  • locally in the method itself
  • static inside the class

Example for the first case:

public int Convert(int i) { int[] lookup = new[] {1, 2, 4, 8, 16, 32, 666, /*...*/ }; return lookup[i]; }

As far as I understand it, a new lookup array will be created by the .net engine each time this method is executed. Is this correct, or is the JITer smart enough to cache and reuse the array between calls?

I presume that the answer is no, so if I want to make sure that the array is cached between calls, one way would be to make it static:

Example for the second case:

private static readonly int[] lookup = new[] { 1, 2, 4, 8, 16, 32, 666, /*...*/ }; public int Convert(int i) { return lookup[i]; }

Is there a way to do this without polluting the namespace of my class? Can I somehow declare a static array that is only visible inside the current scope?

Improve this question
4
  • I dont think jit will cache or anything for the local methods. define it as class level static and be safe specially for huge LUTs Commented Aug 23, 2016 at 16:14
  • If you don't want to pollute the class you could introduce a static Lookup class and move the arrays there. Commented Aug 23, 2016 at 16:19
  • Maybe use a Closure of some kind? Commented Aug 23, 2016 at 16:22
  • 1
    I'm not going to try to outdo AndreyAkinshin's awesome answer. But have a look into stackalloc, that might be what you need. msdn.microsoft.com/en-us/library/cx9s2sy4.aspx Commented Aug 23, 2016 at 23:52

1 Answer 1

Reset to default
56

Local array

The Roslyn compiler puts local arrays in the metadata. Let's take the first version of your Convert method:

public int Convert(int i) { int[] lookup = new[] {1, 2, 4, 8, 16, 32, 666, /*...*/ }; return lookup[i]; }

Here is the corresponded IL code (Release build, Roslyn 1.3.1.60616):

// Token: 0x06000002 RID: 2 RVA: 0x0000206C File Offset: 0x0000026C .method public hidebysig instance int32 Convert ( int32 i ) cil managed noinlining { // Header Size: 1 byte // Code Size: 20 (0x14) bytes .maxstack 8 /* 0x0000026D 1D */ IL_0000: ldc.i4.7 /* 0x0000026E 8D13000001 */ IL_0001: newarr [mscorlib]System.Int32 /* 0x00000273 25 */ IL_0006: dup /* 0x00000274 D001000004 */ IL_0007: ldtoken field valuetype '<PrivateImplementationDetails>'/'__StaticArrayInitTypeSize=28' '<PrivateImplementationDetails>'::'502D7419C3650DEE94B5938147BC9B4724D37F99' /* 0x00000279 281000000A */ IL_000C: call void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array, valuetype [mscorlib]System.RuntimeFieldHandle) /* 0x0000027E 03 */ IL_0011: ldarg.1 /* 0x0000027F 94 */ IL_0012: ldelem.i4 /* 0x00000280 2A */ IL_0013: ret } // end of method Program::Convert

And here is the PrivateImplementationDetails:

// Token: 0x02000003 RID: 3 .class private auto ansi sealed '<PrivateImplementationDetails>' extends [mscorlib]System.Object { .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 ) // Nested Types // Token: 0x02000004 RID: 4 .class nested private explicit ansi sealed '__StaticArrayInitTypeSize=28' extends [mscorlib]System.ValueType { .pack 1 .size 28 } // end of class __StaticArrayInitTypeSize=28 // Fields // Token: 0x04000001 RID: 1 RVA: 0x00002944 File Offset: 0x00000B44 .field assembly static initonly valuetype '<PrivateImplementationDetails>'/'__StaticArrayInitTypeSize=28' '502D7419C3650DEE94B5938147BC9B4724D37F99' at I_00002944 // 28 (0x001c) bytes } // end of class <PrivateImplementationDetails>

As you can see, your lookup array is in the assembly metadata. When you start your application, JIT only has to get the array content from the metadata. An asm example (Windows 10, .NET Framework 4.6.1 (4.0.30319.42000), RyuJIT: clrjit-v4.6.1080.0, Release build):

 int[] lookup = new[] { 1, 2, 4, 8, 16, 32, 666, /*...*/ }; 00007FFEDF0A44E2 sub esp,20h 00007FFEDF0A44E5 mov esi,edx 00007FFEDF0A44E7 mov rcx,7FFF3D1C4C62h 00007FFEDF0A44F1 mov edx,7 00007FFEDF0A44F6 call 00007FFF3E6B2600 00007FFEDF0A44FB mov rdx,134CF7F2944h 00007FFEDF0A4505 mov ecx,dword ptr [rax+8] 00007FFEDF0A4508 lea r8,[rax+10h] 00007FFEDF0A450C vmovdqu xmm0,xmmword ptr [rdx] 00007FFEDF0A4511 vmovdqu xmmword ptr [r8],xmm0 00007FFEDF0A4516 mov r9,qword ptr [rdx+10h] 00007FFEDF0A451A mov qword ptr [r8+10h],r9 00007FFEDF0A451E mov r9d,dword ptr [rdx+18h] 00007FFEDF0A4522 mov dword ptr [r8+18h],r9d return lookup[i]; 00007FFEDF0A4526 cmp esi,ecx return lookup[i]; 00007FFEDF0A4528 jae 00007FFEDF0A4537 00007FFEDF0A452A movsxd rdx,esi 00007FFEDF0A452D mov eax,dword ptr [rax+rdx*4+10h] 00007FFEDF0A4531 add rsp,20h 00007FFEDF0A4535 pop rsi 00007FFEDF0A4536 ret 00007FFEDF0A4537 call 00007FFF3EB57BE0 00007FFEDF0A453C int 3

A LegacyJIT-x64 version:

 int[] lookup = new[] { 1, 2, 4, 8, 16, 32, 666, /*...*/ }; 00007FFEDF0E41E0 push rbx 00007FFEDF0E41E1 push rdi 00007FFEDF0E41E2 sub rsp,28h 00007FFEDF0E41E6 mov ebx,edx 00007FFEDF0E41E8 mov edx,7 00007FFEDF0E41ED lea rcx,[7FFF3D1C4C62h] 00007FFEDF0E41F4 call 00007FFF3E6B2600 00007FFEDF0E41F9 mov rdi,rax 00007FFEDF0E41FC lea rcx,[7FFEDF124760h] 00007FFEDF0E4203 call 00007FFF3E73CA90 00007FFEDF0E4208 mov rdx,rax 00007FFEDF0E420B mov rcx,rdi 00007FFEDF0E420E call 00007FFF3E73C8B0 return lookup[i]; 00007FFEDF0E4213 movsxd r11,ebx 00007FFEDF0E4216 mov rax,qword ptr [rdi+8] 00007FFEDF0E421A cmp r11,7 00007FFEDF0E421E jae 00007FFEDF0E4230 00007FFEDF0E4220 mov eax,dword ptr [rdi+r11*4+10h] 00007FFEDF0E4225 add rsp,28h 00007FFEDF0E4229 pop rdi 00007FFEDF0E422A pop rbx 00007FFEDF0E422B ret 00007FFEDF0E422C nop dword ptr [rax] 00007FFEDF0E4230 call 00007FFF3EB57BE0 00007FFEDF0E4235 nop

A LegacyJIT-x86 version:

 int[] lookup = new[] { 1, 2, 4, 8, 16, 32, 666, /*...*/ }; 009A2DC4 push esi 009A2DC5 push ebx 009A2DC6 mov ebx,edx 009A2DC8 mov ecx,6A2C402Eh 009A2DCD mov edx,7 009A2DD2 call 0094322C 009A2DD7 lea edi,[eax+8] 009A2DDA mov esi,5082944h 009A2DDF mov ecx,7 009A2DE4 rep movs dword ptr es:[edi],dword ptr [esi] return lookup[i]; 009A2DE6 cmp ebx,dword ptr [eax+4] 009A2DE9 jae 009A2DF4 009A2DEB mov eax,dword ptr [eax+ebx*4+8] 009A2DEF pop ebx 009A2DF0 pop esi 009A2DF1 pop edi 009A2DF2 pop ebp 009A2DF3 ret 009A2DF4 call 6B9D52F0 009A2DF9 int 3

Static array

Now, let's compare it with the second version:

private static readonly int[] lookup = new[] { 1, 2, 4, 8, 16, 32, 666, /*...*/ }; public int Convert(int i) { return lookup[i]; }

IL:

// Token: 0x04000001 RID: 1 .field private static initonly int32[] lookup // Token: 0x06000002 RID: 2 RVA: 0x00002056 File Offset: 0x00000256 .method public hidebysig instance int32 Convert ( int32 i ) cil managed noinlining { // Header Size: 1 byte // Code Size: 8 (0x8) bytes .maxstack 8 /* 0x00000257 7E01000004 */ IL_0000: ldsfld int32[] ConsoleApplication5.Program::lookup /* 0x0000025C 03 */ IL_0005: ldarg.1 /* 0x0000025D 94 */ IL_0006: ldelem.i4 /* 0x0000025E 2A */ IL_0007: ret } // end of method Program::Convert // Token: 0x02000003 RID: 3 .class private auto ansi sealed '<PrivateImplementationDetails>' extends [mscorlib]System.Object { .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 ) // Nested Types // Token: 0x02000004 RID: 4 .class nested private explicit ansi sealed '__StaticArrayInitTypeSize=28' extends [mscorlib]System.ValueType { .pack 1 .size 28 } // end of class __StaticArrayInitTypeSize=28 // Fields // Token: 0x04000002 RID: 2 RVA: 0x000028FC File Offset: 0x00000AFC .field assembly static initonly valuetype '<PrivateImplementationDetails>'/'__StaticArrayInitTypeSize=28' '502D7419C3650DEE94B5938147BC9B4724D37F99' at I_000028fc // 28 (0x001c) bytes } // end of class <PrivateImplementationDetails>

ASM (RyuJIT-x64):

 return lookup[i]; 00007FFEDF0B4490 sub rsp,28h 00007FFEDF0B4494 mov rax,212E52E0080h 00007FFEDF0B449E mov rax,qword ptr [rax] 00007FFEDF0B44A1 mov ecx,dword ptr [rax+8] 00007FFEDF0B44A4 cmp edx,ecx 00007FFEDF0B44A6 jae 00007FFEDF0B44B4 00007FFEDF0B44A8 movsxd rdx,edx 00007FFEDF0B44AB mov eax,dword ptr [rax+rdx*4+10h] 00007FFEDF0B44AF add rsp,28h 00007FFEDF0B44B3 ret 00007FFEDF0B44B4 call 00007FFF3EB57BE0 00007FFEDF0B44B9 int 3

ASM (LegacyJIT-x64):

 return lookup[i]; 00007FFEDF0A4611 sub esp,28h 00007FFEDF0A4614 mov rcx,226CC5203F0h 00007FFEDF0A461E mov rcx,qword ptr [rcx] 00007FFEDF0A4621 movsxd r8,edx 00007FFEDF0A4624 mov rax,qword ptr [rcx+8] 00007FFEDF0A4628 cmp r8,rax 00007FFEDF0A462B jae 00007FFEDF0A4637 00007FFEDF0A462D mov eax,dword ptr [rcx+r8*4+10h] 00007FFEDF0A4632 add rsp,28h 00007FFEDF0A4636 ret 00007FFEDF0A4637 call 00007FFF3EB57BE0 00007FFEDF0A463C nop

ASM (LegacyJIT-x86):

 return lookup[i]; 00AA2E18 push ebp 00AA2E19 mov ebp,esp 00AA2E1B mov eax,dword ptr ds:[03628854h] 00AA2E20 cmp edx,dword ptr [eax+4] 00AA2E23 jae 00AA2E2B 00AA2E25 mov eax,dword ptr [eax+edx*4+8] 00AA2E29 pop ebp 00AA2E2A ret 00AA2E2B call 6B9D52F0 00AA2E30 int 3

Benchmarks

Let's write a benchmark with help of BenchmarkDotNet

[Config(typeof(Config)), LegacyJitX86Job, LegacyJitX64Job, RyuJitX64Job, RPlotExporter] public class ArrayBenchmarks { private static readonly int[] lookup = new[] {1, 2, 4, 8, 16, 32, 666, /*...*/}; [MethodImpl(MethodImplOptions.NoInlining)] public int ConvertStatic(int i) { return lookup[i]; } [MethodImpl(MethodImplOptions.NoInlining)] public int ConvertLocal(int i) { int[] localLookup = new[] {1, 2, 4, 8, 16, 32, 666, /*...*/}; return localLookup[i]; } [Benchmark] public int Static() { int sum = 0; for (int i = 0; i < 10001; i++) sum += ConvertStatic(0); return sum; } [Benchmark] public int Local() { int sum = 0; for (int i = 0; i < 10001; i++) sum += ConvertLocal(0); return sum; } private class Config : ManualConfig { public Config() { Add(new MemoryDiagnoser()); Add(MarkdownExporter.StackOverflow); } } }

Note that it's a synthetic toy benchmark which uses NoInlining for the Convert methods. We use it to show the difference between two methods. The real performance will depend on how you are using the Convert method in your code. My results:

Host Process Environment Information: BenchmarkDotNet.Core=v0.9.9.0 OS=Microsoft Windows NT 6.2.9200.0 Processor=Intel(R) Core(TM) i7-4702MQ CPU 2.20GHz, ProcessorCount=8 Frequency=2143474 ticks, Resolution=466.5324 ns, Timer=TSC CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT] GC=Concurrent Workstation JitModules=clrjit-v4.6.1586.0 Type=ArrayBenchmarks Mode=Throughput Method | Platform | Jit | Median | StdDev | Gen 0 | Gen 1 | Gen 2 | Bytes Allocated/Op | ------- |--------- |---------- |-------------- |----------- |--------- |------ |------ |------------------- | Static | X64 | LegacyJit | 24.0243 us | 0.1590 us | - | - | - | 1.07 | Local | X64 | LegacyJit | 2,068.1034 us | 33.7142 us | 1,089.00 | - | - | 436,603.02 | Static | X64 | RyuJit | 20.7906 us | 0.2018 us | - | - | - | 1.06 | Local | X64 | RyuJit | 83.4041 us | 0.9993 us | 613.55 | - | - | 244,936.53 | Static | X86 | LegacyJit | 20.9957 us | 0.2267 us | - | - | - | 1.01 | Local | X86 | LegacyJit | 167.6257 us | 1.3543 us | 431.43 | - | - | 172,121.77 |

enter image description here

Conclusion

  • Does .NET cache hardcoded local arrays? Kind of: the Roslyn compiler put it in the metadata.
  • Do we have any overhead in this case? Unfortunately, yes: JIT will copy the array content from the metadata for each invocation; it will work longer than the case with a static array. Runtime also allocates objects and produce memory traffic.
  • Should we care about it? It depends. If it's a hot method and you want to achieve a good level of performance, you should use a static array. If it's a cold method which doesn't affect the application performance, you probably should write “good” source code and put the array in the method scope.
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

That's really release mode with "suppress optimizations" unchecked? E: also fwiw, it shows that it is copying the entire array just to index into it and immediately throw it away, the x86 version at least, I'm not even sure what the x64 version is trying to do.
@harold, yes, it's the release mode with "suppress optimizations" unchecked: imgur.com/a/sfmc8
Very well, so this is valid, I can't help but be a bit disappointed though
@harold, I also added x86-version, benchmark, and conclusion, see my updates.
The local array is created each time as it could be modified (as could the static array) - so really you are asking does the jit analyse the function and determine that its not modified therefore can be made static.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.