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
//! BFS-based graph reordering for improved cache locality during HNSW search.
//!
//! After index construction, vectors are stored in insertion order. Reordering
//! them in BFS traversal order from the entry point improves spatial locality
//! when following graph edges during search, reducing cache misses by 15-30%.
//!
//! Reference: "Graph Reordering for Cache-Efficient Near Neighbor Search"
//! (arXiv:2104.03221, NeurIPS 2022).
use super::super::distance::DistanceEngine;
use super::super::layer::NodeId;
use super::{NativeHnsw, NO_ENTRY_POINT};
use std::collections::VecDeque;
use std::sync::atomic::Ordering;
/// Minimum element count below which reordering provides no measurable benefit.
/// At <1000 vectors, the entire working set fits in L2 cache.
const REORDER_THRESHOLD: usize = 1000;
impl<D: DistanceEngine> NativeHnsw<D> {
/// Reorders graph nodes in BFS traversal order for improved cache locality.
///
/// After reordering, vectors that are close in the graph are also close
/// in memory, reducing cache misses during search traversal.
///
/// # When to call
///
/// - After `build()` completes for a static index
/// - After compaction of a dynamic index
/// - Not needed for small indices (< 1000 vectors)
///
/// # What the caller has to do with the answer
///
/// **This renumbers every node.** The returned `old_to_new` — `result[i]`
/// is the new id of the node that was `i` — is not a diagnostic: anything
/// outside this graph that is keyed by node id is stale until it has been
/// put through it. Two things are, and neither used to be:
///
/// - `HnswIndex`'s external-id mappings. Without the remap, `ANALYZE` on
/// a 1 100-point collection turned the correct answer
/// `[500, 501, 499, 502, 498]` into `[575, 601, 586, 560, 588]` — every
/// lookup still resolved, to the wrong vector.
/// - The quantized backends' positional code store, whose codes then
/// describe other nodes: recall@10 measured 1.000 before a reorder and
/// **0.000** after, with no error raised anywhere (#2112).
///
/// `None` means the pass declined (below the threshold, or no entry
/// point) and nothing moved.
///
/// # Errors
///
/// Returns an error if vector storage reordering fails.
pub fn reorder_for_locality(&self) -> crate::error::Result<Option<Vec<usize>>> {
let count = self.count.load(Ordering::Relaxed);
if count < REORDER_THRESHOLD {
return Ok(None);
}
let entry = self.entry_point.load(Ordering::Acquire);
if entry == NO_ENTRY_POINT {
return Ok(None);
}
let permutation = self.compute_bfs_order(entry, count);
if permutation.is_empty() {
return Ok(None);
}
let old_to_new = self.apply_permutation(&permutation)?;
// Reordering rewrites both the vector buffer AND every neighbour
// list, so any cached CSR / flat-vector snapshot built from the
// pre-reorder topology is now stale. The contract on
// `invalidate_gpu_caches` is "call after every mutation that
// changes the set of active nodes or their vector data" — an
// in-place permutation qualifies. This was a pre-existing gap
// (PR #626 never invalidated here either); folding the fix into
// PR-B of #634 since the whole point of the unified version
// counter is to close this class of bug.
#[cfg(feature = "gpu")]
self.invalidate_gpu_caches();
Ok(Some(old_to_new))
}
/// Computes BFS traversal order starting from the entry point on layer 0.
///
/// Returns a permutation where `result[i]` is the old node ID that should
/// occupy position `i` after reordering. Disconnected nodes are appended
/// in their original order after the BFS component.
fn compute_bfs_order(&self, entry: NodeId, count: usize) -> Vec<NodeId> {
let layers = self.layers.read();
if layers.is_empty() {
return Vec::new();
}
let mut order = Vec::with_capacity(count);
let mut visited = vec![false; count];
let mut queue = VecDeque::with_capacity(count);
if entry < count {
visited[entry] = true;
queue.push_back(entry);
}
self.bfs_walk(&layers[0], &mut queue, &mut visited, &mut order, count);
// The BFS is the guard's last use; the unvisited sweep reads only
// the local `visited` bitmap.
drop(layers);
self.append_unvisited(&visited, &mut order);
order
}
/// Runs BFS on the given layer, draining the queue and appending nodes to `order`.
#[allow(clippy::unused_self)] // Reason: method receiver for future per-graph config
fn bfs_walk(
&self,
layer: &super::super::layer::Layer,
queue: &mut VecDeque<NodeId>,
visited: &mut [bool],
order: &mut Vec<NodeId>,
count: usize,
) {
while let Some(node) = queue.pop_front() {
order.push(node);
let _ = layer.with_neighbors(node, |neighbors| {
for &neighbor in neighbors {
if neighbor < count && !visited[neighbor] {
visited[neighbor] = true;
queue.push_back(neighbor);
}
}
});
}
}
/// Appends any unvisited nodes (disconnected components) to `order`.
#[allow(clippy::unused_self)] // Reason: method receiver for future per-graph config
fn append_unvisited(&self, visited: &[bool], order: &mut Vec<NodeId>) {
for (node, &was_visited) in visited.iter().enumerate() {
if !was_visited {
order.push(node);
}
}
}
/// Applies a permutation to vectors, neighbor lists, and the entry point.
///
/// Returns the `old_to_new` map it used, so the caller can put whatever
/// it keys by node id through the same renumbering.
fn apply_permutation(&self, new_order: &[NodeId]) -> crate::error::Result<Vec<usize>> {
let count = new_order.len();
let old_to_new = Self::build_reverse_mapping(new_order, count);
// The entry point, and the anchor tree's root with it, moves only under
// the promotion lock (#2259); rank 8, before the vectors and layers
// write locks the permutation takes.
self.with_promotion_lock(|| {
self.reorder_vectors(new_order)?;
self.remap_neighbor_ids(&old_to_new);
self.update_entry_point(&old_to_new, count);
Ok::<(), crate::error::Error>(())
})?;
Ok(old_to_new)
}
/// Builds a reverse mapping: `result[old_id] = new_id`.
fn build_reverse_mapping(new_order: &[NodeId], count: usize) -> Vec<usize> {
let mut old_to_new = vec![0usize; count];
for (new_id, &old_id) in new_order.iter().enumerate() {
if old_id < count {
old_to_new[old_id] = new_id;
}
}
old_to_new
}
/// Reorders vector storage according to the given permutation.
fn reorder_vectors(&self, new_order: &[NodeId]) -> crate::error::Result<()> {
let mut guard = self.vectors.write();
if let Some(storage) = guard.as_mut() {
storage.reorder(new_order)?;
}
drop(guard);
Ok(())
}
/// Remaps all neighbor IDs in all layers according to the mapping.
fn remap_neighbor_ids(&self, old_to_new: &[usize]) {
let mut layers = self.layers.write();
for layer in layers.iter_mut() {
layer.remap_ids(old_to_new);
}
}
/// Updates the entry point to its new ID after permutation.
///
/// Runs under the promotion lock ([`Self::apply_permutation`]), like every
/// other move of the entry point; the anchor tree's root moves with it,
/// renamed by `remap_neighbor_ids`.
fn update_entry_point(&self, old_to_new: &[usize], count: usize) {
let old_ep = self.entry_point.load(Ordering::Acquire);
if old_ep != NO_ENTRY_POINT && old_ep < count {
self.entry_point
.store(old_to_new[old_ep], Ordering::Release);
}
}
}
#[cfg(test)]
#[path = "reorder_tests.rs"]
mod tests;