Runtime: Double bounds checks in List<T>

[EgorBo]

int First(List<int> list) => list[0];

Codegen:

G_M49643_IG01:
       sub      rsp, 40
G_M49643_IG02:
       cmp      dword ptr [rdx+16], 0
       jbe      SHORT G_M49643_IG05
G_M49643_IG03:
       mov      rax, gword ptr [rdx+8]
       cmp      dword ptr [rax+8], 0
       jbe      SHORT G_M49643_IG06 ;; <-- redundant check
       mov      eax, dword ptr [rax+16]
G_M49643_IG04:
       add      rsp, 40
       ret      
G_M49643_IG05:
       call     System.ThrowHelper:ThrowArgumentOutOfRange_IndexException()
       int3     
G_M49643_IG06:
       call     CORINFO_HELP_RNGCHKFAIL ;; <-- redundant check
       int3     
; Total bytes of code: 40

Obviously it happens because JIT doesn't know that _size is always less (or equal) than _items.Length. I wonder if we can improve it. (see https://github.com/dotnet/runtime/blob/master/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs#L148)
Same happens for indexer's setter:

myList[i] = 42

Also, redundant bounds checks are generated even when we simply iterate the list:

void Loop(List<int> list)
{
    foreach (var item in list) // same for "for"
    {
        // two bounds checks each iteration!
    }
}

IMO, List is a quite popular data structure so it worth optimizing them out.

[jkotas]

Obviously it happens because JIT doesn't know that _size is always less (or equal) than _items.Length

This condition can be violated by using List incorrectly from multiple threads.

Our general standard is that race-conditions in safe user code shall not lead to buffer overruns inside the BCL.

[EgorBo]

Obviously it happens because JIT doesn't know that _size is always less (or equal) than _items.Length

This condition can be violated by using List incorrectly from multiple-threads.

Our general standard is that race-conditions in safe user code shall not lead to buffer overruns inside the BCL.

The bound check could look like this then:

if ((uint)index >= Math.Min(_size, items.Length)) ThrowHelper....
return items[index]; // no bounds checks here.

However, it's still probably not thread safe.

[jkotas]

Also, it is not clear whether it would actually save anything meaningful. You are replacing two well-predicted independent conditional jumps that can execute in parallel with data-dependent conditional jump that has to be executed serially.

[GrabYourPitchforks]

One possible area of improvement in List<T> is to use an invariant array as the backing store. This would elide variance checks on write. Really only useful for List<IMyInterface> or List<AbstractBaseClass>, but this might be common enough to be worth pursuing.

[EgorBo]

Also, it is not clear whether it would actually save anything meaningful. You are replacing two well-predicted independent conditional jumps that can execute in parallel with data-dependent conditional jump that has to be executed serially.

Makes sense. The third option: redirect the default bounds check to the existing one, like this:

 G_M49643_IG01:
        sub      rsp, 40
 G_M49643_IG02:
        cmp      dword ptr [rdx+16], 0
        jbe      SHORT G_M49643_IG05
 G_M49643_IG03:
        mov      rax, gword ptr [rdx+8]
        cmp      dword ptr [rax+8], 0
-       jbe      SHORT G_M49643_IG06
+       jbe      SHORT G_M49643_IG05
        mov      eax, dword ptr [rax+16]
 G_M49643_IG04:
        add      rsp, 40
        ret      
 G_M49643_IG05:
        call     System.ThrowHelper:ThrowArgumentOutOfRange_IndexException()
        int3     
- G_M49643_IG06:
-       call     CORINFO_HELP_RNGCHKFAIL
-       int3     
; Total bytes of code: 40

at least makes it a bit smaller.

Basically: don't emit call CORINFO_HELP_RNGCHKFAIL if there is already a similar call. e.g. we can mark such helpers with [RangeCheckFail] attribute so the jit will check if there is already a block with a call with [RangeCheckFail]

[jkotas]

We should not need to have a special attribute for this. The JIT should be produce this code if you do the bounds check manually like this:

                // Following trick can reduce the range check by one
                T[] items = _items;
                if ((uint)index >= (uint)_size || (uint)index >= items.Length)
                {
                    ThrowHelper.ThrowArgumentOutOfRange_IndexException();
                }
                return items[index];

[jkotas]

invariant array as the backing store

Explored in https://github.com/dotnet/coreclr/pull/23571

[GrabYourPitchforks]

Explored, but not rejected. It was met with an exasperated sigh. 😉

[JulieLeeMSFT]

CC @briansull

[briansull]

I will take a look