4 ms·
I read an entire book on applications of space filling curves, and none of the applications seemed to actually work as advertised (though perhaps they did at th
by j2kun 2y ago
I read an entire book on applications of space filling curves, and none of the applications seemed to actually work as advertised (though perhaps they did at the time the book was written, I am skeptical).
All the stuff about database indexing and cache locality seems to have become obsolete with improvements in compilers; the overhead of computing the Hilbert curve indices is just too high. The indexing method that people seem to actually use is the Z-order/Morton order, which just interleaves bits and is mathematically less interesting [1].
[1]: https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
- ashvardanian 2y agoAgreed. There are few practical applications of Space-Filling Curves, but readers may enjoy implementing Z-like and other curves in higher dimensions. Doing it efficiently can be one of those “weekend projects” that takes much longer in practice.
- TinkersW 2y agoI use hilbert curves and I can assure you they are very useful for performance.. Hilbert encoding does take longer than Z order, but I have a SIMD optimized routine for it so it isn't that bad. Your comment about compilers doesn't make sense, compilers can't rearrange memory order so that are incapable of making a hilbert or zorder like transform. I profiled hilbert vs zorder and found hilbert was sufficiently superior to justify the extra overhead, hilbert was about ~22% less work vs zorder.