4 ms·

Many common data structures fail to preserve order. Maps (aka dictionaries) based on hash tables come to mind. Slightly adrift of the topic... I have a HAMT

Many common data structures fail to preserve order. Maps (aka dictionaries) based on hash tables come to mind. Slightly adrift of the topic... I have a HAMT (hash array map trie) implementation that uses a 32-bit unsigned int as a bitfield to indicate which of the 32 possible children nodes are populated. With this trick I could encode any node with 5 or fewer bits flagged with a 16-bit unsigned int instead. I just checked and 1 million keys created roughly 1.3 million nodes (1 million keys, 300k internal nodes). Nearly 90% of the 300k internal nodes have 5 or fewer bits set. This trick would make the HAMT overhead nearly half the size. Very useful! Now, how about 6-bit values in one 32-bit value? I'd like to try this with a 64-bit HAMT. Can this be easily generalized? Edit: Oops, that should be nodes with 4 or fewer bits set, there are only 4, 5-bit values. Interestingly that apparently doesn't make much of a difference for HAMTs only about 2k internal nodes out of 300k have 5 children. So the results remain the same.

sweettea 9y ago
I believe, based on the math, that 6 6-bit values barely don't fit in 32 bits. :(
scythe 9y ago
The number of bags of k N-bit numbers is 2^N + k - 1 choose k: https://en.wikipedia.org/wiki/Multiset#Counting_multisets https://en.wikipedia.org/wiki/Multiset#Counting_multisets The number of bits required to uniquely represent such a bag is thus ⌈log2((2^N+k-1) choose k)⌉. For (N, k) we have: (6, 6) -> ⌈log2(69 choose 6)⌉ = ⌈log2(119877472)⌉ = 27 bits (6, 7) -> ⌈log2(70 choose 7)⌉ = ⌈log2(1198774720)⌉ = 31 bits So you can store seven 6-bit integers without order in one int32. I don't know if it'll be slow, though. It should be possible to infer an encoding algorithm from the proof of the counting formula but it might be slow.
eloff 9y ago
My understanding is you can't tell order using this trick. I guess the bitmap is just an optimization to skip the hash lookup? Order doesn't matter for you? Something I came up with is packing the pointers/values into a contiguous array and using the bitfield to tell not only if it's present, but what offset is at (mask + popcnt) * size of(value). This eliminates wasted space due to unused buckets in the hash table. I'm sure it's been done before, but I haven't seen it anywhere. How's your Go? Want a remote contact doing Go microservices that pays very well? Email is in my profile.
- joshuak 9y ago
  That's pretty much exactly how hash array mapped tries work. Take the first 5 bits of a 32 bit hash, use it to set a flag in the bitfield, a populated field indicates a populated child array element, find out which one using popcnt. When you find a conflict on insert take a step down the tree, use the next 5 bits in the 32 bit hash rinse and repeat. A HAMT is the basis of a fully concurrent data structure for maps which can also do fast atomic snapshots called a ctrie.
  - eloff 9y ago
    I'll add HAMT and tries to my reading list, thanks.

sweettea 9y ago

I believe, based on the math, that 6 6-bit values barely don't fit in 32 bits. :(

scythe 9y ago

The number of bags of k N-bit numbers is 2^N + k - 1 choose k: https://en.wikipedia.org/wiki/Multiset#Counting_multisets https://en.wikipedia.org/wiki/Multiset#Counting_multisets The number of bits required to uniquely represent such a bag is thus ⌈log2((2^N+k-1) choose k)⌉. For (N, k) we have: (6, 6) -> ⌈log2(69 choose 6)⌉ = ⌈log2(119877472)⌉ = 27 bits (6, 7) -> ⌈log2(70 choose 7)⌉ = ⌈log2(1198774720)⌉ = 31 bits So you can store seven 6-bit integers without order in one int32. I don't know if it'll be slow, though. It should be possible to infer an encoding algorithm from the proof of the counting formula but it might be slow.

eloff 9y ago

My understanding is you can't tell order using this trick. I guess the bitmap is just an optimization to skip the hash lookup? Order doesn't matter for you? Something I came up with is packing the pointers/values into a contiguous array and using the bitfield to tell not only if it's present, but what offset is at (mask + popcnt) * size of(value). This eliminates wasted space due to unused buckets in the hash table. I'm sure it's been done before, but I haven't seen it anywhere. How's your Go? Want a remote contact doing Go microservices that pays very well? Email is in my profile.

joshuak 9y ago
That's pretty much exactly how hash array mapped tries work. Take the first 5 bits of a 32 bit hash, use it to set a flag in the bitfield, a populated field indicates a populated child array element, find out which one using popcnt. When you find a conflict on insert take a step down the tree, use the next 5 bits in the 32 bit hash rinse and repeat. A HAMT is the basis of a fully concurrent data structure for maps which can also do fast atomic snapshots called a ctrie.
- eloff 9y ago
  I'll add HAMT and tries to my reading list, thanks.