4 ms·

Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of dis

by vidarh 3y ago

Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of distance is outweighed by the effort in picking the insertion point. You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.

kazinator 3y ago
The roving Insert point is harder to implement, due to the reversed case: [ ][ ][I][ ][ ][H][ ][ ] ^^^^^^^^ `these items move right [ ][ ][H][ ][I][ ][ ][ ] ^^^^ ^^^^^^^ ^- this item moves to the top (left most slot) | `--- these items move right ` these items move right If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.
- 1a1a11a 3y ago
  I totally agree with you, this is not designed for hardware... and as others mentioned RRIP might be better for set-associative caches
  - vidarh 3y ago
    With respect to my other reply mentioning a ring instead of a linked list, here's a quick and dirty Ruby port because I couldn't resist that uses a ring with a single dummy head node to simplify the logic: https://gist.github.com/vidarh/b72615c16673cb38630cab5148190557 https://gist.github.com/vidarh/b72615c16673cb38630cab5148190... You'll note it avoids a bunch of conditionals in add_to_head, remove_node and evict because the wraparound happens automatically and the next/prev pointers are never nil/None I've not verified it matches the behaviour of yours exactly other than adding a handful of extra access calls and comparing the state. If you're not familiar with Ruby, the one particularly dirty trick I'm using is that in Ruby you can define methods directly on a specific object, so by defining the method "@head.visited" to always return true, the eviction will just try to set it to false and move straight over it every run, cutting a conditional. You could do a ring without a dummy @head to but it makes the insertion/deletion logic more annoying.
    - 1a1a11a 3y ago
      it looks like the ring is implemented using a linked list?
      - vidarh 3y ago
        Yes, I wanted to change as little as possible to illustrate why you almost always want to close your lists into a ring when using a linked list ;) It simplifies a lot of algorithms to be able to guarantee no null pointers. It's a very old trick. You trade a lot of conditionals and a risk of null pointers dereference for a smaller risk of non-termination (failure to check for a null pointer is always bad; failure to check for the end is only a problem if the end of the list is actually your termination condition). You could do a ring with an array and modulus too, but then you end up copying the whole thing to open up slots to insert to maintain the property of your insertion point being separate from the hand. That may or may not do worse, but likely to depend on cache size and implementation language. What you'd almost certainly want in a production implementation anyway would in any case be to do away with constantly allocating nodes and just move them to a free list and reuse to avoid dynamic allocation overhead and garbage collection.
      - vidarh 3y ago
        I added a second, singly-linked ring version to the gist I linked above. It doesn't save much, as to be able to unlink the hand you need to keep a pointer to the node adjacent to the hand (I changed "direction" in the naming because it feels weird to have a singly linked list with just "prev" pointers, but that doesn't matter), but it does mean a pointer less for each Node and from experience a lot of people struggle to get the pointer updates right for doubly linked lists, and that is a lot harder to get wrong when singly linked...
        1a1a11a 3y ago
        Got it. Make sense, I like the reason why you want to make it circular. :)
- vidarh 3y ago
  I'd just have implemented it as a ring instead of a list and insertion at any point is identical, but my point was exactly that unless your workload specifically fits insert at the "hand" better than the current algorithm, you will need to account for the cost of whatever complexity you add in order to move the insert point. > If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance. I don't see why I would think about doing it in hardware.

by vidarh 3y ago

kazinator 3y ago

The roving Insert point is harder to implement, due to the reversed case: [ ][ ][I][ ][ ][H][ ][ ] ^^^^^^^^ `these items move right [ ][ ][H][ ][I][ ][ ][ ] ^^^^ ^^^^^^^ ^- this item moves to the top (left most slot) | `--- these items move right ` these items move right If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.

1a1a11a 3y ago
I totally agree with you, this is not designed for hardware... and as others mentioned RRIP might be better for set-associative caches
- vidarh 3y ago
  With respect to my other reply mentioning a ring instead of a linked list, here's a quick and dirty Ruby port because I couldn't resist that uses a ring with a single dummy head node to simplify the logic: https://gist.github.com/vidarh/b72615c16673cb38630cab5148190557 https://gist.github.com/vidarh/b72615c16673cb38630cab5148190... You'll note it avoids a bunch of conditionals in add_to_head, remove_node and evict because the wraparound happens automatically and the next/prev pointers are never nil/None I've not verified it matches the behaviour of yours exactly other than adding a handful of extra access calls and comparing the state. If you're not familiar with Ruby, the one particularly dirty trick I'm using is that in Ruby you can define methods directly on a specific object, so by defining the method "@head.visited" to always return true, the eviction will just try to set it to false and move straight over it every run, cutting a conditional. You could do a ring without a dummy @head to but it makes the insertion/deletion logic more annoying.
  - 1a1a11a 3y ago
    it looks like the ring is implemented using a linked list?
    - vidarh 3y ago
      Yes, I wanted to change as little as possible to illustrate why you almost always want to close your lists into a ring when using a linked list ;) It simplifies a lot of algorithms to be able to guarantee no null pointers. It's a very old trick. You trade a lot of conditionals and a risk of null pointers dereference for a smaller risk of non-termination (failure to check for a null pointer is always bad; failure to check for the end is only a problem if the end of the list is actually your termination condition). You could do a ring with an array and modulus too, but then you end up copying the whole thing to open up slots to insert to maintain the property of your insertion point being separate from the hand. That may or may not do worse, but likely to depend on cache size and implementation language. What you'd almost certainly want in a production implementation anyway would in any case be to do away with constantly allocating nodes and just move them to a free list and reuse to avoid dynamic allocation overhead and garbage collection.
    - vidarh 3y ago
      I added a second, singly-linked ring version to the gist I linked above. It doesn't save much, as to be able to unlink the hand you need to keep a pointer to the node adjacent to the hand (I changed "direction" in the naming because it feels weird to have a singly linked list with just "prev" pointers, but that doesn't matter), but it does mean a pointer less for each Node and from experience a lot of people struggle to get the pointer updates right for doubly linked lists, and that is a lot harder to get wrong when singly linked...
      - 1a1a11a 3y ago
        Got it. Make sense, I like the reason why you want to make it circular. :)
vidarh 3y ago
I'd just have implemented it as a ring instead of a list and insertion at any point is identical, but my point was exactly that unless your workload specifically fits insert at the "hand" better than the current algorithm, you will need to account for the cost of whatever complexity you add in order to move the insert point. > If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance. I don't see why I would think about doing it in hardware.