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

[Jeff R. <je...@gm...>]

All very interesting,

Does anyone have a link or example of how to quickly do a morton or
hilbert lookup?

-Jeff

On Fri, Jun 6, 2008 at 12:40 PM, Mark Duchaineau <duc...@ll...> wrote:
> My colleagues Sung-Eui Yoon and Peter Lindstrom did a very
> thorough study of various cache-efficiency metrics for
> a variety of space-filling variants in a paper
> "Mesh Layouts for Block-Based Caches" from IEEE Vis 2006,
> pdf here:
>
> http://www.cc.gatech.edu/~lindstro/papers/blockcache/paper.pdf
>
> Looks like some special variants on Hilbert and a block
> interpretation of Sierpinski do very well, depending on the
> way you define efficiency (will vary by application requirements
> a bit, in other words).
>
> Cheers,
>
> --Mark D.
>
> Daniel Vollmer wrote:
>> 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.
>>
>> -------------------------------------------------------------------------
>> Check out the new SourceForge.net Marketplace.
>> It's the best place to buy or sell services for
>> just about anything Open Source.
>> http://sourceforge.net/services/buy/index.php
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
> -------------------------------------------------------------------------
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>