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

[Daniel V. <ma...@ma...>]

On Jun 6, 2008, at 01:07 , Tom Forsyth wrote:

> After experience with Morton vs Hilbert in a bunch of areas  
> (rasterization,
> texture storage, vertex caching, etc), my gut feeling is that a  
> Hilbert
> curve very rarely gives a worse cache-traversal pattern than Morton.  
> Note
> the very precise statement! However, it can be a pain to implement  
> (whereas
> Morton is pretty trivial), and whether it's actually a significant  
> *win*
> depends a lot on a bazillion things.

I'd agree with Tom's gut impression. :)

For a wavelet image compression algorithm (shameless plug: http://www.maven.de/code/wavelet/) 
  I went with Morton / Z first, and then later on went ahead and  
implemented a Hilbert curve variant. The Hilbert curve gave slightly,  
but consistently better results (i.e. smaller images) which means it  
extracted locality better than the other space-filling curves, and as  
I stored the curve in a table anyhow the computational cost was  
irrelevant. Of course, there were also cases where the Morton curve  
fared better, but they were very much in the minority (and from and  
Information Theory viewpoint they *have* to exist).
The above-linked code has a nice, self-contained 2D Hilbert Curve  
generation (which gets optimized to a simple loop due to tail- 
recursion), which is quite easy to extend to 3D (as was done in the  
paper referenced in the source).


	Daniel.