spec_stream_cache/
table.rs1use crate::allocator::{compute_block_prefix_hash, BlockAllocator};
2use crate::block::PhysicalBlockId;
3use crate::error::CacheError;
4use spec_stream_core::TokenId;
5
6#[derive(Debug, Clone)]
8pub struct BlockTable {
9 pub physical_blocks: Vec<PhysicalBlockId>,
11 pub prefix_hashes: Vec<u64>,
13 pub seq_len: usize,
15 pub block_size: usize,
17}
18
19impl BlockTable {
20 pub fn new(block_size: usize) -> Self {
21 Self {
22 physical_blocks: Vec::new(),
23 prefix_hashes: Vec::new(),
24 seq_len: 0,
25 block_size,
26 }
27 }
28
29 pub fn append_token(
32 &mut self,
33 token_id: TokenId,
34 allocator: &mut BlockAllocator,
35 ) -> Result<(), CacheError> {
36 if self.seq_len % self.block_size == 0 {
38 let block_id = allocator.allocate()?;
39 self.physical_blocks.push(block_id);
40 }
41
42 let last_idx = self.physical_blocks.len() - 1;
43 let current_block_id = self.physical_blocks[last_idx];
44
45 let block_id_to_use = if allocator.get_block(current_block_id)?.ref_count > 1 {
47 let new_block_id = allocator.clone_block(current_block_id)?;
48 allocator.free(current_block_id)?;
49 self.physical_blocks[last_idx] = new_block_id;
50 new_block_id
51 } else {
52 current_block_id
53 };
54
55 let block = allocator.get_block_mut(block_id_to_use)?;
56 block.tokens.push(token_id);
57 block.num_tokens += 1;
58 self.seq_len += 1;
59
60 if block.is_full() {
62 let parent_hash = self.prefix_hashes.last().copied();
63 let hash = compute_block_prefix_hash(parent_hash, &block.tokens);
64 self.prefix_hashes.push(hash);
65 allocator.register_prefix(hash, block_id_to_use);
66 }
67
68 Ok(())
69 }
70
71 pub fn append_tokens(
73 &mut self,
74 mut tokens: &[TokenId],
75 allocator: &mut BlockAllocator,
76 ) -> Result<(), CacheError> {
77 while !tokens.is_empty() && self.seq_len % self.block_size != 0 {
79 self.append_token(tokens[0], allocator)?;
80 tokens = &tokens[1..];
81 }
82
83 while tokens.len() >= self.block_size {
85 let chunk = &tokens[..self.block_size];
86 let parent_hash = self.prefix_hashes.last().copied();
87 let hash = compute_block_prefix_hash(parent_hash, chunk);
88
89 if let Some(shared_block_id) = allocator.find_prefix(hash) {
90 self.physical_blocks.push(shared_block_id);
92 self.prefix_hashes.push(hash);
93 self.seq_len += self.block_size;
94 } else {
95 let block_id = allocator.allocate()?;
97 {
98 let block = allocator.get_block_mut(block_id)?;
99 block.tokens.extend_from_slice(chunk);
100 block.num_tokens = self.block_size;
101 }
102 allocator.register_prefix(hash, block_id);
103 self.physical_blocks.push(block_id);
104 self.prefix_hashes.push(hash);
105 self.seq_len += self.block_size;
106 }
107
108 tokens = &tokens[self.block_size..];
109 }
110
111 for &t in tokens {
113 self.append_token(t, allocator)?;
114 }
115
116 Ok(())
117 }
118
119 pub fn rollback(
124 &mut self,
125 valid_token_count: usize,
126 allocator: &mut BlockAllocator,
127 ) -> Result<usize, CacheError> {
128 if valid_token_count > self.seq_len {
129 return Err(CacheError::InvalidRollback {
130 target_len: valid_token_count,
131 current_len: self.seq_len,
132 });
133 }
134
135 let tokens_discarded = self.seq_len - valid_token_count;
136 if tokens_discarded == 0 {
137 return Ok(0);
138 }
139
140 let required_blocks = valid_token_count.div_ceil(self.block_size);
142
143 while self.physical_blocks.len() > required_blocks {
145 let block_id = self.physical_blocks.pop().unwrap();
146 allocator.free(block_id)?;
147 if self.prefix_hashes.len() > self.physical_blocks.len() {
148 self.prefix_hashes.pop();
149 }
150 }
151
152 if let Some(&last_block_id) = self.physical_blocks.last() {
154 let tokens_in_last =
155 if valid_token_count % self.block_size == 0 && valid_token_count > 0 {
156 self.block_size
157 } else {
158 valid_token_count % self.block_size
159 };
160
161 if tokens_in_last < self.block_size
163 && self.prefix_hashes.len() == self.physical_blocks.len()
164 {
165 self.prefix_hashes.pop();
166 }
167
168 let last_idx = self.physical_blocks.len() - 1;
169 let block_to_truncate = if allocator.get_block(last_block_id)?.ref_count > 1 {
171 let new_block_id = allocator.clone_block(last_block_id)?;
172 allocator.free(last_block_id)?;
173 self.physical_blocks[last_idx] = new_block_id;
174 new_block_id
175 } else {
176 last_block_id
177 };
178
179 let last_block = allocator.get_block_mut(block_to_truncate)?;
180 last_block.num_tokens = tokens_in_last;
181 last_block.tokens.truncate(tokens_in_last);
182 last_block.prefix_hash = None;
183 }
184
185 self.seq_len = valid_token_count;
186 Ok(tokens_discarded)
187 }
188
189 pub fn translate_logical_offset(
191 &self,
192 logical_index: usize,
193 ) -> Result<(PhysicalBlockId, usize), CacheError> {
194 if logical_index >= self.seq_len {
195 return Err(CacheError::IndexOutOfBounds {
196 index: logical_index,
197 length: self.seq_len,
198 });
199 }
200
201 let block_idx = logical_index / self.block_size;
202 let offset = logical_index % self.block_size;
203 Ok((self.physical_blocks[block_idx], offset))
204 }
205
206 pub fn free_all(&mut self, allocator: &mut BlockAllocator) -> Result<(), CacheError> {
208 for &block_id in &self.physical_blocks {
209 allocator.free(block_id)?;
210 }
211 self.physical_blocks.clear();
212 self.prefix_hashes.clear();
213 self.seq_len = 0;
214 Ok(())
215 }
216}
217
218#[cfg(test)]
219mod tests {
220 use super::*;
221
222 #[test]
223 fn test_prefix_caching_sharing() {
224 let block_size = 4;
225 let mut allocator = BlockAllocator::new(10, block_size);
226 let mut table1 = BlockTable::new(block_size);
227 let mut table2 = BlockTable::new(block_size);
228
229 let system_prompt = vec![101, 102, 103, 104]; table1
233 .append_tokens(&system_prompt, &mut allocator)
234 .unwrap();
235 assert_eq!(allocator.num_free_blocks(), 9);
236 assert_eq!(allocator.num_prefix_entries(), 1);
237
238 table2
240 .append_tokens(&system_prompt, &mut allocator)
241 .unwrap();
242 assert_eq!(allocator.num_free_blocks(), 9); assert_eq!(table1.physical_blocks[0], table2.physical_blocks[0]); assert_eq!(
245 allocator
246 .get_block(table1.physical_blocks[0])
247 .unwrap()
248 .ref_count,
249 2
250 );
251
252 table1.free_all(&mut allocator).unwrap();
254 assert_eq!(allocator.num_free_blocks(), 9);
255 assert_eq!(
256 allocator
257 .get_block(table2.physical_blocks[0])
258 .unwrap()
259 .ref_count,
260 1
261 );
262
263 table2.free_all(&mut allocator).unwrap();
264 assert_eq!(allocator.num_free_blocks(), 10);
265 }
266
267 #[test]
268 fn test_copy_on_write() {
269 let block_size = 4;
270 let mut allocator = BlockAllocator::new(10, block_size);
271 let mut table1 = BlockTable::new(block_size);
272 let mut table2 = BlockTable::new(block_size);
273
274 let prompt = vec![1, 2, 3, 4];
275 table1.append_tokens(&prompt, &mut allocator).unwrap();
276 table2.append_tokens(&prompt, &mut allocator).unwrap();
277
278 let shared_id = table1.physical_blocks[0];
280 assert_eq!(table2.physical_blocks[0], shared_id);
281
282 table2.append_token(99, &mut allocator).unwrap();
284 assert_eq!(table2.seq_len, 5);
285 assert_eq!(table1.seq_len, 4);
286
287 table2.rollback(3, &mut allocator).unwrap();
289 assert_ne!(table1.physical_blocks[0], table2.physical_blocks[0]);
291 let block1 = allocator.get_block(table1.physical_blocks[0]).unwrap();
293 assert_eq!(block1.num_tokens, 4);
294 assert_eq!(block1.tokens, vec![1, 2, 3, 4]);
295
296 let block2 = allocator.get_block(table2.physical_blocks[0]).unwrap();
298 assert_eq!(block2.num_tokens, 3);
299 assert_eq!(block2.tokens, vec![1, 2, 3]);
300 }
301}