1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
//! Clustered index for cache-friendly low-degree vertex storage.
//!
//! This module provides a memory-efficient storage structure that groups
//! multiple neighbor sets into contiguous blocks for optimal cache utilization.
//!
//! # EPIC-020 US-004: Clustered Index for Low-Degree Vertices
//!
//! ## Design
//!
//! Instead of allocating separate `Vec<u64>` per node (48+ bytes overhead each),
//! we store all neighbor sets in a single contiguous buffer with an index
//! mapping node IDs to (offset, length) pairs.
//!
//! ## References
//!
//! - RapidStore Section 6.3: "low-degree vertices use small arrays further
//! grouped into a tree to optimize memory usage"
// Reason: Numeric casts in clustered index are intentional:
// - usize->f64 for fragmentation ratio: precision loss acceptable (0-1 ratio)
// - Values bounded by buffer sizes, used for statistics only
#![allow(clippy::cast_precision_loss)]
use rustc_hash::FxHashMap;
/// Fragmentation threshold (30%) that triggers automatic compaction.
const FRAGMENTATION_THRESHOLD: f64 = 0.30;
/// Clustered index storing multiple neighbor sets in contiguous memory.
///
/// Optimized for low-degree vertices (< 100 neighbors) where memory overhead
/// of individual allocations dominates.
#[derive(Debug, Clone)]
pub struct ClusteredIndex {
/// Contiguous storage for all neighbor targets
data: Vec<u64>,
/// Maps node_id -> (offset, length) in data
index: FxHashMap<u64, (usize, usize)>,
/// Free slots available for reuse: (offset, length)
free_slots: Vec<(usize, usize)>,
/// Total bytes marked as free (for fragmentation calculation)
free_bytes: usize,
}
impl ClusteredIndex {
/// Creates a new empty clustered index.
#[must_use]
pub fn new() -> Self {
Self {
data: Vec::new(),
index: FxHashMap::default(),
free_slots: Vec::new(),
free_bytes: 0,
}
}
/// Creates a clustered index with pre-allocated capacity.
#[must_use]
pub fn with_capacity(node_capacity: usize, data_capacity: usize) -> Self {
Self {
data: Vec::with_capacity(data_capacity),
index: FxHashMap::with_capacity_and_hasher(node_capacity, rustc_hash::FxBuildHasher),
free_slots: Vec::new(),
free_bytes: 0,
}
}
/// Gets the neighbors for a node as a slice.
#[must_use]
pub fn get_neighbors(&self, node_id: u64) -> &[u64] {
if let Some(&(offset, length)) = self.index.get(&node_id) {
&self.data[offset..offset + length]
} else {
&[]
}
}
/// Inserts a target for a node.
///
/// If the node doesn't exist, creates a new entry.
/// If the node exists, may need to relocate to a larger slot.
pub fn insert(&mut self, node_id: u64, target: u64) {
if let Some(&(offset, length)) = self.index.get(&node_id) {
// Check if target already exists
let slice = &self.data[offset..offset + length];
if slice.contains(&target) {
return;
}
// Need to add target - try to extend in place or relocate
let new_length = length + 1;
// Check if we can extend in place (next slot is free or end of data)
let can_extend = offset + length == self.data.len()
|| self.try_merge_adjacent_free(offset + length, 1);
if can_extend && offset + length == self.data.len() {
// Extend at end
self.data.push(target);
self.index.insert(node_id, (offset, new_length));
} else if can_extend {
// Extended into adjacent free slot
self.data[offset + length] = target;
self.index.insert(node_id, (offset, new_length));
} else {
// Need to relocate
let old_data: Vec<u64> = self.data[offset..offset + length].to_vec();
self.mark_free(offset, length);
// Find or allocate new slot
let new_offset = self.allocate_slot(new_length);
for (i, &val) in old_data.iter().enumerate() {
self.data[new_offset + i] = val;
}
self.data[new_offset + length] = target;
self.index.insert(node_id, (new_offset, new_length));
}
} else {
// New node - allocate slot
let offset = self.allocate_slot(1);
self.data[offset] = target;
self.index.insert(node_id, (offset, 1));
}
// Check for compaction
self.maybe_compact();
}
/// Removes a target from a node.
///
/// Returns true if the target was present and removed.
pub fn remove(&mut self, node_id: u64, target: u64) -> bool {
if let Some(&(offset, length)) = self.index.get(&node_id) {
let slice = &self.data[offset..offset + length];
if let Some(pos) = slice.iter().position(|&t| t == target) {
if length == 1 {
// Remove entire entry
self.mark_free(offset, length);
self.index.remove(&node_id);
} else {
// Swap-remove within the slice
self.data[offset + pos] = self.data[offset + length - 1];
self.index.insert(node_id, (offset, length - 1));
// Mark the freed slot
self.free_slots.push((offset + length - 1, 1));
self.free_bytes += 1;
}
return true;
}
}
false
}
/// Removes all neighbors for a node.
pub fn remove_node(&mut self, node_id: u64) {
if let Some((offset, length)) = self.index.remove(&node_id) {
self.mark_free(offset, length);
}
}
/// Returns the number of nodes in the index.
#[must_use]
pub fn node_count(&self) -> usize {
self.index.len()
}
/// Returns the total number of edges stored.
#[must_use]
pub fn edge_count(&self) -> usize {
self.index.values().map(|(_, len)| len).sum()
}
/// Returns the fragmentation ratio (0.0 to 1.0).
#[must_use]
pub fn fragmentation(&self) -> f64 {
if self.data.is_empty() {
0.0
} else {
self.free_bytes as f64 / self.data.len() as f64
}
}
/// Compacts the index, eliminating fragmentation.
pub fn compact(&mut self) {
if self.free_bytes == 0 {
return;
}
// Collect all node data
let entries: Vec<(u64, Vec<u64>)> = self
.index
.iter()
.map(|(&node_id, &(offset, length))| {
(node_id, self.data[offset..offset + length].to_vec())
})
.collect();
// Clear and rebuild
self.data.clear();
self.index.clear();
self.free_slots.clear();
self.free_bytes = 0;
for (node_id, neighbors) in entries {
let offset = self.data.len();
let length = neighbors.len();
self.data.extend(neighbors);
self.index.insert(node_id, (offset, length));
}
}
/// Checks if a node has a specific target.
#[must_use]
pub fn contains(&self, node_id: u64, target: u64) -> bool {
self.get_neighbors(node_id).contains(&target)
}
/// Returns the number of neighbors for a node.
#[must_use]
pub fn neighbor_count(&self, node_id: u64) -> usize {
self.index.get(&node_id).map_or(0, |(_, len)| *len)
}
fn allocate_slot(&mut self, needed: usize) -> usize {
// First-fit allocation from free list
for i in 0..self.free_slots.len() {
let (offset, length) = self.free_slots[i];
if length >= needed {
if length > needed {
// Split the slot
self.free_slots[i] = (offset + needed, length - needed);
} else {
// Exact fit
self.free_slots.swap_remove(i);
}
self.free_bytes = self.free_bytes.saturating_sub(needed);
return offset;
}
}
// No suitable free slot, append to end
let offset = self.data.len();
self.data.resize(self.data.len() + needed, 0);
offset
}
fn mark_free(&mut self, offset: usize, length: usize) {
self.free_slots.push((offset, length));
self.free_bytes += length;
self.merge_adjacent_free_slots();
}
fn try_merge_adjacent_free(&mut self, offset: usize, needed: usize) -> bool {
for i in 0..self.free_slots.len() {
let (free_offset, free_length) = self.free_slots[i];
if free_offset == offset && free_length >= needed {
if free_length > needed {
self.free_slots[i] = (free_offset + needed, free_length - needed);
} else {
self.free_slots.swap_remove(i);
}
self.free_bytes = self.free_bytes.saturating_sub(needed);
return true;
}
}
false
}
fn merge_adjacent_free_slots(&mut self) {
if self.free_slots.len() < 2 {
return;
}
// Sort by offset
self.free_slots.sort_unstable_by_key(|(offset, _)| *offset);
// Merge adjacent slots
let mut i = 0;
while i < self.free_slots.len() - 1 {
let (offset1, len1) = self.free_slots[i];
let (offset2, len2) = self.free_slots[i + 1];
if offset1 + len1 == offset2 {
// Merge
self.free_slots[i] = (offset1, len1 + len2);
self.free_slots.remove(i + 1);
} else {
i += 1;
}
}
}
fn maybe_compact(&mut self) {
if self.fragmentation() > FRAGMENTATION_THRESHOLD {
self.compact();
}
}
}
impl Default for ClusteredIndex {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
#[path = "clustered_index_unit_tests.rs"]
mod tests;