ssz icon indicating copy to clipboard operation
ssz copied to clipboard

Refactor tree view model - built-in fast caches

Open dapplion opened this issue 3 years ago • 0 comments

We have built many additional caches in Lodestar CachedBeaconState to make the beacon state transition as fast as it needs to be. However those structures are very verbose, repetitive in code and have huge memory cost.

Cache to skip traversals

Teku ssz has a nice approach where tree views have a cache attached to prevent having to traverse the tree unless when strictly necessary. The idea is to add a regular fast array that shortcuts to leaf data, either nodes or actual data.

Mutate then commit

Also the Tree views can leverage that cache to make many mutations more cheaply.

  1. Mark view as mutable
  2. Mutate nodes without updating the tree
  3. Commit and propagate change up the tree at once in batch (see https://github.com/ChainSafe/persistent-merkle-tree/pull/53)

This is similar to the persistent-ts architecture but without having to duplicate data.

References:

  • Teku ssz cache of views primitive https://github.com/ConsenSys/teku/blob/3044df72e9/ssz/src/main/java/tech/pegasys/teku/ssz/cache/ArrayIntCache.java
  • Teku BeaconState commit changes entrypoint https://github.com/ConsenSys/teku/blob/9c0086ca5af0f90eddc26ca437475adfa7afc914/ethereum/spec/src/main/java/tech/pegasys/teku/spec/datastructures/state/beaconstate/common/AbstractMutableBeaconState.java#L60
  • Teku BeaconState .update() wrapper to handle toMutable, mutations, commit steps at once https://github.com/ConsenSys/teku/blob/9cd657a7f057a1ed96b3e722df37f42f7bb60be4/ethereum/spec/src/main/java/tech/pegasys/teku/spec/logic/common/block/AbstractBlockProcessor.java#L281-L282
  • Teku ssz tree commit nodes function https://github.com/ConsenSys/teku/blob/b7246424d26194d49b1321e2f090d841468d5982/ssz/src/main/java/tech/pegasys/teku/ssz/impl/AbstractSszMutableComposite.java#L187-L188

dapplion avatar Sep 16 '21 09:09 dapplion