Search code examples
haskellkdtreecatamorphismrecursion-schemes

Are Ana-/Catamorphisms just slower?

After writing this article I decided to put my money where my mouth is and started to convert a previous project of mine to use recursion-schemes.

The data structure in question is a lazy kdtree. Please have a look at the implementations with explicit and implicit recursion.

This is mostly a straightforward conversion along the lines of:

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

to 

data KDTreeF v a f = NodeF a f f | Leaf v a

Now after benchmarking the whole shebang I find that the KDTreeF version is about two times slower than the normal version (find the whole run here).

Is it just the additional Fix wrapper that slows me down here? And is there anything I could do against this?

Caveats:

  • At the moment this is specialized to (V3 Double).
  • This is cata- after anamorphism application. Hylomorphism isn't suitable for kdtrees.
  • I use cata (fmap foo algebra) several times. Is this good practice?
  • I use Edwards recursion-schemes package.

Edit 1:

Is this related? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Is newtype Fix f = Fix (f (Fix f)) not "free"?

Edit 2:

Just did another bunch of benchmarks. This time I tested tree construction and deconstruction. Benchmark here: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

While the Core output indicates that intermediate data structures are not removed completely and it is not surprising that the linear searches dominate now, the KDTreeFs now are slightly faster than the KDTrees. Doesn't matter much though.

Solution

  • I have just implemented the Thing + ThingF + Base instance variant of the tree. And guess what ... this one is amazingly fast.

    I was under the impression that this one would be the slowest of all variants. I really should have read my own post ... the line where I write:

    there is no trace of the TreeF structure to be found

    Let the numbers speak for themselves, kdtreeu is the new variant. The results are not always as clear as for these cases, but in most cases they are at least as fast as the explicit recursion (kdtree in the benchmark).

    Benchmark results