My implementation of lexicographic permutation in F# is 3x slower than C#

Question

Can someone help me with the following micro optimization for the F# code for lexicographic permutation?

I have code in C# which runs for 0.8s. As a learning practice, I translated it into F#. However, it becomes 2.9s. Just out of curiosity, I am wondering why my code in F# runs that slow? Are there any improvement can be made to my F# code without changing the algorithm?

C#

 static bool ToNextLexicographic(int[] myArray)
    {
        int pivot = -1;

        for (int i = myArray.Length - 1; i > 0; i--)
        {
            if (myArray[i] > myArray[i - 1])
            {
                pivot = i - 1;
                break;
            }
        }

        if (pivot == -1)
            return false;

        for (int j = myArray.Length - 1; j > pivot; j--)
        {
            if (myArray[j] > myArray[pivot])
            {
                // swap
                var tmp = myArray[j];
                myArray[j] = myArray[pivot];
                myArray[pivot] = tmp;

                // reverse
                for (int i = pivot + 1, k = myArray.Length - 1; i < k;i++,k-- )
                {
                    var tmp = myArray[i];
                    myArray[i] = myArray[k];
                    myArray[k] = tmp;
                }
                break;
            }
        }
        return true;
    }
    static IEnumerable<int[]> GetPermutationsLexicographic(int[] myArray)
    {
        Array.Sort(myArray);
        yield return myArray;

        while (ToNextLexicographic(myArray))
        {
            //yield return myArray.ToArray();
            yield return myArray;
        }
    }

F# (much readable than C#)

let inline toNextLexicographic (myArray: _[]) =
    let rec findPivot i =
        if i = 0 then -1
        else
            if myArray.[i] > myArray.[i-1] then i - 1
            else findPivot (i - 1)

    let rec findTarget value i =
        if (myArray.[i] > value) then i
        else findTarget value (i - 1)

    let inline swap i j =
        let tmp = myArray.[i]
        myArray.[i] <- myArray.[j]
        myArray.[j] <- tmp

    let inline reverse i =
        let mutable a = i
        let mutable b = myArray.Length - 1
        while a < b do
            swap a b
            a <- a + 1
            b <- b - 1

    let pivot = findPivot (myArray.Length - 1)
    if pivot = -1 then false
    else
        let target = findTarget myArray.[pivot] (myArray.Length - 1)
        swap pivot target
        reverse (pivot + 1)
        true;

let inline getPermutationsLexicographic myArray = seq {
    Array.sortInPlace myArray
    yield myArray
    while toNextLexicographic myArray do
        yield myArray
    }

// benchmark
let mutable d = 0
for x in getPermutationsLexicographic([|1..11|]) do
    d <- d + 1
d

Answer 1

You're not comparing apples to apples. The F# code is generic whereas the C# only works with int arrays. Remove every occurrence of inline and add a type annotation to toNextLexicographic:

let toNextLexicographic (myArray: int[])

In my tests, that takes the time from 2.152 to 0.146 seconds.

The reason for the poor performance is inline isn't working. You can see this by decompiling. Most of the time is spent in LanguagePrimitives.HashCompare.GenericGreaterThanIntrinsic as a result. This is much more expensive than op_GreaterThan.

I'm not sure under what conditions inline is ignored, but I can only guess, in this case, it's due to the complexity of your code and the closures.

Answer 2

I can now confirm the performance difference is due to Seq / IEnumerable

Say, if I remove Seq / IEnumerable, and meausre speed simply use while loop, e.g.

while toNextLexicographic myArray do
    d <- d + 2

The speed of C# and F# are now the same, being 0.6s. So I conclude it is the IEnumerable that make a difference. Still I don't get why Seq is slower than IEnumerable here, as they should be identical.