Core implementaiton of List.sortByDescending

[davidgrenier]

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.

[mohsensc]

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.ofArray

Same 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.

[T-Gro]

A PR with clear benchmarks on CPU + allocations showing evidence for various scenarios including. trivial comparators as well will be accepted 👍 .