-
-
Notifications
You must be signed in to change notification settings - Fork 92
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
Possibility to improve deletion in lru cache using swap back method? #185
Comments
Could you say a bit more about this? I assume it would mean to preserve the carcasses of bookkeeping data structures in an lru-with-deletion once they have been made, to avoid repeated object creation/destruction? |
Hello @mrflip,
mnemonist's implementation of lru cache does not allocate nor destroy objects to work at all. But to be able to handle deletion, it relies on a stack of unused pointers. It has a small performance and memory impact which is why the library packs the This issue is a reminder to me to consider a technique I use sometimes to allow for O(1) deletion in an unordered array to see if it could replace the stack of unused pointers. The idea is that if you need to delete i.e. index 3 of an unordered array, you just need to swap its item with the one in the back, then pop it. I have an intuition it could work for the cache's deletion but I need time to think thoroughly about it and did not find the time yet. |
No description provided.
The text was updated successfully, but these errors were encountered: