3

I am trying to implement a kdtree in Haskell (see implementation) but I tried to be smart and utilize Haskells lazyness while implementing the nearest neighbour algorithm (see line 46).

While it is technically correct, that is:

minimumBy (compare `on` qd q) vs == head . nearestNeighbours (kdtree 5 vs) $ q
==> True

The kdtree based version is much slower (criterion: 5.38ms vs 138.44ms, with 500k datapoints). I first thought that this was due to too strict pattern matching in ordMerge (line 59), but I rewrote it and from my understanding bs should now only be evaluated as needed.

If this is the case the algorithm should only descend to the matching bucket, and reascend while checking that the current best nearest neighbor is really the best candidate.

I did some profiling and nearestNeighhbors is called about 800 times. Given a tree depth of 8 and 100 testcases this sounds about reasonable, doesn't it?

Just uploaded my code to github: https://github.com/fhaust/threesg

This should get you started:

git clone https://github.com/fhaust/threesg
cd threesg
cabal sandbox init
cabal install --enable-benchmarks --enable-tests
cabal test
cabal bench --benchmark-options="+RTS -K100M -RTS"

(-K100M is needed cause the testset is created from 500k points)

While creating a testset for github I noticed, that on normal distributed points, the kdtree search runs alot faster than the linear search ... probably my problem is not the algorithm ... but my testset :(

fho
  • 6,787
  • 26
  • 71
  • 2
    Did you try to profile this function? http://www.haskell.org/ghc/docs/7.2.1/html/users_guide/profiling.html – user3974391 Nov 21 '13 at 14:40
  • Yep ... but that didn't help me. It spends most of the time at `nearestNeighbors.nnl` and `nearestNeighbors.nnr`. – fho Nov 21 '13 at 15:14
  • Are you comparing the construction of the kd tree and then finding its nearest neighbor with brute force finding the nearest neighbor? – DiegoNolan Nov 21 '13 at 16:31
  • @DiegoNolan ... no the kdtree is forced before doing the benchmark. I hope [the `NFData` instance](http://lpaste.net/95972#line81) i wrote is correct. – fho Nov 21 '13 at 17:11
  • Do you have a `main` function and example data we can use? The main thing I notice is that `ordMerge` is probably not being inlined, [as it's recursive](http://stackoverflow.com/questions/9658438/can-ghc-really-never-inline-map-scanl-foldr-etc): try applying the lame static argument transform trick, or try `ordMerge f q p n d = go where go = ...` (nicer pointfree style) so recursion is closed over the constant args. Hopefully that combined with the inlining of `dist'` will expose the sharing of your applications of `f` to `p` and `q` to the compiler. Let us know what you find – jberryman Nov 21 '13 at 18:37
  • also look at how `q` is a constant argument in `nearestNeighbors`, and trace the operations you do on `q`; you want to expose sharing there as well if you can, or rewrite your code to bind the result of `f q` explicitly in a `let` – jberryman Nov 21 '13 at 18:47
  • Maybe you thing in wrong format. It's easy and cheap to find `nearestNeighbours` with `Zipper`s – wit Nov 21 '13 at 18:57
  • @jberryman just uploaded my code to github – fho Nov 21 '13 at 20:28
  • @wit actually it works fine without them :-) – fho Nov 22 '13 at 12:19

1 Answers1

0

In the end this was a question of keeping track of the evaluation order. I uploaded the latest version on github.

Take a look at line 74: the second list is only evaluated if the first entry of the first list doesn't match the "there can't be a better candidate" criterion.

Apropos criterion, I did some benchmarking and the kd-tree ist indeed faster.

What do you think of this solution? I think the code is quite concise and readable. Are there any obvious performance penalties?

fho
  • 6,787
  • 26
  • 71