[Algorithms] Cache-oblivious layout (was: BSP tree, or what?)

[Marc B. R. <mar...@or...>]

> 3) Memory locality is a big deal nowadays. Do people have any 
> experience with van Emde Boas schemes to localize chunks of the tree, 
> or other methods to improve locality (e.g. flattening the tree)? These 
> seem good on paper, but I'd like to know before I spend a few days 
> implementing and find no gain whatever (or, hopefully, large gains). 
> The problem with BSP is that, if you want front to back traversal, the 
> order of traversal does change depending on the view.

Around 2001 (for a previous employer) I did some toy experiments ordering
large octtree memory via 3D-Hilbert curve indices and was seeing worthwhile
performance gains.