6 ms·
Hash Array Mapped Tries (HAMT) to the Rescue
- omginternets 6y agoApart from the Steindorfer and Vinju paper [0], does anybody have any resources for implementing the CHAMP variant of HAMT tries? Better yet, has anybody here implemented one before, and might I pick your brain? [0] https://michael.steindorfer.name/publications/oopsla15.pdf https://michael.steindorfer.name/publications/oopsla15.pdf
- majke 6y agoDoes https://idea.popcount.org/2012-07-25-introduction-to-hamt/ https://idea.popcount.org/2012-07-25-introduction-to-hamt/ count?
- omginternets 6y agoI was looking for more CHAMP-specific stuff, but I've bookmarked this nonetheless. It's always nice to look at something in a few different ways :)
- Apanatshka 6y agoHaven't implemented it myself, though I mean to try one day. But I've spoken to Michael before and used his implementation: https://github.com/usethesource/capsule https://github.com/usethesource/capsule
- omginternets 6y agoOh wow! I imagine he's quite busy -- how did you get in touch with him. I know this is a long-shot, but any chance you might be able to arrange an email intro?
- Apanatshka 6y agoHappenstance really, he briefly joined our research group. I'll send him a link to this thread.
- ianopolous 6y agoI've implemented CHAMP [0] for Peergos in the IPLD/IPFS setting, largely based on the Steindorfer paper. There is one improvement that whyrusleeping from ipfs came up with which is to allow a small number of hash collisions in a level, before pushing things down a level. [0] https://github.com/Peergos/Peergos/blob/master/src/peergos/shared/hamt/Champ.java https://github.com/Peergos/Peergos/blob/master/src/peergos/s...
- omginternets 6y agoThanks for the link, this is super helpful. I posted my parent comment opportunistically, so I have yet to distill my reading into specific, well-formed questions. Is there any way I can message you when I get around to doing so? In the meantime: >There is one improvement that whyrusleeping from ipfs came up with which is to allow a small number of hash collisions in a level, before pushing things down a level. How is this an improvement, exactly?
- ianopolous 6y agoSure, I have a protonmail email with my github username. >How is this an improvement, exactly? This allows you to essentially make the tree "fatter" for a given bitwidth. This matters more in the ipfs setting because links are not memory pointers, but Merkle-links to objects which may be a network request away.
- omginternets 6y agoAh ok, that makes sense. I've sent you an email with from my personal gmail account. I really appreciate the help, thanks!
- 1DRACOSEA8 6y agoThere are conference papers answering your one-level two-level question, but I found you pedantic; comfortable, almost as if you’d want us to do work for you and find you a “link”. Nice and Easy, just felt very “Hey Slave over there”. Uh huh, Go and look for one-level hybrid storage on the USENIX archives.
- neutronicus 6y agoThere's a C++ implementation here: https://github.com/arximboldi/immer https://github.com/arximboldi/immer
- bjoli 6y agoImmer is amazing! I would suggest also looking at his work with transducers in the atria c++ library. The talk he gave about them is what made transducers really click for me.
- joshlemer 6y agoI have done more than enough work on the CHAMP encoded hashmap in Scala 2.13 to call myself a co-author
- omginternets 6y agoAs I mentioned in another comment, I posted my parent comment opportunistically, so I have yet to distill my reading into specific, well-formed questions. Is there any way I can message you when I get around to doing so? I'd really appreciate a super-quick whiteboard session, if you have the time.
- joshlemer 6y agoSure, my email is joshlemer [at] gmail [dot] com
- omginternets 6y agoThanks! I've sent you an email.
- 1DRACOSEA8 6y agoJVM what a piece of shit
- benibela 6y agoI have implemented something like that in Pascal: https://github.com/benibela/hamt https://github.com/benibela/hamt
- invisiblerobot 6y agoClojure has an implementation of these in java.
- joshlemer 6y agoNitpick: Clojure does not use the new CHAMP encoding
- eeperson 6y agoScala experimented[0] with implementing those in its standard library. I'm not sure if it made it in to the final release or not. EDIT It looks like it did make it in: https://github.com/scala/scala/commit/d5ae93e1b35fac4002cfbffff9ec741356549e08 https://github.com/scala/scala/commit/d5ae93e1b35fac4002cfbf... [0] https://github.com/scala/collection-strawman/issues/192 https://github.com/scala/collection-strawman/issues/192
- huhnmonster 6y agoCan someone explain the reasoning for using a HAMT here? I have played around with hashtables quite a bit, but altough HAMT's are cool and a lot more memory efficient, they are likely not faster and will at some point suffer from more severe memory fragmentation than hashtables. Is the concern speed or memory? Because speed would kind of seem strange, since after changing to the new architecture, they should see a strong decrease in messages being exchanged anyways, right? Or are go's maps inefficient? Genuinely curious
- fsloth 6y agoHAMT is excellent for a persistent dictionary. Not persistent as in write-to-disk, but as in immutable-yet-small.
- riwsky 6y agoIt is not clear from the article that the author needed a persistent data structure. It’s also, frankly, not clear they‘d benefit from using an HAMT at all: the only measurements they present are of their problem domain, not of any implementations—and many of the asymptotics they cite are also true of hashmaps. If their initial hashmap approach did have O(N) inserts because they copied the whole map for “immutability” every time, then sure, HAMTs will beat the pants off of it—but did it?
- benibela 6y agoBtw, can it be used to build a persistent dictionary that keeps the key in insertion-order?
- masklinn 6y agoSure. Map the HAMT to an index into a persistent vector or something e.g. Scala's VectorMap and TreeSeqMap. You could also reuse the old "linked list map" idea, but go through the keys every time e.g. whenever you add a value to the map, add a triple of `(Some(last_key), value, None)` and update the last keys value such that the third item becomes the key of the new item.
- sfink 6y agoMaybe I'm just missing it, but I don't see in this description any explanation of how to handle hash collisions - ie, when two keys map to the same hash value. Do you iterate through an infinite series of secondary hash functions when you run out of distinguishing bits? Or do you bottom out at a table that you linearly scan? Overall, it seems like the algorithm is "maintain a trie on the hash values, using an auxiliary bitmap and popcnt to determine the index within any trie node." Does that miss anything?