3 ms·
HAMT by mr Bagwell are great: * https://idea.popcount.org/2012-07-25-introduction-to-hamt/ https://idea.popcount.org/2012-07-25-introduction-to-hamt/ I was mo
by majke 12y ago
HAMT by mr Bagwell are great:
* https://idea.popcount.org/2012-07-25-introduction-to-hamt/ https://idea.popcount.org/2012-07-25-introduction-to-hamt/
I was mostly surprised not by the CPU, but by the memory efficiency. From my experimentation it turns out that if you want to store X bits of data, HAMT will use ~1.5 * X bits per item.
In other words: thousand 8-byte pointers in HAMT will occupy around 12 thousand bytes of memory.
- nazri1 12y agoHAMT is cool! I'm maintaining an ORM objects cache server in my $dayjob that uses HAMT as it's core data structure and I really like the ram usage efficiency.
- tromp 12y agoClosely related are Judy Arrays (aka Judy Trees): https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array