dotnet/runtime

Investigate optimizing some OrderBy().Take calls to use a PriorityQueue

Open

#96,277 opened on 2023年12月22日

GitHub で見る
 (12 comments) (6 reactions) (0 assignees)C# (5,445 forks)batch import
area-System.Linqhelp wantedtenet-performance

Repository metrics

Stars
 (17,886 stars)
PR merge metrics
 (平均マージ 12d 11h) (30d で 661 merged PRs)

説明

Order/OrderBy.Take is currently an O(N log N) operation that allocates an array of length N and keeps all the data around until the relevant portion of the data is consumed. With a PriorityQueue, however, for OrderBy(...).Take(T) this would instead be O(N log T), and it would only need to keep space proportional to T, not N, so if T is significantly smaller than N (which in typical use is the case, often with a small T value passed to Take), this could lead to significant throughput and memory consumption benefits.

Variations of this with OrderByDescending are also possible. It'd also be possible to accomodate OrderBy().Skip(S).Take(T); the priority queue would then need to maintain S+T values, so the benefits would diminish as S grew. However, from an algorithmic complexity perspective, S+T <= N, which means O(N log (S+T)) <= O(N log N). Of course, we'd still need to be careful, since the constants here do matter from a throughput perspective.

コントリビューターガイド