諸事情あり、本年度から Zenn に移行することとなりました。暫くはマルチポストご容赦ください。
はじめに
先日 v1 がリリースされた ZLinq ですが、README に記載の通り IEnumerable<T> を実装していません。
本投稿はそれをどうにかしたい！ というモノになります。
※ 以下のベンチマーク結果は v1 を使用したものです。ZLinq v1.1 では本投稿内で頻出する Order + Take の組み合わせで標準 LINQ より処理速度が遅くなってしまう点に対処しています。
LINQ（IEnumerable）のおさらい
ZLinq の IEnumerable 実装の前に LINQ (IEnumerable) の利点について確認したいと思います。
利点は大きく２つ、
- 遅延実行
- 省メモリ（！）
です。
省メモリ！？
ZLinq はゼロアロケーションを目指した LINQ メソッド群です。それに比べて標準の LINQ は無駄なアロケーションが行われているように見えますが、これには理由があります。
標準 LINQ の方が勝るケース
以下のように特定の条件を満たしたユーザーを100名選ぶようなケースでは、標準 LINQ の方が優れた結果を残します。
[Benchmark]
public int WhereTakeLinq()
{
var ranking = arr.Where(x => x >= 0).Take(100);
return UploadToDatabase(ranking);
}
[Benchmark]
public int WhereTakeZLinq()
{
var ranking = arr.AsValueEnumerable().Where(x => x >= 0).Take(100).ToArray(); // 👈 本投稿の肝 ToArray()
return UploadToDatabase(ranking);
}
外部サービスの API は IEnumerable<T> を引数として取ることが多いので「詰め替え不要」であることは重要です。
public int UploadToDatabase(IEnumerable<int> ranking)
{
// 👇 はテスト用の適当なコードです。
int i = 0;
foreach (var item in ranking)
{
i++;
}
return i;
}
ベンチマーク結果
標準 LINQ の方がアロケーション、処理速度共に勝る結果となっています。
| Method | N | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated |
|---|---|---|---|---|---|---|---|---|
| WhereTakeLinq | 10 | 53.12 ns | 14.528 ns | 0.796 ns | 0.0124 | - | - | 104 B |
| WhereTakeZLinq | 10 | 50.66 ns | 6.689 ns | 0.367 ns | 0.0114 | - | - | 96 B |
| - | ||||||||
| WhereTakeLinq | 100 | 308.07 ns | 13.692 ns | 0.751 ns | 0.0124 | - | - | 104 B |
| WhereTakeZLinq | 100 | 332.61 ns | 33.038 ns | 1.811 ns | 0.0544 | - | - | 456 B |
| - | ||||||||
| WhereTakeLinq | 1000 | 311.63 ns | 97.130 ns | 5.324 ns | 0.0124 | - | - | 104 B |
| WhereTakeZLinq | 1000 | 334.84 ns | 33.794 ns | 1.852 ns | 0.0544 | - | - | 456 B |
| - | ||||||||
| WhereTakeLinq | 10000 | 308.82 ns | 13.124 ns | 0.719 ns | 0.0124 | - | - | 104 B |
| WhereTakeZLinq | 10000 | 335.64 ns | 44.383 ns | 2.433 ns | 0.0544 | - | - | 456 B |
| - | ||||||||
| WhereTakeLinq | 10000000 | 308.31 ns | 6.594 ns | 0.361 ns | 0.0124 | - | - | 104 B |
| WhereTakeZLinq | 10000000 | 332.69 ns | 38.366 ns | 2.103 ns | 0.0544 | - | - | 456 B |
何故なのか
この結果は IEnumerable<T> の遅延実行によるものです。標準 LINQ は「集計方法」を表わすオブジェクト（＝IEnumerable）を生成し、「集計結果」が必要なメソッドに渡すことが出来ます。
集計「方法」を渡されたメソッドは、必要になったタイミングで集計方法から「結果」を必要な数だけ取得できます。（遅延実行）
また、集計結果を保持する必要もありません。（省メモリ）
// 集計「方法」を生成し、
var ranking = arr.Where(x => x >= 0).Take(100);
// 集計「結果」が必要なメソッドに渡す。
UploadToDatabase(ranking);
対して ZLinq は IEnumerable を実装していないため、どうしても ToArray 等して集計「結果」を事前に確定しメソッドに渡す必要があります。モチロン集計結果を収める為のアロケーションも必要になります。
var ranking = arr.AsValueEnumerable()
.Where(x => x >= 0)
.Take(100)
.ToArray(); // ZLinq は「集計方法」ではなく「集計結果」を渡す必要がある。
// 「集計結果」は「集計方法」と互換性があるので渡すことが出来る。
UploadToDatabase(ranking);
メモリ消費もそうですが集計を一気に行うため、そのタイミングで CPU をガッツリ使用するという問題もあります。（スパイク）
LINQ は常に一定のメモリしか消費しない
集計「方法」は元になる要素数（N）や集計結果の数（M）の影響を受けませんが、集計「結果」は M の影響をモロに受けます。メモリ消費が結果の数が増えた分だけ上乗せされることになります。
ZLinq のゼロアロケーションを全て吹き飛ばしてしまうこの問題が、IEnumerable<T> を実装したい最大の理由です。
| Method | N | M | Mean | Error | StdDev | Gen0 | Gen1 | Allocated |
|---|---|---|---|---|---|---|---|---|
| WhereTakeLinq | 1000 | 100 | 299.1 ns | 43.31 ns | 2.37 ns | 0.0124 | - | 104 B |
| WhereTakeZLinq | 1000 | 100 | 335.3 ns | 9.05 ns | 0.50 ns | 0.0544 | - | 456 B |
| - | ||||||||
| WhereTakeLinq | 1000 | 1000 | 2,633.7 ns | 786.79 ns | 43.13 ns | 0.0114 | - | 104 B |
| WhereTakeZLinq | 1000 | 1000 | 3,118.8 ns | 181.92 ns | 9.97 ns | 0.4807 | 0.0038 | 4056 B |
| - | ||||||||
| WhereTakeLinq | 10000 | 100 | 309.8 ns | 22.35 ns | 1.23 ns | 0.0124 | - | 104 B |
| WhereTakeZLinq | 10000 | 100 | 339.7 ns | 78.87 ns | 4.32 ns | 0.0544 | - | 456 B |
| - | ||||||||
| WhereTakeLinq | 10000 | 1000 | 2,803.5 ns | 507.97 ns | 27.84 ns | 0.0114 | - | 104 B |
| WhereTakeZLinq | 10000 | 1000 | 3,098.9 ns | 195.46 ns | 10.71 ns | 0.4807 | 0.0038 | 4056 B |
ZLinq の方が勝るケース
全ての LINQ が遅延実行されるわけではありません。以下のように Order は即時実行されかつ、並び替え結果を保持しなければならない為 ZLinq に軍配が上がります。
例）スコアが高い上位100名を抽出（イメージ）
[Benchmark]
public int SortTakeLinq()
{
var ranking = arr.OrderDescending().Take(100);
return UploadToDatabase(ranking);
}
[Benchmark]
public int SortTakeZLinq()
{
var ranking = arr.AsValueEnumerable().OrderDescending().Take(100).ToArray();
return UploadToDatabase(ranking);
}
ベンチマーク結果
ZLinq の方がメモリ効率が良いですが、処理速度が大分遅くなってしまう理由は謎です。（ソートのアルゴリズム？）
| Method | N | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated |
|---|---|---|---|---|---|---|---|---|
| SortTakeLinq | 10 | 147.85 ns | 6.008 ns | 0.329 ns | 0.0362 | - | - | 304 B |
| SortTakeZLinq | 10 | 95.27 ns | 12.460 ns | 0.683 ns | 0.0248 | - | - | 208 B |
| - | ||||||||
| SortTakeLinq | 100 | 1,603.65 ns | 213.537 ns | 11.705 ns | 0.1221 | - | - | 1024 B |
| SortTakeZLinq | 100 | 844.46 ns | 205.519 ns | 11.265 ns | 0.0677 | - | - | 568 B |
| - | ||||||||
| SortTakeLinq | 1000 | 5,903.77 ns | 1,111.586 ns | 60.930 ns | 0.9766 | 0.0076 | - | 8224 B |
| SortTakeZLinq | 1000 | 10,376.86 ns | 358.087 ns | 19.628 ns | 0.0610 | - | - | 600 B |
| - | ||||||||
| SortTakeLinq | 10000 | 45,274.88 ns | 4,608.351 ns | 252.599 ns | 9.5215 | 1.1597 | - | 80224 B |
| SortTakeZLinq | 10000 | 147,498.03 ns | 13,780.986 ns | 755.382 ns | - | - | - | 600 B |
| - | ||||||||
| SortTakeLinq | 10000000 | 61,013,314.81 ns | 6,759,436.720 ns | 370,507.537 ns | 444.4444 | 444.4444 | 444.4444 | 80000423 B |
| SortTakeZLinq | 10000000 | 280,530,650.00 ns | 12,023,278.588 ns | 659,036.473 ns | - | - | - | 968 B |
IEnumerable<T> の実装
閑話休題、ZLinq の IEnumerable 実装ですが、結論は「.NET 9 だとムリだが .NET 8 なら可能」です。
ZLinq 公式からダウンロードしたプロジェクトの内、Benchmarks と ZLinq のターゲットプラットフォームから net9.0 を取り除き以下のコードを追加すると、AsEnumerable() が使えるようになります。
※ net9.0 を取り除いたのは手っ取り早く
NET9_0_OR_GREATERを消す（＝allows ref structを消す）のが目的です。実際には .NET 9 がダメなのではなく、型制約のallows ref structがとにかく重いからムリ！ って感じです。
public struct ZLinqEnumerable<T>
: IEnumerable<T>
, IEnumerator<T>
, IAsyncEnumerator<T> // async は実装しない方が良いかも
, IAsyncEnumerable<T> // 同上
{
// 具象型の場合は readonly トル
readonly IValueEnumerator<T> enumerator;
T current;
public ZLinqEnumerable(IValueEnumerator<T> enumerator)
{
this.enumerator = enumerator;
this.current = (((default)))!;
}
IEnumerator<T> IEnumerable<T>.GetEnumerator() => this;
IEnumerator IEnumerable.GetEnumerator() => this;
IAsyncEnumerator<T> IAsyncEnumerable<T>.GetAsyncEnumerator(CancellationToken cancellationToken = default) => this;
public T Current => this.current;
object IEnumerator.Current => this.current;
public bool MoveNext() => enumerator.TryGetNext(out current);
public void Dispose()
{
current = (((default)))!;
enumerator.Dispose();
}
void IEnumerator.Reset() => throw new NotSupportedException();
public ValueTask<bool> MoveNextAsync()
{
var ret = enumerator.TryGetNext(out current);
return new ValueTask<bool>(ret);
}
public ValueTask DisposeAsync()
{
Dispose();
return new(Task.CompletedTask);
}
}
拡張メソッド。
public static class ZLinqEnumerable
{
public static ZLinqEnumerable<T> AsEnumerable<T>(this IValueEnumerator<T> enumerator)
{
return new(enumerator);
}
}
テストコードとベンチマーク結果
上記の ZLinqEnumerable<T> を用いたテストコード。
[Benchmark]
public int Linq()
{
var ranking = arr.OrderDescending().Take(M);
return UploadToDatabase(ranking);
}
[Benchmark]
public int ZLinq()
{
var ranking = arr.AsValueEnumerable().OrderDescending().Take(M).ToArray();
return UploadToDatabase(ranking);
}
[Benchmark]
public int ZLinqEnum()
{
var ranking = arr.AsValueEnumerable().OrderDescending().Take(M).Enumerator.AsEnumerable();
return UploadToDatabase(ranking);
}
public int UploadToDatabase(IEnumerable<int> ranking)
{
int i = 0;
foreach (var item in ranking)
{
i++;
}
return i;
}
実行結果は以下の通り。
意図した通り、「集計結果」の数に影響を受けなくなっています。（処理速度が遅くなってしまうのは謎）
| Method | N | M | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated |
|---|---|---|---|---|---|---|---|---|---|
| Linq | 1000 | 100 | 6.945 us | 1.7554 us | 0.0962 us | 0.9766 | 0.0076 | - | 8224 B |
| ZLinq | 1000 | 100 | 10.863 us | 0.1562 us | 0.0086 us | 0.0610 | - | - | 600 B |
| ZLinqEnum | 1000 | 100 | 10.962 us | 1.5831 us | 0.0868 us | 0.0305 | - | - | 296 B |
| - | |||||||||
| Linq | 1000 | 1000 | 19.769 us | 1.8344 us | 0.1006 us | 0.9766 | - | - | 8224 B |
| ZLinq | 1000 | 1000 | 12.332 us | 0.7399 us | 0.0406 us | 0.4883 | - | - | 4168 B |
| ZLinqEnum | 1000 | 1000 | 12.794 us | 0.8273 us | 0.0453 us | 0.0305 | - | - | 296 B |
| - | |||||||||
| Linq | 10000 | 100 | 45.892 us | 3.2693 us | 0.1792 us | 9.5215 | 1.1597 | - | 80224 B |
| ZLinq | 10000 | 100 | 148.827 us | 14.4081 us | 0.7898 us | - | - | - | 600 B |
| ZLinqEnum | 10000 | 100 | 150.096 us | 2.0773 us | 0.1139 us | - | - | - | 296 B |
| - | |||||||||
| Linq | 10000 | 1000 | 60.922 us | 7.0835 us | 0.3883 us | 9.5215 | 1.1597 | - | 80224 B |
| ZLinq | 10000 | 1000 | 149.630 us | 2.2578 us | 0.1238 us | 0.4883 | - | - | 4200 B |
| ZLinqEnum | 10000 | 1000 | 148.851 us | 6.3202 us | 0.3464 us | - | - | - | 296 B |
| - | |||||||||
| Linq | 10000000 | 100 | 52,678.207 us | 5,928.5015 us | 324.9612 us | 400.0000 | 400.0000 | 400.0000 | 80001637 B |
| ZLinq | 10000000 | 100 | 266,093.017 us | 15,235.8069 us | 835.1260 us | - | - | - | 968 B |
| ZLinqEnum | 10000000 | 100 | 271,718.600 us | 100,678.2548 us | 5,518.5149 us | - | - | - | 664 B |
| - | |||||||||
| Linq | 10000000 | 1000 | 60,983.478 us | 4,386.5359 us | 240.4408 us | 444.4444 | 444.4444 | 444.4444 | 80000423 B |
| ZLinq | 10000000 | 1000 | 278,373.350 us | 14,932.8319 us | 818.5189 us | - | - | - | 4568 B |
| ZLinqEnum | 10000000 | 1000 | 271,367.583 us | 15,597.0636 us | 854.9277 us | - | - | - | 664 B |
※ とにかく処理速度が遅いので、.NET 9 をターゲットプラットフォームに追加し直して再起動、リビルドして以下を実行した結果がコチラ。
追記： ZLinq 最新版で対応済みです。詳しくは本投稿のコメント欄をご覧ください。
// ZLinq 無しでは動かないメソッドになってしまうがやむなし
[Benchmark]
public int ZLinqDedicated()
{
var ranking = arr.AsValueEnumerable().OrderDescending().Take(M);
int i = 0;
foreach (var item in ranking)
{
i++;
}
return i;
}
なにかミスってる気もしますが、実行速度は標準 LINQ の方が速い結果となりました。
（Intel CPU が悪い？ ただ、ReadMeBenchmark は ZLinq の方が速いのでテストコードの Linq の組み合わせが単純に遅い可能性）
メモリ効率に関しては ZLinqEnumerable を越えています。処理速度に関してはほぼ同じなので、遅いと言われているインターフェイス越しのメソッド呼び出しは殆ど影響を与えなかったようです。
| Method | N | M | Mean | Error | StdDev | Gen0 | Allocated |
|---|---|---|---|---|---|---|---|
| ZLinqDedicated | 1000 | 100 | 10.89 us | 2.980 us | 0.163 us | 0.0153 | 144 B |
| ZLinqDedicated | 1000 | 1000 | 12.53 us | 5.929 us | 0.325 us | 0.0153 | 144 B |
| - | |||||||
| ZLinqDedicated | 10000 | 100 | 148.66 us | 40.993 us | 2.247 us | - | 144 B |
| ZLinqDedicated | 10000 | 1000 | 152.31 us | 34.979 us | 1.917 us | - | 144 B |
| - | |||||||
| ZLinqDedicated | 10000000 | 100 | 268,417.80 us | 29,667.028 us | 1,626.150 us | - | 512 B |
| ZLinqDedicated | 10000000 | 1000 | 271,838.93 us | 18,617.717 us | 1,020.500 us | - | 512 B |
追記： 標準 LINQ の分類表
※ Visual Basic 版しか存在しないようです。
おわりに
IEnumerable<T> の実装がないと単なる配列生成メソッド群でしかないのと、（ZLinqDedicated() のベンチマークにミスが無かった場合）ref struct はメモリ削減には寄与しているが処理速度には恩恵がないという事になるので、あえて .NET 8 で止めて使うというのはアリかもしれません。
（出来れば ZLINQ_DISABLE_ALLOWS_REF_STRUCT プリプロセッサーシンボルが欲しい）
allows ref struct の影響で IEnumerable<T> の GetEnumerator()（インターフェイスへのキャストが必要）の実装が出来ないのが根本的な問題なので、InterceptsLocation を使って無理矢理なんかするとかもあり？
https://andrewlock.net/exploring-the-dotnet-8-preview-changing-method-calls-with-interceptors/
もしかしたら 👇 の様に current を参照型にして構造体を readonly にしたら処理速度あがるかも？
以上です。お疲れ様でした。