Performance of different comparison methods in F#

[AKisoku]

Hi,
I was doing some tests with BenchmarkDotNet to try to figure out if there are differences when using different comparison methods.
Here is the code that I used:

type TestType =
    | A
    | B
    | C
    | D
    member this.Compare (other: TestType) =
        if this < other then -1 elif this = other then 0 else 1

[<CustomEquality;CustomComparison>]
type TestTypeCustom =
    | A
    | B
    | C
    | D
    interface System.IComparable<TestTypeCustom> with
        member this.CompareTo (other: TestTypeCustom) =
            match this, other with
            | TestTypeCustom.A, TestTypeCustom.A
            | TestTypeCustom.B, TestTypeCustom.B
            | TestTypeCustom.C, TestTypeCustom.C
            | TestTypeCustom.D, TestTypeCustom.D ->
                0
            | TestTypeCustom.A, TestTypeCustom.B
            | TestTypeCustom.A, TestTypeCustom.C
            | TestTypeCustom.A, TestTypeCustom.D
            | TestTypeCustom.B, TestTypeCustom.C
            | TestTypeCustom.B, TestTypeCustom.D
            | TestTypeCustom.C, TestTypeCustom.D ->
                -1
            | TestTypeCustom.B, TestTypeCustom.A
            | TestTypeCustom.C, TestTypeCustom.A
            | TestTypeCustom.C, TestTypeCustom.B
            | TestTypeCustom.D, TestTypeCustom.A
            | TestTypeCustom.D, TestTypeCustom.B
            | TestTypeCustom.D, TestTypeCustom.C ->
                1

    interface System.IComparable with
        member this.CompareTo (other: System.Object) =
            match other with
            | :? TestTypeCustom as b ->
                (this :> System.IComparable<_>).CompareTo b
            | _ ->
                invalidArg "other" $"cannot compare TestTypeCustom and {other.GetType()}"

    interface System.IEquatable<TestTypeCustom> with
        member this.Equals (other: TestTypeCustom) =
            match this, other with
            | TestTypeCustom.A, TestTypeCustom.A
            | TestTypeCustom.B, TestTypeCustom.B
            | TestTypeCustom.C, TestTypeCustom.C
            | TestTypeCustom.D, TestTypeCustom.D ->
                true
            | _ ->
                false

    override this.Equals (other: System.Object) =
        match other with
        | :? TestTypeCustom as b ->
            (this :> System.IEquatable<_>).Equals b
        | _ -> 
            false

    override this.GetHashCode () =
        match this with
        | TestTypeCustom.A -> 1
        | TestTypeCustom.B -> 2
        | TestTypeCustom.C -> 3
        | TestTypeCustom.D -> 4

    member this.Compare (other: TestTypeCustom) =
        if this < other then -1 elif this = other then 0 else 1

    member this.CompareAlternative (other: TestTypeCustom) =
        (this :> System.IComparable<_>).CompareTo other

let possibleData = [TestType.A; TestType.B; TestType.C; TestType.D]
let possibleDataCustom = [TestTypeCustom.A; TestTypeCustom.B; TestTypeCustom.C; TestTypeCustom.D]

[<MemoryDiagnoser>]
type Test() =
    [<Params(1, 100, 1000)>]
    member val public Count = 0 with get, set

    member val private Data : TestType list = [] with get, set
    member val private DataCustom : TestTypeCustom list = [] with get, set

    [<GlobalSetup>]
    member this.GlobalSetup() =
        this.Data <- [1 .. this.Count] |> List.map (fun i -> possibleData.[i%possibleData.Length])
        this.DataCustom <- [1 .. this.Count] |> List.map (fun i -> possibleDataCustom.[i%possibleDataCustom.Length])

    [<Benchmark>]
    member this.Baseline() =
        let c = TestType.C
        this.Data |> List.filter (fun v -> c < v)

    [<Benchmark>]
    member this.Compare() =
        let c = TestType.C
        this.Data |> List.filter (fun v -> compare c v < 0)

    [<Benchmark>]
    member this.CompareMember() =
        let c = TestType.C
        this.Data |> List.filter (fun v -> c.Compare v < 0)

    [<Benchmark>]
    member this.Custom() =
        let c = TestTypeCustom.C
        this.DataCustom |> List.filter (fun v -> c < v)

    [<Benchmark>]
    member this.CustomCompare() =
        let c = TestTypeCustom.C
        this.DataCustom |> List.filter (fun v -> compare c v < 0)

    [<Benchmark>]
    member this.CustomCompareMember() =
        let c = TestTypeCustom.C
        this.DataCustom |> List.filter (fun v -> c.Compare v < 0)

    [<Benchmark>]
    member this.CustomCompareMemberAlternative() =
        let c = TestTypeCustom.C
        this.DataCustom |> List.filter (fun v -> c.CompareAlternative v < 0)

And here are the results I got:

| Method                         | Count | Mean          | Error       | StdDev      | Median        | Gen0   | Gen1   | Allocated |
|------------------------------- |------ |--------------:|------------:|------------:|--------------:|-------:|-------:|----------:|
| Baseline                       | 1     |     15.050 ns |   0.1687 ns |   0.1578 ns |     15.014 ns | 0.0038 |      - |      24 B |
| Compare                        | 1     |      5.544 ns |   0.0558 ns |   0.0495 ns |      5.566 ns | 0.0038 |      - |      24 B |
| CompareMember                  | 1     |     14.502 ns |   0.1457 ns |   0.1363 ns |     14.460 ns | 0.0038 |      - |      24 B |
| Custom                         | 1     |     21.681 ns |   0.2416 ns |   0.2142 ns |     21.661 ns | 0.0038 |      - |      24 B |
| CustomCompare                  | 1     |     23.199 ns |   0.4960 ns |   0.4640 ns |     23.055 ns | 0.0038 |      - |      24 B |
| CustomCompareMember            | 1     |     34.580 ns |   0.5829 ns |   0.5167 ns |     34.558 ns | 0.0038 |      - |      24 B |
| CustomCompareMemberAlternative | 1     |      7.975 ns |   0.2014 ns |   0.2320 ns |      7.942 ns | 0.0038 |      - |      24 B |
| Baseline                       | 100   |  1,568.202 ns |  56.6517 ns | 164.3569 ns |  1,535.596 ns | 0.1297 |      - |     824 B |
| Compare                        | 100   |    308.954 ns |   6.1021 ns |   7.4939 ns |    308.574 ns | 0.1311 |      - |     824 B |
| CompareMember                  | 100   |  1,384.905 ns |  27.2374 ns |  33.4500 ns |  1,371.577 ns | 0.1297 |      - |     824 B |
| Custom                         | 100   |  2,307.485 ns |  43.0887 ns |  57.5222 ns |  2,315.916 ns | 0.1297 |      - |     824 B |
| CustomCompare                  | 100   |  1,995.331 ns |  39.9583 ns |  99.5100 ns |  1,956.936 ns | 0.1297 |      - |     824 B |
| CustomCompareMember            | 100   |  3,020.200 ns |  51.7973 ns |  48.4512 ns |  3,011.194 ns | 0.1297 |      - |     824 B |
| CustomCompareMemberAlternative | 100   |    433.300 ns |   4.5363 ns |   4.2433 ns |    432.670 ns | 0.1311 |      - |     824 B |
| Baseline                       | 1000  | 14,215.749 ns | 211.2888 ns | 187.3020 ns | 14,170.760 ns | 1.2665 | 0.0305 |    8024 B |
| Compare                        | 1000  |  3,055.480 ns |  59.6021 ns | 101.2089 ns |  3,039.601 ns | 1.2741 | 0.0305 |    8024 B |
| CompareMember                  | 1000  | 13,525.248 ns | 267.3593 ns | 338.1239 ns | 13,473.766 ns | 1.2665 | 0.0305 |    8024 B |
| Custom                         | 1000  | 21,033.612 ns | 302.5656 ns | 283.0201 ns | 20,990.953 ns | 1.2512 | 0.0305 |    8024 B |
| CustomCompare                  | 1000  | 19,070.534 ns | 345.3997 ns | 288.4244 ns | 19,011.877 ns | 1.2512 | 0.0305 |    8024 B |
| CustomCompareMember            | 1000  | 27,972.162 ns | 372.8456 ns | 510.3552 ns | 27,855.775 ns | 1.2512 | 0.0305 |    8024 B |
| CustomCompareMemberAlternative | 1000  |  4,213.653 ns |  49.8904 ns |  44.2265 ns |  4,214.124 ns | 1.2779 | 0.0343 |    8024 B |

Now my question is, why is using compare so much faster than using the naive comparison with <? It also seems like implementing custom comparison removes this performance benefit and only way to get similar performance is to upcast to System.IComparable<_> and only then do the comparison. Why is there such difference between the automatically implemented comparison and the custom comparison?

[vzarytovskii]

Short answer is because of how comparison works in F# historically (see GenericComparison in prim types), we probably can improve things like we did with Equality for structs, but this will need a specific suggestion (fsharp/fslang-suggestions#1280 might be partially covers it and explains what's going on, you also might be interested in the linked issues).