ben-manes / caffeine / #3265
100%
master: 100%

LAST BUILD BRANCH: v3.dev
DEFAULT BRANCH: master
Ran
Jobs 1
Files 77
Run time 14s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
#3265

push

github-actions

ben-manes 
Simplify the eviction logic and add more explicit scenarios

The attempt to simplify the logic in 25b7d17 accidentally removed the
candidate evaluations when multiple entries need to be evicted. The
original logic conditionally swiched between MRU and LRU order based
on the queue it was consuming. As the logic was confusing it seemed
related to weights, whereas it was related to LRU promotions.

When the admission window evicts it promotes its entries to the
probation queue's MRU position. Previously a counter was used to track
this so that if the main space evicts it can use TinyLFU to chose
between the LRU victim or the newly admitted candidate. This causes a
dual walk from the MRU and LRU ends of the queue, with fallback to the
other queues if exhausted.

A simpler variant than a counter is to provide the first promoted
candidate entry. Then the candidates are LRU'd out starting near the
tail position, whereas the victims are LRU'd starting from the head
position. The same traversal order is used and the walks can switch
to the alternative queues as needed.

The tests uncovered cases that were implicitly handled but should have
been explicit for clarity. In particular that a concurrently removed
entry should be discarded promptly by eviction, that the cursors could
overlap and point to the same entry, and that the window might not be
emptied due to skipping zero weight entries.

7359 of 7481 relevant lines covered (98.37%)

0.98 hits per line

Jobs
ID Job ID Ran Files Coverage
1 #3265.1 0
98.37
Source Files on build #3265
Detailed source file information is not available for this build.