Range Indexer
11/20/2024
5 minutes
With C# 12's collection expression feature, the range indexers has become also more powerful.
These two constructs along with the C#'s spreads feature allow to easily create new collections by slicing and concatenating existing ones. For example, given the following snippet:
int[] a = [1, 2]; int[] b = [3, 4, 5]; int[] c = [..a, ..b[..1]];
When executing the snippet, variable c will reference an integer array containing 1 2 and 3 values. While these operations are universal in many languages for a longer time, they are only introduced as new in C# 12.
In a previous post I have already explored the collection expression feature, and in this post I will look into some of the aspects of using the range operator.
Using the range operator
A range index allows to create a subrange of a collection. For example, in the above sample b[..1] creates a range that contains the 0th item of the original collection. Most built-in collections support the range operator out of the box. However, their behavior might vary. In the following example a range of an array and a range of a span is returned.
int[] _data = [1, 2, 3, 4, 5]; //... Span<int> ArrayRange() => _data[..4]; Span<int> SpanRange() => _data.AsSpan()[..4];
While both seem to return a Span<int> the range operator used in the ArrayRange method returns an int[] that is casted to Span<int> before it is being returned. The SpanRange method creates a span over the original array then uses the range operator over this span. Using the range operator directly on an array allocates a new array that is sized as the selected range, and the corresponding items of the original array are copied into this new array. From performance point of view this means that ArrayRange is significantly slower:
| Method | Mean | Error | StdDev | Median | Gen0 | Allocated | |---------------- |----------:|----------:|----------:|----------:|-------:|----------:| | ArrayRange | 3.9518 ns | 0.0922 ns | 0.1098 ns | 3.9416 ns | 0.0064 | 40 B | | SpanRange | 0.0128 ns | 0.0198 ns | 0.0175 ns | 0.0036 ns | - | - |
Using the range operator on a string or over a Span<char> shows a similar performance deviation. While it is easy to miss this subtle difference even for someone with well-trained eyes, fortunately there is a C# analyzer rule, CA1833 that warns the developer about this behavior.
Custom collections with range operator
Explicit support
Custom collections can participate in using the range index in two ways: with implicit or explicit support. In case of explicit support, a developer would create an indexer property that takes a Range parameter. For example, a custom collection could define the following method:
public Span<T> this[Range r] => _data.AsSpan()[r];
When using explicit support for range operators, the developer can decide the way the operator is implemented: whether the implementation allocates a new object for the selected section or not. In the above implementation the range is applied on a Span<T> that avoids the additional object and copy operation. However, from performance point of view such a method will not meet expectations:
| Method | Mean | Error | StdDev | Median | Gen0 | Allocated | |------------|----------:|----------:|----------:|----------:|-------:|----------:| | ArrayRange | 3.9518 ns | 0.0922 ns | 0.1098 ns | 3.9416 ns | 0.0064 | 40 B | | SpanRange | 0.0128 ns | 0.0198 ns | 0.0175 ns | 0.0036 ns | - | - | | MyRange | 4.8549 ns | 0.0414 ns | 0.0387 ns | 4.8703 ns | - | - |
While it avoids the extra allocation, the additional bound checks hamper the performance.
Implicit support
A custom collection can implicitly support the range operator by being countable (having a visible int Count or int Length property) and having a Slice(int start, int length) method. The return type of this method is not limited to spans, it could be a Span<T>, ReadOnlySpan<T>, T[], etc:
public Span<T> Slice(int start, int length) => _data.AsSpan(start, length);
Using the range operator on a custom collection with implicit support shows a similar performance characteristic as the built-in collections. With the above implementation no additional object is allocated, and the mean execution time is close to equal to the SpanRange method's execution time.
| Method | Mean | Error | StdDev | Gen0 | Code Size | Allocated | |----------- |----------:|----------:|----------:|-------:|----------:|----------:| | ArrayRange | 3.9786 ns | 0.0656 ns | 0.0613 ns | 0.0064 | 449 B | 40 B | | SpanRange | 0.1536 ns | 0.0101 ns | 0.0089 ns | - | 72 B | - | | MyRange | 0.1529 ns | 0.0135 ns | 0.0126 ns | - | 61 B | - |
One interesting detail though is that the above Slice method implementation along with a benchmark method of Span<int> MyRange() => _data2[..4]; generates slightly less code as the JIT seems to exclude a "fast path" branch that would otherwise save a few dereferencing instructions.
Lastly, note that the range operator's two parameters refer to indexes, while the Slice method refer to a start index and a length. This is a slight difference in the semantics, but the compiler takes care of this and invokes the Slice method with the parameters adjusted to the length semantics.
Performance measurement
The code snippet below shows the code used for the performance tests and the corresponding results.
[SimpleJob, MemoryDiagnoser, DisassemblyDiagnoser] public class Benchmarks { private static int[] _data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]; private static string _stringData = "Hello World"; private static MyCollectionAddRange<int> _data2 = new MyCollectionAddRange<int>([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]); [Benchmark] public Span<int> ArrayRange() => _data[..4]; [Benchmark] public Span<int> SpanRange() => _data.AsSpan()[..4]; [Benchmark] public string StringRange() => _stringData[..4]; [Benchmark] public ReadOnlySpan<char> StringSpanRange() => _stringData.AsSpan()[..4]; [Benchmark] public Span<int> MyRange() => _data2[..4]; } // public class MyCollectionAddRange ...
Measurements with Explicit range operator for MyRange implementation:
| Method | Mean | Error | StdDev | Median | Gen0 | Allocated | |---------------- |----------:|----------:|----------:|----------:|-------:|----------:| | ArrayRange | 3.9518 ns | 0.0922 ns | 0.1098 ns | 3.9416 ns | 0.0064 | 40 B | | SpanRange | 0.0128 ns | 0.0198 ns | 0.0175 ns | 0.0036 ns | - | - | | StringRange | 3.6617 ns | 0.1023 ns | 0.1257 ns | 3.6454 ns | 0.0051 | 32 B | | StringSpanRange | 0.1388 ns | 0.0153 ns | 0.0136 ns | 0.1380 ns | - | - | | MyRange | 4.8549 ns | 0.0414 ns | 0.0387 ns | 4.8703 ns | - | - |
Measurements with Implicit range operator for MyRange implementation:
| Method | Mean | Error | StdDev | Gen0 | Code Size | Allocated | |----------- |----------:|----------:|----------:|-------:|----------:|----------:| | ArrayRange | 4.1323 ns | 0.1037 ns | 0.1896 ns | 0.0064 | 449 B | 40 B | | SpanRange | 0.1573 ns | 0.0180 ns | 0.0160 ns | - | 72 B | - | | MyRange | 0.1775 ns | 0.0287 ns | 0.0353 ns | - | 61 B | - |