ついこないだの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を使って見てください！

最近はSource Generatorブームが続いていて、去年末に2022年のC# (Incremental) Source Generator開発手法という記事を出しましたが、まずは今年第一弾のSource Generatorライブラリです。

• github.com/Cysharp/StructureOfArraysGenerator

これは何かというと、structure of arrays(SoA)を使いやすくするためのコードを生成するというものです。まずそもそもSoAですが、WikipediaのAoS and SoAという記事によるところ（日本語版はない）、CPUキャッシュを有効活用したりSIMDを適用させやすくなる構造だよ、と。通常C#の配列はarray of structures(AoS)になります。

上の通常の配列がAoSでXYZXYZXYZXYZといったように並んでいる構造ですが、下のStructureOfArraysGeneratorで生成したSoAの配列はXXXXYYYYZZZZという並び順になります。実際にシンプルなパフォーマンステスト（Vector3[10000]に対してYの最大値を求める）によるところ

そのまま書いても2倍、SIMDで書きやすい状態なのでSIMDで処理してしまえば10倍高速化されます。というわけで、パフォーマンスが求められるシチュエーションで非常に有用です。

このライブラリはZigという最近、日本でも注目されている言語（Node.jsの高速な代替として注目されているBunの実装言語）のMultiArrayListにインスパイアされました。Zigの作者 Andrew Kelley氏が講演した A Practical Guide to Applying Data-Oriented Design という素晴らしい講演があるので是非見て欲しいのですが

データ指向設計(Data-Oriented Design)はパフォーマンスを飛躍的に改善する魔法なのです。ん、それはどこかで聞いたような……？そう、UnityのDOTSです。Data-Oriented Technology Stackです。ECSです。……。まぁ、そんなわけで全体に導入するにはそうとうガラッと設計を変える必要があるので大変厳しくはあるのですが、講演での実例としてZig自身のコンパイラの事例が出てますが、まぁつまりは徹底的にやれば成果は出ます。

しかしまぁ徹底的にやらず部分的に使っても効果があるのはUnityで Job System + Burst ぐらいでいいじゃん、という気持ちになっていることからも明らかです。というわけで部分的なSoA構造の導入にお使いください、かつ、導入や利用の敷居は全然高くないように設計しました。

MultiArray

NuGetからインストール（Unityの場合はgit参照か.unitypackageで）するとAnalyzerとして参照されます。StructureOfArraysGeneratorは属性も含めて依存はなく全てのコードが生成コードに含まれる（属性はinternal attributeとして吐かれる）ので、不要なライブラリ依存が増えることはありません。

[MultiArray(Type)]を配列的に使いたいreadonly partial structにつけます。

using StructureOfArraysGenerator;

[MultiArray(typeof(Vector3))]
public readonly partial struct Vector3MultiArray
{
}

するとSource Generatorは内部的にはこういうコードを生成します。

partial struct Vector3MultiArray
{
    // constructor
    public Vector3MultiArray(int length)

    // Span<T> properties for Vector3 each fields
    public Span<float> X => ...;
    public Span<float> Y => ...;
    public Span<float> Z => ...;

    // indexer
    public Vector3 this[int index] { get{} set{} }

    // foreach
    public Enumerator GetEnumerator()
}

Structure of Arrays と言ってますが、StructureOfArraysGeneratorは Arrays は生成しません。内部的には単一の byte[] と各開始地点のオフセットのみを持っていて、生成されるプロパティによってSpan<T>のビューを返すという設計になっています。

使い方的には配列のように使えますが、Span<T>の操作、例えばref var item inによるforeachを使うと、より効率的に扱えます。

var array = new Vector3MultiArray(4);

array.X[0] = 10;
array[1] = new Vector3(1.1f, 2.2f, 3.3f);

// multiply Y
foreach (ref var item in v.Y)
{
    item *= 2;
}

// iterate Vector3
foreach (var item in array)
{
    Console.WriteLine($"{item.X}, {item.Y}, {item.Z}");
}

Yに2倍を掛ける処理などは、メモリ領域が連続していることにより、Vector3[]を item.Y *= 2 などとして書くよりも高速に処理されます．

他にList<T>のようにAddできるMultiArrayListや、内部的にはbyte[]を持っているだけであることを生かしたMemoryPackでの超高速なシリアライズなどにも対応しています。気になったら是非ReadMeのほうを見てください。

.NET 7 時代のSIMD

.NETはSIMD対応が進んでいて、System.Runtime.Intrinsics.X86によって、直接ハードウェア命令を書くことが出来ます。

しかし、しかしですね、最近は .NET を Arm で動かすことが現実的になってきました。iOSやAndroidでけはなくMacのArm化、そしてAWS GravitonのようなArmサーバーはコスト面でも有利で、選択肢に十分入ります。そこでAvx.Addなんて書いていたらArmで動きません。勿論 System.Runtime.Intrinsics.Arm というクラスも公開されていて、Arm版のSIMDを手書きすることもできるんですが、分岐して似たようなものを二個書けというのか！という話です。

そこで、 .NET 7こそがC# SIMDプログラミングを始めるのに最適である理由 という記事があるのですが、確かに .NET 7 から追加された Vector256.LoadUnsafe がまずめちゃくくちゃイイ！馴染みが深い（？）Unsafeによる ref var T で書けます！そしてExpose cross-platform helpers for Vector64, Vector128, and Vector256により、Vector64/128/256<T>にプラットフォーム抽象化されたSIMD処理が書けるようになりました、やはり .NET 7から。

例えば .NET 7 でint[]のSumのSIMD化を書いてみます。

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

ref var begin = ref MemoryMarshal.GetArrayDataReference(array);
ref var last = ref Unsafe.Add(ref begin, array.Length);

var vectorSum = Vector256<int>.Zero;
ref var current = ref begin;

// Vector256で処理できるだけ処理
ref var to = ref Unsafe.Add(ref begin, array.Length - Vector256<int>.Count);
while (Unsafe.IsAddressLessThan(ref current, ref to))
{
    // 直接足し算できて便利
    vectorSum += Vector256.LoadUnsafe(ref current);
    current = ref Unsafe.Add(ref current, Vector256<int>.Count);
}

// Vector256をintに戻す
 var sum = Vector256.Sum(vectorSum);

// 残りの分は単純処理
while (Unsafe.IsAddressLessThan(ref current, ref last))
{
    sum += current;
    current = ref Unsafe.Add(ref current, 1);
}

Console.WriteLine(sum); // 5050

まぁforがwhileのアドレス処理になっていたり、最後にはみ出た分を処理する必要がありますが、かなり自然にSIMDを扱えているといってもいいんじゃないでしょうか。(Unsafeに慣れていれば)かなり書きやすいです。いいね。

ところで .NET 7からLINQがSIMD対応してるからこんなの書く必要ないでしょ？というと、対応してません。LINQのSIMDはint[]のAverage, int[]のMin, Max, long[]のMin, Maxのみと、かなり限定的です。これは互換性の問題などなどがあり、まぁオマケみたいなものだと思っておきましょう。必要な局面があるなら自分で用意する方が無難です。

ともあれ、.NET 7 からは手書きX86 SIMDはArm対応が漏れやすいので、極力Vectorによって抽象化されたコードで書きましょう、ということになります。どうしてもVectorじゃ書けないところだけ、仕方なく書くという感じですね。

まとめ

反響全然ないだろうなあと想定していましたが、やはり反響全然ないです！まぁでも結構面白いライブラリになったと思うので、是非使ってください。それと、Incremental Source Generatorの作り方がMemoryPackの頃よりも習熟していて、コードがかなり洗練されたものになっているので、Source Generatorの作り方として参照するならMemoryPackのコードよりもこちらのコードのほうがお薦めです。

というわけで、まだまだSource Generatorネタはいっぱいあるので、今年は大量に量産します！