Runtime: Indexer.Set of List is much slower than Array

[adamsitnik]

How to run the benchmarks:

git clone https://github.com/dotnet/performance.git
# if you have .NET Core 3.0 installed
dotnet run -c Release -f netcoreapp3.0 -p .\performance\src\benchmarks\micro\MicroBenchmarks.csproj --filter *IndexerSet*.List *IndexerSet*.Array --join
# if you don't have .NET Core 3.0 installed
py .\performance\scripts\benchmarks_ci.py -f netcoreapp3.0 --filter *IndexerSet*.List *IndexerSet*.Array --bdn-arguments="--join true"

| Type | Method | Size | Mean |
|-------------------------- |------- |----- |---------:|
| IndexerSet<Int32> | Array | 512 | 198.7 ns |
| IndexerSet<String> | Array | 512 | 199.5 ns |
| IndexerSetReverse<Int32> | Array | 512 | 215.6 ns |
| IndexerSetReverse<String> | Array | 512 | 219.7 ns |
| IndexerSet<Int32> | List | 512 | 986.2 ns |
| IndexerSet<String> | List | 512 | 930.1 ns |
| IndexerSetReverse<Int32> | List | 512 | 947.0 ns |
| IndexerSetReverse<String> | List | 512 | 817.4 ns |

Full docs for the new benchmarking workflow: https://github.com/dotnet/performance/blob/master/docs/benchmarking-workflow-corefx.md

[stephentoub]

Indexer.Set of List is much slower than Array

Why is this surprising? What's the action item here?

[gfoidl]

Seems that the indexer of List is not inlined (callsite boring).

Test-code

; Assembly listing for method Program:Do(ref,int,int)
; Emitting BLENDED_CODE for X64 CPU with AVX - Unix
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  3,  3   )     ref  ->  rdi         class-hnd
;  V01 arg1         [V01,T01] (  3,  3   )     int  ->  rax
;  V02 arg2         [V02,T02] (  3,  3   )     int  ->  rdx
;# V03 OutArgs      [V03    ] (  1,  1   )  lclBlk ( 0) [rsp+0x00]   "OutgoingArgSpace"
;
; Lcl frame size = 8

G_M56183_IG01:
       50                   push     rax
       0F1F4000             nop
       8BC6                 mov      eax, esi

G_M56183_IG02:
       8BF2                 mov      esi, edx
       8BD0                 mov      edx, eax
       393F                 cmp      dword ptr [rdi], edi
       E8FEE1FFFF           call     List`1:set_Item(int,int):this
       90                   nop

G_M56183_IG03:
       4883C408             add      rsp, 8
       C3                   ret

; Total bytes of code 24, prolog size 5 for method Program:Do(ref,int,int)
; ============================================================
; Assembly listing for method Program:Do(ref,int,int)
; Emitting BLENDED_CODE for X64 CPU with AVX - Unix
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  4,  4   )     ref  ->  rdi         class-hnd
;  V01 arg1         [V01,T02] (  3,  3   )     int  ->  rsi
;  V02 arg2         [V02,T01] (  4,  4   )     int  ->  rdx
;# V03 OutArgs      [V03    ] (  1,  1   )  lclBlk ( 0) [rsp+0x00]   "OutgoingArgSpace"
;
; Lcl frame size = 8

G_M56183_IG01:
       50                   push     rax
       0F1F4000             nop

G_M56183_IG02:
       3B5708               cmp      edx, dword ptr [rdi+8]
       730C                 jae      SHORT G_M56183_IG04
       4863C2               movsxd   rax, edx
       89748710             mov      dword ptr [rdi+4*rax+16], esi

G_M56183_IG03:
       4883C408             add      rsp, 8
       C3                   ret

G_M56183_IG04:
       E8359AB678           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3

; Total bytes of code 28, prolog size 5 for method Program:Do(ref,int,int)
; ============================================================

```c#
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;

namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
List list = Enumerable.Range(0, 10).ToList();
int[] array = Enumerable.Range(0, 10).ToArray();

        int value = 42;
        int index = 3;

        Do(list, value, index);
        Do(array, value, index);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void Do(List<int> list, int value, int index)
    {
        list[index] = value;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void Do(int[] array, int value, int index)
    {
        array[index] = value;
    }
}

}
```

With AggressiveInlining it will inline, but still has the bounds check (+ the check for size), so an additional condition in comparison to the array case. The bounds check could be eliminated with https://github.com/dotnet/corefx/issues/36133

[adamsitnik]

Why is this surprising?

List is an Array wrapper. 20% slower would be acceptable, but 4-5 times slower is definitely not

What's the action item here?

Investigate and fix?

[yahorsi]

There is relativery limple to implement proposal here that could make things a bit better. It wont fix setter but could give a good option when high perf needed. Please consider implementing.

https://github.com/dotnet/corefx/issues/19814

[felipepessoto]

I was curious about it. I tried to see what are the differences in assembly code, and it seems List do a lot more than Array method. I though List wouldn't have bound checks when using it inside a _for_ where the condition is the List.Count

Array:

List:

Assembly from Sharplab