3 ms·

Wait, what's wrong with removal? I assumed the algorithm was talking about "copy to compact as you go" ...

• vidarh 3y ago
  Copy to compact might be fine if your cache is small. The larger the cache is, the more expensive copy to compact gets relative to the rest of your logic. Hence why the original in the paper uses a linked list. You can still get closer to what an array would buy you. E.g. the example code in the paper uses a doubly linked list and there's reason to, so you can reduce overhead right away there. One of the other benefits of an array is you can wrap around just by using a modulo of an index, but you can avoid the conditionals for their list implementation by linking the list together into a ring instead. Those bits I've implemented in a quick and dirty Ruby version (the singly linked ring is last here: https://gist.github.com/vidarh/b72615c16673cb38630cab5148190557 https://gist.github.com/vidarh/b72615c16673cb38630cab5148190... ). You can then also do a "linked ring in array" version, and use that to both reduce the memory overhead (both from individual node allocations and from the size of the pointers in the linked list) by placing linked list/ring nodes in a statically sized array. You just need to relink the node you evict into where you want to insert. You can save on pointer size if that matters to you as well by using array indices instead of pointers in that case. Whether any of these matters is something you really should measure in your preferred implementation language.