Generic function significantly slower than function with specific type

[davidbruce]

A C# vs F# performance question was asked on the fsharp.org forums and I was able to solve the issue, but I am not sure what's going on. It would appear that a generic function is significantly slower than a type specified one. I'm reposing this here to hopefully get some more visibility because this seems like unexpected behavior.

The post in question: F# vs C# performance

Copy of altbodhi's Original post:

I do not understand why F# so slow

let inline swap<'a> (a: byref<'a>, b: byref<'a>) =
    let t = a
    a <- b
    b <- t

let sort arr =
    let ln = Array.length arr

    for i = 0 to ln - 1 do
        for j = 0 to ln - 2 - i do
            if arr.[j + 1] < arr.[j] then
                swap (&arr.[j + 1], &arr.[j])

let doTest () =
    let max = 100_000
    let value = float (max)

    let arr =
        Array.init max (fun i -> value - float (i))

    sort arr
    printfn "%A" (arr.[0..5])

#time

doTest ()

It is very slow (few minutes).
Analog on C# take above few seconds. Why?
Original cod here vostok/example/BubbleSort.mod at master · Vostok-space/vostok (github.com) 1
(Interesting post about result for it on Oberon(simple language from Nicolaus Wirth) Восток: Скорость пузырьковой сортировки на Oberon, C++, Go, Rust (vostok-space.blogspot.com))

using System.Runtime.CompilerServices;

var m = 100_000;
var a = new double[m];
var s = (double)m;
for (var i = 0; i < m; i++)
{
    a[i] = s;
    s = s - 1;
}

Sort(a);

Console.WriteLine(a[0]);

static void Sort(double[] a)
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    void Swap(ref double x, ref double y)
    {
        var t = x;
        x = y;
        y = t;
    };

My original response:

I’m new to F# so I can’t really offer an explanation, but the following change on my local machine dramatically improves performance:

let sort arr =

to

let sort (arr: float array) =

Without the type annotation I ended up having to kill FSI after a few minutes. With the annotation I get the following:

[|1.0; 2.0; 3.0; 4.0; 5.0; 6.0|]
Real: 00:00:08.292, CPU: 00:00:00.201, GC gen0: 0, gen1: 0, gen2: 0

I would love to know what’s going on here myself. It must have something to do with the generic function not properly passing by reference or something?

I’m on an M1 Mac with .NET 7.0.100.

[vzarytovskii]

TL;DR it's likely because of how comparison works in F# (due to comparison constraint).

Generic comparison will be involved (like GenericLessThanIntrinsic, since function is, well, generic), which is not inlined as far as I remember as well as has some logic in it to chose specific implementation.

[brianrourkeboll]

Yes, this is definitely a case of #9348, #526, etc. Take a look at the decompiled code.

This line —

if arr.[j + 1] < arr.[j] then

— becomes the equivalent of —

a x = arr[num4 + 1];
a y = arr[num4];
if (LanguagePrimitives.HashCompare.GenericLessThanIntrinsic(x, y))

That ends up boxing the float arguments, etc.

[vzarytovskii]

Yeah, this is unfortunately, how comparison was designed. We try to slowly work around it with keeping it backwards compatible, meanwhile, something like the following can be used;

let inline swap<'a when 'a : comparison> (a: byref<'a>, b: byref<'a>) =
    let t = a
    a <- b
    b <- t

let inline clt a b = (# "clt" a b : bool #)

let sort arr =
    let ln = Array.length arr
    for i in 0 .. ln - 1 do
        for j in 0 .. ln - 2 - i do
            if clt arr[j + 1] arr[j] then
                swap (&arr[j + 1], &arr[j])

let max = 100_000
let arr = [| for i in 1 .. max do float i |] |> Array.rev

sort arr

printfn $"Sorted: {arr.[0]}, {arr.[1]}, {arr.[2]}, ..., {arr.[max - 1]}"

Which is quite an improvement:

> time dotnet run -c Release

Build succeeded in 1,2s
Sorted: 1, 2, 3, ..., 100000
dotnet run -c Release  11.27s user 0.29s system 107% cpu 10.773 total