3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Well, have you tried profiling the code to find out what slows it down? \$\endgroup\$ – svick May 1 '13 at 0:35
  • \$\begingroup\$ @svick the profiling info shows difference between x64 and x86, even though I struggled to find anything useful \$\endgroup\$ – colinfang May 8 '13 at 15:58
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – colinfang May 1 '13 at 15:10
  • \$\begingroup\$ 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? \$\endgroup\$ – Daniel May 1 '13 at 15:25
  • \$\begingroup\$ 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>. \$\endgroup\$ – colinfang May 1 '13 at 15:42
  • \$\begingroup\$ Can you update to include your test code? \$\endgroup\$ – Daniel May 1 '13 at 15:54
  • \$\begingroup\$ Ok, done. Btw it doesn't seem that inline was broken. Without inline and without type annotation, the program takes 20s. \$\endgroup\$ – colinfang May 1 '13 at 16:02
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.