SIEVE Cache (C)
Topics: cache eviction, doubly-linked list, second-chance
Problem
Implement the SIEVE eviction algorithm (Zhang et al., NSDI '24) — simpler than
LRU, with a better hit rate. It's a FIFO-ordered doubly-linked list of int -> int
where each entry has a visited bit, plus a hand that scans for a victim.
Nodes live in caller-provided storage (no allocation); look entries up with a
linear scan.
typedef struct SieveNode { int key, val; int visited; int used; struct SieveNode *older, *newer; } SieveNode;
typedef struct { SieveNode *nodes; size_t cap; size_t count; SieveNode *head, *tail, *hand; } Sieve;
void sieve_init(Sieve *c, SieveNode *storage, size_t cap);
bool sieve_get(Sieve *c, int key, int *out); // sets the visited bit
void sieve_put(Sieve *c, int key, int val); // insert at head / update; evict when full
size_t sieve_len(const Sieve *c);
The algorithm
sieve_get: on a hit, set the entry's visited bit (a "second chance") and
return its value.sieve_put: if the key exists, update its value and set visited. Otherwise
evict (when full), then insert the new entry at the head (newest) with
visited = 0.- Eviction (the heart of it): start at the hand (or the tail — oldest — on
the first eviction) and walk toward the head. For each entry: if
visited is
set, clear it and move on; the first entry whose bit is already clear is
evicted. Leave the hand pointing at the next entry toward the head, so the next
eviction continues from where this one stopped — that retained position is what
distinguishes SIEVE from a plain second-chance/CLOCK.
Key concepts
- Two links, two directions:
older points toward the tail (oldest), newer
toward the head (newest). Inserting at the head and scanning via newer gives
the old→new sweep.
- The hand persists: it is not reset to the tail each time. Keeping it in
place is why a hot entry near the tail isn't repeatedly rescanned.
- Wrap-around: if the hand runs past the head (
newer == NULL), wrap to the
tail. A full pass clears every bit, after which the oldest unvisited entry goes.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/sieve && /tmp/sieve
Sign in to submit your solution.