ZLinq に IEnumerable を実装したい

諸事情あり、本年度から Zenn に移行することとなりました。
Qiita にも色々と書いているのでぜひ読んでみてください。

はじめに

先日 v1 がリリースされた ZLinq ですが、README に記載の通り IEnumerable<T> を実装していません。

https://github.com/Cysharp/ZLinq

本投稿はそれをどうにかしたい！ というモノになります。

※ 以下のベンチマーク結果は 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);
}

UploadToDatabase (IEnumerable<int>)

外部サービスの 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 版しか存在しないようです。

https://learn.microsoft.com/ja-jp/dotnet/visual-basic/programming-guide/concepts/linq/classification-of-standard-query-operators-by-manner-of-execution#classification-table

おわりに

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/

readonly 化

もしかしたら 👇 の様に current を参照型にして構造体を readonly にしたら処理速度あがるかも？

https://github.com/sator-imaging/Unity-Fundamentals/blob/main/Runtime/Threading/WhenEachEnumerator.cs#L74-L102

以上です。お疲れ様でした。