Possibility to improve deletion in lru cache using swap back method?

[mrflip]

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? How big is the performance hit and is it for all use cases?

[Yomguithereal]

Hello @mrflip,

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?

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 LRUCacheWithDelete class separately so people who don't need deletions don't have to pay the cost.

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.