Getting rid of array bound checks using ref-returns and .NET 5

Imagine we have a simple class, a wrapper around some array of structs (better data locality etc.):

Now, I would like to have an efficient access to every element. Obviously, a trivial indexer would be inefficient here, as it would return a copy of the given array element (a struct):

Luckily, since C# 7.0 we can “ref return” to efficiently return a reference to a given array element which is super nice (refer to my article about ref for more info):

Here, 99.9999% of devs will stop and will be satisfied with the semantics and performance results. But… if we know we will call it tremendously often, can we do better?!

First of all, let’s see what is being JITted by the .NET Core x64 runtime (5.0rc) when accessing 9th element (index is 8):

To those who know assembler a little, it may be clear what is going on here. But let’s make a short summary:

  • we see a little of “stack frame” creation here (sub/add rsp) – could we get rid of it in such a simple method?
  • we see bound check in line 4 (cmp the index to 8) to check if we are accessing an array with a correct index – could we get rid of it because we trust our code? 😇

Disclaimer: Getting rid of bound checks is very risky and the resulting dangers probably will overcome the performance benefits. Thus, use it only after heavy consideration, if you are sure why you need it and you can ensure caller’s code will be correct (providing valid indices).

To continue, we will be walking on thin ice of unsafe code now.

The first idea is to use Unsafe.Add to provide kind of “pointer arithmetic” – add an index-element to the first element:

The “problem” here is, it produces almost identical results because _array[0] is still a bound-checked array access (and we don’t get rid of stack frame too):

Hence, the non trivial question arises – how to get the address/ref to the first element of an array?

We could think of doing some Span-based magic (to use MemoryMarshal.GetReference):

But you can probably feel it – it produces even slower and bigger code (Span creation handling etc.) while still bound check will be there (Span is “safe”).

So, we need somehow to find a better way of getting an address of the first array’s element. The thing is, the internal structure of the array type is an implementation detail (although well-known). How can we overcome that?

The idea is… to rely on that implementation detail. This approach is being used by DangerousGetReferenceAt method from Microsoft.Toolkit.HighPerformance package maintained by Sergio Pedri. DangerousGetReferenceAt source code explains it well:

So, we are casting (reinterpreting) an array reference as a reference to some artificial RawArrayData class, which has a layout corresponding to an array layout. Thus, getting “data” reference is now just trivial. No bound checks at all!

The good news is this method has been ported to .NET 5! So, in .NET 5.0rc we can already use MemoryMarshal.GetArrayDataReference which does exactly the same thing:

Thus, without any external dependencies our code in .NET 5 may be rewritten to:

And the resulting code is indeed much more lightweight:

No bound-checks, and as an additional reward from the method simplicity – no stack frame.

Benchmarks are indeed showing a noticeable (well, in ns order of magnitude) difference:

Which simply means, we are now about 5x faster than with the initial solution!

Disclaimer #2: Approach taken here with the usage of GetArrayDataReferece is super dangerous. As Levi Broderick, one of .NET framework developers, said: “Also, read the method documentation. It does more than remove bounds checks; it also removes array variance checks. So it might not be valid to write to the ref, even if the index is within bounds. Misuse of the method will bite you in the ass, guaranteed.”  Moreover, documentation clearly states that “a reference may be used for pinning but must never be dereferenced” 😇

1 comment

  1. Pingback:

Leave a Reply

Your email address will not be published. Required fields are marked *