.NET 5におけるOrderBy(keySelector).First(predicate)の計算量が増える破壊的変更と、それから考える.NET 5の立ち位置

『.NET 5は、.NET Core 3.1の次期バージョンであると同時に、.NET Framework 4.8の移行先でもある。』

そんなことを[.NET 5の破壊的変更リスト一覧](https://docs.microsoft.com/en-us/dotnet/core/compatibility/5.0)にある「[Complexity of LINQ OrderBy.First{OrDefault} increased](https://docs.microsoft.com/en-us/dotnet/core/compatibility/core-libraries/5.0/orderby-firstordefault-complexity-increase)」から感じました。

この投稿では、その破壊的内容と背景を紹介します。

# 破壊的変更の概要

.NET 5の破壊的変更である「[Complexity of LINQ OrderBy.First{OrDefault} increased](https://docs.microsoft.com/en-us/dotnet/core/compatibility/core-libraries/5.0/orderby-firstordefault-complexity-increase)」の概要説明文は以下の通りです。

> The implementation of `OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>)` and `OrderBy.FirstOrDefault
<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>)` has changed, resulting in increased complexity for the operation.


（.NET Core 3.1から比較し）`OrderBy(keySelector).First(predicate)`などの実装が変わり、計算量が増えた、と。

「計算量が増えた」

これだけ読むと、何事かとちょっとびっくりしますよね。

# 以前の実装と計算量

まず`OrderBy(keySelector)`の計算量が.NET Coreではどうなっていたか把握しましょう。

ソートを行う処理では、計算量がO(n log n)かかりますよね。そして、`OrderBy(keySelector)`メソッドはソートを行うメソッドです。`OrderBy(keySelector)`メソッドの結果を列挙したら、その計算量はO(n log n)です。（C#に慣れている方はご存知の通り、`OrderBy(keySelector)`メソッドを呼び出したタイミングでソート処理がされるわけではなく、`OrderBy(keySelector)`の結果を列挙したタイミングで、ソート処理がされることに注意してください）

ところが.NET Coreでは、`OrderBy(keySelector)`の後に`First()`や`First(predicate)`がきた場合、なんとO(n)で計算できるような実装が行われていました。

`OrderBy(keySelector).First()`の呼び出しを考えてみましょう。直接的な意味としては、「ソートした後、最初の要素を取得」しています。ということは、「一番小さい要素」を取得できればいいですね。であるのならば、この二つのメソッド呼び出しが連続する場合、ソート処理をする必要はありません。「全要素を列挙して、一番小さいもの」を取得すればいいですね。これならば、O(n log n)は必要なくてO(n)で計算できてしまいます。`OrderBy(keySelector).First()`と連続した呼び出しの場合、.NET Coreでは、ソートの処理を行っていません。（詳しくはこちらの「[.NETや.NET CoreのOrderBy(keySelector).First()はO(n log n)でなくてO(n)な件](https://qiita.com/RyotaMurohoshi/items/5b515bf2ee544cc1b016)」を読んでみてください）

では次に、`OrderBy(keySelector).First(predicate)`の呼び出しを考えてみましょう。意味としては、「ソートした後、条件を満たす最初の要素を取得」しています。ということは、「全要素を列挙して、predicateの条件をみたす内、一番小さいもの」を取得すればいいですね。これを実現するためには、全要素を一巡列挙するだけで良いので、ソートする必要はありません。こちらも、O(n log n)は必要なくてO(n)で計算できそうです。こちらも、.NET Coreでは、ソートの処理を行っていませんでした。

このように、.NET Coreの`OrderBy(keySelector)`と`First()`の連続呼び出し、`OrderBy(keySelector)`と`First(predicate)`の連続呼び出しでは、特別な工夫をしています。

---

ところで、.NET Coreの`OrderBy(keySelector).First(predicate)`の実装には注意点があります。

それは、「.NET Coreの実装では、必ず全ての要素に対して、引数のpredicateを適用する」という点です。

もし仮に、`OrderBy(keySelector).First(predicate)`の実装が.NET Coreの実装と異なり、「シンプルにソートしたものの最初の要素を取得」していた場合を考えます。この場合、ソートでO(n log n)の計算量がかかりますが、一方でpredicateを適用するのは必ずしも全ての要素とは限りません。ソートした後、predicateを満たす最初の要素が見つかったタイミングで、後続の要素へ適用はされません。「1要素にのみ、predicateを適用する」ということもありえますし、「2要素にのみ、predicateを適用する」こともありえますし、「全ての要素に、predicateを適用する」こともありえます。

.NET Coreの`OrderBy(keySelector).First(predicate)`の実装、「必ず全ての要素に対して、引数のpredicateを適用する」は違和感を覚える人もいるかもしれません。内部実装とその意図を知っていないと、混乱するでしょう。

---

一方で.NET Frameworkです。

.NET Frameworkでは、`OrderBy(keySelector).First(predicate)`の実装は、「シンプルにソートしたものの最初の要素を取得」と言う実装でした。ソートした後、predicateを満たす最初の要素が見つかったタイミングで、後続の要素へ適用はされません。「1要素にのみ、predicateを適用する」ということもありえますし、「2要素にのみ、predicateを適用する」こともありえますし、「全ての要素に、predicateを適用する」こともありえます。

O(n log n)だったわけです。

---

まとめると

* .NET Coreの`OrderBy(keySelector).First(predicate)`の実装
    * O(n)で処理される
    * 必ず全ての要素に引数のpredicateを適用する必要がある
* .NET Frameworkの`OrderBy(keySelector).First(predicate)`の実装
    * O(n log n)で処理される
    * 引数のpredicateを適用されるのは、最初の1つだけかもしれないし、2つかもしれないし、n個すべてかもしれない

となります。

# .NET Coreの最適化の実装の問題点

.NET Coreの`OrderBy(keySelector).First(predicate)`コードは最適化がされていて、一見とても良さそうですね。

しかし、.NET Frameworkから.NET Coreに移行した場合、問題になることがあります。それは「必ず全ての要素に引数のpredicateを適用する必要がある」という点です。

次のコードは、https://github.com/dotnet/runtime/issues/31554 より、コードフォーマットを変えたコードです。

```csharp
// これはLINQ中に副作用のあるメソッドを呼んでいる良くないコード
var account = accounts
    .OrderBy(x => x.UsageCount)
    .FirstOrDefault(x => x.TryReserve(token));
```

このコード中、`TryReserve`メソッドは副作用のあるメソッドです。そして、このコードを.NET Frameworkから.NET Coreに移行した時に問題が発生します。


.NET Frameworkの場合：

```
accountsのUsageCountが少ない人からTryReserveを試みて、一人でも成功したらそこで処理が終了。
予約ができるのは一要素もしくはどの要素も予約を行わない。
accountにはUsageCountが最小の要素が代入される。

```

.NET Coreの場合：

```
accounts全ての要素がTryReserveを試みる。
予約可能な要素が全て予約できてしまう。
accountにはUsageCountが最小の要素が代入される。
```

このようにこのコードを.NET Frameworkから.NET Coreに移行した時に、「全ての要素が予約を試みてしまい、予約可能な要素が全て予約できてしまう。」という問題が発生しまいますね。

私としてはこのコードは良くないコードだと思います。「副作用があるような処理をLINQの中で使うべきでない」からです。

良くないコードではあるのですが、実プロダクトとしてすでにこのようなコードがあり、移行した際にこのような問題が起こる可能性もあるのは確かです。

# 破壊的な変更の内容と理由

ここでやっと、.NET 5での`OrderBy(keySelector).First(predicate)`の実装の破壊的な変更内容の紹介です。

NET 5での`OrderBy(keySelector).First(predicate)`は、.NET Core 3.1までの「O(n)で処理され、必ず全ての要素に引数のpredicateを適用する必要がある」実装ではなくなりました。「O(n log n)で処理される、引数のpredicateを適用されるのは、最初の1つだけかもしれないし、2つかもしれないし、n個すべてかもしれない」というシンプルな実装に変わりました。.NET Frameworkと同じ実装方針になったわけです。

計算量だけで言うと、O(n)から、O(n log n)に増えました。

「計算量が増えた」というよりも、「工夫していた実装を、シンプルで素直な実装に戻した」とも言えます。

「[Complexity of LINQ OrderBy.First{OrDefault} increased](https://docs.microsoft.com/en-us/dotnet/core/compatibility/core-libraries/5.0/orderby-firstordefault-complexity-increase)」の理由の説明には、以下のようにあります。

> The benefit of invoking the predicate fewer times outweighs a lower overall complexity, so the implementation that was introduced in .NET Core 1.0 was reverted. For more information, see this dotnet/runtime issue.

なるほど「predicate」の呼び出し回数を少なくするメリットが、全体的な計算量を下げることを上回ったと。詳しくは、こちらの「[dotnet/runtimeのissue](https://github.com/dotnet/runtime/issues/31554)」を参考にとあります。先に紹介したコードは、このissueの概要で説明されているコードです。

.NET 5は、.NET Core 3.1の次期バージョンであると同時に、.NET Framework 4.8の移行先でもあります。もし仮に、「.NET 5の実装が、.NET Core 3.1と同じだったら」を想像しましょう。.NET Framework 4.8から.NET 5に移行した時に、先に紹介した問題が発生してしまう可能性は確かにあります。

パフォーマンス最適化はなくなるが、.NET 3.1から.NET 5で破壊的な変更を行い、.NET Framework 4.8と同じような挙動にする、というのにも納得できます。

---

この破壊的変更を行っている「[Pull Requestの説明](https://github.com/dotnet/runtime/pull/36643)」は以下の通りです。

> The optimization removes the O(N log N) cost of the OrderBy. But it can result in executing the predicate passed to First{OrDefault} more than in .NET Framework; it would always execute it N times, whereas in .NET Framework it would execute it <= N times. Developers have expressed concern about the change, in particular when using a relatively expensive predicate on a relatively short list, or when unadvisedly relying on side-effecting predicates.

> This optimization has been in .NET Core since 1.0. If the original optimization is considered breaking from .NET Framework, then undoing it is breaking, too.



# 自分の意見

最後に自分の意見をいくつか述べたいと思います

* `OrderBy(keySelector).First()`で最適化がかかるのは、いいと思う
* けど↑のコードは自分じゃ書かないし、コードレビューなどの機会では、MinByなどを作って使うように指摘すると思う
* .NET Coreの`OrderBy(keySelector).First(predicate)`の最適化、あんまり好きじゃない。予測・期待している挙動と違うから
* こちらも↑のコードは自分じゃ書かないし、コードレビューなどの機会では、Whereと共に、MinByを使うように指摘すると思う
* 副作用のあるコードをLINQで書くな！副作用あるなら、foreachしてくれ！
* .NET 5は.NET Framework 4.8の移行先でもあるので、結構気を遣うところもあるのかなーと思う
* パフォーマンスのメリットよりも、予期しにくい挙動でバグを生む方がこわいなー
* 逆に.NET Core 3.1からの破壊的な変更になってしまうという側面もあるよなーとも思う
   * がしかし、全ての要素にpredicateを適用することに依存したコードってよくないよね
   * それから`OrderBy(keySelector).First()`ってそもそもそんなに書く機会ないよね？MinBy作ろ？使お？ね！
* .NETのコアライブラリ、いい加減MinBy/MaxByいれない？
* コアライブラリの挙動の破壊的な変更、難しいなー