# Understanding swap_remove Semantics and Order Preservation in Turbovec

> Understand turbovec swap_remove semantics. Learn how O(1) removal sacrifices order preservation by swapping with the last element. Discover the former index of the moved vector.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: internals
- Published: 2026-06-16

---

**`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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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

```rust
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

```rust
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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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.