アジョブジ星通信

進捗が出た頃に更新されるブログ。

CoreFXで進化したLINQのお話

昔々のお話

こんなライブラリを作った記憶があったのですが、最近 C# パフォーマンスヤクザ[要出典]になりかけている僕に、 IReadOnlyCollection<T> を使用することで、 リスト→LINQ→ToArray といった処理を効率化できるのではないだろうかと考えて、このライブラリをちゃんと書き直すぞ!と考えていた矢先、 CoreFXSystem.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については、 WhereSelect はよく使われるので、専用の Iterator が用意されていましたし、2については ICollection<T> ならば Count プロパティを使うということをしていました。とはいえこれだけでは不十分なのは2で例に挙げたものからも明らかだと思います。

そこで、新たに導入されたのが、 IIListProviderIPartition です。まずは定義を見てみましょう。

// 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) になったり、 ToArrayToList で配列のアロケーション回数を減らしたりできます。

簡単な例を紹介します。

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 までしか出力されません。これは、 RangeIteratorIPartition を実装しており、 SelectSelectIPartitionIterator が使用され、うまく Skip を省略することに成功しています。 IPartitionRange のほか、 RepeatOrderBy の結果が実装しています。もちろん IList<T>Select, Skip, Take を実行した場合にも IPartition を実装した戻り値が生成されます。

また、 IIListProvider 単体は、 DistinctUnion など、すべて Set に突っ込んだ結果を配列に移す操作がショートカットできる場所や、 Append, Prepend, Concat のように ToList を効率化できる場所に使用されています。

まとめ

Append, Prepend, ConcatIPartition を特別扱いしないのが気に食わないですが、とにかく、何も考えずに LINQ を使っても圧倒的無駄な処理にならずに済むようになるのはとても大きいと思います。というわけで早く .NET Framework 4.6.3 出してくれ。