Lower performance when virtual call loop unrolling

[tastynoob]

I have a loop unrolling optimization
such as:

execute();
execute();
...
execute(); // repeat 10 times

it will bring 25% performance improvement
but i repeat it 20 times, its performance has regressed
I guess it optimizes the code to this

for (int i=0;i<20;i++) execute();

I would like to know how to solve this problem

[tastynoob]

After profiling, I found the loop overhead is still high, more than 20% or even 40%

[huoyaoyuan]

Can you share the actual code you are testing with? There's risk of inappropriate measurement. There's also a chance that the BCL provides SIMD optimized version of the action you are doing.

[huoyaoyuan]

First, this is not related to the language. Performance questions should go to https://github.com/dotnet/runtime/discussions .

I guess it optimizes the code to this

There's no such type of optimization. Neither C# and JIT compiler will do this transformation.
However, if the body of execute is considered simple, it will be inlined by the JIT compiler. You can use [MethodImpl(MethodImplOptions.NoInlining)] to disable that.

A general rule of optimization is to know what's happening. There are several tools can help you understand how your C# code is compiled:

• https://sharplab.io and ILSpy to understand how C# compiles to IL.
• sharplab (JIT Asm mode), https://godbolt.org , BenchmarkDotNet with [DisassemblyDiagnoser], and https://marketplace.visualstudio.com/items?itemName=EgorBogatov.Disasmo to view the compiled assembly code.

I have a loop unrolling optimization

Loop unrolling is a very low level optimization. It's very uncommon to see "random" unrolling ratio like 10 or 20, but typically 2's exponents like 4, 8, or 16.

[tastynoob]

yes, I tried, you are right, but i still don't understand why it's regress
actually i find it regress if repeat count is not 10 (any number)
use 10: 3s
not use 10: 4s
project: https://github.com/tastynoob/FAST-PSASM/blob/0e37739e1f46b9f9960c630e973d260115c45caa/Program.cs#L117

[tastynoob]

but in profiling(dotTrace), the 20 repeats time is lower than 10 repeats

[huoyaoyuan]

When using Visual Studio profiler, the "self CPU" column of the Step10 method is very low.

In this case, I suspect the actual culprit to be devirtualization and branch prediction of virtual method dispatch. Since your program is an assembly simulator, each iteration of your code is calling different virtual instruction. When the loop is expanded, every single invocation is treated as different call site and will be optimized separately. However, if your unrolling ratio is too big, the invocation count of each call may drop below the optimization threshold.

I'd expect to see best performance if the unrolling ratio matches exactly the loop size in your code, which is 10 in the sample. In this case, each invocation will be devirtualized to the precise instruction in the loop.

[huoyaoyuan]

In short, it's a pitfall that JIT gets the chance to burn the simulated code into the simulator, which gives you a false sense of "better performance".

There are also other performance issues in your code, for example in should never be used with reference types.

[tastynoob]

Correct! indirect branch prediction is something I didn't take into account, this make sense
thanks a lot!

[huoyaoyuan]

Well it should be mainly about devirtualization.

Here is the fully optimized (Tier 1) result for your code:

; Assembly listing for method RunTimeContext:Steps10():this (Tier1)
; Emitting BLENDED_CODE for X64 with AVX512 - Windows
; Tier1 code
; optimized code
; rsp based frame
; partially interruptible
; 1 inlinees with PGO data; 17 single block inlinees; 0 inlinees without PGO data

G_M000_IG01:                ;; offset=0x0000
       push     rbx
       sub      rsp, 48
       mov      gword ptr [rsp+0x40], rcx
 
G_M000_IG02:                ;; offset=0x000A
       mov      rdx, gword ptr [rsp+0x40]
       mov      gword ptr [rsp+0x28], rdx
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       mov      rdx, 0x7FF955847710
       cmp      qword ptr [rcx], rdx
       jne      G_M000_IG10
 
G_M000_IG03:                ;; offset=0x0046
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      rax, rdx
       mov      r8d, dword ptr [rcx+0x08]
       mov      r10d, dword ptr [rcx+0x0C]
       cmp      r10d, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      edx, dword ptr [rdx+4*r10+0x10]
       add      edx, dword ptr [rcx+0x10]
       cmp      r8d, dword ptr [rax+0x08]
       jae      G_M000_IG20
       mov      ecx, r8d
       mov      dword ptr [rax+4*rcx+0x10], edx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       mov      rdx, 0x7FF955847910
       cmp      qword ptr [rcx], rdx
       jne      G_M000_IG11
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      rax, rdx
       mov      r8d, dword ptr [rcx+0x0C]
       cmp      r8d, dword ptr [rax+0x08]
       jae      G_M000_IG20
       mov      eax, dword ptr [rax+4*r8+0x10]
       mov      r8d, dword ptr [rcx+0x10]
       cmp      r8d, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       cmp      eax, dword ptr [rdx+4*r8+0x10]
       jge      SHORT G_M000_IG05
 
G_M000_IG04:                ;; offset=0x00EB
       mov      rdx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x08]
       mov      dword ptr [rdx+0x24], ecx
 
G_M000_IG05:                ;; offset=0x00F6
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       mov      rbx, 0x7FF9557D24B0
       cmp      qword ptr [rcx], rbx
       jne      G_M000_IG12
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       cmp      qword ptr [rcx], rbx
       jne      G_M000_IG13
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       cmp      qword ptr [rcx], rbx
       jne      G_M000_IG14
 
G_M000_IG06:                ;; offset=0x01C8
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       mov      rdx, 0x7FF9557D0D98
       cmp      qword ptr [rcx], rdx
       jne      G_M000_IG15
       lea      rdx, [rsp+0x28]
       call     [AsmInstPush:Execute(byref):this]
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       cmp      qword ptr [rcx], rbx
       jne      G_M000_IG16
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       cmp      qword ptr [rcx], rbx
 
G_M000_IG07:                ;; offset=0x029F
       jne      G_M000_IG17
       cmp      byte  ptr [rcx], cl
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       cmp      qword ptr [rcx], rbx
       jne      G_M000_IG18
       cmp      byte  ptr [rcx], cl
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x10]
       mov      eax, dword ptr [rcx+0x08]
       mov      ecx, dword ptr [rcx+0x0C]
       cmp      eax, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      dword ptr [rdx+4*rax+0x10], ecx
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
       mov      rdx, 0x7FF9557D0C70
       cmp      qword ptr [rcx], rdx
       jne      G_M000_IG19
       cmp      byte  ptr [rcx], cl
       lea      rdx, [rsp+0x28]
       call     [AsmInstPop:Execute(byref):this]
 
G_M000_IG08:                ;; offset=0x0358
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
 
G_M000_IG09:                ;; offset=0x0360
       add      rsp, 48
       pop      rbx
       ret      
 
G_M000_IG10:                ;; offset=0x0366
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001C8
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG11:                ;; offset=0x039F
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001D0
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG12:                ;; offset=0x03D8
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001D8
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG13:                ;; offset=0x0411
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001E0
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG14:                ;; offset=0x044A
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001E8
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG15:                ;; offset=0x0483
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001F0
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG16:                ;; offset=0x04BC
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF9554001F8
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG17:                ;; offset=0x04F5
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF955400200
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      SHORT G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG18:                ;; offset=0x052A
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF955400208
       call     [r11]IAsmInst:Execute(byref):this
       mov      rdx, gword ptr [rsp+0x28]
       inc      dword ptr [rdx+0x24]
       mov      rdx, gword ptr [rsp+0x28]
       mov      rdx, gword ptr [rdx+0x08]
       mov      rcx, gword ptr [rsp+0x28]
       mov      ecx, dword ptr [rcx+0x24]
       cmp      ecx, dword ptr [rdx+0x08]
       jae      SHORT G_M000_IG20
       mov      rcx, gword ptr [rdx+8*rcx+0x10]
 
G_M000_IG19:                ;; offset=0x055F
       lea      rdx, [rsp+0x28]
       mov      r11, 0x7FF955400210
       call     [r11]IAsmInst:Execute(byref):this
       jmp      G_M000_IG08
 
G_M000_IG20:                ;; offset=0x0576
       call     CORINFO_HELP_RNGCHKFAIL
       int3     
 
; Total bytes of code 1404

The real virtual calls (call [r11]IAsmInst:Execute(byref):this) are put into the fallback area of code. The optimal area of the method is doing different things for each invocation between each inc dword ptr [rdx+0x24].