『.NET 5は、.NET Core 3.1の次期バージョンであると同時に、.NET Framework 4.8の移行先でもある。』
そんなことを.NET 5の破壊的変更リスト一覧にある「Complexity of LINQ OrderBy.First{OrDefault} increased」から感じました。
この投稿では、その破壊的内容と背景を紹介します。
破壊的変更の概要
.NET 5の破壊的変更である「Complexity of LINQ OrderBy.First{OrDefault} increased」の概要説明文は以下の通りです。
The implementation of
OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>)andOrderBy.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)な件」を読んでみてください）
では次に、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 より、コードフォーマットを変えたコードです。
// これは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」の理由の説明には、以下のようにあります。
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」を参考にとあります。先に紹介したコードは、この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の説明」は以下の通りです。
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いれない？
- コアライブラリの挙動の破壊的な変更、難しいなー