forest icon indicating copy to clipboard operation
forest copied to clipboard

Implement hamt diff algorithm

Open elmattic opened this issue 3 years ago • 1 comments

Issue summary

Our current implementation of the state-diff util library is inefficient. It takes two different state roots and computes which address/ actor state KVs changed, have been added or removed.

A likely faster way to implement this would be to use the same algorithm than from the go-hamt-ipld library.

Other information and links

go-hamt-ipld library

elmattic avatar Jul 12 '22 09:07 elmattic

While implementing this algorithm, I came across many unexpected roadblocks. The go tooling for HAMT and types required to implement this diff aren't available in rust or the FVM, or similar looking functionality behaves completely different. The Go implementation of the algorithm expects two different chainstores. One previous, one current, along with the previous and current CID's to diff. We weren't able to figure out why we need two and we discovered they could not be the same because there was a check to verify they aren't the same store.

connormullett avatar Sep 01 '22 16:09 connormullett

I don't think this is a priority anymore. Will re-open if diff performance becomes an issue.

lemmih avatar Feb 21 '23 14:02 lemmih