Price to pay for CPS in F#

[Jack Fox]

Experiences in converting Okasaki's ML to F# for PairingHeap: the mergePairs algorithm (6 lines of code in F#) decomposes a PairingHeap, but a direct translation from ML to F# is not tail recursive.

Changing the algorithm to CPS makes it tail recursive, and my first thought was this will be perfect for the ofSeq type member. (I took an educated guess that it should be O(log n).) But no...a simple Seq.fold (which is clearly O(n)) performed as well or better than CPS mergPairs:

loading 100,000 elements from array, times in milliseconds, first time CPS, second Seq.fold

ascending integer  25.8 vs 23.7

random integer     25.3 vs 23.3

ascending string   23.3 vs 18.8

random string      28.3 vs 18.6

...and non-CPS mergePairs does stackoverflow at 100,000 elements.

This is bad news, since the the algorithm is central to the very useful tail and uncons members. As it turns out no test case I developed iterated enough times through the algorithm to actually stackoverflow (testing PairingHeaps of up to 10^6 elements), so I kept the non-CPS version of the algorithm, which is clearly faster than the CPS version:

taking 100,000 element PairingHeap and decomposing by tail, tail, tail... until empty

order refers to order of array from which heap was originally built

first number is CPS, second is non-CPS number

ascending integer  15.3 vs 5.2

random integer    196.6 vs 185.3

ascending string   24.8 vs 7.4

random string     201.6 vs 185.4

It is possible I botched the CPS algorithm, for which I will be grateful if someone points that out. I would also be interested if someone can develop a test case of 1,000,000 or fewer elements which causes tail to stackoverflow. I left the cps algorithm commented in the F# code for PairingHeap here https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/DataStructures/PairingHeap.fs

The most recent implementation in FSharpx uses the fast (non-CPS) algorithms.

[Jon Harrop]

I'm just taking a look at this now. FWIW, an August 2010 article in the F#.NET Journal already covered implementing a pairing heap in 21 lines of code using continuation passing style and benchmarked it against several other heap implementations:

  http://fsharpnews.blogspot.com/2010/08/data-structures-heaps.html

Your boolean is bad news for several reasons but, again, I'd forget about performance and focus on simplicity here.

An alternative to CPS is to use your own Stack and an imperative loop. This also means you can inline, which can massively improve the performance of generic comparison.

Cheers,

Jon.

[Jon Harrop]

Incidentally, what are the performance characteristics of generics in other languages (e.g. comparing tuples vs comparing their fields directly)? In OCaml and F#, this kind of genericity is very inefficient.

Also, another pragmatic aspect of purely functional data structures that has been neglected is serialization.

Here is the OCaml port of Okasaki's code by Markus Mottl that I mentioned in the pub:

  https://bitbucket.org/mmottl/pure-fun

Cheers,

Jon.

On Tuesday, December 4, 2012 9:57:40 AM UTC-8, Jack Fox wrote:

[Jack Fox]

"..at the cost of several times more code"... seems to be a near perfect inverse correlation between lines of code and performance of purely functional structures. Thanks for the link to Motl as well. There's a long ongoing discussion (including Don) about the future organization of the OS project. I'm trying to nudge the Data Structures in the direction we talked about. In the mean time I'm just waiting for the dust to settle. 

I recognize at least some of the issues with the boolean. I actually needed a heap just a few days ago. Coincidentally I needed an ascending heap, but ascending or descending should cost the same (from a pragmatic perspective). Was bemused a couple weeks back to find lists only natively sort ascending and to get descending List.sort |> List.rev is faster than List.sortWith (comparer function).