← SIEVE Cache cachingmedium ready

Problem

SIEVE Cache (Rust)

Topics: cache eviction, index arena, SIEVE

Problem

Implement the SIEVE eviction algorithm (Zhang et al., NSDI 2024) — simpler than LRU, with a better hit rate. It's a single FIFO-ordered doubly-linked list where each entry has a visited bit, plus a hand that scans for a victim.

pub struct Sieve { /* … */ }
impl Sieve {
    pub fn new(capacity: usize) -> Self;
    pub fn get(&mut self, key: i32) -> Option<i32>;
    pub fn put(&mut self, key: i32, val: i32);
    pub fn len(&self) -> usize;
}

New entries are inserted at the head (newest) with their visited bit clear.
get (a hit) sets the entry's visited bit — its "second chance" — and does not move it.
On a full put, evict: start at the hand (or the tail/oldest on the first eviction) and scan toward the head, clearing any set visited bit you pass; evict the first entry whose bit is already clear. The hand then advances to the next candidate (toward the head) and keeps that position for the next eviction.
Updating an existing key refreshes its value and marks it visited.

put 1,2,3 (cap 3); get(1); put(4)   → evicts 2, not 1 (1 had its bit set)

The list is held in an index arena (a Vec<Node> + a free list) so links are O(1) without raw pointers. The arena plumbing (alloc, insert_at_head, unlink) is provided; you implement get, put, and evict.

Grading

Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using rustc --test. Only solution.rs is yours to edit.

Sign in to submit your solution.

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.

use std::collections::HashMap;

// SIEVE (Zhang et al., NSDI '24): a single FIFO-ordered doubly-linked list where
// each entry has a `visited` bit, plus a `hand` that scans old→new looking for an
// unvisited victim. A hit just sets the bit; the hand clears bits as it passes and
// evicts the first entry whose bit is already clear, keeping its position between
// evictions. Simpler than LRU, with a better hit rate.
//
// The arena + list plumbing (alloc, insert_at_head, unlink) is provided; implement
// `get`, `put`, and the `evict` policy. `older` points toward the tail (oldest),
// `newer` toward the head (newest); new entries are inserted at the head.
struct Node {
    key: i32,
    val: i32,
    visited: bool,
    older: Option<usize>,
    newer: Option<usize>,
}

pub struct Sieve {
    cap: usize,
    nodes: Vec<Node>,
    free: Vec<usize>,
    index: HashMap<i32, usize>,
    head: Option<usize>, // newest
    tail: Option<usize>, // oldest
    hand: Option<usize>,
}

impl Sieve {
    pub fn new(capacity: usize) -> Self {
        Sieve {
            cap: capacity,
            nodes: Vec::new(),
            free: Vec::new(),
            index: HashMap::new(),
            head: None,
            tail: None,
            hand: None,
        }
    }

pub fn len(&self) -> usize {
        self.index.len()
    }

pub fn is_empty(&self) -> bool {
        self.index.is_empty()
    }

/// A hit sets the visited bit (the entry's "second chance") and returns the value.
    pub fn get(&mut self, key: i32) -> Option<i32> {
        let _ = key;
        unimplemented!()
    }

/// Updating an existing key refreshes its value and marks it visited; a new key
    /// is inserted at the head, evicting first if the cache is full.
    pub fn put(&mut self, key: i32, val: i32) {
        let _ = (key, val);
        unimplemented!()
    }

fn alloc(&mut self, node: Node) -> usize {
        if let Some(i) = self.free.pop() {
            self.nodes[i] = node;
            i
        } else {
            self.nodes.push(node);
            self.nodes.len() - 1
        }
    }

fn insert_at_head(&mut self, i: usize) {
        self.nodes[i].older = self.head;
        self.nodes[i].newer = None;
        if let Some(h) = self.head {
            self.nodes[h].newer = Some(i);
        }
        self.head = Some(i);
        if self.tail.is_none() {
            self.tail = Some(i);
        }
    }

fn unlink(&mut self, i: usize) {
        let (older, newer) = (self.nodes[i].older, self.nodes[i].newer);
        match older {
            Some(o) => self.nodes[o].newer = newer,
            None => self.tail = newer,
        }
        match newer {
            Some(n) => self.nodes[n].older = older,
            None => self.head = older,
        }
    }

/// Scan from the hand (or the tail on the first eviction) toward the head,
    /// clearing visited bits, and drop the first entry whose bit is already clear.
    fn evict(&mut self) {
        unimplemented!()
    }
}