LINQ のコツ 2021 年版 (2)
この記事は 2021 年現在の LINQ のコツを，基本的なところから最新の応用例まで書いていく連載です．背景や予定に関しては， 前回の記事 のまえがきをご覧ください．
2. materialization
今回は LINQ の materialization（マテリアライゼーション） についてです．
materialization とは，実体化などという意味で， LINQ においてはとくに要素の評価戦略が lazy な（またはその可能性のある）シーケンスから，すべての要素が計算済みの具体的なコレクションを得るような操作のことを指すことが多いです．例としては， ToArray などの操作がそれにあたります．
2.1. 実行と評価のタイミングを整理する
これ以降混乱するといけないので，もういちど評価戦略についてのおさらいと，用語の再定義をします．操作自体の実行と，それぞれの要素の評価との 2 つのタイミングが組み合わさるため，一般的な lazy/eager の区別よりも少し複雑なものになっています．
前回の記事で扱った 遅延評価 (lazy evaluation) とは，それぞれの要素の評価をその要素が必要になるまで保留するという評価戦略でした． 実行タイミングとしては遅れて実行されるので，遅延実行 (deferred execution) と呼ばれます．
この遅延実行 (deferred execution) の評価戦略にはもうひとつ， 先行評価 (eager evaluation) と呼ばれるものがあります．これは，要素の評価自体はその場で行わないけれども，ひとつめの要素を評価する際にほかの要素もすべて評価してしまうようなものです．
具体的には，要素をグループ化する GroupBy や並べ替えを行う OrderBy などの操作がこれにあたります．
そして，実行タイミングには遅延実行の反対である 即時実行 (immediate execution) があります．その操作の時点でただちにすべての評価を済ませるような， ToArray などの操作がこれに分類されます．
まとめると下記のような分類になります．
- 即時実行 (immediate execution) : すぐに実行
- 遅延実行 (deferred execution) : 必要になるまで遅らせて実行
- 遅延評価 (lazy evaluation) : 必要になった要素だけ評価し，それ以外の要素の評価は遅らせる
- 先行評価 (eager evaluation) : ひとつめの要素が評価されるタイミングで，すべての要素を評価する
前回の記事 では，このうちの deferred execution の lazy evaluation について考えていたことになります．
2.2. 各 LINQ メソッドの実行と評価のタイミング
.NET 6 までの LINQ のメソッドについて，実行と評価のタイミングを表にまとめます． 評価については
- immediate: ただちに実行
- deferred / lazy : 遅延実行かつ各要素が遅延評価
- deferred / eager : 遅延実行だがすべての要素を同時に評価
の 3 つの分類にしています．
| method | execution / evaluation |
|---|---|
| Aggregate | immediate |
| Any / All | immediate |
| Append / Prepend | deferred / lazy |
| Average | immediate |
| Chunk | deferred / lazy (size 分だけ先行評価) |
| Concat | deferred / lazy |
| Contains | immediate |
| Count | immediate |
| DefaultIfEmpty | deferred / lazy |
| Distinct | deferred / lazy |
| ElementAt / ElementAtOrDefault | immediate |
| Except | deferred / lazy (2 つめの引数は最初の要素の評価時にすべて評価) |
| First / FirstOrDefault | immediate |
| GroupJoin | deferred / lazy (inner は最初の要素の評価時にすべて評価) |
| GroupBy | deferred / eager |
| Intersect | deferred / lazy (2 つめの引数は最初の要素の評価時にすべて評価) |
| Join | deferred / lazy (inner は最初の要素の評価時にすべて評価) |
| Last | immediate |
| Lookup | immediate |
| Min/Max | immediate |
| OfType | deferred / lazy |
| OrderBy | deferred / eager |
| Range | deferred / lazy |
| Repeat | deferred / lazy |
| Reverse | deferred / eager |
| Select | deferred / lazy |
| SelectMany | deferred / lazy |
| SequenceEqual | immediate |
| Single / SingleOrDefault | immediate |
| Skip | deferred / lazy |
| Sum | immediate |
| Take | deferred / lazy |
| ToArray | immediate |
| ToList | immediate |
| ToDictionary | immediate |
| ToHashSet | immediate |
| Union | deferred / lazy |
| Where | deferred / lazy |
| Zip | deferred / lazy |
こうして並べてみると，少し法則が見えてきます．
IEnumerable<T>を返すメソッドはほとんど遅延実行かつ遅延評価 (例:Select,Where,OfType)boolなど，まったく違う型を返すメソッドは即時実行 (例:Sum,Any,First)- 遅延実行かつ先行評価なのは
GroupByとReverseのみ- これらは原理的にひとつめの要素を知るためにすべての要素を評価しなければならない
List<T>やDictionary<TKey, TValue>などの具体的なコレクションを返すメソッドは即時実行 (例:LookUp,ToHashSet,ToArray)- この操作を materialize と呼ぶ
2.3. materialization の基本
前回の記事 で見たように， LINQ の基本は遅延評価 (lazy) であり，一度評価した結果も保持しないのでした． これはパフォーマンス上有利に働く場面が多いのですが，要素を複数回列挙(multiple enumeration) したい場合には，要素の評価も複数回おこなわれてしまいます．
2.3.1. 例: lazy な要素の multiple enumeration
void Main()
{
IEnumerable<int> seq = GenerateSequence();
// 5 以下の数のみになるようにフィルタし，各要素を string に変換する
IEnumerable<string> stringSeq = seq
.Where(x => x <= 5)
.Select(x => x.ToString());
// 2 回の foreach と Count() でそれぞれ要素の評価が行われる
foreach (string s in stringSeq) Console.WriteLine($"foreach1: {s}");
foreach (string s in stringSeq) Console.WriteLine($"foreach2: {s}");
Console.WriteLine($"count: {stringSeq.Count()}")
}
// 1 から 10 までの lazy なシーケンスをつくる
IEnumerable<int> GenerateSequence()
{
foreach (var x in Enumerable.Range(1, 10))
{
Console.WriteLine($"enumerate {x}");
yield return x;
}
}
2.3.2. 要素の再評価を避けるための materialization
複数回の列挙の際に，要素の評価を 1 回で済ませるためには
- 一度評価した要素の評価結果を覚えておく
- いったん配列などに materialize したうえで利用する
といった方法が考えられます．
1 つめの「評価結果を覚えておく」という方法ですが，これは便利な場面もあるものの，場合によっては大きなメモリ領域を必要としたり，実装が複雑化してしまいます．また，標準の LINQ はこのような機構を提供していません．
一方 materialize する方法では，実際に配列などを作ってしまうという単純な手法のため，実現も容易でハマりどころもあまりありません．また，標準の LINQ で ToArray などの materialize のための操作が提供されているので，こちらがよく使われる一般的な方法です．
2.3.3. 例: ToArray による materialize
void Main()
{
IEnumerable<int> seq = GenerateSequence();
// 5 以下の数のみになるようにフィルタし，各要素を string に変換する
string[] stringSeq = seq
.Where(x => x <= 5)
.Select(x => x.ToString())
.ToArray(); // この時点ですべての要素が評価される
// これ以降要素の再評価は発生しない
foreach (string s in stringSeq) Console.WriteLine($"foreach1: {s}");
foreach (string s in stringSeq) Console.WriteLine($"foreach2: {s}");
Console.WriteLine($"count: {stringSeq.Count()}")
}
// 1 から 10 までの lazy なシーケンスをつくる
IEnumerable<int> GenerateSequence()
{
foreach (var x in Enumerable.Range(1, 10))
{
Console.WriteLine($"enumerate {x}");
yield return x;
}
}
このように， materialization は場合によっては強力なパフォーマンス改善手法となります．
2.4. materialization のパフォーマンスへの影響
materialization は LINQ を使う上でぜひおさえておきたいテクニックですが，利用は最小限にとどめ，濫用は避けるべきです． ここでは， materialization のパフォーマンスへの影響を調べます．
2.4.1. 例: materialization の濫用
たとえば，つぎのような実装では materialization の濫用によってパフォーマンスが著しく低下します．
void Main()
{
IEnumerable<int> seq = GenerateSequence();
// 5 以下の数のみになるようにフィルタし，各要素を string に変換する
string[] stringSeq = seq
.ToArray() // materialize!
.Where(x => x <= 5)
.ToArray() // materialize!
.Select(x => x.ToString())
.ToArray(); // materialize!
// これ以降要素の再評価は発生しない．．．が．．．
foreach (string s in stringSeq) Console.WriteLine($"foreach1: {s}");
foreach (string s in stringSeq) Console.WriteLine($"foreach2: {s}");
}
// 1 から 100000 までの lazy なシーケンスをつくる
IEnumerable<int> GenerateSequence()
{
foreach (var x in Enumerable.Range(1, 100000))
{
Console.WriteLine($"enumerate {x}");
yield return x;
}
}
この場合，本当に必要なのは最後の ToArray だけで，途中の ToArray は必要ありません．
2.4.2. 例: materialization の適正な使用
void Main()
{
IEnumerable<int> seq = GenerateSequence();
// 5 以下の数のみになるようにフィルタし，各要素を string に変換する
string[] stringSeq = seq
.Where(x => x <= 5)
.Select(x => x.ToString())
.ToArray(); // 最後に一度だけ materialize
// これ以降要素の再評価は発生しない．
foreach (string s in stringSeq) Console.WriteLine($"foreach1: {s}");
foreach (string s in stringSeq) Console.WriteLine($"foreach2: {s}");
}
// 1 から 100000 までの lazy なシーケンスをつくる
IEnumerable<int> GenerateSequence()
{
foreach (var x in Enumerable.Range(1, 100000))
{
Console.WriteLine($"enumerate {x}");
yield return x;
}
}
このように，基本的に materialization は利用の直前だけで十分です． また，何度も列挙を行わない場合はそもそも materialization の必要がありません．
2.4.3. materialization のベンチマーク
では materialization がどのくらいパフォーマンスに影響を与えるのか，測定してみましょう．
下記のようにベンチマーク用のコードを用意します． このコードは GitHub に置いてあります．
class Program
{
static void Main(string[] args)
{
var config = new ManualConfig()
.AddJob(Job.ShortRun)
.AddExporter(MarkdownExporter.GitHub)
.AddDiagnoser(MemoryDiagnoser.Default)
.AddLogger(ConsoleLogger.Default)
.AddColumnProvider(DefaultColumnProviders.Instance);
BenchmarkRunner.Run<Benchmark1>(config);
}
}
public class Benchmark1
{
private TestData[] _source;
private readonly Consumer _consumer = new();
[GlobalSetup]
public void Setup()
{
// 10万件のテストデータを用意
_source = GenerateTestData().Take(100000).ToArray();
}
// materialize しない
[Benchmark(Baseline = true)]
public void WithoutMaterialize()
{
var results = _source
.Where(x => x.Name == "taro")
.Select(x => (x.Id, x.Name.ToUpper()))
.Where(x => x.Id > 100)
.Select(x => x.Id);
// 2 回 results を使う
results.Consume(_consumer);
results.Consume(_consumer);
}
// 適正な materialize
[Benchmark]
public void MaterializeOnce()
{
var results = _source
.Where(x => x.Name == "taro")
.Select(x => (x.Id, x.Name.ToUpper()))
.Where(x => x.Id > 100)
.Select(x => x.Id)
.ToArray();
// 2 回 results を使う
results.Consume(_consumer);
results.Consume(_consumer);
}
// materialize の濫用
[Benchmark]
public void MaterializeMany()
{
var results = _source
.ToArray()
.Where(x => x.Name == "taro")
.ToArray()
.Select(x => (x.Id, x.Name.ToUpper()))
.ToArray()
.Where(x => x.Id > 100)
.ToArray()
.Select(x => x.Id)
.ToArray();
// 2 回 results を使う
results.Consume(_consumer);
results.Consume(_consumer);
}
private static IEnumerable<TestData> GenerateTestData()
{
Random random = new Random();
var names = new[] { "foo", "bar", "hanako", "taro", "jiro", "kyoko" };
int id = 0;
while (true)
yield return new TestData(++id, names[random.Next(0, names.Length - 1)]);
}
private record TestData(int Id, string Name);
}
ベンチマークの結果は下記のようになります．
| Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------------- |---------:|----------:|----------:|------:|--------:|---------:|---------:|---------:|----------:|
| WithoutMaterialize | 3.622 ms | 0.1726 ms | 0.0095 ms | 1.00 | 0.00 | 601.5625 | - | - | 1,236 KB |
| MaterializeOnce | 2.005 ms | 0.1706 ms | 0.0093 ms | 0.55 | 0.00 | 375.0000 | 42.9688 | - | 836 KB |
| MaterializeMany | 5.197 ms | 6.3204 ms | 0.3464 ms | 1.43 | 0.09 | 492.1875 | 492.1875 | 335.9375 | 2,818 KB |
まず，materialize をまったくしないものでは 3.622 ms かかっており，メモリは 1236KB 消費しています． 次に，適正に materialize を行ったものでは， 2.005ms になっており，メモリも 836KB とパフォーマンスが良くなっています． 逆に，materialize を濫用したものでは 5.197ms もかかってしまっていて，メモリ消費量も多くなっています．
このように， materialize をただしく行うことで， LINQ を使った処理のパフォーマンスを改善することができます． また， materialize は注意深く行わないと，逆にパフォーマンスが低下します．
2.4. materialization のまとめ
ポイントをまとめると下記のようになります．
- LINQ の評価タイミングにはいろいろなものがある
- 遅延評価の欠点を補うために materialization を活用しよう
- materialization の濫用は厳禁
次回の記事では，SelectMany の活用について書く予定です．