mina
mina copied to clipboard
Defer hashing in staged ledger diff application
Problem: when performing transaction application, all merkle ledger hashes are recomputed for every account update. This is wasteful for a number of reasons:
- Transactions normally contain more than one account update and a hash computed for an account update is sometimes overwritten by a subsequent account update
- 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
- 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