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

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

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.

StackExchange Code Review Q#25666, answer score: 3