はじめまして。KLab で開発をしている藤倉です。

先日デバッグ中に見つけた、LINQ の OrderBy(keySelector).First(predicate) の奇妙な挙動の話をします。

環境によって異なる OrderBy(keySelector).First(predicate) の挙動

まず次のC#のコードを見てみてください。

static bool IsEven(int i)
{
    return i % 2 == 0;
}

static int Test()
{
    var arr = new [] { 5, 8, 3, 1, 4 };
    return arr.OrderBy(x => x).First(IsEven);
}

このコードで Test() を実行すると IsEven() は何回呼び出されるでしょうか？

素朴に考えると......、

• まず OrderBy(x => x) によってリストが 1, 3, 4, 5, 8 の順に並べ替えられる
• 続いて First(IsEven) によって先頭の要素から順に IsEven() が true を返すものの探索が行われる
  • IsEven(1), IsEven(3) が false を返し、IsEven(4) が true を返すので、そこで探索が終了する

となり、IsEven() は計3回呼び出されるものと思われます。

しかしこのコードを実際にいくつかの環境で実行してみると、IsEven() の呼び出しが3回となる環境と5回となる環境がありました。

• IsEven() の呼び出し回数が3回となる環境
  • Unity 2020.3.22f1 Macスタンドアロンビルド（IL2CPP）
  • .NET Core 5.0.203
• IsEven() の呼び出し回数が5回となる環境
  • Unity 2020.3.22f1 エディタ上
  • Unity 2020.3.22f1 Macスタンドアロンビルド（Mono）
  • mono 6.12.0.125
  • .NET Core 3.1.409

IsEven() の呼び出し回数が5回となる環境では何が起こっているのでしょうか。

実装を追ってみる

とりあえず、 IsEven() の呼び出し回数が5回となる .NET Core 3.1.4 の実装を見てみます。

まず OrderBy(keySelector) の実装です。

https://github.com/dotnet/corefx/blob/v3.1.4/src/System.Linq/src/System/Linq/OrderBy.cs#L11-L12

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) =>
    new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false, null);

OrderedEnumerable<TSource, TKey> のインスタンスを生成して返しているようです。

これを踏まえて、次に First(predicate) の実装です。

https://github.com/dotnet/corefx/blob/v3.1.4/src/System.Linq/src/System/Linq/First.cs#L22-L31

public static TSource First<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    TSource first = source.TryGetFirst(predicate, out bool found);
    if (!found)
    {
        ThrowHelper.ThrowNoMatchException();
    }

    return first;
}

source.TryGetFirst() というメソッドが呼び出されているので、そのメソッドの実装を探すと IEnumerable<TSource> に対する拡張メソッドとして同じファイル中に見つかります。 https://github.com/dotnet/corefx/blob/v3.1.4/src/System.Linq/src/System/Linq/First.cs#L75-L103

private static TSource TryGetFirst<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate, out bool found)
{
    /* ...略... */

    if (source is OrderedEnumerable<TSource> ordered)
    {
        return ordered.TryGetFirst(predicate, out found);
    }

    /* ...略... */
}

これを見ると、source が OrderedEnumerable<TSource> の場合には、インスタンスメソッドの OrderedEnumerable<TElement>.TryGetFirst() を呼び出していることがわかりますので、今度はそちらを見てみましょう。

https://github.com/dotnet/corefx/blob/v3.1.4/src/System.Linq/src/System/Linq/OrderedEnumerable.cs#L72-L103

public TElement TryGetFirst(Func<TElement, bool> predicate, out bool found)
{
    CachingComparer<TElement> comparer = GetComparer();
    using (IEnumerator<TElement> e = _source.GetEnumerator())
    {
        TElement value;
        do
        {
            if (!e.MoveNext())
            {
                found = false;
                return default(TElement);
            }

            value = e.Current;
        }
        while (!predicate(value));

        comparer.SetElement(value);
        while (e.MoveNext())
        {
            TElement x = e.Current;
            if (predicate(x) && comparer.Compare(x, true) < 0)
            {
                value = x;
            }
        }

        found = true;
        return value;
    }
}

まず do { ... } while (!predicate(value)) の部分は、条件に合致しない要素を読み飛ばしているようです。 条件に合致する要素を見つけたら、続く while (e.MoveNext()) { ... } の部分では、 その後のすべての要素を走査して 条件に合致しつつソート 順がより先に来るものを探しています。

つまり predicate は（先の例で言えば IsEven() は）必ず全要素に対して呼び出されることになります。これにより .NET Core 3.1.4 で IsEven() が5回呼び出されたようです。

OrderBy(keySelector).First(predicate) の素朴に推測される挙動と、今確認した .NET Core 3.1.4 での挙動をそれぞれ簡単に自然文で書き表すと次のようになります。

• 素朴に推測される挙動
  1. まずリストをソートする
  2. リストの要素を先頭から順に走査:
     • もし要素が predicate を満たせば、その要素を返す
• .NET Core 3.1.4 での挙動
  1. （ソートは行わずに）リストの要素の中で predicate を満たす最初の要素を変数 value に代入。もし predicate を満たす要素がひとつもなければここで終了。
  2. 1 で見つけた以降のリストの要素を先頭から順に走査:
     • もし要素が predicate を満たし、かつその要素が変数 value よりもソート順で先に来るならば、変数 value にその要素を代入
  3. 変数 value を返す

.NET Core 3.1.4 以外で IsEven() の呼び出しが5回となる環境の実装は確認していませんが、同様の実装になっているのではないかと思われます。

なぜこのような実装になっているのか

.NET Core 3.1.4 ではなぜこのような実装になっているのでしょうか。

先に書いた2種類の挙動で何が異なるかを考えると、とりあえず計算量が違うということに気付きます。

素朴に推測される挙動の場合、ソートの計算量を O(n log n) とすれば、それに引っ張られて全体の計算量も O(n log n) となります。ソートの最悪計算量が O(n ^ 2) であれば、全体の最悪計算量も O(n ^ 2) となります。

一方で .NET Core 3.1.4 の実装の場合、リストを一度走査するだけで済みますから、全体の計算量は O(n) となります。

つまり .NET Core 3.1.4 の実装の方が、要素数が増えた場合の処理時間の増加をより抑えられるということになります。

なおここでは実装の確認から入ったのですが、調べてみるとこれについての issue が立っていました。

https://github.com/dotnet/runtime/issues/31554

詳細な議論はリンク先を確認して欲しいですが、まさに計算量を抑える最適化のために .NET Core 1.0 からこのような実装がされていた旨が書かれています。

.NET 5.0 でなぜこの実装は修正されたのか

.NET 5.0 以降ではこの実装は修正され、先のプログラムを実行しても IsEven() は3回しか呼び出されないようになっています。 これが修正された経緯についても先の issue を参照して欲しいですが、その内容をまとめると次のような理由によるもののようです。

• 比較的短いリストで、比較的実行コストの高い predicate を First(predicate) に渡した場合に、素朴な実装よりもむしろ遅くなる
• 副作用のある predicate を First(predicate) に渡した場合に、意図しない副作用が発生する（ただそもそも LINQ の中で副作用のあるものを使うことは避けた方がよいでしょう）

さらに言えば、結果としてこれらの点について .NET Framework と .NET Core で挙動が異なってしまっていたことも修正の理由となったようです。

他の LINQ メソッドの事情

今回取り上げたのは OrderBy(keySelector).First(predicate) でしたが、実は他にも同様に、素朴な推測とは異なった挙動になっているものがいくつかあります。 .NET 5.0 以降もそのような挙動になっている例をいくつか下記にあげておきます。

• Where(predicate1).Where(predicate2): Where(predicate) を2つつなげても、ループは2回ではなく1回しか行われず、その1回のループですべての predicate のチェックが行われます。
• Where(predicate).Select(selector): この場合も1回のループで predicate と selector の処理がまとめて行われるようになっています。
• OrderBy(keySelector).First(): 今回取り上げた例と違って、.NET 5.0 以降も First() にデリゲートを渡さない場合はやはり O(n) で処理されます。（これは先にあげたような修正理由の懸念が当てはまらないためでしょう）

おわりに

以上、デバッグ中に見つけた OrderBy(keySelector).First(predicate) の奇妙な挙動の話でした。