Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix: More reliably cache NameAccumulator modexps #326

Merged
merged 6 commits into from
Aug 17, 2023

Conversation

matheus23
Copy link
Member

BigUint::modexp operations take up to 14ms in Wasm on my machine, and it's the core operation for NameAccumulators.

This introduces a LRU cache inside HamtForest that caches NameAccumulator operations.

This is much more reliable than sprinkling OnceCells every here and there, since

  1. The "eviction" of these OnceCell caches depends on the lifetime of the object they're contained in, and it's harder to make these structs longer-lived in some cases.
  2. Sometimes the structs that these OnceCells are contained inside are mutable via &mut self operations. We need to remember to always empty these OnceCells when that happens. This is bad for two reasons: (1) we might forget doing so sometimes, keeping stale, incorrectly cached data around and (2) even though the cache doesn't match the object anymore, it may still be a useful cache!

@matheus23 matheus23 self-assigned this Aug 11, 2023
@matheus23 matheus23 requested a review from a team as a code owner August 11, 2023 12:53
@codecov
Copy link

codecov bot commented Aug 11, 2023

Codecov Report

Merging #326 (e4d26f9) into main (aa44005) will decrease coverage by 0.04%.
The diff coverage is 68.65%.

Impacted file tree graph

@@            Coverage Diff             @@
##             main     #326      +/-   ##
==========================================
- Coverage   56.30%   56.27%   -0.04%     
==========================================
  Files          43       43              
  Lines        3204     3172      -32     
  Branches      773      770       -3     
==========================================
- Hits         1804     1785      -19     
+ Misses        904      892      -12     
+ Partials      496      495       -1     
Files Changed Coverage Δ
wnfs/examples/write_proofs.rs 0.00% <0.00%> (ø)
wnfs/src/private/link.rs 51.89% <ø> (+2.50%) ⬆️
wnfs/src/private/forest/proofs.rs 53.22% <57.14%> (-1.78%) ⬇️
wnfs/src/private/forest/hamt.rs 44.76% <61.90%> (+1.60%) ⬆️
wnfs-nameaccumulator/src/name.rs 81.06% <66.66%> (-1.45%) ⬇️
wnfs/src/private/node/header.rs 79.10% <66.66%> (-1.72%) ⬇️
wnfs/src/private/directory.rs 68.44% <75.00%> (+0.65%) ⬆️
wnfs/src/private/file.rs 80.06% <83.33%> (+1.15%) ⬆️
wnfs/src/private/node/node.rs 71.25% <83.33%> (+1.31%) ⬆️
wnfs/src/private/forest/traits.rs 100.00% <100.00%> (ø)
... and 2 more

Copy link
Member

@appcypher appcypher left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks great to go. Another performance boost.
Great stuff @matheus23. We slowly getting there.

wnfs/src/private/node/header.rs Outdated Show resolved Hide resolved
@matheus23 matheus23 merged commit 380ee8c into main Aug 17, 2023
8 checks passed
@matheus23 matheus23 deleted the matheus23/modexp-cache branch August 17, 2023 12:09
@github-actions github-actions bot mentioned this pull request Aug 17, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants