Parallel KD-Tree Construction (Benchmarks)

I was playing around with using parallelism to build a KD-Tree in Haskell.

Here's the  Src Code. I compiled with:

ghc -threaded -rtsopts -O2

And I ran it with the following arguments:

+RTS -N8 -A512K -K64M -H1G

Let me just show you the results and then I'll explain them.

Depth represents how deep down the tree we go before we stop adding additional threads of work. Each level should double the number of working threads. At a depth of one, we should have two threads working. At a depth of two, there should be four.. The number of entities greatly affects how much work we can extract by adding more threads. At 1000 entities, we have almost no improvement. With 5,000 entities at a depth of two, we have almost a 7% increase. Once you get to 10,000 entities, then the numbers start to get interesting. At a depth of one, you get almost a 100% increase! I have no idea why that's the case but I think GHC's parallel garbage collector may have something to do with that. At a depth of two and three you get a moderate increase for both. It levels off at a depth of four and begins to increase at a depth of five. 

Constructing a KD-Tree in parallel is a huge win when you get 10,000+ entities. For smaller amounts, it's minimal to no gain. For my purposes it will be nearly useless. Oh well, I have more exciting things in the works.

Splitting up the blog

We decided it would be best if Zach and I each started reporting on our technical progression and not just outline the overall progress of the game.

I will still be keeping up on the overview updates in the Home thread but it has come to our attention people may be interested in the more nitty gritty details of the work we are doing.   This was of course the original intent of the blog but time and details slipped through my fingers and it became a snap shot of progress, not a catalog of experiences with implementations.

So the blog has been split into the three logical components.
    - Overview / Home (non-technical)
    - Model (Haskell language implementation details)
    - View and Controller (Javascript language implementation details)

That's pretty much it.  Hopefully you'll get the implementation details I know you're craving in the Javascript and Haskell threads and that we can keep you up to date with our overall progress in the Home thread.

Thanks for your continued reading.