Perf improvement for primitive comparison

[thinkbeforecoding]

Is your feature request related to a problem? Please describe.

The compiled code is never fast enough. The code for GenericComparisonWithComparerFast generates specific IL code for primitive data types. This code use an if then else branching to return -1, 0 or 1. Branches are costly.

https://github.com/dotnet/fsharp/blob/main/src/fsharp/FSharp.Core/prim-types.fs#L1061

Comparison is used a lot in Set and Map as well as all sorting algorithms.

Describe the solution you'd like

It is possible to get the same result without branching. In the following image, there is the code as currently generated for its, and as it could be implemented.

it uses the fact that clt and cgt actually push 0 or 1 on the stack that can be used directly as an int instead as a bool.

The logic behind this is simple:

• when x > y, cgt returns 1, clt returns 0 => 1 - 0 = 1
• when x < y, cgt returns 0, clt returns 1 => 0 - 1 = -1
• when x = y, cgt returns 0, clt returns 0 => 0 - 0 = 0

The assembly code generated by the JIT have the same size, but the second one contains no branching:

Benchmarking such code cannot be done on a single sample.. it can be subject to constant propagation (this is true in both cases if you call the functions with constant parameters), and branch prediction that can hide the cost of branching. It is better to test it on a large array of random values:

#nowarn "42"
let inline stdcmp (x: int) (y: int) = 
    if (# "clt" x y : bool #) then (-1) else (# "cgt" x y : int #)


let inline fastcmp (x: int) (y: int) =
    (# "cgt" x y : int #) - (# "clt" x y : int #) 

open BenchmarkDotNet
open BenchmarkDotNet.Attributes
 [<SimpleJob>]
 type Bench() =
    let rnd = System.Random(1234)
    let values =
        [|for _ in 0 .. 10000 -> struct(rnd.Next(), rnd.Next()) |]
    [<Benchmark(Baseline = true)>]
    member _.Std() =
        let mutable sum = 0
        for i in 0 .. values.Length - 1 do 
            let struct(x,y) = values[i]
            sum <- sum + stdcmp x y

    [<Benchmark()>]
    member _.Fast() =
        let mutable sum = 0
        for i in 0 .. values.Length - 1 do 
            let struct(x,y) = values[i]
            sum <- sum + fastcmp x y


Running.BenchmarkRunner.Run(typeof<Bench>)

In the benchmark, we sum the results. If not, result is discarded and actually not computed at all.

The result shows the version without branches takes 1/3 of the time compared to the version with branches:

Of course, when the branch is systematically not taken, we do more work while the branch prediction is systematically correct. Here is a benchmark with random x, but y is always x + 2:

When the branch is systematically taken, both version do globally the same work since the branch is not costly. The branch seems even to be free, while the subtraction takes an instruction.

However, these situations where the result are always the same and same branch is always take is less probable than have variable inputs, and the gain when there is misprediction is higher than the loss when prediction is always correct.

Describe alternatives you've considered

Not do it.

[En3Tho]

It is worth mentioning that comparing any struct type outside of predefined set of intrinsic types will result in boxing too. Like equality operator. You shoud probably add a benchmark showing IComparable comparsion result e.g. cmp<'a when 'a :> IComparable>

[dsyme]

Could you add a PR for this please?

[En3Tho]

I believe it's important to check first what C# does - because JIT team is much more likely to optimize C# stuff. It's not reasonable to make custom il generation just to rewrite it again when jit team does new optimization for C# il patterns.

Also, such test is quite cpu-specific and needs to have broader benchmark cpu coverage. Because amd/intel/arm cpus are quite different at handling branches. This is once again why I think its important to check what C# does.

[thinkbeforecoding]

@En3Tho Actually the implementation in the BCL is not better:

https://sharplab.io/#v2:DYLgZgzgNALiCGEC2AfA9GgBAVwgSwDsBzTAIQGEAZTPJAB2AFMlGCZ4Y8B7AgWACgmMTGEwAKAB4hCMAJTiAntLbyAvJgkA6cl3rwATowAqXMQtkCBGHPmKYAYgGJMAYy6Ga9JizYdufQUZhMABycSkZeTNlOUx1Nz0PCUwFS35rOn0uOi4IRgATTwZmVnZOHgEhERCwyRiopRoVOPFnACIXIhg2jRTMECbhR3kAWlbMDuBu3oV+wcxhoA=

[thinkbeforecoding]

The last thing that annoys me is that the Jit is producing a movzx eax,al and a movezy edx,dl to extend the result after the setg, setl, but it could factorize it by doing the substraction first, the sign extend...

[En3Tho]

@thinkbeforecoding maybe you can first post issue in dotnet/runtime? I'm curious what jit team has to say about this

[thinkbeforecoding]

Yes for that part, I'll make a suggestion there.
The implementation of int.CompareTo in the Bcl incurs a double conditional jump, but if it is written in C#, it is not possible to use inline IL like in F#

[thinkbeforecoding]

Cgt and clt are pushing an int on the stack, but the setx instruction works only on 8bits registers (al, dl etc) so you need zero extension to get an int.
But there seem to be no optimization done there.
For instance if you have a clt followed by a cast to byte (# clt x y : byte#) you could expect it to remove the movzx as you will not use the higher reg part. But it doesn't.
I found no way to get rid of the movzx

[thinkbeforecoding]

I also didn't touch the implementation for float as it seems to behave differently due to NaN.

[En3Tho]

@thinkbeforecoding please use x64 mode in sharplab. It will use latest stable corclr in amd64 mode. Default is x86.
I'm curious what 7.0 runtime can do here. Maybe some of those are already fixed.

[thinkbeforecoding]

Yes the sample above is using x64.

[En3Tho]

That example with movs is x86 I believe.