4 ms·
Apart 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
by omginternets 6y ago
Apart 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