velesdb-core 7.0.0

//! HNSW Graph Structure
//!
//! Implements the hierarchical navigable small world graph structure
//! as described in the Malkov & Yashunin paper.
//!
//! # Module Organization
//!
//! - `insert`: Vector insertion and layer growth
//! - `search`: k-NN search, multi-entry search, and layer-level search
//! - `neighbors`: Neighbor selection (VAMANA diversification) and bidirectional connections
//! - `anchors`: Reachability anchors, one protected base-layer in-edge per node (#2259)

mod anchors;
mod insert;
pub(crate) mod locking;
mod neighbors;
mod reorder;
pub(crate) mod safety_counters;
mod search;
pub(crate) use search::ResumableSearch;
mod search_pipeline;
mod search_pools;
mod search_state;
#[cfg(test)]
mod search_tests;

#[cfg(feature = "gpu")]
mod gpu_search;

use super::distance::DistanceEngine;
use super::layer::Layer;
use crate::perf_optimizations::ContiguousVectors;
use locking::{record_lock_acquire, record_lock_release, LockRank};
use parking_lot::RwLock;
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};

/// Sentinel value for `NativeHnsw::entry_point` (private field): indicates no
/// entry point exists.
///
/// Using `usize::MAX` instead of `Option<NodeId>` behind an `RwLock` allows
/// lock-free reads on the search hot path (`Ordering::Acquire` load) while
/// writes, rare, take the promotion lock (#2259).
pub const NO_ENTRY_POINT: usize = usize::MAX;

/// Default VAMANA alpha for neighbor diversification.
///
/// Alpha > 1.0 biases `select_neighbors` toward graph navigability:
/// a candidate is accepted when `alpha * candidate_dist <= dist_to_selected`,
/// so higher alpha keeps neighbors that are farther from each other, producing
/// a more connected graph with better recall for all search modes.
///
/// 1.2 is the value recommended by the VAMANA paper (Subramanya et al., 2019).
pub const DEFAULT_ALPHA: f32 = 1.2;

/// Native HNSW index implementation.
///
/// # Type Parameters
///
/// * `D` - Distance engine (CPU, SIMD, or GPU)
pub struct NativeHnsw<D: DistanceEngine> {
    /// Distance computation engine
    pub(in crate::index::hnsw::native) distance: D,
    /// Contiguous vector storage (node_id -> vector slice).
    /// `None` until the first vector is inserted (dimension is inferred lazily).
    pub(in crate::index::hnsw::native) vectors: RwLock<Option<ContiguousVectors>>,
    /// Hierarchical layers (layer 0 = bottom, dense connections)
    pub(in crate::index::hnsw::native) layers: RwLock<Vec<Layer>>,
    /// Entry point for search (highest layer node).
    ///
    /// Stores `NO_ENTRY_POINT` (`usize::MAX`) when the index is empty.
    /// Read with `Ordering::Acquire` and no lock; written only under
    /// `promotion`: by `claim_first_entry_point`, `promote_entry_point` and
    /// the renumbering of `reorder_for_locality`.
    pub(in crate::index::hnsw::native) entry_point: AtomicUsize,
    /// Maximum layer for entry point.
    ///
    /// Read without a lock; written with `entry_point`, under `promotion`.
    pub(in crate::index::hnsw::native) max_layer: AtomicUsize,
    /// Serializes every move of the entry point: the first claim, each
    /// promotion with the anchor reparenting that follows it, and the
    /// renumbering of `reorder_for_locality` (#2259). Two
    /// promotions that overlapped could otherwise reparent in the wrong order
    /// and strand the tree below one of them. Rank `EntryPointPromotion`,
    /// taken before `vectors`.
    pub(in crate::index::hnsw::native) promotion: parking_lot::Mutex<()>,
    /// Number of elements in the index
    pub(in crate::index::hnsw::native) count: AtomicUsize,
    /// Simple PRNG state for layer selection during insertion.
    ///
    /// Used exclusively by `random_layer()` on the write path.  The search
    /// path previously also consumed this via `gather_multi_entry_points`, but
    /// that was replaced by the thread-local `PROBE_RNG` in `search.rs`
    /// (issue #967) to eliminate shared-atomic contention under concurrent load.
    pub(in crate::index::hnsw::native) rng_state: AtomicU64,
    /// Maximum connections per node (M parameter)
    pub(in crate::index::hnsw::native) max_connections: usize,
    /// Maximum connections at layer 0 (M0 = 2*M)
    pub(in crate::index::hnsw::native) max_connections_0: usize,
    /// ef_construction parameter
    pub(in crate::index::hnsw::native) ef_construction: usize,
    /// Level multiplier for layer selection (1/ln(M))
    pub(in crate::index::hnsw::native) level_mult: f64,
    /// VAMANA alpha parameter for neighbor diversification (default: 1.2).
    ///
    /// Alpha > 1.0 biases neighbor selection toward diversity over proximity,
    /// producing a more navigable graph with better recall across all search
    /// modes. The value 1.2 follows the VAMANA paper recommendation.
    pub(in crate::index::hnsw::native) alpha: f32,
    /// Maximum consecutive candidates without improving top-k before early termination.
    /// Default: `ef_construction / 2`. Set to `0` to disable.
    pub(crate) stagnation_limit: usize,
    /// Node slots every layer holds, at least: `expand_layers()` skips the
    /// write lock for a node below it on an existing layer. Only grows, and
    /// only under `layers.write`, after the layers it describes (#2306).
    /// Transient: not serialized to disk, so a loaded index starts at 0.
    pub(in crate::index::hnsw::native) pre_allocated_capacity: AtomicUsize,
    /// Per-instance CSR cache for GPU traversal.
    ///
    /// Each `NativeHnsw` instance owns its own cache, preventing cross-collection
    /// contamination when multiple indices exist in the same process.
    /// Invalidated automatically on insert/delete via [`Self::invalidate_gpu_caches`].
    #[cfg(feature = "gpu")]
    pub(in crate::index::hnsw::native) gpu_csr_cache: crate::gpu::gpu_csr::CsrCache,
    /// Cached flat vector snapshot for GPU upload.
    ///
    /// Stores `(version_at_snapshot, dimension, Arc<[f32]>)`. Validity is
    /// checked against [`Self::gpu_snapshot_version`] rather than `count`
    /// alone so that a hypothetical future delete+insert that returns to
    /// the same count cannot silently serve stale vectors.
    #[cfg(feature = "gpu")]
    pub(in crate::index::hnsw::native) gpu_vectors_snapshot:
        parking_lot::Mutex<Option<GpuVectorsSnapshot>>,
    /// Monotonic version counter bumped on every vectors / topology
    /// mutation. Anchors GPU cache validity (snapshot + CSR) to a single
    /// observable value — the snapshot compares its recorded version
    /// against this counter on read, so the cache remains invalid after
    /// any mutation even if a future code path forgets to explicitly
    /// clear the snapshot mutex (belt-and-suspenders).
    #[cfg(feature = "gpu")]
    pub(in crate::index::hnsw::native) gpu_snapshot_version: AtomicU64,
    /// The arena file this graph owns, when its vectors live on disk.
    ///
    /// # Drop order
    ///
    /// Declared **last**, and specifically after `vectors`: dropping this
    /// unlinks the file, and the mapping in `vectors` must be released first.
    /// Rust drops fields in declaration order, so the position *is* the
    /// mechanism — the same technique `HnswIndex` uses for `inner` before
    /// `io_holder`. `graph_field_order_keeps_the_arena_alive_until_unmapped`
    /// pins it.
    ///
    /// `None` for a heap-backed graph, which is every `Full`-mode graph and
    /// every graph built without a collection directory.
    pub(in crate::index::hnsw::native) arena_home:
        Option<crate::index::hnsw::native::arena_home::ArenaHome>,
}

/// Cached GPU vector snapshot: `(version, dimension, flat_vectors)`.
///
/// Only refreshed when [`NativeHnsw::gpu_snapshot_version`] moves past
/// the value captured at build time. Subsequent queries clone the `Arc`
/// (O(1) pointer bump) instead of copying ~1.5GB.
#[cfg(feature = "gpu")]
pub(in crate::index::hnsw::native) type GpuVectorsSnapshot = (u64, usize, std::sync::Arc<[f32]>);

/// How many vectors a mapped arena is sized for before it has any.
///
/// The heap arena pre-allocates `max_elements` because growing it means
/// copying the whole block. A mapped arena does not: `grow` extends the file
/// and re-maps, leaving every written page where it is, so pre-sizing buys
/// nothing and costs a great deal. `HnswParams::auto` defaults
/// `max_elements` to 100 000, which at 768 dimensions is a **292 MB file
/// created before the collection holds a single vector** — measured, not
/// estimated. On the small devices this feature exists for, that is the
/// difference between a working install and a full disk.
///
/// So the initial size is capped and growth does the rest.
#[cfg(feature = "persistence")]
fn initial_arena_capacity(max_elements: usize) -> usize {
    /// ~12 MB at 768 dimensions: large enough that a small collection never
    /// grows, small enough that an empty one costs nothing worth counting.
    const CAP: usize = 4096;
    max_elements.min(CAP)
}

impl<D: DistanceEngine> NativeHnsw<D> {
    /// Creates a new native HNSW index with VAMANA diversification (`alpha = 1.2`).
    ///
    /// Vector storage is initialized lazily on the first `insert()` call,
    /// using the dimension of the first inserted vector.
    #[must_use]
    pub fn new(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
    ) -> Self {
        Self::build(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            DEFAULT_ALPHA,
            None,
            None,
        )
    }

    /// Creates a new native HNSW index with a known vector dimension.
    ///
    /// Pre-allocates contiguous vector storage for cache-friendly access.
    /// Uses `DEFAULT_ALPHA` (1.2) for VAMANA diversification.
    ///
    /// # Errors
    ///
    /// Returns an error if the vector storage allocation fails.
    pub fn new_with_dimension(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        dimension: usize,
    ) -> crate::error::Result<Self> {
        Self::new_with_dimension_and_alpha(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            dimension,
            DEFAULT_ALPHA,
        )
    }

    /// Creates a new native HNSW index with a known dimension and custom alpha.
    ///
    /// Pre-allocates contiguous vector storage for cache-friendly access.
    /// `alpha` controls VAMANA neighbor diversification: 1.0 = no diversification,
    /// 1.2 = recommended default, >1.2 = more diversity.
    ///
    /// # Errors
    ///
    /// Returns an error if the vector storage allocation fails.
    #[allow(clippy::too_many_arguments)]
    pub fn new_with_dimension_and_alpha(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        dimension: usize,
        alpha: f32,
    ) -> crate::error::Result<Self> {
        let storage = ContiguousVectors::new(dimension, max_elements)?;
        Ok(Self::build(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            alpha,
            Some(storage),
            None,
        ))
    }

    /// As [`new_with_dimension_and_alpha`], but the arena lives in `dir`.
    ///
    /// Only quantized backends should ask for this. In `Full` mode the f32
    /// vectors *are* the traversal data, so every hop would fault a page and
    /// the mapping would cost latency for nothing; in `SQ8`/`RaBitQ` the
    /// traversal runs entirely on the codes and the f32 is touched only by
    /// `rerank_with_exact_f32`, on `k * oversampling` candidates. That
    /// difference is the whole reason this constructor exists (#2112).
    ///
    /// [`new_with_dimension_and_alpha`]: Self::new_with_dimension_and_alpha
    ///
    /// # Errors
    ///
    /// Returns an error if the arena file cannot be created or mapped.
    #[cfg(feature = "persistence")]
    #[allow(clippy::too_many_arguments)]
    pub(in crate::index::hnsw) fn new_file_backed_with_alpha(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        dimension: usize,
        alpha: f32,
        dir: &std::path::Path,
    ) -> crate::error::Result<Self> {
        let home = crate::index::hnsw::native::arena_home::ArenaHome::claim(dir);
        let storage =
            Self::new_arena(Some(&home), dimension, initial_arena_capacity(max_elements))?;
        Ok(Self::build(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            alpha,
            Some(storage),
            Some(home),
        ))
    }

    /// A graph whose arena lives in `dir`, sized eagerly or lazily.
    ///
    /// `dimension == 0` means the caller does not know it yet, so the arena
    /// is deferred to the first insert — the home is claimed now either way,
    /// so the lazy path in `allocate_and_store_vector` finds it.
    ///
    /// # Errors
    ///
    /// Returns an error if the arena file cannot be created or mapped.
    #[cfg(feature = "persistence")]
    #[allow(clippy::too_many_arguments)]
    pub(in crate::index::hnsw) fn standard_in_dir(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        dimension: usize,
        alpha: f32,
        dir: &std::path::Path,
    ) -> crate::error::Result<Self> {
        if dimension > 0 {
            return Self::new_file_backed_with_alpha(
                distance,
                max_connections,
                ef_construction,
                max_elements,
                dimension,
                alpha,
                dir,
            );
        }
        let home = crate::index::hnsw::native::arena_home::ArenaHome::claim(dir);
        Ok(Self::build(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            alpha,
            None,
            Some(home),
        ))
    }

    /// Builds an arena of `capacity` vectors, on disk when `home` says so.
    ///
    /// The single place that answers "heap or file?" for this graph. All four
    /// sites that can create an arena — the two constructors, the lazy
    /// first-insert path, and the batch-reserve path — route through it, so a
    /// graph cannot end up with a heap arena on one path and a mapped one on
    /// another.
    ///
    /// # Errors
    ///
    /// Returns an error if the allocation or the file mapping fails.
    pub(in crate::index::hnsw::native) fn new_arena(
        home: Option<&crate::index::hnsw::native::arena_home::ArenaHome>,
        dimension: usize,
        capacity: usize,
    ) -> crate::error::Result<ContiguousVectors> {
        #[cfg(feature = "persistence")]
        if let Some(home) = home {
            // A mapped arena is an optimisation, never a requirement: it
            // lowers the resident set and changes nothing a caller can
            // observe. So a filesystem that will not host one — read-only
            // directory, no space, no permission, a platform where the
            // mapping is refused — must cost the optimisation and nothing
            // else. Failing here instead would mean this feature could stop a
            // collection from opening that opened fine before it existed,
            // which is not a trade worth making for a memory saving.
            match ContiguousVectors::new_file_backed(home.path(), dimension, capacity) {
                Ok(mapped) => return Ok(mapped),
                Err(e) => tracing::warn!(
                    "vector arena at {:?} could not be mapped ({e}); \
                     falling back to an in-memory arena, which costs memory, not correctness",
                    home.path()
                ),
            }
        }
        #[cfg(not(feature = "persistence"))]
        let _ = home;
        ContiguousVectors::new(dimension, capacity)
    }

    /// Creates a new native HNSW index with VAMANA-style diversification.
    #[must_use]
    pub fn with_alpha(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        alpha: f32,
    ) -> Self {
        Self::build(
            distance,
            max_connections,
            ef_construction,
            max_elements,
            alpha,
            None,
            None,
        )
    }

    /// Internal constructor shared by all public constructors.
    fn build(
        distance: D,
        max_connections: usize,
        ef_construction: usize,
        max_elements: usize,
        alpha: f32,
        vectors: Option<ContiguousVectors>,
        arena_home: Option<crate::index::hnsw::native::arena_home::ArenaHome>,
    ) -> Self {
        let max_connections_0 = max_connections * 2;
        let level_mult = 1.0 / (max_connections as f64).ln();
        Self {
            distance,
            vectors: RwLock::new(vectors),
            layers: RwLock::new(vec![Layer::new_base(max_elements)]),
            entry_point: AtomicUsize::new(NO_ENTRY_POINT),
            max_layer: AtomicUsize::new(0),
            promotion: parking_lot::Mutex::new(()),
            count: AtomicUsize::new(0),
            rng_state: AtomicU64::new(0x5DEE_CE66_D1A4_B5B5),
            max_connections,
            max_connections_0,
            ef_construction,
            level_mult,
            alpha,
            // ef/2 gives beam search more exploration budget at scale.
            // The prior ef/4 caused premature termination at 100K+ vectors,
            // contributing to recall degradation (97% at 10K → 64% at 100K).
            stagnation_limit: ef_construction / 2,
            // Not `max_elements`, although the base layer holds that many
            // slots: every layer added later is grown to this capacity, so
            // seeding it would make each upper layer as long as the base.
            pre_allocated_capacity: AtomicUsize::new(0),
            #[cfg(feature = "gpu")]
            gpu_csr_cache: crate::gpu::gpu_csr::CsrCache::new(),
            #[cfg(feature = "gpu")]
            gpu_vectors_snapshot: parking_lot::Mutex::new(None),
            // Starts at 0. Snapshots built before any mutation store
            // `0` as `version_at_build`; a fresh index therefore hits
            // the cache on its first read, and any mutation bumps this
            // counter to invalidate all subsequent reads.
            #[cfg(feature = "gpu")]
            gpu_snapshot_version: AtomicU64::new(0),
            arena_home,
        }
    }

    /// Returns the alpha diversification parameter.
    #[must_use]
    pub fn get_alpha(&self) -> f32 {
        self.alpha
    }

    /// Returns M, the maximum connections per node above layer 0.
    #[must_use]
    pub(crate) fn get_max_connections(&self) -> usize {
        self.max_connections
    }

    /// Returns the beam width the graph is built with.
    #[must_use]
    pub(crate) fn get_ef_construction(&self) -> usize {
        self.ef_construction
    }

    /// Returns the number of elements in the index.
    #[must_use]
    pub fn len(&self) -> usize {
        self.count.load(Ordering::Relaxed)
    }

    /// Returns true if the index is empty.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Invalidates both GPU caches (CSR topology + vectors snapshot) as a
    /// single atomic step.
    ///
    /// Call this **after every mutation** that changes the set of active
    /// nodes or their vector data — currently insert and parallel insert;
    /// a future delete path must call this too.
    ///
    /// Bumps [`Self::gpu_snapshot_version`] first (Release), then
    /// invalidates the CSR cache, then clears the snapshot mutex. The
    /// version bump is the canonical invalidation signal: even if a
    /// hypothetical caller forgot the explicit `None`-clear, the next
    /// snapshot read would still observe `stored_version !=
    /// current_version` and rebuild from the fresh vectors. The explicit
    /// clear is kept as belt-and-suspenders (frees the `Arc` promptly so
    /// the old buffer can drop).
    #[cfg(feature = "gpu")]
    pub(in crate::index::hnsw::native) fn invalidate_gpu_caches(&self) {
        use self::locking::{record_lock_acquire, record_lock_release, LockRank};
        // Release ordering: any thread that subsequently loads the
        // version with Acquire will observe every mutation that
        // happened-before this fetch_add.
        self.gpu_snapshot_version.fetch_add(1, Ordering::Release);
        self.gpu_csr_cache.invalidate();
        record_lock_acquire(LockRank::GpuVectorsSnapshot);
        *self.gpu_vectors_snapshot.lock() = None;
        record_lock_release(LockRank::GpuVectorsSnapshot);
    }

    /// Computes the raw distance between two vectors using this index's distance engine.
    ///
    /// **Note:** For `CachedSimdDistance` with Euclidean metric, this returns
    /// **squared L2** (no sqrt). Pass the result through
    /// `NativeHnsw::transform_score` (private) to obtain actual Euclidean
    /// distance.
    #[inline]
    #[must_use]
    pub fn compute_distance(&self, a: &[f32], b: &[f32]) -> f32 {
        self.distance.distance(a, b)
    }

    /// Executes a closure with a vectors read snapshot and tracked lock rank.
    ///
    /// The closure receives `&ContiguousVectors`; if storage is not yet
    /// initialized (no vectors inserted), the closure is **not** called and
    /// the supplied `default` value is returned instead.
    #[inline]
    pub(in crate::index::hnsw) fn with_vectors_read<R>(
        &self,
        f: impl FnOnce(&ContiguousVectors) -> R,
    ) -> R
    where
        R: Default,
    {
        record_lock_acquire(LockRank::Vectors);
        let guard = self.vectors.read();
        let result = match guard.as_ref() {
            Some(v) => f(v),
            None => R::default(),
        };
        drop(guard);
        record_lock_release(LockRank::Vectors);
        result
    }

    /// Runs `f` holding the promotion lock: every move of the entry point, with
    /// the anchor reparenting that follows it, happens there (#2259).
    pub(in crate::index::hnsw::native) fn with_promotion_lock<R>(
        &self,
        f: impl FnOnce() -> R,
    ) -> R {
        record_lock_acquire(LockRank::EntryPointPromotion);
        let guard = self.promotion.lock();
        let result = f();
        drop(guard);
        record_lock_release(LockRank::EntryPointPromotion);
        result
    }

    /// Executes a closure with mutable access to the contiguous vector storage.
    ///
    /// Acquires a write lock on `vectors`. Used by [`Self::push_unlinked`],
    /// the direct writer's placement during bulk insert (deferred HNSW
    /// indexing).
    ///
    /// # Errors
    ///
    /// Returns [`crate::error::Error::Internal`] if vector storage is not initialized.
    /// Propagates any error returned by the closure.
    ///
    /// [`crate::error::Error::Internal`]: crate::error::Error::Internal
    pub(in crate::index::hnsw) fn with_vectors_write<R>(
        &self,
        f: impl FnOnce(&mut ContiguousVectors) -> crate::error::Result<R>,
    ) -> crate::error::Result<R> {
        record_lock_acquire(LockRank::Vectors);
        let mut guard = self.vectors.write();
        let storage = guard.as_mut().ok_or_else(|| {
            crate::error::Error::Internal("ContiguousVectors not initialized".to_string())
        })?;
        let result = f(storage);
        drop(guard);
        record_lock_release(LockRank::Vectors);
        result
    }

    /// Executes a closure with a layers read snapshot and tracked lock rank.
    // Its callers are crash recovery's `unlinked_nodes` (`persistence`) and the
    // GPU search (`gpu`); a build with neither has none.
    #[cfg_attr(not(any(feature = "persistence", feature = "gpu")), allow(dead_code))]
    #[inline]
    pub(in crate::index::hnsw::native) fn with_layers_read<R>(
        &self,
        f: impl FnOnce(&[Layer]) -> R,
    ) -> R {
        record_lock_acquire(LockRank::Layers);
        let layers = self.layers.read();
        let result = f(&layers);
        drop(layers);
        record_lock_release(LockRank::Layers);
        result
    }

    /// The nodes among `nodes` that no search can reach: allocated, never
    /// linked into layer 0.
    ///
    /// A mapped id can outlive its link: `upsert_bulk`'s V2 path places each
    /// vector, maps its id to the slot it got and leaves the graph insert to
    /// the async builder, so a save in that window persists a node with no
    /// neighbours (#2246). Every node an insert linked has at least one
    /// layer-0 neighbour once the graph holds two nodes. The entry point is
    /// exempt whatever its list holds: every search starts there, so it is
    /// reachable by construction — and a save that raced the builder reloads
    /// with slot 0 as an entry point nothing ever linked.
    #[cfg(feature = "persistence")]
    pub(in crate::index::hnsw) fn unlinked_nodes(
        &self,
        nodes: impl IntoIterator<Item = usize>,
    ) -> Vec<usize> {
        let entry_point = self.entry_point.load(Ordering::Acquire);
        self.with_layers_read(|layers| {
            let base = layers.first();
            nodes
                .into_iter()
                .filter(|&node| {
                    node != entry_point
                        && base
                            .and_then(|layer| layer.with_neighbors(node, <[usize]>::is_empty))
                            .unwrap_or(true)
                })
                .collect()
        })
    }

    /// Executes a closure with both vectors AND layers read locks held simultaneously.
    ///
    /// Acquires locks in correct rank order: vectors (10) → layers (20).
    /// This avoids repeated lock acquire/release in tight search loops (F-03/F-04).
    ///
    /// # Concurrent-search scalability — investigation closed (issue #967, 2026-06-03)
    ///
    /// Benchmark (`scalability_benchmark::concurrent_queries`, M5 Pro, 100 K × 768-dim):
    /// 8 parallel searches achieve ~5× throughput instead of the ideal ~8×,
    /// with per-batch latency 66% higher than single-threaded.
    ///
    /// **Cause 1 — `rng_state` CAS (fixed in this file's companion `search.rs`).**
    /// `gather_multi_entry_points` called `self.rng_state.fetch_update` once per
    /// search when `num_probes > 1` (triggered at 100 K vectors with the default
    /// `Balanced` quality, ef_search = 320).  With 8 concurrent threads, all
    /// competing on the same `AtomicU64`, this produced measurable cache-line
    /// bouncing (~1 cache miss per search per thread).  **Fix**: thread-local
    /// XORshift64 in `NativeHnsw::next_probe_rng()` — zero shared atomics on
    /// the steady-state search path.
    ///
    /// **Cause 2 — DRAM latency (fundamental hardware limit, not fixable in SW).**
    /// 100 K × 768-dim = 307 MB of vector data; the M5 Pro's shared L3 is 24 MB.
    /// HNSW beam-search (ef = 320) accesses ~400–600 random 3 KB chunks per query,
    /// almost all of which miss L3 and stall on DRAM.
    /// With 8 threads sharing one memory controller (~32 outstanding requests),
    /// each thread sees more DRAM stalls than a lone thread, giving the
    /// observed ~5× rather than ~8× throughput scaling.  This is an inherent
    /// physical limit; software mitigations are:
    ///   - FP16 storage (halves DRAM traffic, not yet implemented),
    ///   - BFS reordering (`reorder_for_locality` — already available),
    ///   - keeping indices ≤ L3 size (≤ ~7 M vectors at 128-dim, ≤ 800 K at 768-dim).
    ///
    /// **`parking_lot::RwLock` reader-counter overhead**: each `read()` does one
    /// `fetch_add` + one `fetch_sub` on the lock word. At 8 threads × 2 locks ×
    /// 2 ops = 32 atomic ops per search, next to a whole graph traversal, this
    /// is not a meaningful contributor.
    ///
    /// If vector storage is not yet initialized, the closure is **not** called
    /// and `R::default()` is returned.
    #[inline]
    pub(in crate::index::hnsw::native) fn with_vectors_and_layers_read<R>(
        &self,
        f: impl FnOnce(&ContiguousVectors, &[Layer]) -> R,
    ) -> R
    where
        R: Default,
    {
        record_lock_acquire(LockRank::Vectors);
        let vectors_guard = self.vectors.read();
        let Some(vectors) = vectors_guard.as_ref() else {
            drop(vectors_guard);
            record_lock_release(LockRank::Vectors);
            return R::default();
        };
        record_lock_acquire(LockRank::Layers);
        let layers = self.layers.read();
        let result = f(vectors, &layers);
        drop(layers);
        record_lock_release(LockRank::Layers);
        drop(vectors_guard);
        record_lock_release(LockRank::Vectors);
        result
    }

    // Reason: Layer selection uses exponential distribution capped at 15.
    // - cast_precision_loss: u64 to f64 may lose precision but is acceptable for PRNG
    // - cast_possible_truncation: floor() result is capped at 15, fitting in usize
    // - cast_sign_loss: -ln(uniform) is always positive since uniform is in (0, 1)
    #[allow(
        clippy::cast_precision_loss,
        clippy::cast_possible_truncation,
        clippy::cast_sign_loss
    )]
    fn random_layer(&self) -> usize {
        let old_state = self
            .rng_state
            .fetch_update(Ordering::Relaxed, Ordering::Relaxed, |state| {
                let seed = if state == 0 {
                    0x853c_49e6_748f_ea9b
                } else {
                    state
                };
                Some(xorshift64(seed))
            })
            .unwrap_or_else(|s| s);
        let seed = if old_state == 0 {
            0x853c_49e6_748f_ea9b
        } else {
            old_state
        };
        let uniform = (xorshift64(seed) as f64) / (u64::MAX as f64);
        let uniform_safe = uniform.max(f64::MIN_POSITIVE);
        let level = (-uniform_safe.ln() * self.level_mult).floor() as usize;
        level.min(15)
    }
}

/// XORshift64 step (Marsaglia 2003): advances a non-zero PRNG `state` by one
/// iteration with the canonical `13/7/17` shift triple. Shared by the
/// insert-path `random_layer` (above) and the search-path `next_probe_rng`
/// (in `search.rs`) so the generator stays identical across both paths.
#[inline]
fn xorshift64(mut state: u64) -> u64 {
    state ^= state << 13;
    state ^= state >> 7;
    state ^= state << 17;
    state
}