Summary:
The outer HNSW search loop called `vt->advance()` a second time. `HNSW::search`
already ends with `vt.advance()` at `impl/HNSW.cpp:1861`, so the caller in
`IndexHNSW.cpp` advanced the visited table once more per query. This diff
removes that call and adds a comment that names the owner of the advance.
The sibling call in `search_level_0` stays, because `search_level_0_impl` does
not advance.
**Microbenchmark.** The host holds 72 Cooper Lake cores. The build is
`mode/opt`. One core is pinned, and the two binaries interleave over 5 rounds.
The table reports the median of the medians. `IndexHNSWFlat`, `d=64`, `M=16`,
`use_visited_hashset=false` to select the versioned array, one query for each
iteration.
| ntotal | before | after | ratio |
|---|---|---|---|
| 100k | 44.2 us | 44.2 us | 1.00x |
| 400k | 63.8 us | 69.1 us | 0.92x |
**The change gives no measurable speed gain.** Both rows sit inside a 10% to 27%
spread. The arithmetic agrees: `visno` is a `uint8_t` that cycles from 1 to 254,
so the code clears the table once for every 250 advances. Two advances for each
query halve that interval, which costs about 800 extra bytes of memset for each
query against a search of 44 us to 69 us.
The value of the diff is the removal of a redundant call, not a speed gain.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5596
Test Plan:
`buck2 test fbcode//faiss/tests:test_ivf_index fbcode//faiss/tests:test_custom_result_handler fbcode//faiss/tests:test_hnsw fbcode//faiss/tests:test_rabitq_simd_neon fbcode//faiss/tests:test_params_override fbcode//faiss/tests:test_hnsw_rabitq fbcode//faiss/tests:test_rabitq fbcode//faiss/tests:test_search_params fbcode//faiss/tests:test_io_corrupted fbcode//faiss/tests:test_rabitq_utils`, run at the top of the stack on aarch64: 173 pass, 0 fail, 3 skip.
`buck2 build fbcode//faiss:faiss` succeeds in the static aarch64 build and with `-c faiss.dynamic_dispatch=true`.
Reviewed By: alibeklfc
Differential Revision: D121846632
Pulled By: mnorris11
fbshipit-source-id: 8928c4d4648ce061e63c084ded9c74fa17ef66bd
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5670
Follow-up to D121368933 and public PR https://github.com/facebookresearch/faiss/pull/5657.
HNSW and RaBitQ search statistics are available to C++ and Python. Faiss collects them by default. Every search updates shared counters. Under high concurrency, these updates are expensive. In the 64-thread relaxed-atomic profile, `HNSWStats::combine_atomic` uses 74.14% of the sampled user cycles.
This diff adds one process-wide flag in `faiss/utils/utils.h`:
- `set_search_stats_enabled(bool)`
- `get_search_stats_enabled()`
The flag is a relaxed `std::atomic<bool>`. It is private to `utils.cpp`. The default is enabled, for backward compatibility. Callers that do not read the statistics can disable collection. Then the searches skip the global atomic updates.
At the moment, the flag controls `hnsw_stats` and `rabitq_stats`. The name is generic on purpose. The other global stats objects (for example `indexIVF_stats`, `indexPQ_stats` and `indexPanorama_stats`) use plain `+=` on shared counters, so they have the same scaling problem. Later diffs can put these objects under the same flag without a new API. The documentation says that the values of global stats objects are unspecified when the flag is disabled. Thus, more coverage does not change the contract.
API design:
- Faiss often exposes a plain global for a setting, for example `distance_compute_blas_threshold`. This diff does not do that. The flag is for concurrent searches, and a thread can change it while other threads search. A plain `bool` is then a data race, and TSAN reports it. This stack fixed TSAN races in D121097648.
- SWIG cannot wrap `std::atomic<bool>`. Thus, the setter and the getter are the only API. Python calls `faiss.set_search_stats_enabled(False)`.
Other changes:
- `bench_hnsw_stats` has a `stats` argument. `stats:0` disables collection, and `stats:1` enables it. One binary measures the two modes.
- The tests save the flag value and restore it after the test. The C++ tests use `SearchStatsEnabledGuard`. The Python tests use `addCleanup`. Thus, a failed assertion does not change the flag for later tests in the same process.
Mode/opt benchmark from V12, five sequential repetitions (mean real-time throughput):
| External pthreads | Relaxed atomic stats enabled | Stats disabled | Change |
| ---: | ---: | ---: | ---: |
| 1 | 2.516 M/s | 2.411 M/s | 0.96x |
| 2 | 3.919 M/s | 4.164 M/s | 1.06x |
| 4 | 7.494 M/s | 8.260 M/s | 1.10x |
| 8 | 12.717 M/s | 14.170 M/s | 1.11x |
| 16 | 16.074 M/s | 22.979 M/s | 1.43x |
| 32 | 19.929 M/s | 36.841 M/s | 1.85x |
| 64 | 22.101 M/s | 66.642 M/s | 3.02x |
The 0.96x value at 1 pthread is noise. A longer pinned measurement in the test plan shows no slowdown. At 1 thread, the atomic adds have no contention, so the expected gain is small.
The disabled path scales 27.64x from 1 to 64 pthreads. The enabled path scales 8.78x. The disabled path does not scale linearly, because this one-vector search is very small. At 64 threads, the OpenMP runtime uses about 28% of the sampled cycles. Allocator, RTTI and shared-cache costs also contribute.
Reviewed By: luciang
Differential Revision: D121374405
fbshipit-source-id: a54ee81a68a63df01c93bd5098171658883cd5ab
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5663
Follow-up to D121097648 (public PR: https://github.com/facebookresearch/faiss/pull/5657).
Related public PR: https://github.com/facebookresearch/faiss/pull/4910
Use relaxed atomic additions for HNSW, RaBitQ, and IVFPQ stats aggregation. Builds with `std::atomic_ref` support use `fetch_add(..., std::memory_order_relaxed)`; older standard libraries fall back to `__atomic_fetch_add(..., __ATOMIC_RELAXED)`. This removes the global OpenMP critical sections that serialize concurrent searches while preserving exact counter updates.
Benchmark design: mode/opt `bench_hnsw_stats` binary, one shared HNSW index, `N` external pthreads, one OpenMP thread per search (each worker calls `omp_set_num_threads(1)` once before its timed loop), five repetitions per point.
Performance:
| External pthreads | Critical M/s | Relaxed atomic M/s | Speedup |
|---:|---:|---:|---:|
| 1 | 2.228 | 2.503 | 1.12x |
| 2 | 3.716 | 3.853 | 1.04x |
| 4 | 5.662 | 7.357 | 1.30x |
| 8 | 6.384 | 12.843 | 2.01x |
| 16 | 2.697 | 15.804 | 5.86x |
| 32 | 0.951 | 18.910 | 19.88x |
| 64 | 0.117 | 21.866 | 186.89x |
At 64 pthreads, the feature-detected `atomic_ref` path measured 21.918 M/s mean over 10 repetitions (21.907 M/s median, 2.59% CV). The `__atomic_fetch_add` fallback measured 22.563 M/s mean (22.511 M/s median, 3.24% CV).
The 64-thread profile attributes 97.38% of cycles in the critical-section version to lock acquisition and waiting. With relaxed atomic aggregation, 74.14% is in the stats combine path instead. The remaining non-linear scaling, 21.866 M/s at 64 threads versus the 2.503 M/s single-thread baseline, comes from cache-line contention on the global counters and shared-index memory-bandwidth and cache pressure.
Reviewed By: mnorris11
Differential Revision: D121368933
fbshipit-source-id: 8dd26313e55aa73c0cdd379c7648efacd4f5f1d8
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5448
## Background
Every `IndexHNSW::search()` call enters an `#pragma omp parallel` region in which each thread constructs its own `VisitedTable` via `VisitedTable::create(ntotal, ...)`. For the versioned-array strategy (`VisitedTableVector`), a fresh array allocation is paid **per thread, per Search() call** - this is an O(ntotal) allocation plus zero-fill overhead. It's freed every time the region exits.
## Problem
When a statically-built index is searched repeatedly with small or even single-query batches, this per-call alloc+zero can dominate the actual graph traversal (the search visits only a handful of nodes, but still pays to allocate and zero the whole `ntotal`-byte array).
## Solution
This adds `VisitedTable::get_reusable()` API to return a reference to the `thread_local` VisitedTable. The O(size) versioned array is **allocated once per thread and reused across all subsequent Search() calls**. This changed is applied to 3 code paths for search (`IndexHNSW.cpp`):
- `hnsw_search`
- `search_level_0` - only used by IndexHNSWCagra
- `IndexHNSWCagra::range_search` - only used by IndexHNSWCagra
Why `thread_local` rather than a member of the index:
- It is inherently per-OS-thread, so it survives across `search()` calls (OpenMP reuses its worker pool) and each thread gets its own table with no cross-thread coordination.
- faiss supports calling `const` search concurrently on one index from multiple threads. A member array indexed by `omp_get_thread_num()` would let two concurrent searches race on slot 0; `thread_local` cannot, since each OS thread has its own copy.
- The table grows on demand (`ensure_size`) if `ntotal` increases and never shrinks. Retained memory is bounded by the array-vs-hash-set threshold (D112025912).
## Correctness
`get_reusable()` calls `advance()` before returning the table. A prior search that threw exception without correctly `advance()` may have left version stamps NOT updated; without the reset those would read as spurious "visited" hits on the next search on that thread. `advance()` - might be redundant - in `get_reusable()` guarantees correct query version id.
## Minor notes
The `IndexHNSW2Level` mixed-search path is deliberately left on per-search `create()` rather than `get_reusable()`. It is a legacy path that uses the tri-state visited flags of `search_from_candidates_2` (two `advance()` calls per query), whose reset semantics differ from the bi-state paths above; keeping a fresh per-search table there leaves its behavior unchanged and scopes reuse to the paths where a single `advance()` at handout is correct.
Reviewed By: mnorris11, pankajsingh88
Differential Revision: D112042940
fbshipit-source-id: c6be0effdb2f52d21f6bb16db2d2ad0972a71bc0
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5234
There are two VisitedTable implementations. Avoid runtime checks between the two by making them separate classes and templatizing the visited tables on them.
Reviewed By: mnorris11
Differential Revision: D105961848
fbshipit-source-id: 8c82c4ba2cf13e221a4f6a4e534f49e58073355d
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5031
`IndexHNSW` allocates an initializes locks for `ntotal+n` nodes on every call to `add()`. This makes batched insertion very costly, and incremental insertion prohibitively so.
This diff introduces optional persistent locks for `IndexHNSW` to improve incremental `add()` performance. Previously, `omp_lock_t` arrays of size `ntotal+n` were created/destroyed on each `add()` call. Now locks can be retained via a new `retain_locks` flag (default: false), using a new `HNSW::Lock` RAII wrapper with geometric growth.
RFC: Instead of `retain_locks` being the only way to opt into this new behavior, this could be inferred on the first incremental add. That is, clear the locks after insertion iff `n0 == 0`. Workloads which call `add()` once would be unaffected, but workloads which call `add()` repeatedly would 1) forego the clearing of the lock vector after `add()` call #2, and reuse locks for all subsequent calls. The downside would be the lack of the ability to reclaim the locks after insertion without HNSW-specific behavior at the call site.
Reviewed By: mdouze
Differential Revision: D98232750
fbshipit-source-id: ef55cd9e4eb79793267a29a06502a582873e6a74
Summary:
**Summary**
Resolved https://github.com/facebookresearch/faiss/issues/4927.
- Fixes base-level-only `IndexHNSWCagra::range_search` to return results without an entry point.
- Adds a C++ unit test reproducing the base-level-only range search case and a GPU interop Python test.
**Changes**
- Implement base-level-only range search path in `IndexHNSWCagra` using per-query range handlers.
- Add C++ helper to copy level-0 graph only and a new test for base-level-only range search.
- Add GPU interop Python test for base-level-only range search.
**Tests**
- `docker build -f docker/Dockerfile.dev -t faiss-dev:local --build-arg UID="$(id -u)" --build-arg GID="$(id -g)" .`
- `docker run --rm -v "$PWD:/workspace" -w /workspace faiss-dev:local bash -lc "cmake -B build-docker -G Ninja -DFAISS_ENABLE_GPU=OFF -DFAISS_ENABLE_PYTHON=ON -DBUILD_TESTING=ON -DBUILD_SHARED_LIBS=ON -DCMAKE_BUILD_TYPE=RelWithDebInfo . && cmake --build build-docker -j --target faiss faiss_test swigfaiss && ./build-docker/tests/faiss_test --gtest_filter=HNSW.Test_IndexHNSWCagra_BaseLevelOnly_RangeSearch"`
**Notes**
- The Python GPU test is skipped without CUVS/GPU support; it is included for GPU-enabled CI.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4963
Reviewed By: alibeklfc
Differential Revision: D97766638
Pulled By: mnorris11
fbshipit-source-id: 3bd50fa783d3ddfab14e0485ef975c821732ff6c
Summary:
- Fix compiler warnings in all 20 FAISS C++ test files
- Fixes include `-Wshadow`, `-Wunused-parameter`, and signed/unsigned comparisons
All changes are mechanical. No functional changes.
Part 13/13 of the compiler warnings cleanup (split from https://github.com/facebookresearch/faiss/issues/4810 per maintainer request).
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4944
Test Plan:
- [x] No functional changes — all fixes are mechanical renames and annotations
🤖 Generated with [Claude Code](https://claude.com/claude-code)
Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Reviewed By: mnorris11
Differential Revision: D96996609
Pulled By: alibeklfc
fbshipit-source-id: 72555246a4ccf540eb5422e64018c8d5e2660dce
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4735
`VisitedTable` accounts for a huge portion of `HNSW::search()` for unbatched searches of large indices.
As demonstrated in the benchmarks shown below, the vector-based implementation is much faster for smaller `ntotal` values, but at ~2M and above, it becomes slower, often significantly so. E.g.: At 64M slots, without batching, a workload of 1000 `set()`/`get()`s is >100x slower. Even with batching, this workload is still 3x slower with vectors.
This is a very likely explanation for the poor performance of HNSW in a 2023 USearch blog post (https://www.unum.cloud/blog/2023-11-07-scaling-vector-search-with-intel), which shows the same high throughput below 1M docs, and the same O(n) slowdown as the size grows beyond >2M:
Reviewed By: mnorris11, mdouze
Differential Revision: D89515309
fbshipit-source-id: 08bc4a54faa311eeb9946f2a43482ae52b61566e
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4762
Some search functions require special handling on the search resutls. For example collecting resutls from diverse groups.
In order to support this, we re-purpose the ResultHandler object to offer an arbitrary callback whenever a new vector should be taken in consideration.
Many indexes did already have such a callback, but in non-uniform formats. This diff consolidates these diverse implementations. This is especially the case for the InvertedListScanner that is now implemented on top of that.
Most indexes now get a `search1` that searches one query vector and takes a ResultCollector as input. This is the object that can be used a a callback to do specific handling on the results.
The current impleentatoin of search1 may not be perfectly optimized, especially for IndexFlatCodes indexes. Another todo is to support BlockResultHandlers to allow multiple queries at a time.
Differential Revision: D91003349
fbshipit-source-id: 3ce98145f9633174bd3d84bb1ae85f36084e41ce
Summary:
Fix https://github.com/facebookresearch/faiss/issues/4224.
The issue is that `IndexHNSW`'s internal `Index* storage` doesn't inherit `metric_arg`. One solution is to set `metric_arg` in `IndexHNSW::add`, which is what I did. Not sure what the best place to do this would be.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4239
Reviewed By: mdouze
Differential Revision: D71225749
Pulled By: gtwang01
fbshipit-source-id: b27a592febadea153b575252df0c8ef14f7705d2
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4061
search_level_0 is not unit tested yet. It isn't called anywhere so we can't test from the Index level, but it may be in the future, so adding a quick test for it.
Reviewed By: junjieqi
Differential Revision: D66800813
fbshipit-source-id: 5f1cf189b43610bc6c40c324343b5a55789d88ab
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4059
Add unit test to compare reference version with optimized version.
Reviewed By: mengdilin
Differential Revision: D66793367
fbshipit-source-id: 8da25e79f66d079f76d237c10fc3db4a0def767d
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4029
Remove headers flagged by facebook-unused-include-check over fbcode.faiss.
+ format and autodeps
This is a codemod. It was automatically generated and will be landed once it is approved and tests are passing in sandcastle.
You have been added as a reviewer by Sentinel or Butterfly.
Autodiff project: uif
Autodiff partition: fbcode.faiss
Autodiff bookmark: ad.uif.fbcode.faiss
Reviewed By: dtolnay
Differential Revision: D65957849
fbshipit-source-id: f6199250db595defd56f5e7b2828f838702e9a16
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3919
These tests are passing successfully in `dev` mode during my local development when I added them but I recently noticed they are failing on contbuild which is running them in opt/mode: https://www.internalfb.com/intern/test/281475152762853/
Upon further inspection, 2 of these were from floating point comparisons which we can fix with `EXPECT_NEAR`. The another one stems from indeterminism of the results in opt mode, so we will relax the test until we figure out a way to deal with the indeterminism
Reviewed By: junjieqi
Differential Revision: D63942329
fbshipit-source-id: 60f1c0b8a0db93015cd32bf991ab983ff2d1af13
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3849https://github.com/facebookresearch/faiss/issues/3845
Add unit tests for helper search utilities for HNSW. These utility functions live inside an anonymous namespace and each has a reference version gated behind a const bool, I refactored them so the reference version is a flag for the function which defaults to false.
If we are concerned about the performance overhead of the extra if branching (whether to use reference version or not) inside these utility functions, I'm happy to lift out the reference versions to their own functions inside the unit test
Reviewed By: junjieqi
Differential Revision: D62510014
fbshipit-source-id: b92ed4db69d125c7830da93946f1c2374fb87b08
lyang24