Hacker News Reader

Comment by omginternets | Hacker News Reader

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

View on HN

I'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/s...

Thanks 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?

Sure, 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.

Ah ok, that makes sense.

I've sent you an email with from my personal gmail account. I really appreciate the help, thanks!

Haven'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

Oh 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?

Happenstance really, he briefly joined our research group. I'll send him a link to this thread.

I have done more than enough work on the CHAMP encoded hashmap in Scala 2.13 to call myself a co-author

As 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.

Sure, my email is joshlemer [at] gmail [dot] com

Thanks! I've sent you an email.

Scala 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/d5ae93e1b35fac4002cfbf...

[0] https://github.com/scala/collection-strawman/issues/192

There's a C++ implementation here:

https://github.com/arximboldi/immer

Immer 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.

Does https://idea.popcount.org/2012-07-25-introduction-to-hamt/ count?

I 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 :)

I have implemented something like that in Pascal:

https://github.com/benibela/hamt

Clojure has an implementation of these in java.

Nitpick: Clojure does not use the new CHAMP encoding

Reply on news.ycombinator.com