ハクソク

世界を動かす技術を、日本語で。

「ZLinq」.NET向けゼロアロケーションLINQライブラリ

370日前原文(neuecc.medium.com)

概要

  • ZLinqは 構造体 と ジェネリクス に基づき、 ゼロアロケーション を実現した革新的なLINQライブラリです。
  • .NET 10の全メソッド を100%カバーし、 SIMD最適化 や複数プラットフォーム対応を提供します。
  • パフォーマンス と アセンブリ肥大化回避 を両立し、既存のLINQ実装の課題を解決しました。
  • Drop-In Replacement Source Generator や テスト互換性 も確保し、既存コードの置き換えも容易です。
  • 詳細な最適化設計 やアーキテクチャの工夫についても解説します。

ZLinq v1リリースとその特徴

  • ZLinq v1 は、構造体・ジェネリクス活用により ゼロアロケーション を実現することに成功したLINQライブラリであることを発表
  • LINQ to Span, LINQ to SIMD, LINQ to Tree （FileSystem, JSON, GameObject等）などの拡張を提供すること
  • Source GeneratorによるDrop-In Replacement 機能や、.NET Standard 2.0, Unity, Godotなど 複数プラットフォーム への対応を実現
  • GitHubで 2000スター超 を獲得するなど、注目を集めていることを報告
  • 詳細は公式リポジトリ（https://github.com/Cysharp/ZLinq）で確認すること

過去のLINQ実装の課題とZLinqの優位性

  • 構造体ベースのLINQは過去にも存在したが、 実用的なものはなかった ことを指摘
    • アセンブリサイズの肥大化
    • オペレータカバレッジ不足
    • 最適化不足によるパフォーマンス問題
  • ZLinqは .NET 10の全メソッド・オーバーロードを100%カバー し、 99%の動作互換 を実現
  • SIMD最適化 や アロケーション削減以外の最適化 も実装し、多くのケースで標準LINQを上回る性能を達成すること
  • 開発者の豊富なLINQ実装経験（linq.js, UniRx, R3, SimdLinq等）や高速シリアライザ（MessagePack-CSharp, MemoryPack等）知見を融合していること

パフォーマンスとベンチマーク

  • 通常のLINQはメソッドチェーンが増えると アロケーションが増加 するが、ZLinqは 常にゼロアロケーション を維持
  • ベンチマークシナリオをGitHub Actionsで公開し、多くの実用ケースでZLinqが優位であることを検証
  • Selectの多重呼び出し や Distinct/OrderBy等の中間バッファ必須操作 で特に大きな差を実証
  • .NET 9の演算子チェーン最適化 も全て実装し、 全世代の.NET で最新最適化を享受可能
  • AsValueEnumerable() を追加するだけで既存コードをZLinq化できる利便性
  • System.Linq.Tests を移植し、9000件のテストで動作互換性を保証

Drop-In Replacement Source Generator

  • Drop-In Replacement Source Generator により、 AsValueEnumerable()さえ不要 でZLinqへの置き換えが可能
  • 置き換え範囲の制御も柔軟に行えること
  • テストコードも変更なしでZLinqに切り替えられる運用性

ValueEnumerableアーキテクチャと最適化

  • ValueEnumerable<T> は、 ref struct によるチェーンを可能にし、 IValueEnumerator<T> インターフェースを基盤とする設計
  • 型推論の制約を回避するため、 型宣言で型を明示 し、アセンブリ肥大化を防止
  • TryGetNext(out T current) 方式を採用し、 MoveNext + Current の2メソッド呼び出しを 1回に集約 して高速化
  • 構造体サイズの増大 を最小化し、チェーン時のコピーコストを抑制
  • 共変・反変非対応 だが、Span<T>との互換性や安全性を優先

TryGetNextの詳細

  • IEnumerator<T> はMoveNext()とCurrentの2操作が必要だが、ZLinqは TryGetNext で1回の呼び出しに集約
  • Rustのイテレータ設計も参考にした設計思想
  • Select実装 比較で、ZLinqは「current」フィールド不要で構造体サイズを縮小
  • 構造体チェーン が深くなってもパフォーマンスを維持

共変・反変の非対応について

  • 共変・反変 はSpan<T>と非互換であり、現代.NETでは 安全性の観点から非推奨
  • 例：配列のSpan変換でランタイムエラー発生リスク
  • ZLinqは 安全性とパフォーマンス を優先し、これらの機能を割り切っていること

TryGetNonEnumeratedCount, TryGetSpan, TryCopyToの最適化

  • TryGetNonEnumeratedCount ：元ソースが確定サイズかつフィルタなしの場合、ToArray等で 固定長配列確保 が可能
  • TryGetSpan ：連続メモリアクセス可能な場合、 SIMDやSpanベース高速処理 が実現
  • TryCopyTo ：内部イテレータによる パフォーマンス向上 を実現
  • 外部イテレータと内部イテレータ の違いを活かした最適化設計

このように、ZLinqは 構造体ベースLINQの集大成 として、 パフォーマンス・安全性・実用性・互換性 を高次元で融合した次世代LINQライブラリであることを強調することができます。

Hackerたちの意見

なんでこういう改善が.NET自体に戻せないのかな？

└

それができない理由はないと思うよ: https://github.com/dotnet/runtime/pulls API変更リクエストの公式プロセスがあるから: https://github.com/dotnet/runtime/blob/main/docs/project/api...

└

こういうものを作るような人は、.NETに統合するための官僚的な手続きにはあまり耐えられないだろうなって想像できる。

└

ZLinqはValueEnumerableという独自の列挙型に依存してるんだけど、これは構造体なんだ。これをドロップイン置き換えとして使って再コンパイルすればたぶん動くけど、大きなアプリケーションではもっと複雑になるかも。Linqメソッドの正確なシグネチャに依存しているコードがあるかもしれないし、リフレクションを使った場合には検出できないこともあって、静かに壊れちゃう可能性もある。別の列挙型を追加するのは、全体のAPIの面積を実質的に倍増させるような大きな変更になるから、時間がかかるかも。まだSpanをサポートしてないところもあるしね。それに、Linqに関してはオーバーロードの数が考慮されたデザインの決定もあった。これを.NETに追加するのは、ValueEnumerableに変換する拡張メソッドを使えばできるかもしれないけど、その列挙型のサポートがなければ、異なる列挙型の間で行き来しなきゃいけない壁のある庭みたいになっちゃう。あんまり良くないと思うけど、可能ではあるかな。

└

ブログ記事を見た感じ、ジェネリックインスタンスの爆発はコードサイズや起動時間にとって深刻な問題になりそうだけど、なんとか解決できるかもね。パフォーマンスは確かに印象的だし。今のLINQのデフォルトの動きは、実際にイテレートしている型を隠すためにIEnumerableみたいなインターフェースを積極的に使ってるから、パフォーマンスに影響が出るんだ（これがZLinqが勝てる理由の一部ね）。でも、利点もあって、例えばWhere(seq)の同じ実装をいろんなTに使えるから、イテレートするたびに独自のボディをJITやAOTコンパイルする必要がないんだ。ZLinqを見てると、クエリが複雑になるにつれてユニークなジェネリック構造体の型が爆発的に増える可能性があるみたいだけど、実際にはそれほど悪くないかもしれないね。

└

C#では参照型を使うのがよりイディオマティックだね。ある程度、バグが少ないとも言える（問題なく渡せるから）。ほとんどのコアライブラリは、値型とボクシングから始める代わりに参照型を使ってる。TaskライブラリはValueTaskを追加したけど、結構手間がかかった。逆にLINQは展開されたループやライブラリに置き換えやすいから、あまりプレッシャーがなかったんだ。将来的に何か起こるかもしれないけど、かなりの努力が必要だね。

└

いくつかの小さな破壊的変更があって、イテレーションの順序が公式のLINQ実装と必ずしも同じじゃなかったり、Sumがチェックありとなしで異なる値を返すことがある。ほとんどの人には問題ないだろうけど、微妙な破壊的変更ではあるね。

これは素晴らしいね。生産環境の.NETサービスで働いてたけど、アロケーションのせいでホットパスではLINQを避けなきゃいけなかったことが多かった。forループや他の構造を使って関数を再実装するのは、LINQのメソッドチェーンに比べて時間がかかるしエラーが起きやすかった。LINQメソッドをチェーンするのはめちゃくちゃ強力で、JSのfilter、map、reduceみたいな感じだけど、他にもいろんな演算子や最適化がある。もっと多くの言語にこういうのがあればいいのに。

└

これを使う利点は、高階関数を使うのと比べて何があるの？Rubyだとlist.map { }やselect { }ができるけど、そっちの方が自然に感じるし（特別な言語サポートがいらない）、関数のセットも豊富（group_byやchunk_whileとか）で、ユーザーが自分のメソッドを追加することもできるし（モンキーパッチが気にならなければね）。

└

いくつかの企業は、基本的にLINQを避けようとするみたいだけど、実際にはLINQを避けても大したメリットはないことが多いよね。もちろん、行列の掛け算みたいなホットパスの場合は全然意味があるけど、LINQを避けることで不快な副作用が出ることもある。コードの健全性や品質が失われるっていうね。

理論的には.NET 10がこれを時代遅れにするはずで、見出しの機能[1]は基本的にこれに関するものだよ。実際には、まあ、ヒューリスティックだから、今ちょうど特にパフォーマンスに敏感なプロジェクトにこれを追加してるところ :) 編集: それと、C#はLinqを契約として認識してるのがいいね。正しいメソッド名とシグネチャがあれば（ちゃんとあるよ）、Linqの構文が自動的に使えるようになる。自分の作ったものにもこのトリックを使えるよ（Select、Join、Whereなどのオーバーロードを追加する）もしLinqの構文が好きならね。[1]: https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotn...

└

もう少し詳しく説明してもらえる？イテレータのパフォーマンス改善については何も見当たらないんだけど。Zlinqはヒープ上でイテレータを割り当ててガベージコレクトされるペナルティを取り除くようだね。君が送ったリンクには改善について触れてるけど、どうやってLINQがヒープ割り当てを避けるのかは分からないな。

C#にはLINQを可能にする特徴があって、他の言語にはないのは何？

└

ジェネリクスを持つほとんどの言語にはLINQがある気がする。Pythonのfunctoolsやitertools、JavaScriptのlodashみたいな感じで。結局、同じアイデアの違った表現なんだよね。

└

それはコンパイラーの一部、つまりASTだよ。LINQには2つの形式があって、1つは普通のLINQ構文で「xからx.nameを選択」とかね。もう1つはラムダ式と匿名型を使ったやつ。ラムダ構文の場合、これをやればいいよ: https://www.npmjs.com/package/linq もちろん、クエリプロバイダーに対してこれを実行したいなら、式ツリーを提供するためのコンパイラーサポートが必要で、プロバイダーがそれを処理してデータベースが理解できる言語（たいていはSQL）に変換する必要があるよ。トランスパイラーみたいなものもあるみたいだけど、今の最先端がどうなってるかは分からないな: https://github.com/sinclairzx81/linqbox

└

メモリ内コレクションでの基本的なLINQは、他の言語のものとあまり変わらないよ。特別なのはEntity Frameworkで使われるLINQだね。これは式に基づいて動作して、コードをアプリケーションにコンパイルして実行時に操作できるようにするんだ。例えば、Where()に渡すラムダ式は、SQLクエリのwhere句に変換するEFクエリプロバイダーによって検査されるよ。

└

Goのメンテナはシンプルさを保ちたいのは分かるけど、これらの機能は結構役立つよね。

└

C#は唯一の選択肢じゃないけど、いくつか目立つポイントがあるね。1. 他の人のインターフェースを拡張できる。メソッドチェイニングを気にするなら、そういうのが必要だよね（代替案としては、メソッドチェイニングのための構文サポートがある一般的な関数呼び出し構文がある）。2. 言語は「コードをデータとして扱う」ことをサポートしてる。メカニズムは式ツリーだけど、メソッドチェイニングを使って計算を定義して、それを異なるバックエンドに送信できるのは本当に強力だよ。最適化ステップも含まれてるしね。3. 言語には構文シュガーの一形態としてサブ言語があって、特定の特別な構文を基本的にインラインSQLとして書けて、エディタのフルサポートがある。

└

C#はラムダを実行時に式ツリーに変換できるから、EFみたいなライブラリがdb.Products.Where(p => p.Price p.Name);みたいなコードをSQLに変換できるんだ。この能力があれば、JavaScriptのORMは革命的になるだろうね。

└

これは、同じ構文の2つの異なるAPIが傘の下にある感じだね。1: メモリ内で遅延的に動作するIEnumerable（著者の改善に似てる）って、ファーストクラス関数がある言語ならどれでもできるよ。著者のlinq.jsやJavaのストリームライブラリを見てみて（遅延だからmap/reduce/filterのチェーンとは完全に同じではないけど、一時的なストレージオブジェクトを取り除くことでパフォーマンスが向上するから、ほとんど欠点ではない）。2: IQueryableが本当に魔法の部分なんだ。特定のラッパータイプを指定することで、コンパイラはライブラリがあなたが書いた式の構文木（AST）を期待していることを知ることができる。そうすると、ライブラリはその構文木をSQLクエリに変換して、サーバーに送信して処理させることができる。だから、大きなテーブルも普通のC#を書くだけで効率的にクエリできて、SQLには触れなくて済む。ほとんどのORMでは面倒だったりインピーダンスミスマッチがあるけど、EFならコードを書けば良いSQLクエリが生成されるってかなり確信できるよ。LINQの構文はSQLにかなり近いからね。

└

（注：多くの回答がLINQ to SQLについて話しているが、ZLinqは最適化していないようだ。）イテレーター：LINQはイテレーターをサポートする任意のタイプで動作する。ほとんどの言語では、これはコレクション/配列/リストの各アイテムに対して操作を行うためにfor（foreach）ループを書ける任意のタイプだよ。（C#では、コレクションはIEnumerableインターフェースを実装する必要がある。）ラムダ関数：LINQはラムダ関数に大きく依存していて、フィルターやデータの変換/絞り込みに使われる。ほとんどの言語にも似たようなものがある。ジェネリクス：C#は「fooオブジェクトのリスト」を許可していて、「fooにキャストしなければならないオブジェクトのリスト」ではない。LINQのようなものを他の言語で実装するために明示的に必要ではないけど、型を検証するコンパイラーはオートコンプリートやIDE内の提案に役立つし、バグを避けるのにも役立つ。ジェネリック推論：C#はラムダ関数から戻り値の型を推論できて、ラムダ関数内の引数の型も推論できる。これにより、LINQ構文に型情報を装飾する必要がなくなる。例外的なケースを除いてね。だから、例えばJavascriptやRustにはLINQのようなライブラリがあるんだ。JavaもLINQのようなものをサポートしてるけど、私の限られたJavaの経験では、あまり使わなかったから本当に「使いこなす」ことができなかった。--- LINQには非常に深刻な落とし穴があることに注意してほしい。フィルターを誤って作ってしまうと、ソースコレクションを再読み込みするために高コストな操作を再実行するオーバーヘッドが発生しやすい。これを避ける最も簡単な方法は、チェーンの最後で.ToArray()または.ToList()を呼び出して、結果を一度コレクションに保存することだよ。

これいいね - 試してみるのが楽しみだ - ちなみに、私はもう15年近くdotnetのグラントをやってるんだ。得意だし、言語の使い方も知ってるし、エコシステムもわかってる。このレベルの言語への親しみは自分には無理だな。コードを読むのは（ほとんど）理解できるけど、これを思いつくことすらできなかったし、実装するなんて絶対無理だった。著者に拍手を送りたい。

これは面白いけど、どうやってゼロアロケーションを実現してるの？Funcを使ってるみたいだけど、Funcは参照型だから、これだとアロケーションが発生するよね。ILはどう見ても参照型を形成してるように見えるんだけど。

└

JITはこれを最適化できるよ。ラムダにキャプチャがなければ、確実にメモリを割り当てないってわかってる。関数のパラメータが呼び出し元のライフタイムを超えない場合も、割り当てをしないって認識できるくらい賢いと思う。

.NETは使ってないけど、LINQは本当に面白い部分だと思ってた。

これについて詳しい人、'平均的な' .NET開発者にとって何を意味するのか教えてくれない？ .NET (Core) WebアプリではLINQの呼び出しにかなり依存してるんだけど、これをZlinqの呼び出しに置き換えた方がいいのかな？それとも、例えばゲームループの終わりにガベージコレクションされるような1000個のオブジェクトにLINQ操作をしたい場合だけ役立つのかな？

└

記事の著者は、もうメンテナンスしていない linq.js について書いてるけど、誰かがフォークしたみたいだね。このライブラリは、著者が飽きたらそのうちメンテナンスされなくなると思うから、特にこのライブラリで解決したい問題がない限り、俺のウェブアプリの本番コードには使わないかな。「速いから」ってだけで全部置き換えるのは良くない気がする。

└

つまり、パフォーマンスの問題を見つけて、それを手動で解決できる（例えば、列挙可能なものを使う代わりにforループや事前に確保したバッファを使うなど）なら、コードをクリーンに保つために役立つかもしれないってこと。これはQueryable/Enumerable拡張に対するValueTaskのようなもので、ref構造体に対する構造体みたいな感じ。もしTaskからValueTaskに切り替えることで大きなメリットを感じるタイプの開発者なら、これも役立つと思うよ。

└

おそらく、これをEF CoreのLINQ式で使うべきではないよ。そうすると、テーブル全体をマテリアライズすることになっちゃうから！

今の時代、C++の式テンプレートを覚えてる人いるかな。昔、計算のストリームやマップを連結するための式テンプレートのライブラリを作ったことがあるんだけど、サブストリームをメモリに完全に実現する必要がないっていう、要するにUnixパイプラインの古いアイデアみたいな感じだった。書くのはすごく楽しかったけど、コンパイラーエラーのデバッグは全然楽しくなかった。C++のテンプレート言語には静的型付けがないから、エラーが式ツリーのかなり深いところで発生しちゃうんだよね。式ツリーはコンパイル時に処理されてインライン化されるから、ランタイムでのオーバーヘッドはほとんどない。GCCのインライン化とベクトル化にはすごく感心したよ。特に、なぜベクトル化できなかったのかを説明するメッセージが良かった。

これって俺だけ？それともこれ、誇大広告のケースじゃない？アロケーションの最大の原因の一つはラムダキャプチャなんだよね。例えば、こんな感じで var myPerson = people.First(x=>x.Name==myPersonName); って書くと、myPersonName変数をキャプチャするファントムオブジェクトがアロケートされて、そのためにデリゲートがアロケートされて、First()メソッドに渡されるから、呼び出しごとのアロケーション数が最低でも2になるんだ。ZLinqがこれに対して何かしているとは思えないんだけど。