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.
