Understanding swap_remove Semantics and Order Preservation in Turbovec

TurboQuantIndex::swap_remove performs O(1) removal by swapping the target vector with the last element and truncating the buffer, which intentionally does not preserve original ordering and returns the former index of the moved vector.

In the turbovec crate, efficient vector management is critical for high-performance similarity search. The swap_remove method on TurboQuantIndex offers a constant-time deletion mechanism that trades order preservation for speed, mirroring the semantics of Rust's standard Vec::swap_remove. This operation is fundamental for applications that need to remove vectors from a quantized index without rebuilding the entire data structure.

How TurboQuantIndex::swap_remove Works

The swap_remove method in turbovec/src/lib.rs implements an optimized deletion strategy that completes in constant time regardless of the number of stored vectors.

The O(1) Removal Mechanism

Instead of shifting all subsequent elements to fill the gap (which would be O(n)), the method swaps the vector at the requested index with the last stored vector. According to the source code in turbovec/src/lib.rs (lines 694-707), the implementation performs these atomic steps:

1. Bounds validation – An assert! macro verifies that the supplied idx is less than n_vectors, panicking immediately if the index is out of bounds.
2. Data swapping – The packed codes of the last vector are copied into the slot at idx using self.packed_codes.copy_within (lines 178-181).
3. Scale adjustment – The norm value (scale) of the last vector is moved to the removed slot via self.scales[idx] = self.scales[last] (lines 222-224).
4. Truncation – Both the packed_codes and scales buffers are truncated to remove the last element, and n_vectors is decremented (lines 268-272).

Order Preservation Semantics

The original order of vectors is explicitly not preserved. As documented in the source comments (lines 692-698), the method moves the last vector into the deleted position, meaning any code relying on stable vector positions will break. The documentation explicitly states: "order is not preserved; the index of the previously-last vector changes."

Return Value Significance

The method returns the index of the vector that was moved into the deleted slot. This equals the supplied idx only when removing the last element (a no-swap operation). Otherwise, it returns the former last index (last), allowing callers to track which vector now occupies the removed position.

Implementation Details and Cache Management

Beyond the basic swap operation, swap_remove handles several internal consistency requirements to maintain index validity.

SIMD Cache Invalidation

Turbovec maintains a SIMD-blocked layout (blocked) derived from the packed codes for accelerated search operations. After a structural modification like swap_remove, this cached layout becomes stale. The implementation resets it via self.blocked = OnceLock::new(); (lines 331-332), ensuring that subsequent searches operate on fresh data.

Byte Layout Calculations

The method calculates bytes_per_vec from the dimension and bit-width parameters to determine the exact memory offsets for the copy_within operation. This ensures that quantized code data aligns correctly when moved between positions.

Stable ID Mapping with IdMapIndex

While TurboQuantIndex operates on raw indices, the IdMapIndex wrapper in turbovec/src/id_map.rs provides stable external ID mapping atop the raw index.

Bidirectional Mapping Maintenance

When IdMapIndex::remove is called, it translates the external ID to an internal slot, invokes inner.swap_remove, then mirrors the swap-and-pop operation in its bidirectional mapping tables (id_to_slot and slot_to_id). As implemented in lines 65-78, this ensures that after removal, the ID-to-slot mapping remains consistent with the new internal layout while preserving the stability of remaining IDs.

This wrapper allows applications to use stable string or integer identifiers while still benefiting from the O(1) removal performance of the underlying量化 index.

Verification Through Testing

The repository includes comprehensive validation in turbovec/tests/swap_remove.rs that confirms all semantic guarantees:

• Length contraction – The vector count decreases by exactly one after removal.
• Index return values – Removing the last element returns its own index; removing any other element returns the former last index.
• Search consistency – After removal and cache invalidation, the index returns correct top-k results that exclude deleted vectors.
• Self-query integrity – Remaining vectors still correctly identify themselves in search results.
• Bounds safety – Out-of-bounds indices trigger panics as expected.

These tests verify that the cache reset, scale copying, and truncation operations work in concert to maintain index integrity.

Practical Examples

Basic swap_remove Usage

use turbovec::TurboQuantIndex;

// Create an index with dimension 128 and 4-bit codes.
let mut idx = TurboQuantIndex::new(128, 4).unwrap();

// Add 5 random vectors.
let vectors = vec![0.0f32; 5 * 128]; // (normally filled with real data)
idx.add(&vectors);
assert_eq!(idx.len(), 5);

// Remove the vector at position 2.
// The last vector (index 4) is swapped into slot 2.
let moved_from = idx.swap_remove(2);
assert_eq!(moved_from, 4);   // index of the moved vector
assert_eq!(idx.len(), 4);    // length decreased

// Removing the last element performs a no-swap.
let moved_from = idx.swap_remove(3);
assert_eq!(moved_from, 3);
assert_eq!(idx.len(), 3);

Stable ID Removal with IdMapIndex

use turbovec::IdMapIndex;

// Stable-ID wrapper.
let mut id_idx = IdMapIndex::new(128, 4).unwrap();

// Insert vectors with external IDs.
let vectors = vec![0.0f32; 3 * 128];
id_idx.add_with_ids(&vectors, &[101, 102, 103]).unwrap();

// Remove by ID – the underlying swap_remove is used.
let removed = id_idx.remove(102);
assert!(removed);
assert_eq!(id_idx.len(), 2);

// The remaining IDs are still stable.
let (scores, ids) = id_idx.search(&vectors[0..128], 2);
assert!(ids.contains(&101));
assert!(ids.contains(&103));

Summary

• TurboQuantIndex::swap_remove provides O(1) removal by swapping the target with the last vector and truncating, deliberately destroying original ordering.
• The method returns the former index of the vector moved into the deleted slot, or the same index when removing the last element.
• Bounds checking occurs via assert! before any mutation, panicking on invalid indices.
• Internal buffers including packed_codes, scales, and the SIMD-blocked cache are updated atomically to maintain consistency.
• IdMapIndex wraps the raw operation to provide stable external IDs while maintaining O(1) performance.
• All semantics are validated by the test suite in turbovec/tests/swap_remove.rs.

Frequently Asked Questions

Does swap_remove preserve the order of vectors in turbovec?

No. According to the source code documentation in turbovec/src/lib.rs, the method explicitly does not preserve order. It moves the last vector into the position of the deleted element, changing the index of the previously-last vector. This trade-off enables O(1) performance instead of the O(n) cost of shifting all subsequent elements.

What does the return value of swap_remove indicate?

The return value is the previous index of the vector that was moved into the deleted slot. If you remove the last element (index n-1), the method returns n-1 since no swap occurs. For any other index, it returns the former last index (which was n-1 before the operation). This allows callers to track which vector now occupies the removed position.

How does IdMapIndex maintain stable IDs when using swap_remove?

IdMapIndex maintains bidirectional mapping tables (id_to_slot and slot_to_id) that translate external IDs to internal indices. When remove is called, it performs the underlying swap_remove on the raw index, then updates both mapping tables to reflect the swap. This ensures that external IDs remain stable while the internal TurboQuantIndex optimizes for speed.

Why is the blocked cache invalidated after swap_remove?

The blocked field contains a SIMD-optimized layout of the packed codes that is derived lazily and cached using OnceLock. After swap_remove modifies the vector storage, this cached layout becomes stale. The implementation resets it with self.blocked = OnceLock::new(); to force recomputation on the next search, preventing stale results from the previous buffer layout.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}