# 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 < 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;
}
}


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

• Well, have you tried profiling the code to find out what slows it down? May 1, 2013 at 0:35
• @svick the profiling info shows difference between x64 and x86, even though I struggled to find anything useful May 8, 2013 at 15:58

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.

• I did what you suggested, it still takes 2.2s, not improved at all. Also I updated the C# code in question so it becomes generic. (time spent stays the same) May 1, 2013 at 15:10
• Something's amiss. You added the type annotation and it stayed the same? I see a huge difference. After the change to the C#, you're still not comparing the same code. Change the F# to use CompareTo. GenericGreaterThanIntrinsic is slow. You want to eliminate those calls. Also, are you compiling in Release mode? May 1, 2013 at 15:25
• I updated the post so that you can see my changed F#, (it is nothing new but to add int[] and remove some inline) Since the C# version is 0.8s, I don't think you can get less than that in F#. Your result of 0.146s is suspicious. The reason why I use inline at the first place is that I know GenericGreaterThanIntrinsic (doesn't implement IComparable<T>) is slower than CompareTo<T>. May 1, 2013 at 15:42
• Can you update to include your test code? May 1, 2013 at 15:54
• Ok, done. Btw it doesn't seem that inline was broken. Without inline and without type annotation, the program takes 20s. May 1, 2013 at 16:02

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.