SimdLinq - LINQをそのままSIMD対応して超高速化するライブラリ

2023-01-30

ついこないだのStructureOfArraysGenerator - C#でSoAを簡単に利用するためのSource Generatorは、SoAになってるとSIMDを適用しやすいよ、という話だったのですが、そもそもSIMD手書きはカジュアルにやらないし、気合い入れてSIMD書くシチュエーションなら構造も気合い入れて専用に設計するよなぁ。と、なると、カジュアルにSIMD使えるライブラリが必要で、まぁLINQですね、と。

Cysharp/SimdLinq

これを入れると別にSoA関係なく、SIMDが適用できる状態(例えばint[]にSum)だと、自動的にSIMDが適用されるようになります。そして、実際めちゃくちゃ速い。

SIMDとLINQの組み合わせが威力を発揮するというのは、別に新しいことではなく、そもそも .NET 7でもPerformance Improvements in .NET 7 LINQで、幾つかのメソッドが内部でSIMD化されて高速化されていることが発表されています。しかし、 .NET 7のSIMD対応は非常に限定的なもので、具体的にはint[]のAverage,Min,Max、それとlong[]のMin,Maxだけです。これには理由はなくはないのですが、本来SIMD対応できる範囲はもっと広いため、これでは非常にもったいない。

SimdLinqを適用できるメソッドは Sum, Average, Min, Max, MinMax, Contains, SequenceEqual、要素の型は byte, sbyte, short, ushort, int, uint, long, ulong, float, double、コレクションの型は T[], List<T>, Span<T>, ReadOnlySpan<T>, Memory<T>, ReadOnlyMemory<T> と理屈上SIMD化できるものを全て詰め込みました。特にSpan<T>/ReadOnlySpan<T>は通常のLINQでは使えない（メソッドが定義されていない）ので、有益です。また、Min, Maxを同時に取得するMinMaxというメソッドを独自に追加しています。

専用メソッドを呼ばせる（例えばSumSimd()とか)ようでは使いにくいと思ったので、現在のコードを何も弄らずとも、ライブラリ参照してglobal usingを設定すれば、全ての適用可能なメソッドに自動適用される仕組みにしました。これは同名メソッドを定義して、具象型のほうにオーバーロード解決が優先採用されることを利用しています。

使い方

なので、使い方もなにもなく、usingすれば勝手にSimdLinqになって高速化されます。

using SimdLinq; // enable SimdLinq extension methods

var array = Enumerable.Range(1, 100000).ToArray();

var sum = array.Sum(); // used SimdLinqExtensions.Sum

using忘れちゃうというのはあるので、そこでglobal usingです。csprojに

<ItemGroup>
    <Using Include="SimdLinq" />
</ItemGroup>

というのを仕込んでやれば、SimdLinqが使える場合はSimdLinqに、そうじゃないものは普通のLinqでオーバーロードが解決されるようになります。便利。

具体的にSimdLinqが適用されるメソッドは以下のものになります。

Sum for int, uint, long, ulong, float, double
LongSum for int, uint
Average for int, uint, long, ulong, float, double
Min for byte, sbyte, short, ushort, int, uint, long, ulong, float, double
Max for byte, sbyte, short, ushort, int, uint, long, ulong, float, double
MinMax for byte, sbyte, short, ushort, int, uint, long, ulong, float, double
Contains for byte, sbyte, short, ushort, int, uint, long, ulong, float, double
SequenceEqual for byte, sbyte, short, ushort, int, uint, long, ulong, float, double

互換性と安全性

.NET 7の標準に、このSimdLinqのようなアグレッシブなSIMD化が入らなかった理由は、互換性と安全性になります。え、安全じゃないの？というと怖くなるので、何が違うのかはしっかり把握しておきましょう。別に危険、というわけではないですが。

まずSumとAverage(Averageの中身はSumしたのをLengthで割るだけなので中身は実質Sum)ですが、LINQのSumはcheckedで、オーバーフローすると例外を吐きます。SimdLinqはuncheckedです、つまりオーバーフローするとそのままオーバーフローしたまま結果を返します。checkedのほうが挙動としてはいいんですが、SIMD演算がオーバーフローのチェックできないので、SimdLinqではuncheckedとして提供しています。オーバーフローに関しては自己責任で。さすがにbyteのSumとかだとすぐオーバーフローしちゃうので、SimdLinqのSumは32 bit以上の要素にだけ提供しています、つまりint, long, uint, ulong, double, float です。そもそも元々のLINQのSum(引数なし)もintからなので、その辺は一緒ということで。

そうしたオーバーフローの危険性を避けたい場合、独自拡張として LongSum というlongを戻り値にするSumメソッドを追加しています。内部的にlongで処理するため、(若干性能は落ちますが)オーバーフローしなくなります。

float/doubleの扱いは挙動の違いが若干あります。まず、通常のLINQのMin, MaxはNaNをチェックしますがSimdLinqはNaNをチェックしません。NaNチェックがあったほうが丁寧ですが、SIMDでそれは入れずらい＆NaNが入ってくるケースってあまりないので現実的にすごい問題か、というとそうではないかな、と。

それとSumの場合に足し算の順序が変わって(LINQは前から順番に足しますが、SIMDだと並列に足すので)、浮動小数点演算だと足す順序が変わると微妙に誤差が出て同じ結果になりません。例えばLINQだと1.5710588FだけどSimdLinqだと1.5710589Fになる、といったような違いが出てきます。結果としては別にどっちでも良い（ある意味で別にどっちも厳密にはあってない）と思いますが、結果の互換性がないですよ、ということは留意してください。

まとめ

高速なLINQのAlternativeって、結構あります。LinqAF、LinqFaster、NetFabric.Hyperlinqなど。ただ、どれも大仰なんですよね、StructのIteratorを作ってー、とか。専用メソッドを呼ぶためにラップするのも手間だし、その割に凄い効果的というほどでもないから、依存を増やす割にはメリットも薄くなので、私自身は使おうとはあまり思ってませんでした。

そこでSimdLinqではLINQ全体を高速化させることを狙っているわけではなくて、SIMDが適用できるものだけピンポイントに、そしてソースコードには一切手を入れる必要のない"Drop-in replacement"になるようにデザインしました。また、SIMDのみに絞ったことで性能面に明らかに圧倒的な差をだして、あえて使う理由を作る、といったところですね。

ついでにそうなると欲張ってどんどん適用できる箇所を増やしたい、つまりはStructureOfArraysGeneratorだ、みたいなコンボも狙っています。エコシステム囲い込み！囲い込みはEvil！

そんなわけでSIMDシリーズ第一弾でした。今年はSIMD関連も幾つか出していくかもしれませんし、Source Generatorネタがめちゃくちゃ溜まってるので時間が無限大に必要です。まぁ、ともかくまずはSimdLinqを使って見てください！

SimdLinq - LINQをそのままSIMD対応して超高速化するライブラリ

使い方

互換性と安全性

まとめ

Profile

Archive