Hash Array Mapped Tries (HAMT) to the Rescue

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @07:45AM (#24398726)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by ianopolous on Monday September 07, 2020 @09:37AM (#24399337)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @11:47AM (#24400190)

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?

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by ianopolous on Monday September 07, 2020 @12:04PM (#24400342)

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.

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @12:35PM (#24400554)

Ah ok, that makes sense.

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by Apanatshka on Monday September 07, 2020 @09:09AM (#24399178)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @11:51AM (#24400219)

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?

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by Apanatshka on Tuesday September 08, 2020 @03:41PM (#24412191)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by joshlemer on Monday September 07, 2020 @11:10AM (#24399927)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @11:52AM (#24400227)

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.

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by joshlemer on Monday September 07, 2020 @11:55AM (#24400248)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @12:28PM (#24400502)

Thanks! I've sent you an email.

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by eeperson on Monday September 07, 2020 @03:15PM (#24401861)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by neutronicus on Monday September 07, 2020 @10:21AM (#24399580)

There's a C++ implementation here:

https://github.com/arximboldi/immer

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by bjoli on Tuesday September 08, 2020 @02:31AM (#24405730)

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.

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by majke on Monday September 07, 2020 @08:33AM (#24398979)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by omginternets on Monday September 07, 2020 @11:39AM (#24400126)

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

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by benibela on Monday September 07, 2020 @12:58PM (#24400732)

I have implemented something like that in Pascal:

https://github.com/benibela/hamt

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by invisiblerobot on Monday September 07, 2020 @02:46PM (#24401580)

Clojure has an implementation of these in java.

[ Parent | on HN ]

Re:Hash Array Mapped Tries (HAMT) to the Rescue by joshlemer on Monday September 07, 2020 @02:47PM (#24401595)

Nitpick: Clojure does not use the new CHAMP encoding

[ Parent | on HN ]