CoreFXで進化したLINQのお話
昔々のお話
こんなライブラリを作った記憶があったのですが、最近 C# パフォーマンスヤクザ[要出典]になりかけている僕に、 IReadOnlyCollection<T>
を使用することで、 リスト→LINQ→ToArray といった処理を効率化できるのではないだろうかと考えて、このライブラリをちゃんと書き直すぞ!と考えていた矢先、 CoreFX の System.Linq.Enumerable
が進化していることに気づいたのでまとめておきます。
なお、ここで紹介する内容は、 .NET Core 1.0 に含まれており、 .NET Core App で使うことができます。 .NET Standard 1.6 以上である必要があるので、 .NET Framework のほうで使えるようになるのは 4.6.3 になると思います。先が長い。
追記: .NET Framework 4.7.1 では IListProvider
だけ導入されました。とはいえ、配列や List
に対する最適化が入っていないので、変化はないでしょう。 IPartition
は最後の例が示すように互換性に問題があるので .NET Framework には導入されないかもしれません。
追加されたメソッド
- Append
- Prepend
Append は最後に 1 要素追加、 Prepend は最初に 1 要素を追加するメソッドです。こんな感じに使えます。
var e = new[] { 1 }.Prepend(0).Append(2); foreach (var x in e) Console.WriteLine(x); // 0 // 1 // 2
これで .Concat(new[] { hoge })
とか書かなくてよくなりますね。やった。
最適化のお話
ではメインのお話行きましょう。今まで LINQ は「書きやすいけど遅い」という問題が付き物でした。原因は主に以下の 2 つだと考えています。
IEnumerator<T>
を愚直にラップしまくっていく挙動をするので、1回MoveNext
を呼び出すだけで深いコールスタックが生まれる(しかもインターフェイスメソッド)array.Select(x => ...).ToArray()
のような出力される配列の長さが明らかな操作であっても、長さ 4 の配列を確保して足りなくなったら 2 倍して…という挙動をする
今までも対策がされていなかったわけではなく、1については、 Where
と Select
はよく使われるので、専用の Iterator
が用意されていましたし、2については ICollection<T>
ならば Count
プロパティを使うということをしていました。とはいえこれだけでは不十分なのは2で例に挙げたものからも明らかだと思います。
そこで、新たに導入されたのが、 IIListProvider
と IPartition
です。まずは定義を見てみましょう。
// Copyright (c) .NET Foundation and Contributors /// <summary> /// An iterator that can produce an array or <see cref="List{TElement}"/> through an optimized path. /// </summary> internal interface IIListProvider<TElement> : IEnumerable<TElement> { /// <summary> /// Produce an array of the sequence through an optimized path. /// </summary> /// <returns>The array.</returns> TElement[] ToArray(); /// <summary> /// Produce a <see cref="List{TElement}"/> of the sequence through an optimized path. /// </summary> /// <returns>The <see cref="List{TElement}"/>.</returns> List<TElement> ToList(); /// <summary> /// Returns the count of elements in the sequence. /// </summary> /// <param name="onlyIfCheap">If true then the count should only be calculated if doing /// so is quick (sure or likely to be constant time), otherwise -1 should be returned.</param> /// <returns>The number of elements.</returns> int GetCount(bool onlyIfCheap); } internal interface IPartition<TElement> : IIListProvider<TElement> { IPartition<TElement> Skip(int count); IPartition<TElement> Take(int count); TElement TryGetElementAt(int index, out bool found); TElement TryGetFirst(out bool found); TElement TryGetLast(out bool found); }
corefx/Partition.cs at release/1.1.0 · dotnet/corefx · GitHub
このインターフェイスを実装しているイテレーターは、インターフェイスのメンバーにある処理が普通にループを回すのに比べて省略可能だということを表します。これによって操作が最適化され、可能な場合には ElementAt
, Last
が O(1) になったり、 ToArray
や ToList
で配列のアロケーション回数を減らしたりできます。
簡単な例を紹介します。
var e = Enumerable.Range(0, 100) .Select(x => { Console.WriteLine(x); return x; }) .Skip(95); foreach (var _ in e);
このコードを .NET Framework 4.6.2 で実行すると、 0 から 99 までコンソールに出力されますが、 .NET Core で実行すると 95 から 99 までしか出力されません。これは、 RangeIterator
が IPartition
を実装しており、 Select
で SelectIPartitionIterator
が使用され、うまく Skip
を省略することに成功しています。 IPartition
は Range
のほか、 Repeat
や OrderBy
の結果が実装しています。もちろん IList<T>
に Select
, Skip
, Take
を実行した場合にも IPartition
を実装した戻り値が生成されます。
また、 IIListProvider
単体は、 Distinct
や Union
など、すべて Set
に突っ込んだ結果を配列に移す操作がショートカットできる場所や、 Append
, Prepend
, Concat
のように ToList
を効率化できる場所に使用されています。
まとめ
Append
, Prepend
, Concat
が IPartition
を特別扱いしないのが気に食わないですが、とにかく、何も考えずに LINQ を使っても圧倒的無駄な処理にならずに済むようになるのはとても大きいと思います。というわけで早く .NET Framework 4.6.3 出してくれ。