mina icon indicating copy to clipboard operation
mina copied to clipboard

Defer hashing in staged ledger diff application

Open georgeee opened this issue 6 months ago • 1 comments

Problem: when performing transaction application, all merkle ledger hashes are recomputed for every account update. This is wasteful for a number of reasons:

  1. Transactions normally contain more than one account update and a hash computed for an account update is sometimes overwritten by a subsequent account update
  2. Ledger's depth is 35, whereas only around 2^18 records are actually populated. This means that each account update induces an wasteful overhead of at least 17 hashes
  3. When an account is touched in a few transactions of the same block, it's gets hashed a few times, whereas in fact only the final hash is truly needed

Solution: defer computation of hashes in mask. When an account is added, it's stacked in a list unhashed_accounts of masks which is processed at the time of next access to hashes.

This fix improved performance of handling 9-account-update transactions by ~60% (measured by #14582 on top of #15979 and #15978).

Explain how you tested your changes:

  • [x] Measured performance with #14582

Checklist:

  • [x] Dependency versions are unchanged
    • Notify Velocity team if dependencies must change in CI
  • [ ] Modified the current draft of release notes with details on what is completed or incomplete within this project
  • [x] Document code purpose, how to use it
    • Mention expected invariants, implicit constraints
  • [x] Tests were added for the new behavior
    • Document test purpose, significance of failures
    • Test names should reflect their purpose
  • [x] All tests pass (CI will check this if you didn't)
  • [x] Serialized types are in stable-versioned modules
  • [x] Does this close issues? None

georgeee avatar Aug 26 '24 12:08 georgeee