Concurrent HAMT

[cryptoquick]

Issue summary In looking into HAMT data structures, I noticed there's something called a Ctrie. It's interesting, because it offers some very intriguing performance characteristics. However, it does require some gymnastics when it comes to garbage collection. According to the Wikipedia article, there's an (albeit unmaintained) implementation using hazard pointers, and it also mentions using reference counters.

But, before any of this, it'd be important to develop a benchmarking strategy, to get a sense of the value here. That said, from a computer science perspective, the Ctrie approach seems... Ideal. Overall, I'd just be curious if HAMT is a major performance roadblock, and what value a Ctrie could have in a Filecoin implementation, since it's ideal for parallel programming.

Other information and links

• https://github.com/ballard26/concurrent-hamt - Ancient
• https://github.com/junkerjorg/peril - Brand spanking new
• https://github.com/oliver-giersch/hazptr - No new updates for over a year
• https://en.wikipedia.org/wiki/Ctrie - Wikipedia article
• https://godoc.org/github.com/Workiva/go-datastructures/trie/ctrie - Go implementation (less useful as a reference due to Go GC, however, it'd be good to investigate for performance reasons, and I'd be curious what the lotus folks have to say one this)
• https://github.com/Daniel-Liu-c0deb0t/triple_accel - This library looks decent for hamming distance SIMD in Rust, which is important (the one piece of the "three layer cake of shared memory programming" that I couldn't remember on our call, the other two being, fork-join and message-passing).

[austinabell]

So here's the thing about our Hamt: it's a specific Ipld one that is not just an in memory store and the serialized format and also the specific functionality needs to exactly match the go-implementation to match consensus (Hamt is just used within the state transition of the node).

Also, this structure is only used in a sync context so there wouldn't be a benefit for this yet. Since it's only meaningfully used with consensus critical things, it's extremely unlikely it will switch to need to be asynchronous anytime soon

[ec2]

Our HAMT is rarely or maybe not even ever used in a concurrent setting. Would still be interesting to look at Ctries. Important thing though, is that our HAMT implementation needs to be consensus compatible with all the other implementation's. Would be quite the undertaking to also fork and add all the necessary IPLD stuff to a filecoin compatible Ctrie HAMT, but is def interesting to look at eventually if it becomes a bottleneck.

[cryptoquick]

That answers my questions! In that case, let's just... Set this this aside for now. That said, it's an idea to keep in the back of our minds as the protocol and spec is improved over time.