use std::collections::HashMap;
use crate::kv_cache::{BlockId, PagedKvCache};
use crate::spec::TokenId;
pub type KvSlot = (BlockId, usize);
struct RadixNode {
token: TokenId,
parent: Option<usize>,
children: HashMap<TokenId, usize>,
kv: Option<KvSlot>,
last_used: u64,
}
pub struct RadixCache {
nodes: Vec<RadixNode>,
root: usize,
owned: HashMap<BlockId, usize>,
clock: u64,
num_insertions: usize,
num_queries: usize,
hit_queries: usize,
hit_tokens: usize,
}
impl Default for RadixCache {
fn default() -> Self {
Self::new()
}
}
impl RadixCache {
pub fn new() -> Self {
let root = RadixNode {
token: TokenId::MAX,
parent: None,
children: HashMap::new(),
kv: None,
last_used: 0,
};
Self {
nodes: vec![root],
root: 0,
owned: HashMap::new(),
clock: 0,
num_insertions: 0,
num_queries: 0,
hit_queries: 0,
hit_tokens: 0,
}
}
fn new_node(&mut self, token: TokenId, parent: usize) -> usize {
let id = self.nodes.len();
self.clock += 1;
self.nodes.push(RadixNode {
token,
parent: Some(parent),
children: HashMap::new(),
kv: None,
last_used: self.clock,
});
self.nodes[parent].children.insert(token, id);
id
}
pub fn match_prefix(&self, tokens: &[TokenId]) -> (usize, Option<usize>) {
let mut cur = self.root;
let mut matched = 0;
for &t in tokens {
match self.nodes[cur].children.get(&t) {
Some(&next) => {
cur = next;
matched += 1;
}
None => break,
}
}
(matched, if matched > 0 { Some(cur) } else { None })
}
pub fn match_path(&mut self, tokens: &[TokenId]) -> (usize, Vec<KvSlot>) {
let mut cur = self.root;
let mut slots = Vec::new();
for &t in tokens {
match self.nodes[cur].children.get(&t) {
Some(&next) => {
cur = next;
match self.nodes[cur].kv {
Some(slot) => {
self.clock += 1;
self.nodes[cur].last_used = self.clock;
slots.push(slot);
}
None => break,
}
}
None => break,
}
}
(slots.len(), slots)
}
pub fn insert(&mut self, tokens: &[TokenId]) -> usize {
self.num_insertions += 1;
let mut cur = self.root;
let mut i = 0;
while i < tokens.len() {
match self.nodes[cur].children.get(&tokens[i]) {
Some(&next) => {
cur = next;
i += 1;
}
None => break,
}
}
for j in i..tokens.len() {
let id = self.new_node(tokens[j], cur);
cur = id;
}
tokens.len() - i
}
pub fn insert_with_kv(
&mut self,
tokens: &[TokenId],
slots: &[KvSlot],
kv: &mut PagedKvCache,
) -> usize {
debug_assert_eq!(tokens.len(), slots.len());
self.num_insertions += 1;
let mut cur = self.root;
let mut i = 0;
while i < tokens.len() {
match self.nodes[cur].children.get(&tokens[i]) {
Some(&next) => {
cur = next;
i += 1;
}
None => break,
}
}
for j in i..tokens.len() {
let id = self.new_node(tokens[j], cur);
self.nodes[id].kv = Some(slots[j]);
self.mark_owned(slots[j].0, kv);
cur = id;
}
tokens.len() - i
}
fn mark_owned(&mut self, block: BlockId, kv: &mut PagedKvCache) {
let count = self.owned.entry(block).or_insert(0);
if *count == 0 {
kv.inc_ref(block);
}
*count += 1;
}
pub fn record_match(&mut self, tokens: &[TokenId]) -> usize {
let (matched, _) = self.match_prefix(tokens);
self.record_matched(matched);
matched
}
pub fn record_matched(&mut self, matched: usize) {
self.num_queries += 1;
self.hit_tokens += matched;
if matched > 0 {
self.hit_queries += 1;
}
}
pub fn num_nodes(&self) -> usize {
self.nodes.len() - 1
}
pub fn num_insertions(&self) -> usize {
self.num_insertions
}
pub fn num_queries(&self) -> usize {
self.num_queries
}
pub fn hit_queries(&self) -> usize {
self.hit_queries
}
pub fn hit_tokens(&self) -> usize {
self.hit_tokens
}
pub fn cache_hit_rate(&self) -> f64 {
if self.num_queries == 0 {
0.0
} else {
self.hit_queries as f64 / self.num_queries as f64
}
}
pub fn evict_lru(&mut self, kv: &mut PagedKvCache, target: usize) -> usize {
let mut evicted = 0;
while evicted < target {
let mut best: Option<usize> = None;
for idx in 1..self.nodes.len() {
let node = &self.nodes[idx];
if node.kv.is_some() && node.children.is_empty() {
best = Some(match best {
None => idx,
Some(b) => {
if node.last_used < self.nodes[b].last_used {
idx
} else {
b
}
}
});
}
}
let Some(idx) = best else { break };
let (parent, token, slot) = {
let node = &self.nodes[idx];
(node.parent.expect("non-root node"), node.token, node.kv)
};
if let Some((block, _off)) = slot {
let reached_zero = match self.owned.get_mut(&block) {
Some(owned) => {
*owned = owned.saturating_sub(1);
*owned == 0
}
None => false,
};
if reached_zero {
self.owned.remove(&block);
kv.dec_ref(block);
}
}
self.nodes[parent].children.remove(&token);
self.nodes[idx].kv = None;
self.nodes[idx].parent = None;
self.nodes[idx].last_used = 0;
evicted += 1;
}
evicted
}
}
#[cfg(test)]
mod tests {
use super::*;
fn toks(s: &str) -> Vec<u32> {
s.bytes().map(|b| b as u32 + 3).collect()
}
#[test]
fn match_and_insert() {
let mut rc = RadixCache::new();
assert_eq!(rc.insert(&toks("hello world")), 11);
let (matched, _) = rc.match_prefix(&toks("hello there"));
assert_eq!(matched, 6); }
#[test]
fn hit_rate_accounting() {
let mut rc = RadixCache::new();
rc.insert(&toks("the quick"));
let m = rc.record_match(&toks("the quick brown"));
assert_eq!(m, 9);
rc.record_match(&toks("unrelated"));
assert_eq!(rc.num_queries(), 2);
assert_eq!(rc.hit_queries(), 1);
assert!((rc.cache_hit_rate() - 0.5).abs() < 1e-9);
}
#[test]
fn match_path_reports_slots() {
let mut kv = PagedKvCache::new(8, 4);
let mut rc = RadixCache::new();
let tokens = toks("hello");
let b0 = kv.alloc().unwrap();
let b1 = kv.alloc().unwrap();
let slots: Vec<KvSlot> = (0..tokens.len())
.map(|i| {
if i < 2 {
(b0, i)
} else {
(b1, i - 2)
}
})
.collect();
rc.insert_with_kv(&tokens, &slots, &mut kv);
assert_eq!(rc.match_path(&tokens).1, slots);
assert_eq!(kv.ref_count(b0), 2);
assert_eq!(kv.ref_count(b1), 2);
}
#[test]
fn evict_lru_releases_owned_blocks() {
let mut kv = PagedKvCache::new(8, 4);
let mut rc = RadixCache::new();
let tokens_a = toks("aaaa");
let b0 = kv.alloc().unwrap();
let b1 = kv.alloc().unwrap();
let slots_a: Vec<KvSlot> = vec![(b0, 0), (b0, 1), (b0, 2), (b1, 0)];
rc.insert_with_kv(&tokens_a, &slots_a, &mut kv);
let tokens_b = toks("bbbb");
let b2 = kv.alloc().unwrap();
let b3 = kv.alloc().unwrap();
let slots_b: Vec<KvSlot> = vec![(b2, 0), (b2, 1), (b2, 2), (b3, 0)];
rc.insert_with_kv(&tokens_b, &slots_b, &mut kv);
let _ = rc.match_path(&tokens_a);
assert_eq!(kv.ref_count(b2), 2);
assert_eq!(kv.ref_count(b3), 2);
let evicted = rc.evict_lru(&mut kv, 1);
assert_eq!(evicted, 1);
assert_eq!(rc.match_path(&tokens_a).0, tokens_a.len());
assert!(rc.match_path(&tokens_b).0 < tokens_b.len());
}
}