GeezerVison is showing github.com — Core implementaiton of List.sortByDescending · dotnet/fsharp · Discussion #20848
Core implementaiton of List.sortByDescending
#20848
Oct 22, 2026
·
2 comments
Discussion options
-
Uh oh!
There was an error while loading. Please reload this page.
|
The current implementation:
[<CompiledName("SortByDescending")>]
let inline sortByDescending projection list =
let inline compareDescending a b =
compare (projection b) (projection a)
sortWith compareDescending list
Can be extremely slow if the projection is modestly compute intensive. This is because this implementation will call that projection on (perhaps) O(n log n) pair of elements in the collection. I think this might be an expected behavior if the signature of the sorting function was expecting some kind of comparator.
compare: 'a -> 'a -> int
However in this case it can make the call drastically slower than say List.sortBy (as the latter's implementation is different), or even simply List.sortByDescending was implemented as say:
[<CompiledName("SortByDescending")>]
let inline sortByDescending projection list = List.sortBy (fun x -> -projection x) list
I wonder if such a PR might be smoothly accepted? I've never contributed before.
|
You must be logged in to vote
Comment options
-
Uh oh!
There was an error while loading. Please reload this page.
|
Diagnosis is right. sortBy projects each element once into a keys array (stableSortInPlaceBy in local.fs), sortByDescending goes through sortWith and calls the projection twice per comparison. On 2000 items i counted 39,668 projection calls vs 2,000.
The -projection x version won't fly as the PR though:
- the signature only requires
comparison, so keys can be strings, tuples, DateTimes etc. Negation only works for signed numerics (and -Int32.MinValue overflows)
sortBy |> List.rev isn't a fix either, sortByDescending is documented stable (listStable in list.fsi) and reversing flips the order of equal keys
A version that keeps both properties is project once, then stable sort by key descending:
let sortByDescending projection list =
match list with
| [] | [ _ ] -> list
| _ ->
let arr = List.toArray list
let keys = Array.map projection arr
Array.init arr.Length id
|> Array.sortWith (fun i j ->
let c = compare keys.[j] keys.[i]
if c <> 0 then c else compare i j)
|> Array.map (fun i -> arr.[i])
|> List.ofArraySame result as the built-in on my test data, with one projection per element. Array.sortByDescending has the identical pattern (array.fs) so a PR would probably want to fix both. Usable today as a local helper while you wait.
|
You must be logged in to vote
0 replies
Comment options
-
Uh oh!
There was an error while loading. Please reload this page.
|
A PR with clear benchmarks on CPU + allocations showing evidence for various scenarios including. trivial comparators as well will be accepted 👍 .
|
You must be logged in to vote
0 replies