How to roll a fast BVH representation in Haskell

Question

I'm playing with a Haskell Raytracer and currently use a BVH implementation which stresses a naive binary tree to store the hierarchy,

data TreeBvh
   = Node Dimension TreeBvh TreeBvh AABB
   | Leaf AnyPrim AABB

where Dimension is either X, Y or Z (used for faster traversal) and AABB is my type for an axis-aligned bounding box. This is working reasonably well, but I'd really like to get this as fast as I possibly can. So my next step (when using C/C++) would be to use this tree to construct a flattened representation where the nodes are stored in an array, the "left" child immediately follows it's parent node and the index of right child of the parent is stored with the parent, so I have something like this:

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

I didn't really try out this one yet, but I fear the performance would still be sub-par because I can't store LinearNode instances in an UArray, neither could I store the Int indexing the right child together with the Float values which make up the AABB in a single UArray (correct me if I got this wrong). And using two Arrays would mean bad cache coherency. So I'm basically looking for a way to efficiently store my tree so I can expect good performance for traversal. It sould be

• compact
• have good locality properties
• work with recent GHC compilers
• should go through as little indirections as possible (going though a "thunk" can't help performance, so "unboxed" types would help I think)

Answer 1

If I understood you correctly you want unboxed arrays of user-defined types? if so check-out the vector package which also supports loop fusion. It's worth checking out slides for High-Performance Haskell

Answer 2

I should really point out that Haskell is not very good at giving the programmer a means of choosing data layout in memory.

You might be interested in storing the tree in a flat array in cache-oblivious way ("Van Emde Boas tree"). It should work, but who knows. :)

(shameless plug: I've made a similar effort some time ago; I've used some advanced type system features of the ATS programming language to make the raytracer both safer and faster; see the code here: http://code.google.com/p/ats-miscellanea/ -- I didn't go very far yet, unfortunately)