In this blog post, we will explore the use of SIMD instructions to speed up LINQ queries. We will use the Vector

## The "problem"

Let's say we have a list of numbers and we want to find the sum of all the numbers. What would be the fastest way to do this? Well, we could use a `for`

loop and add each number to a variable. But this is not the fastest way. The fastest way is to use SIMD instructions. SIMD stands for "Single Instruction Multiple Data". It allows us to perform the same operation on multiple data points at the same time. This is much faster than performing the same operation on each data point one by one. A word of warning: There are two pitfalls involved with this. 1. Complexity. Obviously, this approach is far more advanced than a simple loop or using LINQ directly. 2. I would not recommend this approach for small datasets and when performance is not critical. I said it before and I say it again: Measure your stuff first before you optimize at the wrong place!

Back to topic, let's see how we can do this.

## The `Vector<T>`

type

The entry point to SIMD operations is the `Vector<T>`

type. It is a generic type that can hold a vector of data. The `T`

type argument can be any numeric type. The `Vector<T>`

type has a `Count`

property that tells us how many elements it can hold. That is important because if we, for example, add two vectors which each other, we do this in "one" operation. The result will be a vector with the same number of elements as the input vectors. So the more elements we can hold, the faster our code will be. The size of how many elements your vector can hold depends on your architecture. Your CPU has something called **SSE**: "Streaming SIMD Extensions". This is a set of instructions that allow you to perform SIMD operations. The size of the vectors you can hold depends on the SSE version your CPU supports. For example, if your CPU supports SSE2, you can hold two elements in a vector. If your CPU supports SSE4.1, you can hold 4 elements in a vector. And so on. I wrote an article some time ago that also explains it to somewhat more detail: *"Using SSE in C# on the example of the sum of a list"*.

## Generic Math and SIMD

With the introduction of C# 10, we now have a new feature called "generic math". This allows us to use SIMD operations on any numeric type. This is great because we can now use SIMD operations on `int`

, `float`

, `double`

, and so on without creating a function for each type. This is also great because we can now use SIMD operations on user-defined types. Let's see how this works.

## Creating the `Min`

function

For SIMD it is important that the data is as independent as possible. The idea is that we tile our problem into smaller subproblems those subproblems will be solved in a single operation. So if we have a vector of 4 elements, we want to perform the same operation on each element simultaneously.

In our case we have a `Min`

function that should retrieve the smallest value in our array. To do so we tile the whole array into smaller chunks and check for each what is the smallest value.

```
public static T Min<T>(this Span<T> span)
where T : unmanaged, IMinMaxValue<T>, INumber<T>
```

For the sage of simplicity we use a `Span<T>`

. The important part is we need contiguous memory as the memory blocks get streamed to your SIMD processor that can not handle arbitrary memory addresses. `INumber<T>`

is a marker interface that tells us that the type is a number. `IMinMaxValue<T>`

is a marker interface that tells us that the type has a minimum and maximum value. This is important because we need to initialize our result with the maximum value of the type. `unmanaged`

is a constraint that tells us that the type is a value type and the type does not contain any reference type. This is important because we need to be able to store the type in a vector. Well, technically `Vector<T>`

only has the constraint `struct`

but as a `struct`

can contain a reference type, we need to add the `unmanaged`

constraint. So we can use stuff like `stackalloc`

and prohibit scenarios where a struct with a reference type yields unexpected results.

The function itself is pretty simple. We first create a vector with the maximum value of the type. That is where the generic math really kicks in!
We also cast our `Span`

directly to a `Vector`

.

```
var spanAsVectors = MemoryMarshal.Cast<T, Vector<T>>(span);
Span<T> vector = stackalloc T[Vector<T>.Count];
vector.Fill(T.MaxValue);
var minVector = new Vector<T>(vector);
```

In this case we are using `T.MaxValue`

because later we want to retrieve the minimum value. If we would use `T.MinValue`

or `T.Zero`

we are running into the problem that this might be the smallest value present and therefore would lead to wrong results. And by the way things like `T.MinValue`

or `T.Zero`

are possible because of generic math.

The next step is retrieving is comparing each vector entry against every other vector to retrieve the minimum:

```
foreach (var spanAsVector in spanAsVectors)
{
minVector = Vector.Min(spanAsVector, minVector);
}
```

In the end we will have a Vector with n-entries where one of them is the total minimum. BUt we are not done. `MemoryMarshal.Cast<T, Vector<T>>(span);`

has a big downside: Assume our `Vector<T>.Length`

is 4 and our input is a list with 9 entries. The function would only return 2 vectors. So all in all one element is missing. Therefore if we have a "left-over" we have to compare it against the vector we have so far. This is done by the following code:

```
var remainingElements = span.Length % Vector<T>.Count;
if (remainingElements > 0)
{
Span<T> lastVectorElements = stackalloc T[Vector<T>.Count];
lastVectorElements.Fill(T.MaxValue);
span[^remainingElements..].CopyTo(lastVectorElements);
minVector = Vector.Min(minVector, new Vector<T>(lastVectorElements));
}
```

Now the last part: We need to retrieve the minimum value from the vector.

```
var minValue = T.MaxValue;
for (var i = 0; i < Vector<T>.Count; i++)
{
minValue = T.Min(minValue, minVector[i]);
}
return minValue;
```

And there we go! We successfully implemented a SIMD version of the `Min`

function. Let's see how this performs.

### Performance

To measure the performance we will use the BenchmarkDotNet library. We will compare the performance of the SIMD version of the `Min`

function with the performance of the non-SIMD (LINQ) version of the `Min`

function. Here the setup code:

```
public class MinBenchmark
{
private readonly int[] _numbers = Enumerable.Range(0, 1000).ToArray();
[Benchmark(Baseline = true)]
public int LinqSum() => Enumerable.Min(_numbers);
[Benchmark]
public int LinqSIMDSum() => LinqSIMDExtensions.Min(_numbers);
}
```

And here are the results from my MacBook M1:

```
| Method | Mean | Error | StdDev | Ratio |
|------------ |---------:|--------:|--------:|------:|
| LinqMin | 166.9 ns | 0.94 ns | 0.78 ns | 1.00 |
| LinqSIMDMin | 125.3 ns | 0.69 ns | 0.61 ns | 0.75 |
```

Not bad! We are 25% faster than the LINQ version. Keep in mind that this is a very simple example.

## More use cases - Average

Thanks to the generic math we can even do things like `Sum`

or `Average`

on user-defined types. I will link the whole library and code samples at the end of the blog post anyway. The `Sum`

is almost like the `Min`

method, therefore I will not show it here. A bit special might be `Average`

though. Here is the code:

```
public static T Average<T>(this Span<T> span)
where T : unmanaged, INumberBase<T>, IDivisionOperators<T, T, T>
{
var length = T.CreateChecked(span.Length);
var divisionOperators = span.Sum() / length;
return divisionOperators;
}
```

Here are some key takeawys. We are using the `IDivisionOperators<T, T, T>`

interface. This interface is a marker interface that tells us that the type has a division operator. So we are getting the generic sum and divide this by the amounts of entries in our list.
As the `span.Length`

is a simple integer we have to convert it to the type of our list. This is done by the `T.CreateChecked`

method. It takes any other number-like type and tries to convert it to our type in a checked fashion. This means that if the conversion would lead to an overflow, an exception is thrown. This is important because we do not want to silently ignore overflows. We are doing this because the `/`

is only valid for the same type in generic math. So we can not divide an `int`

by an `int`

and get a `double`

as result. That has a big pitfall here: If we are using just integers and we retrieve the average we will get an integer as result. So the `Average`

of `[1, 2]`

is 1.

### Performance

Like before we are creating a benchmark and check the difference to the plain old LINQ method:

```
public class AverageBenchmark
{
private readonly float[] _numbers = Enumerable.Range(0, 1000).Select(f => (float)f).ToArray();
[Benchmark(Baseline = true)]
public float LinqAverage() => Enumerable.Average(_numbers);
[Benchmark]
public float LinqSIMDAverage() => LinqSIMDExtensions.Average(_numbers);
}
```

Results:

```
| Method | Mean | Error | StdDev | Ratio |
|---------------- |-----------:|--------:|--------:|------:|
| LinqAverage | 1,055.2 ns | 4.79 ns | 4.48 ns | 1.00 |
| LinqSIMDAverage | 179.9 ns | 1.00 ns | 0.94 ns | 0.17 |
```

Well. This is a huge difference. We are almost 6 times faster than the LINQ version.

## Conclusion

With the introduction of generic math we can now do SIMD operations on user-defined types and for a wider range of types without adopting code. This is a huge step forward for the .NET ecosystem. Based on the examples I showed here, I created a small library called: **LinqSIMDExtensions** that also brings some more methods you can use besides `Min`

and `Average`

. In the readme you will also find the nuget package download.

## Resources

- The source code as well as the library can be found here:
**LinqSIMDExtensions** - The nuget download can be found here:
**LinqSIMDExtensions**