search

filecoin-project / go-amt-ipld

Implementation of an array mapped trie using go and ipld
Other
9 stars 15 forks source link

collapse the height of empty AMTs #34

Closed Stebalien closed 4 years ago

Stebalien commented 4 years ago

Currently, when we empty an AMT, we wouldn't collapse the height. This change fixes that.

Stebalien commented 4 years ago

This patch extracts the bugfix from #30.

anorth commented 4 years ago

Thanks, this is nice and small and a very clear fix.

What will be the impact on chain state of not landing this right away? Are the HAMTs with incorrect height broken, or just inefficient?

Landing the rest of #30 later will require another version bump, since it changes store interactions. Which is fine.

Stebalien commented 4 years ago

It looks like it works, it just pushes everything out to a deeper height than necessary.

Stebalien commented 4 years ago

Now that I think about the fix doesn't require a full re-write. All we need to do is explicitly collapse AMTs that either:

  1. Have no children.
  2. Have a single branch to the left.

Effectively, just apply the delete logic.

Stebalien commented 4 years ago

We decided to ship everything (#30) all at once instead of landing this bit by bit.