Iterating with ForEach over ImmutableArray is slower than over Array

[hnrqbaggio]

This is a spin off issue from https://github.com/dotnet/corefx/issues/36416, to scope down to just the ImmutableArray case.

As mentioned in other issues, the immutability sometimes comes with trade-offs in some operations, but in this case it seems that the extra overhead can be optimized, at least for when it's a collection of value type.

Comparing with Array

Looking at the ASM code generated, the Array version is high inlined, while for the ImmutableArray the JIT is able to inline the loop itself, but not the call to ImmutableArray<T>.GetEnumerator(). The method itself is quite simple, but calls to an internal method called ThrowNullRefIfNotInitialized() to validate that the underlying array is not null.

It seems that the extra method causes the collection to have more branch mis-predictions and cache misses than the array case (the cache misses show up in the results when the collection is larger, say 2048 instead of the default 512 elements).

Possible fix

If we change the implementation of GetEnumerator to use MethodImplOptions.AggressiveInlining, the JIT is able to inline the call and the stats of both benchmarks match and the Median for the Int32 case improves by 4x.

No Slower results for the provided threshold = 3% and noise filter = 0.3ns.

Faster	base/diff	Base Median (ns)	Diff Median (ns)	Modality
IterateForEach.ImmutableArray(Size: 512)	4.07	1110.44	273.14	several?

Unfortunately, this seems to not be enough for the Reference Type case. When the benchmark runs using String instead of Int32 the results are still the same as before, so it seems that marking the methods as inline is still not sufficient for the JIT to optimize them.

Correctness

The code in ThrowNullRefIfNotInitialized is just accessing the underlying Array.Length property and relying on that to throw if the object is null.

In the optimized version, I can't see the exact same instructions, so would still need to confirm that the optimizer is not discarding that check. However, the tests that validate that GetEnumerator will throw NRE in that condition did pass.

I have the changes above in my fork of the repo, but this is my first contribution so would like to check the feedback on the findings and not send a PR right away. 😁

Baseline

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-8650U CPU 1.90GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
  [Host]     : .NET Framework 4.8 (4.8.4075.0), X64 RyuJIT
  Job-RUPWLA : .NET Core 5.0.0 (CoreCLR 5.0.19.61001, CoreFX 5.0.19.61001), X64 RyuJIT

PowerPlanMode=00000000-0000-0000-0000-000000000000  Toolchain=CoreRun  IterationTime=250.0000 ms  
MaxIterationCount=20  MinIterationCount=15  WarmupCount=1  

Type	Method	Size	Mean	Error	StdDev	Median	Min	Max	Gen 0	Gen 1	Gen 2	Allocated	BranchInstructions/Op	CacheMisses/Op	BranchMispredictions/Op
IterateForEach<Int32>	Array	512	173.4 ns	18.47 ns	21.28 ns	177.2 ns	145.1 ns	199.3 ns	-	-	-	-	212	0	1
IterateForEach<String>	Array	512	157.5 ns	15.91 ns	18.32 ns	169.4 ns	131.8 ns	179.9 ns	-	-	-	-	205	0	1
IterateForEach<Int32>	ImmutableArray	512	1,083.9 ns	38.67 ns	44.53 ns	1,110.4 ns	997.1 ns	1,115.4 ns	-	-	-	-	415	0	2
IterateForEach<String>	ImmutableArray	512	1,101.5 ns	38.80 ns	44.69 ns	1,115.3 ns	1,010.2 ns	1,175.2 ns	-	-	-	-	462	0	2

Array

; System.Collections.IterateForEach`1[[System.Int32, System.Private.CoreLib]].Array()
       xor     eax,eax
       mov     rdx,qword ptr [rcx+8]
       xor     ecx,ecx
       mov     r8d,dword ptr [rdx+8]
       test    r8d,r8d
       jle     M00_L01
M00_L00:
       movsxd  rax,ecx
       mov     eax,dword ptr [rdx+rax*4+10h]
       inc     ecx
       cmp     r8d,ecx
       jg      M00_L00
M00_L01:
       ret
       sbb     dword ptr [rax],eax
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax-76h],dh
       rcr     dword ptr [rdx-6],cl
       jg      M00_L02
M00_L02:
       add     byte ptr [rbp+48h],dl
       mov     ebp,esp
       mov     qword ptr [rbp+10h],rcx
       mov     rax,qword ptr [rbp+10h]
       mov     rax,qword ptr [rax+58h]
; Total bytes of code 64

ImmutableArray

; System.Collections.IterateForEach`1[[System.Int32, System.Private.CoreLib]].ImmutableArray()
       push    rsi
       sub     rsp,40h
       xor     eax,eax
       mov     qword ptr [rsp+38h],rax
       mov     qword ptr [rsp+28h],rax
       mov     qword ptr [rsp+30h],rax
       xor     esi,esi
       mov     rcx,qword ptr [rcx+0C0h]
       mov     qword ptr [rsp+38h],rcx
       lea     rcx,[rsp+38h]
       lea     rdx,[rsp+28h]
       call    System.Collections.Immutable.ImmutableArray`1[[System.Int32, System.Private.CoreLib]].GetEnumerator()
       jmp     M00_L01
M00_L00:
       cmp     dword ptr [rsp+30h],edx
       jae     M00_L02
       mov     rax,qword ptr [rsp+28h]
       mov     edx,dword ptr [rsp+30h]
       movsxd  rdx,edx
       mov     esi,dword ptr [rax+rdx*4+10h]
M00_L01:
       mov     eax,dword ptr [rsp+30h]
       inc     eax
       mov     dword ptr [rsp+30h],eax
       mov     rdx,qword ptr [rsp+28h]
       mov     edx,dword ptr [rdx+8]
       cmp     edx,eax
       jg      M00_L00
       mov     eax,esi
       add     rsp,40h
       pop     rsi
       ret
M00_L02:
       call    CoreCLR!JIT_RngChkFail
       int     3
       add     byte ptr [rcx],bl
       add     eax,72050002h
       add     dword ptr [rax+40h],esp
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax-26h],ah
; Total bytes of code 138

; System.Collections.Immutable.ImmutableArray`1[[System.Int32, System.Private.CoreLib]].GetEnumerator()
       push    rbp
       push    rdi
       push    rsi
       sub     rsp,40h
       vzeroupper
       lea     rbp,[rsp+50h]
       xor     eax,eax
       mov     qword ptr [rbp-18h],rax
       mov     qword ptr [rbp-28h],rax
       mov     qword ptr [rbp+10h],rcx
       mov     qword ptr [rbp+18h],rdx
       mov     rcx,qword ptr [rbp+10h]
       mov     rcx,qword ptr [rcx]
       mov     qword ptr [rbp-18h],rcx
       lea     rcx,[rbp-18h]
       call    System.Collections.Immutable.ImmutableArray`1[[System.Int32, System.Private.CoreLib]].ThrowNullRefIfNotInitialized()
       vxorps  xmm0,xmm0,xmm0
       vmovdqu xmmword ptr [rbp-28h],xmm0
       lea     rcx,[rbp-28h]
       mov     rdx,qword ptr [rbp-18h]
       call    System.Collections.Immutable.ImmutableArray`1+Enumerator[[System.Int32, System.Private.CoreLib]]..ctor(Int32[])
       mov     rdi,qword ptr [rbp+18h]
       lea     rsi,[rbp-28h]
       call    CoreCLR!JIT_ByRefWriteBarrier
       movs    qword ptr [rdi],qword ptr [rsi]
       mov     rax,qword ptr [rbp+18h]
       lea     rsp,[rbp-10h]
       pop     rsi
       pop     rdi
       pop     rbp
       ret
       int     3
       int     3
       sbb     dword ptr [rdi],eax
       add     al,0
       ???
       jb      00007ffa`5ad52c12
       ???
       add     dh,byte ptr [rax+1]
       push    rax
       add     byte ptr [rax],al
       add     al,cl
       fcmovbe st,st(4)
       pop     rdx
       cli
       jg      00007ffa`5ad52c1f
; Total bytes of code 127

; System.Collections.Immutable.ImmutableArray`1[[System.Int32, System.Private.CoreLib]].ThrowNullRefIfNotInitialized()
       push    rbp
       mov     rbp,rsp
       mov     qword ptr [rbp+10h],rcx
       mov     rax,qword ptr [rbp+10h]
       mov     rax,qword ptr [rax]
       mov     eax,dword ptr [rax+8]
       pop     rbp
       ret
       sbb     dword ptr [rcx],eax
       add     dword ptr [rax],eax
       add     dword ptr [rax],edx
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       and     bl,bl
       ???
       pop     rdx
       cli
       jg      M02_L00
M02_L00:
       add     byte ptr [rbp+48h],dl
; Total bytes of code 50

With Aggressive Inlining

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-8650U CPU 1.90GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
  [Host]     : .NET Framework 4.8 (4.8.4075.0), X64 RyuJIT
  Job-RUPWLA : .NET Core 5.0.0 (CoreCLR 5.0.19.61001, CoreFX 5.0.19.61001), X64 RyuJIT

PowerPlanMode=00000000-0000-0000-0000-000000000000  Toolchain=CoreRun  IterationTime=250.0000 ms  
MaxIterationCount=20  MinIterationCount=15  WarmupCount=1  

Type	Method	Size	Mean	Error	StdDev	Median	Min	Max	Gen 0	Gen 1	Gen 2	Allocated	BranchInstructions/Op	CacheMisses/Op	BranchMispredictions/Op
IterateForEach<Int32>	Array	512	156.5 ns	6.94 ns	7.71 ns	154.1 ns	148.4 ns	173.3 ns	-	-	-	-	223	0	1
IterateForEach<String>	Array	512	140.1 ns	4.23 ns	4.87 ns	138.7 ns	131.3 ns	148.8 ns	-	-	-	-	226	0	1
IterateForEach<Int32>	ImmutableArray	512	271.6 ns	24.17 ns	27.84 ns	273.1 ns	233.7 ns	301.4 ns	-	-	-	-	424	0	2
IterateForEach<String>	ImmutableArray	512	1,125.9 ns	107.31 ns	123.58 ns	1,071.1 ns	997.4 ns	1,293.6 ns	-	-	-	-	434	0	2

Array

; System.Collections.IterateForEach`1[[System.Int32, System.Private.CoreLib]].Array()
       xor     eax,eax
       mov     rdx,qword ptr [rcx+8]
       xor     ecx,ecx
       mov     r8d,dword ptr [rdx+8]
       test    r8d,r8d
       jle     M00_L01
M00_L00:
       movsxd  rax,ecx
       mov     eax,dword ptr [rdx+rax*4+10h]
       inc     ecx
       cmp     r8d,ecx
       jg      M00_L00
M00_L01:
       ret
       sbb     dword ptr [rax],eax
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax-76h],dh
       fistp   word ptr [rcx-6]
       jg      M00_L02
M00_L02:
       add     byte ptr [rbp+48h],dl
       mov     ebp,esp
       mov     qword ptr [rbp+10h],rcx
       mov     rax,qword ptr [rbp+10h]
       mov     rax,qword ptr [rax+58h]
; Total bytes of code 64

ImmutableArray

; System.Collections.IterateForEach`1[[System.Int32, System.Private.CoreLib]].ImmutableArray()
       sub     rsp,28h
       xor     eax,eax
       mov     rdx,qword ptr [rcx+0C0h]
       mov     ecx,dword ptr [rdx+8]
       mov     r8d,0FFFFFFFFh
       jmp     M00_L01
M00_L00:
       cmp     r8d,ecx
       jae     M00_L02
       movsxd  rax,r8d
       mov     eax,dword ptr [rdx+rax*4+10h]
M00_L01:
       inc     r8d
       cmp     ecx,r8d
       jg      M00_L00
       add     rsp,28h
       ret
M00_L02:
       call    CoreCLR!JIT_RngChkFail
       int     3
       add     byte ptr [rcx],bl
       add     al,1
       add     byte ptr [rdx+rax*2],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax-26h],dl
       loopne  00007ffa`59e12bb5
       cli
       jg      M00_L03
M00_L03:
       add     byte ptr [rbp+48h],dl
; Total bytes of code 82

[hnrqbaggio]

/cc @adamsitnik who opened the original issue about all Immutable collections.

[adamsitnik]

Inlining GetEnumerator looks good to me. The code size is going to grow, but I believe that x4 speed improvement is worth it.

I am suprised that ThrowNullRefIfNotInitialized is not getting inlined by default. Are you sure about this? To verify that you can use --profiler ETW and open the trace file with PerfView and go to events tab. There should be events for inlining succeeded and failed. You might find this blog post useful.

Where most of the time is spent for the string case? You can use one of the recommended profilers to find out: https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md

Also, I wonder what perf we would get if GetEnumerator was implemented as return this.array.GetEnumerator()?

[hnrqbaggio]

Thanks for the pointer @adamsitnik. I didn't know I could use PerfView for the Inline Events and was having trouble with the InliningDiagnoser because it emits the output to the screen it was too much info.

Looking now, it seems that the JIT is successfully inlining the ctor and ThrowNullRefIfNotInitialized inside GetEnumerator but then on the caller it says that GetEnumerator is not profitable:

ThreadID="29,572" ProcessorNumber="2" MethodBeingCompiledNamespace="System.Collections.IterateForEach_1[System.Int32]" MethodBeingCompiledName="ImmutableArray" MethodBeingCompiledNameSignature="instance !0 ()" InlinerNamespace="System.Collections.IterateForEach_1[System.Int32]" InlinerName="ImmutableArray" InlinerNameSignature="instance !0 ()" InlineeNamespace="System.Collections.Immutable.ImmutableArray_1[System.Int32]" InlineeName="GetEnumerator" InlineeNameSignature="instance value class Enumerator<!0> ()" FailAlways="False" FailReason="unprofitable inline" ClrInstanceID="7"

I've tried to do some research on what that reason is, but could not find much data. Maybe the JIT is considering that MoveNext and GetCurrent are more important to inline than the single call to GetEnumerator?

About the String case

I've tried looking at the ETL traces when I started this investigation, but for some reason I'm not able to see anything inside the benchmark method itself, because it's grayed out in PerfView and can't expand further.

This is what I get in the call stacks. Even if I load all symbols for the modules that are with ? in there the leaf node doesn't change. I've tried to follow the posts on your blog and the tutorial for PerfView but wasn't able to fix the problem (even in WPA I see the same pattern, I'll see if I can use Visual Studio and get something).

The JIT Events for that case show the same pattern than for Int32: the sub-methods seem to be successfully selected for inlining, but at GetEnumerator the JIT decides that's not worth it.

Just use this.array.GetEnumerator

Finally, at some point I did test just forwarding the call to this.array.GetEnumerator, but that didn't seem to be enough to optimize the flow. It also changes the exceptions that the methods can return (because the are some checks in MoveNext and GetCurrent that would not apply anymore) so it would require adjusting some unit tests and maybe a review if that's a breaking change or not.

But I still might give that another try at least to use as a base to compare the JIT behavior.

[hnrqbaggio]

Got some interesting information after the suggestions.

Why inlining GetEnumerator helps

I was curious why a method that is called only once and it's not that heavy would make such a difference in the results. In the VS Profiler, it shows that most of the time is spent on the assignment inside the loop, and the assembly shows the difference in terms of the instructions executed.

The assembly snips I've posted earlier show that the loop for Array or for the Inlined case is very small, and works on registers only for both the array address in RDX and the loop index variable in RAX.

The loop in the baseline shows that the address of the array and the loop variable are loaded from the stack and stored back on every iteration. It seems that the overhead of these extra memory access compounds during the loop, which is reasonable even if if using the L1 cache (it also might explain why that case has more cache misses).

I'm not sure if this is expected or not, but it seems that the non-inlined function blocks the JIT from seeing that the array can be accessed directly from the registers from earlier in the code and optimize the calls. Once we remove that "barrier" the code gets optimized.

Code size

It also seems that inlining also helps with the code size, and the reported number of bites for the benchmark is smaller, because the extra memory operations mentioned above get optimized away.

Benchmark for String

After testing a few variants of the benchmark to understand the differences in the code, I've noticed that the JIT is able to inline GetEnumerable if the benchmark is not inside a generic class itself. By default, the code in the Performance repo uses a generic class with GenericTypeArgumentsAttribute to test both Int32 and String.

In PerfView, the JIT Inlining events report a different reason for not optimizing the String case when my fix is on: before it was due to an "Unprofitable Inlining" and now it reports a "Runtime Dictionary Lookup".

Below is the result a similar benchmark that doesn't use a generic class and just the target type directly. The times drop to the same range as the Int32 case. So it seems that the proposed fix would benefit both cases.

@adamsitnik is this something that you've encountered before when working with the benchmarks?

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-8650U CPU 1.90GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
  [Host]     : .NET Framework 4.8 (4.8.4075.0), X64 RyuJIT
  Job-RUPWLA : .NET Core 5.0.0 (CoreCLR 5.0.19.61901, CoreFX 5.0.19.61901), X64 RyuJIT

PowerPlanMode=00000000-0000-0000-0000-000000000000  Toolchain=CoreRun  IterationTime=250.0000 ms  
MaxIterationCount=20  MinIterationCount=15  WarmupCount=1  

Type	Method	Size	Mean	Error	StdDev	Median	Min	Max	Gen 0	Gen 1	Gen 2	Allocated	BranchInstructions/Op	BranchMispredictions/Op	CacheMisses/Op
IterateForEach<Int32>	Array	512	369.9 ns	15.74 ns	16.84 ns	364.3 ns	351.5 ns	404.8 ns	-	-	-	-	519	1	0
IterateForEach<String>	Array	512	305.1 ns	10.97 ns	12.63 ns	304.9 ns	288.7 ns	334.0 ns	-	-	-	-	518	1	0
IterateForEach_Int32	Array	512	288.5 ns	25.03 ns	28.83 ns	272.9 ns	254.4 ns	331.7 ns	-	-	-	-	517	1	0
IterateForEach_String	Array	512	317.7 ns	25.76 ns	29.67 ns	321.8 ns	251.4 ns	371.4 ns	-	-	-	-	517	1	0
IterateForEach<Int32>	ImmutableArray	512	396.7 ns	9.58 ns	10.25 ns	395.1 ns	378.2 ns	419.2 ns	-	-	-	-	1,031	1	0
IterateForEach<String>	ImmutableArray	512	1,531.5 ns	91.32 ns	93.78 ns	1,514.5 ns	1,439.6 ns	1,823.3 ns	-	-	-	-	1,059	2	1
IterateForEach_Int32	ImmutableArray	512	314.8 ns	28.15 ns	32.42 ns	303.5 ns	270.7 ns	359.0 ns	-	-	-	-	1,030	1	0
IterateForEach_String	ImmutableArray	512	421.9 ns	8.41 ns	9.35 ns	423.7 ns	408.8 ns	437.3 ns	-	-	-	-	1,031	1	0

; System.Collections.IterateForEach_String.ImmutableArray()
       sub     rsp,28h
       xor     eax,eax
       mov     rdx,qword ptr [rcx+0C0h]
       mov     ecx,dword ptr [rdx+8]
       mov     r8d,0FFFFFFFFh
       jmp     M00_L01
M00_L00:
       cmp     r8d,ecx
       jae     M00_L02
       movsxd  rax,r8d
       mov     rax,qword ptr [rdx+rax*8+10h]
M00_L01:
       inc     r8d
       cmp     ecx,r8d
       jg      M00_L00
       add     rsp,28h
       ret
M00_L02:
       call    CoreCLR!JIT_RngChkFail
       int     3
       sbb     dword ptr [rcx+rax],eax
       add     byte ptr [rdx+rax*2],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax],al
       add     byte ptr [rax-0Ah],bl
       and     dh,byte ptr [rdi]
       ???
       jg      M00_L03
M00_L03:
       add     byte ptr [rbp+48h],dl
; Total bytes of code 82

[danmoseley]

cc @AndyAyersMS for observations about inlining above

[AndyAyersMS]

@hnrqbaggio: thanks for the observations!

For the int case, the GetEnumerator method just misses being inlined by default:

multiplier in methods of promotable struct increased to 3.
Inline candidate callsite is boring.  Multiplier increased to 4.3.
calleeNativeSizeEstimate=461
callsiteNativeSizeEstimate=85
benefit multiplier=4.3
threshold=365
Native estimate for function size exceeds threshold for inlining 46.1 > 36.5 (multiplier = 4.3)
INLINER: during 'fgInline' result 'failed this call site' reason 'unprofitable inline' for 'X`1[Int32][System.Int32]:IA():int:this' calling 'System.Collections.Immutable.ImmutableArray`1[Int32][System.Int32]:GetEnumerator():Enumerator[Int32]:this'

We might consider boosting the "promotable struct" multiplier somewhat to give this sort of inline an extra nudge in the jit, since we get a lot of benefit out of promotion. I'll put this on my todo list.

For the string case: the jit is unable to inline a method from one shared generic class into a method from another shared generic class. So when benchmarking a shared generic method, the calling context matters quite a bit.

We can sometimes work around this if the method being inlined doesn't actually use the results of the runtime lookup. Let me dig in and see if that's the case here.

I am also looking into the inlined int case, seems like we ought to be able to match the array version codegen but can't remove the bounds check.

[AndyAyersMS]

In the inlined int case, the jit can't perform what we call a "do-while" transformation on the loop, because the loop exit block has multiple statements. Basically the code (after inlining) resembles this:

    static int F(int[] a)
    {
        int r = 0;
        for (int i = -1; ++i < a.Length; )
        {
            r = a[i];
        }
        return r;
    }

And without this transformation the jit won't optimize out the bounds check.

This is limitation is going to hold for any sort of inlined enumerator because MoveNext must do two things: update some internal state and perform a test. We ought to look at relaxing this constraint and be willing to let the jit duplicate more statements if the state update and test are sufficiently cheap.

[AndyAyersMS]

As for the "inlined" string case -- the inline currently fails when inlining GetEnumerator once the importer reaches the call to ThrowNullRefIfNotInitialized, because that method's signature indicates that it requires an generic context parameter, and that parameter requires a runtime lookup, and there's currently no way to do runtime lookups safely, unless we're in the root method.

It turns out that ThrowNullRefIfNotInitialized does not use its generic context, but the jit doesn't have any way of figuring that out before it has to decide whether or not to allow GetEnumerator to inline. And even if we could get past that, we'd hit the same issue on the Enumerator constructor call.

[AndyAyersMS]

So, areas for codegen follow-up:

• look at boosting inline mulitplier for promotable structs
• look at allowing multiple statements in the do-while transformation

[danmoseley]

Is the upshot that until those changes, it is worth force inlining it?

[AndyAyersMS]

Yes, I think adding forceinline here is reasonable. Seems like whoever wrote the code was expecting inlining to happen...

runtime/src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Enumerator.cs

Lines 15 to 20 in bc47321

	/// It is important that this enumerator does NOT implement <see cref="IDisposable"/>.
	/// We want the iterator to inline when we do foreach and to not result in
	/// a try/finally frame in the client.
	/// </remarks>
	public struct Enumerator
	{

[danmoseley]

@hnrqbaggi do you want to offer a PR?