Skip to content

perf: Track VecDeque positions in HashMap for O(1) LRU touch - #146

Merged
adityamukho merged 1 commit into
mainfrom
perf/hashmap-lru-touch
Apr 17, 2026
Merged

adityamukho merged 1 commit into
mainfrom
perf/hashmap-lru-touch

Conversation

@adityamukho

Copy link
Copy Markdown
Collaborator

Summary

  • Add positions: HashMap<u64, usize> to CacheInner to track page positions in VecDeque
  • Replace O(c) linear scan in touch() with O(1) HashMap lookup
  • Use swap-with-back optimization to avoid updating all positions after removal
  • Update invalidate and invalidate_from to also clean up positions

Fixes #141

@codecov

codecov Bot commented Apr 17, 2026 •

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 86.66667% with 2 lines in your changes missing coverage. Please review.
✅ Project coverage is 83.41%. Comparing base (a608b14) to head (3e8968f).
⚠️ Report is 2 commits behind head on main.

Files with missing lines Patch % Lines
src/storage/cache.rs 86.66% 2 Missing ⚠️
Additional details and impacted files

Impacted file tree graph

@@           Coverage Diff           @@
##             main     #146   +/-   ##
=======================================
  Coverage   83.40%   83.41%           
=======================================
  Files          26       26           
  Lines        4810     4823   +13     
=======================================
+ Hits         4012     4023   +11     
- Misses        798      800    +2     
Files with missing lines Coverage Δ
src/storage/cache.rs 85.93% <86.66%> (-0.34%) ⬇️
🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@adityamukho
adityamukho merged commit c88e666 into main Apr 17, 2026
22 checks passed
@adityamukho
adityamukho deleted the perf/hashmap-lru-touch branch April 17, 2026 10:25
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.

perf: Track VecDeque positions in HashMap for O(1) LRU touch

1 participant