mirror of
https://github.com/facebookresearch/faiss.git
synced 2026-10-11 22:50:00 +00:00
main
2354
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
 Weixiang Hong
|
cec5702b0b |
DD: give fvec_L2sqr_ny_nearest_y_transposed_D internal linkage (#5720)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5720 `fvec_L2sqr_ny_nearest_y_transposed_D<DIM>` is a template defined at namespace scope in both `distances_avx2.cpp` (`-mavx2`) and `distances_avx512.cpp` (`-mavx512*`), with the same signature, so both TUs emit the same weak symbols and the linker keeps one copy per `DIM`. Whichever copy it keeps is used by both levels. In a current DD build the AVX512 copies of `D<1>`, `D<2>`, `D<4>` were kept (72-95 `zmm` instructions each) and the AVX2 copy of `D<8>`, so the AVX512 path ran AVX2 code for `D<8>`. Nothing on the AVX2 path calls `D<1/2/4>` today, so there is no crash now; but a link that keeps the AVX512 `D<8>` would make the AVX2 path execute AVX512 instructions and raise SIGILL on CPUs without AVX512 (e.g. AMD Milan). Same class as D124399620 (`PQCodeDistanceScalar`), found by scanning the DD binary for functions that contain `zmm` instructions but are not marked as an AVX512 level and have external linkage. The only other hits were `DCBF16_IP` / `DCBF16_L2`, which are defined only in `sq-avx512-spr.cpp` and reached only through AVX512_SPR dispatch. Fix: put the template in an anonymous namespace in each TU, so each level keeps its own copy. Reviewed By: mnorris11 Differential Revision: D124411046 fbshipit-source-id: 9165061e67f1476ff038c173aa837f7e0959e920 |
||
|
Weixiang Hong
|
5d635f354c |
DD: give PQCodeDistanceScalar a SIMD level so the AVX2 path cannot run AVX512 code (#5719)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5719 `PQCodeDistanceScalar<PQDecoderT>` is defined in a header and instantiated in every per-SIMD translation unit (`avx2.cpp` with `-mavx2`, `avx512.cpp` with `-mavx512*`, the generic TU). All copies have the same symbol, so the linker keeps one. In a dynamic-dispatch x86 build it kept the `-mavx512*` copy: `PQCodeDistanceScalar<PQDecoderGeneric>::distance_four_codes` contained 93 `zmm` instructions and was called from `PQCodeDistance<PQDecoderGeneric, SIMDLevel::AVX2>`. On a CPU without AVX512 (AMD Milan, T1_MLN), IVFPQ search with a non-8-bit PQ (`PQDecoderGeneric`, also `PQDecoder16`) on the AVX2 path raises SIGILL. Found by running the faiss C++ tests under the vendored `qemu-x86_64`, which has no AVX512: `IVFPQFastScan.*` (`test_fast_scan_distance_to_code`) died with SIGILL at `vmovdqa64 ...,%zmm0` in that function. Same class as S672695 (AVX512 code reached on a CPU without it); found before any non-AVX512 host was added to the Cogwheel suite. Fix: template `PQCodeDistanceScalar` on `SIMDLevel` as well, as the DD migration guide prescribes for code compiled per level, so each TU's instantiation is a distinct symbol. `PQCodeDistance<D, SL>` passes its level; the NONE and ARM_NEON specializations in `pq_code_distance-generic.h` pass theirs. Applied to both definitions (`impl/pq_code_distance/pq_code_distance-inl.h` and `utils/pq_code_distance.h`). `SL` defaults to `SIMDLevel::NONE` so code outside faiss that names only the decoder keeps compiling: `unicorn/features/encoders/PQFSTable.h` uses `faiss::PQCodeDistanceScalar<PQDecoderT>`, and without the default 15 Unicorn targets failed to build on this diff. Reviewed By: mnorris11 Differential Revision: D124399620 fbshipit-source-id: ece1baf0e1eba39712f881976dea33fe22b265c1 |
||
|
Alibek Zhakubayev
|
07979b10e6 |
Randomized Ball Carving partition (#5714)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5714 We add the Randomized Ball Carving partition, which splits the dataset into small overlapping leaves, and `gather_rows`, which reads rows of the storage as floats for the kernels. **Motivation** The PiPNN graph build (Rubel et al., "PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing", KDD '26, arXiv:2602.21247) first partitions the dataset into small overlapping leaves, then builds candidate edges inside each leaf. The partition must read the vectors exactly as search sees them, whatever the storage. It must produce the same leaves for any thread count, so that builds are reproducible, and its memory must stay bounded at billion scale. It must also terminate on degenerate data, such as duplicate points, or inner-product data where one high-norm leader attracts every point. **Implementation** - `faiss/impl/pipnn/kernels.{h,cpp}`: `gather_rows(storage, ids, k, out)` reads rows with `reconstruct()`, except `IndexScalarQuantizer` rows, which it decodes with one `SQuantizer` per call. We do not use `sa_decode` or `reconstruct` for SQ storage: `ScalarQuantizer::decode` opens an OpenMP region, and a nested region inside the partition's `schedule(dynamic)` loops segfaults with the libomp of fbcode builds. - `faiss/impl/pipnn/Partition.{h,cpp}`: Randomized Ball Carving (paper Alg. 5) with multi-level fanout. A root level runs first, then memory-bounded waves of root children. Each wave runs level-synchronous `omp for schedule(dynamic)` item lists that mix stripe items (one single-threaded `stripe_assign` call per 1024-point stripe) and leaf items, which are handed to a `LeafVisitor`. Each level runs four steps that share a `LevelContext`: `plan_level` (leaders and work items), `assign_leaders` (the stripe and leaf loop), `scatter_children` (the counting sort below) and `collect_children` (the merge and degenerate-child rules). - A per-block counting sort scatters the children, so every child lists its points in parent order. Small children are merged in a seeded Fisher-Yates order. An IP-ranked child that holds more than 90% of its parent is re-partitioned by L2, and a child equal to its parent or at the depth limit is cut into id slices. Together these rules guarantee termination. - Leader sampling (Floyd's algorithm), the merge order and every child seed come from `SplitMix64RandomGenerator` and `mix_seed`, and every selection uses a strict total order, so the leaves do not depend on the thread count or on the wave budget. - The stripe and leaf loop captures exceptions per item and rethrows them after the loop. Its master thread polls `InterruptCallback` after its first item and then every 64 items, and the partition checks it between levels. A throwing `InterruptCallback` is captured like any item exception. The classify loop also captures and rethrows exceptions; the counting-sort loops cannot throw. - Memory: the per-level assignment, count and child-id arrays are uninitialized heap arrays, so they are not zero-filled before being overwritten. The per-level node and work-item lists are reserved heap vectors, proportional to the number of nodes in the level. Every partition buffer is released on exit, including on the throwing paths. We reject `c_max > 4096`, because each thread holds a `c_max` x `c_max` float matrix for its leaves. - The `test_pipnn_cpp` test target gains the `openmp` dependency, because the tests include `omp.h` to set the OpenMP thread count. - No caller yet outside the tests. The graph build uses this code in a later diff of the stack. Reviewed By: mnorris11 Differential Revision: D123103150 fbshipit-source-id: df2b82457f9c9840846a4707847f37bf03266ac7 |
||
|
Weixiang Hong
|
f46050eb56 |
Deflake test_io TestIVFPQRead.test_reader (#5718)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5718 `test_reader` searches one IVFPQ index loaded twice, with and without the precomputed table, and required the neighbor ids to be identical. The two paths add the distance terms in a different order, so near-tied neighbors can swap. With unseeded data it failed in 7 of 400 random draws, and once in seven runs of the Cogwheel faiss suite on T1_BGM (2 of 10000 ids). Compare with `check_ref_knn_with_draws`, which allows swaps only among tied distances, and seed the data so a failure reproduces. `test_io` moves to `py_tests_with_contrib` for the helper. Reviewed By: mnorris11 Differential Revision: D124383290 fbshipit-source-id: ceb81262ffaba81ac23e5a592e1658741192060d |
||
|
Weixiang Hong
|
db6aa06d96 |
Hoist per-list allocations out of the IVF fast-scan search loops (#5717)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5717 `IndexIVFFastScan::search_implem_12` and `search_implem_14` allocate a fresh `AlignedTable<uint8_t> LUT`, `q_map` and `lut_entries` for every inverted list they visit, and call `get_block_stride()`, which heap-allocates a `CodePacker` on each call; `search_implem_10` makes the same `get_block_stride()` call per list. These loops run on OpenMP worker threads, so with jemalloc heap profiling on (the production default for task 0 of every job) on aarch64 every sampled allocation pays libunwind's slow fallback at the `__kmp_invoke_microtask` frame. gdb thread snapshots of the D124204736 build under profiling (`hr_ivf1024_rabitqfs4`, Grace): of 206 threads caught in jemalloc's `prof_backtrace`, 163 were in `posix_memalign` called from `search_implem_12` (the per-list LUT), 6 in its per-list vectors and 4 in `get_block_stride()`. This allocates those buffers once per call / per thread, sized for the largest batch (`qbs2` queries x `dim12`), and computes the block stride once. Each iteration still uses only the first `nc` entries, so the search is unchanged. Reviewed By: junjieqi Differential Revision: D124387842 fbshipit-source-id: 6bcfe66270fcc0b208b0c88aaf578fea952f6174 |
||
|
Fadi Arafeh
|
39079668a8 |
Select OpenBLAS OMP build in conda for AArch64 + Linux (#5669)
Summary: - The current Faiss conda recipe does not specify the OpenBLAS threading variant. - On Linux AArch64, the dependency solver selects the pthreads build. - This causes problems when Faiss calls BLAS from within an existing OpenMP parallel region due to nested threading - As a result, the benchmark below (with an OOB conda install of faiss) only yields 7% of the throughput reachable when an OMP build of OpenBLAS is selected (what this PR does) - This PR fixes the issue, and as a result accelerates affected workloads by ~ 14x ``` # SPDX-FileCopyrightText: Copyright 2026 Arm Limited and/or its affiliates <[email protected]> # SPDX-License-Identifier: MIT import ctypes import statistics import time import faiss import numpy as np rng = np.random.default_rng(1234) d = 128 nlist = 4096 nq = 40_000 quantizer = faiss.IndexFlatL2(d) quantizer.add(rng.random((nlist, d), dtype=np.float32)) index = faiss.IndexIVFPQFastScan(quantizer, d, nlist, 128, 4) # index is empty - this only triggeres the course quantizer index.is_trained = True index.nprobe = 64 xq = rng.random((nq, d), dtype=np.float32) openblas = ctypes.CDLL("libopenblas.so.0") openblas.openblas_get_parallel.restype = ctypes.c_int openblas.openblas_get_num_threads.restype = ctypes.c_int print(f"nq={nq:,}, d={d}, nlist={nlist}, nprobe={index.nprobe}") print(f"OpenMP threads={faiss.omp_get_max_threads()}") print( f"OpenBLAS parallel={openblas.openblas_get_parallel()}, " f"threads={openblas.openblas_get_num_threads()}" ) print(f"BLAS threshold={faiss.cvar.distance_compute_blas_threshold}") index.search(xq, 10) times = [] for _ in range(20): start = time.perf_counter() index.search(xq, 10) times.append(time.perf_counter() - start) elapsed = statistics.median(times) print(f"median={elapsed:.6f}s, throughput={nq / elapsed:,.0f} QPS") ``` Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5669 Reviewed By: weixianghong Differential Revision: D124380509 Pulled By: mnorris11 fbshipit-source-id: 16e1521e7aaf7d65c6a4ce8e404a47bdb26c1198 |
||
|
Weixiang Hong
|
44afa7729d |
Stop allocating per (query, probe) on OpenMP workers in IVF RaBitQ fast-scan (#5716)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5716 `IndexIVFRaBitQFastScan` heap-allocated up to three times per (query, probe) inside the OpenMP parallel regions of `compute_LUT` / `compute_LUT_uint8`: - `compute_residual_LUT` built a fresh `std::vector<uint8_t> rotated_qq(d)` on every call. - For multi-bit indexes, it copied `rotated_q` (d floats) into a temporary `QueryFactorsData`. - `compute_LUT_uint8` then copied that temporary into `context.query_factors[ij]` instead of moving it. Under jemalloc heap profiling on aarch64, which Tupperware enables by default in task 0 of every job, each sampled allocation on an OpenMP worker unwinds through libomp's `__kmp_invoke_microtask`. That frame has no CFI, so libunwind's fallback maps and unmaps a whole ELF image per sample, serialised on `mmap_lock` (same mechanism as D123990523; details in that diff). After D123990523, a 74-scenario ServiceLab sweep with profiling on still showed IVF RaBitQ fast-scan at up to 30k (1-bit) and 57k (multi-bit) minor faults per pass, with up to 58 of 72 threads blocked. gdb stack snapshots of a profiled `hr_ivf1024_rabitqfs4` run (348 threads caught inside `je_prof_backtrace`) attributed 149 samples to the `rotated_q` copy and 31 to `rotated_qq` inside `compute_residual_LUT`. The second copy, in `compute_LUT_uint8`, is visible in the code; its frames were not symbolised in the snapshot. This diff: - makes `rotated_qq` a per-thread buffer, like `rotated_q` and `centroid_buf` already are; - stores multi-bit rotated queries in one block allocated once per search in `search_preassigned`, outside the parallel region and uninitialised. Each (query, probe) writes its slice and the handler reads it by storage index, via a new `FastScanDistancePostProcessing::rotated_q` that is offset per thread slice like `query_factors`; - moves rather than copies into `context.query_factors[ij]`; - keeps the capacity of a reused `QueryFactorsData` in `compute_residual_LUT`, so the single-query `IVFRaBitQFastScanScanner` no longer reallocates `rotated_q` on every `set_list`. Memory is unchanged: the same n × nprobe × d floats as before, now contiguous instead of in n × nprobe separate vectors. **Effect** (devbig334 Grace, Tupperware-matched environment, heap profiling on as in production, nq=10000, single runs on a busy shared host; recall unchanged): | hr_ivf1024 | nprobe | QPS before → after | minor faults per pass before → after | |---|---|---|---| | rabitqfs4 (multi-bit) | 16 | 27,032 → 36,069 | 4,006 → 1,911 | | rabitqfs4 (multi-bit) | 64 | 10,168 → 23,295 | 14,932 → 5,822 | | rabitqfs4 (multi-bit) | 256 | 2,883 → 6,438 | 49,841 → 20,371 | | rabitqfs (1-bit) | 256 | 3,179 → 6,854 | 23,935 → 20,654 | Profiling off, rabitqfs4 at nprobe=256: 14,337 → 13,151 QPS, within this host's noise. **What this does not fix.** With these allocations gone, 1-bit and multi-bit converge on about 20k faults per pass at nprobe=256. gdb attributes 163 of the 206 remaining samples to `posix_memalign` in `IndexIVFFastScan::search_implem_12` on worker threads: the LUT tables (`dis_tables`, n × nprobe × LUT size) that each thread slice allocates. Those allocations are needed, and jemalloc samples them by bytes. The remedy for that remainder is unwind info for libomp's aarch64 `__kmp_invoke_microtask`, being raised separately, rather than more FAISS changes. Reviewed By: alibeklfc Differential Revision: D124204736 fbshipit-source-id: 28be93c1cabbcb679bd5328808207fd8e24828b8 |
||
|
Eppalapelly Madhukar
|
8b884ecc96 |
Fix IndexFastScan::reset() leaving stale ntotal2 (crash on search) (#5614)
Summary: reset() cleared ntotal and the codes buffer but left ntotal2 (the bbs-padded scan count) unchanged. A search after reset then scans ntotal2/bbs blocks over the freed, empty code buffer, dereferencing a null pointer in the SIMD kernel and crashing with SIGSEGV (Fixes https://github.com/facebookresearch/faiss/issues/5591). Clear ntotal2 in reset() too, matching init_fastscan(). This covers all flat FastScan indexes (PQ/AQ/RaBitQ), which share this reset(). Add test_reset reproducing train -> add -> reset -> search: it checks ntotal2 == 0 after reset and that searching the emptied index is safe and returns the -1 sentinel. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5614 Reviewed By: junjieqi Differential Revision: D124253538 Pulled By: mnorris11 fbshipit-source-id: 038186130c03534fc353eae9390f031413a05a5e |
||
|
Weixiang Hong
|
6692d7ab37 |
Stop copying QueryFactorsData per block in RaBitQHeapHandler
Summary: `RaBitQHeapHandler::handle()` in `IndexRaBitQFastScan.h` copied `rabitq_utils::QueryFactorsData` by value once per (query, 32-vector block). The struct owns `std::vector<float> rotated_q`, so each copy is a heap malloc + free inside the scan's innermost loop: about 312M allocations per 10,000-query pass on sift-1M. It now binds a `const&` to `context->query_factors[q]`, or to a function-local `static const` empty instance when there is no context. `compute_1bit_adjusted_distance` already takes `const&`, so nothing downstream changes. **Why this showed up as an ARM "page-fault storm"** The copy is wasteful on every platform. It becomes catastrophic with jemalloc heap profiling on aarch64, when the allocation happens on an OpenMP worker thread: - Heap profiling is on by default in task 0 of every Tupperware job: the TW scheduler appends `prof:true,prof_final:false,prof_prefix:/tmp/jeprof` when `taskID % contHeapEnabledRatio == 0` (`tupperware/scheduler/JobSpecUtil.cpp`). jemalloc then backtraces one allocation per 512 KiB on average (`lg_prof_sample` 19), through libunwind on aarch64 (`config.prof_libunwind=1`). - On OpenMP workers the stack runs through `__kmp_invoke_microtask`, libomp's assembly entry, which has no usable CFI. DWARF unwinding fails there, and libunwind's aarch64 fallback (`get_frame_state`) calls `get_proc_name`, which maps the frame's whole ELF image and unmaps it on every call. Every map and unmap serialises on `mmap_lock`. - gdb on a reproducer without FAISS: all 95 `get_proc_name` fallbacks hit `__kmp_invoke_microtask`; the same allocations on plain pthreads hit none. - The fault count tracks the sampling rate exactly: 3,053,990 / 1,525,976 / 764,008 faults per pass at `lg_prof_sample` 18 / 19 / 20. That is about 305k samples per pass (160 GB of 512 B copies ÷ 512 KiB) at roughly 5 faults each. **Numbers**, hr_rabitqfs, sift-1M, recall 0.3567 throughout. ServiceLab Grace (72 threads, heap profiling on as in production), nq=10000: | | QPS | minor faults / pass | |---|---|---| | before | 91 | 1.53M | | after (E2362759441136789) | 17,186 | 858 | devbig334 Neoverse-V2, environment matched to Tupperware (no `KMP_*` variables), nq=10000, single runs on a busy shared host, so treat as indicative: | | QPS | kcycles/query | minor faults / pass | |---|---|---|---| | before, profiling off | 9,342 | 13,223 | 322 | | after, profiling off | 11,083 | 11,831 | 341 | | before, profiling on | 93 | 33,563 | 1,525,976 | | after, profiling on | 10,970 | 11,756 | 840 | Without profiling the copy alone costs about 10% more cycles per query. **Not fixed here: `IndexIVFRaBitQFastScan`.** Its scan already reads query factors by reference, but a ServiceLab sweep with this fix and profiling on still shows up to 30k (1-bit) and 57k (multi-bit) faults per pass with up to 58 threads blocked. The allocation site is being located and will be fixed in a separate diff. Reviewed By: mnorris11 Differential Revision: D123990523 fbshipit-source-id: 0112bdbe78ac0fd647ea6199b00000193f96788e |
||
|
Junjie Qi
|
3a98062426 |
faiss/conda: extend LSQ NEON-flaky test skip to all arm64 (#5713)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5713 Two Local Search Quantizer tests are numerically flaky under ARM NEON FMA ordering: - `TestComponents_ARM_NEON.test_update_codebooks_with_double`: `err_double` can exceed `err_float` on ARM even though it is better on x86. - `TestProductLocalSearchQuantizer.test_lut`: `compute_LUT` rounds differently on NEON; max relative diff reaches ~1.7e-3, above the x86-tuned `rtol=5e-4`. D121930308 already skips both via `pytest -k` on `osx and arm64`. This widens the conda selectors to `arm64` so linux-aarch64 nightly builds skip them too: - `pytest` test requirement and the `pytest -k` command: `[osx and arm64]` -> `[arm64]` - `unittest` `test_*` command: `[not (osx and arm64)]` -> `[not arm64]` The root fix (platform guards / looser `rtol` in the test files) is still pending. Reviewed By: mnorris11 Differential Revision: D122238335 fbshipit-source-id: c18fa2ecec29602e758bc20e2bc0dfc3e5d207d0 |
||
|
Michael Norris
|
2839c39f20 |
Make the GPU IVF search return the same neighbours on every run (#5682)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5682 This diff adds an option, `deterministic_tie_break`, that makes a GPU IVF search return the same neighbours on every run. It is off by default. **CHANGES THAT APPLY BY DEFAULT. No option turns these off. The id tie break itself is the new option `deterministic_tie_break`, which is off by default.** 1. **Tie order:** the interleaved IVF scan (`GpuIndexIVFFlat`, `GpuIndexIVFScalarQuantizer`) orders an exact distance tie by the position in the list, for `k` up to 1024. Before, the order followed the arrival order in the sort network. Only the choice among exactly equal distances can change. REASON: it blew up binary size to make it not like this. see below. 2. **Launch shape:** the first pass of the `k <= 32` interleaved scan runs with 64 threads in a block instead of 128. Measured on one A100 with `deterministic_tie_break` off: 1.8% faster than master. REASON: perf improvement. 3. **Padding:** pass 2 of the interleaved scan rejects the padding slots of a list shorter than `k`. On master a pad cannot win, because `Comparator` is strict. The tie order of item 1 lets a pad win a tie with the heap sentinel, so this check goes with item 1. REASON: used for deterministic, but should have no impact on non deterministic flow. 4. **`copy_subset_to` with `SUBSET_TYPE_ID_MOD`:** a vector with a negative id goes to the subset that its id selects. Before, it was dropped from every subset, and a multi-GPU clone with `shard_type` 1 failed its `ntotal` check. REASON: bug fix. 5. **`merge_knn_results`** (used by `IndexShards` and `IndexShardsIVF`): only `-1` marks a missing result. Before, every negative id did, so a sharded search with signed ids lost results. REASON: bug fix. 6. **Shared k-selection code** (`Select.cuh`, the merge networks): every comparison receives the value as well as the key. The default comparator ignores the value, so the results do not change. REASON: used for deterministic, but should have no impact on non deterministic flow. Below changes do not change the default results: - The RAFT `TieBreak` template parameter defaults to false, and generates the same code as upstream. - The new cuVS `search_params::select_algo` defaults to `kAuto`. **Behaviour before:** - A query whose candidates tie on distance can get a different neighbour on a second run. - `copy_subset_to` with `SUBSET_TYPE_ID_MOD` drops every vector with a negative id from every subset. - `merge_knn_results`, which `IndexShards` and `IndexShardsIVF` use, treats every negative id as a missing result. It drops a shard's results from its first negative id onward. - The `k <= 32` IVF scan runs its first pass with 128 threads in a block. **Behaviour after:** - With `deterministic_tie_break` on, a repeated search returns the same ids and the same distances. - With `deterministic_tie_break` off, the search behaves as before. Only the choice among exactly equal distances can differ from master, as it can between any two layouts. - `SUBSET_TYPE_ID_MOD` keeps a vector with a negative id, in the subset that its id selects. - `merge_knn_results` treats only `-1` as a missing result, so a sharded search returns negative ids. - The `k <= 32` IVF scan runs its first pass with 64 threads in a block. **Gating:** - `GpuIndexIVFConfig::deterministic_tie_break` and `GpuClonerOptions::deterministic_tie_break` default to false. The cloner copies `GpuClonerOptions::deterministic_tie_break` into the IVF config. The caller sets it when it creates or clones the index. - These indexes honour `deterministic_tie_break`: - `GpuIndexIVFFlat` and `GpuIndexIVFScalarQuantizer` with the interleaved layout, which is the default, for `k` up to 1024. This path needs no cuVS change. - The cuVS `GpuIndexIVFPQ` and the cuVS `GpuIndexIVFScalarQuantizer`, for `k` and `nprobe` up to 256, in a build that defines `FAISS_CUVS_HAS_STABLE_SELECT`. - The classic `GpuIndexIVFPQ` and cuVS IVF-Flat ignore `deterministic_tie_break`. - The interleaved scan ignores `deterministic_tie_break` above `k` = 1024. Its kernels for a larger `k` keep `Comparator`, because a tie break in their large merge networks costs much code size. - The cuVS indexes ignore `deterministic_tie_break` above 256, and in a build without the `FAISS_CUVS_HAS_STABLE_SELECT` macro. **Why the `FAISS_CUVS_HAS_STABLE_SELECT` macro exists:** - The cuVS path sets `search_params::select_algo` to `raft::matrix::SelectAlgo::kWarpDistributedShmStable`. - That field and that enum value exist only in a cuVS and RAFT tree that has the cuVS and RAFT changes in this diff. They are not in cuVS 26.02, and they are not upstream yet. - Code that names them does not compile against such a tree. The macro tells the compiler that the symbols exist. It does not turn `deterministic_tie_break` on. - The internal Buck build defines the macro for its patched cuVS 26.06 tree. The CMake build does not define it. - When upstream cuVS and RAFT have the symbols, a cuVS version check can replace the macro. **Why each change is needed:** - The GPU k-selection ordered on the distance alone, so an exact tie followed the order in which the data reached the sort network. - With `deterministic_tie_break` on, `TieBreakComparator` orders a tie by the user id, which the IVF pass-1 kernel carries as the value. Pass 1 loads an id only when its candidate can still enter the top `k`. - With `deterministic_tie_break` off, pass 1 keeps the list offset as before, and pass 2 translates the offset to the user id as before. - IVF pass 2 rejects the padding that pass 1 leaves in a short list. A padded slot could otherwise win a tie and reach the output. - `raft/util/bitonic_sort.cuh` and `raft/matrix/detail/select_warpsort.cuh` add a tie break on the payload index as a template parameter, `TieBreak`, false by default. With false, the generated code is the same as upstream. - The new RAFT selector `kWarpDistributedShmStable` uses the new class `warp_sort_distributed_ext_stable`, which sets `TieBreak` to true. It supports `float` and `half` keys, and fails for other key types, so their `select_k` instantiations do not grow. - cuVS `ivf_pq.hpp` and `ivf_sq.hpp` add `search_params::select_algo`, with the default `kAuto`. The IVF-PQ and IVF-SQ searches pass it to their `select_k` calls. With `deterministic_tie_break` on, faiss asks for `kWarpDistributedShmStable`. - A sharded index with signed ids lost about half of its neighbours. On one A100, 4 shards of an `IVF64,SQ8` index with 20,000 signed random ids agreed with the unsharded index on 28% to 29% of the neighbours, with the id split and with the list split. With the fix, they agree on 100%. - `copy_subset_to` tested `id % n == i`. C++ gives a negative remainder for a negative id, so the test never matched. The fold `((id % n) + n) % n` maps every id into `[0, n)`. - The first pass of the `k <= 32` scan is faster with 64 threads. The measurements follow. **A caller that wants a repeatable search must also do two things itself:** - Train the codec once and reuse it, because k-means is not repeatable. - Sort each inverted list by id after the build. cuVS IVF-PQ, cuVS IVF-SQ, and an index with `INDICES_CPU` or `INDICES_IVF`, break a tie on the position in the list, and position follows insertion order. **Build size:** - The RAFT tie break is a template parameter, so only the stable selector instantiates the tie-break code. The other `select_k` instantiations generate the same code as upstream. - The scan kernels for `k` above 1024 keep `Comparator`, because a tie break in their large merge networks costs much code size. - A local dev ASAN build of `libfaiss_gpu_faiss.so` is 829.3 MiB. The `.nv_fatbin` section is 265.1 MiB. - CI reports no build size or build speed regression signals. **Measurements** Every number comes from one A100 80GB unless otherwise noted, and an opt build: - Base: 2,000,000 vectors, d = 768, float32, uniform in `[0, 1)` from `np.random.RandomState(1234).rand`. - Queries: 20,000 vectors from the same generator. - Metric: L2. - Coarse quantizer: `IndexFlatL2` with `nlist` = 519, so a list holds about 3,850 vectors. Training uses the first 200,000 base vectors. - Timing: one `search` call over all 20,000 queries. QPS is 20,000 divided by the best wall time. - Noise: six builds of the unchanged code differ by 0.33%. *Classic GPU IVF scan.* `IndexIVFScalarQuantizer` with `QT_8bit`, cloned with `use_cuvs = False`. `k` = 10, `nprobe` = 16, 61,657 candidates for each query. Best of 3 searches, two runs for each build: | build | QPS | | --- | --- | | master | 7,740 / 7,732 | | this diff, `deterministic_tie_break` off | 7,862 / 7,878 | | this diff, `deterministic_tie_break` on | 7,857 / 7,861 | - `deterministic_tie_break` costs about 0.1%, which is inside the noise. - With `deterministic_tie_break` off, this diff is 1.8% faster than master. The gain comes from the 64-thread first pass. First-pass threads in a block, same data, `deterministic_tie_break` on: | threads | QPS | | --- | --- | | 32 | 7,240 | | 64 | 7,877 | | 128 (the master launch shape) | 7,493 | | 256 | 6,428 | 512 threads does not build: `FinalBlockMerge` has no specialisation for 16 warps. The 64-thread gain over 128 holds across shapes on A100, H100, GB300. The H100 and GB300 rows below ran with `deterministic_tie_break` off: ``` ┌───────┬─────┬─────┬────────┬────────────────────────────┬─────────────────────────────────────┬─────────────────┐ │ GPU │ d │ k │ nprobe │ 64 threads (run 1 / run 2) │ 128 threads, master (run 1 / run 2) │ gain │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 10 │ 16 │ 15,726 / 15,691 │ 14,316 / 14,258 │ +9.9% / +10.1% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 32 │ 16 │ 15,668 / 15,645 │ 14,273 / 14,228 │ +9.8% / +10.0% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 128 │ 10 │ 16 │ 144,849 / 145,020 │ 125,843 / 125,592 │ +15.1% / +15.5% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ H100 │ 768 │ 10 │ 64 │ 3,946 / 3,946 │ 3,585 / 3,580 │ +10.1% / +10.2% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 10 │ 16 │ 16,627 / 16,629 │ 8,693 / 8,694 │ +91.3% / +91.3% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 32 │ 16 │ 16,576 / 16,570 │ 8,670 / 8,672 │ +91.2% / +91.1% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 128 │ 10 │ 16 │ 157,620 / 157,534 │ 79,062 / 79,100 │ +99.4% / +99.2% │ ├───────┼─────┼─────┼────────┼────────────────────────────┼─────────────────────────────────────┼─────────────────┤ │ GB300 │ 768 │ 10 │ 64 │ 4,116 / 4,116 │ 2,167 / 2,167 │ +89.9% / +89.9% │ └───────┴─────┴─────┴────────┴────────────────────────────┴─────────────────────────────────────┴─────────────────┘ ``` A thread queue of 3 was 2.5% faster than 2 on the A100 and level on an H100, so this diff keeps 2. *cuVS IVF-PQ.* `GpuIndexIVFPQ` with `use_cuvs = True`, `M` = 384, 8 bits for each code, trained and filled on the GPU, copied to the CPU, then cloned twice: once with `deterministic_tie_break` off (`kAuto`) and once with it on (`kWarpDistributedShmStable`). Timed searches alternate between the two clones. Best of 5, two runs: | k | nprobe | `deterministic_tie_break` off | `deterministic_tie_break` on | cost | | --- | --- | --- | --- | --- | | 10 | 16 | 16,078 / 15,984 | 16,043 / 15,964 | +0.22% / +0.13% | | 100 | 64 | 3,967 / 3,965 | 3,988 / 3,960 | -0.52% / +0.11% | - The stable selector costs about 0.1% to 0.2%, which is inside the noise. - The two selectors returned different ids for 0.0015% to 0.045% of the results. These are exact distance ties: PQ sums table entries, so equal distances are more frequent than with raw floats. *cuVS IVF-SQ.* `GpuIndexIVFScalarQuantizer` with `QT_8bit` and `use_cuvs = True`, `INDICES_64_BIT`, built on the CPU, then cloned twice: once with `deterministic_tie_break` off (`kAuto`) and once with it on (`kWarpDistributedShmStable`). Timed searches alternate between the two clones. All 5 searches of both runs, in QPS: | run | k | nprobe | `deterministic_tie_break` off | `deterministic_tie_break` on | best off / best on | | --- | --- | --- | --- | --- | --- | | 1 | 10 | 16 | 14,189 / 14,290 / 14,359 / 14,311 / 14,321 | 14,252 / 14,266 / 14,337 / 14,340 / 14,245 | 14,359 / 14,340 | | 1 | 100 | 64 | 2,923 / 2,945 / 2,950 / 2,952 / 2,951 | 2,932 / 2,950 / 2,943 / 2,952 / 2,936 | 2,952 / 2,952 | | 2 | 10 | 16 | 14,232 / 14,290 / 14,288 / 14,259 / 14,143 | 14,219 / 14,280 / 14,278 / 14,184 / 14,301 | 14,290 / 14,301 | | 2 | 100 | 64 | 2,934 / 2,941 / 2,949 / 2,947 / 2,945 | 2,934 / 2,944 / 2,941 / 2,941 / 2,936 | 2,949 / 2,944 | - The best-of-5 difference is between -0.17% and +0.08%, which is inside the noise. - The two selectors returned different ids for 0.0090% (k = 10) and 0.0578% (k = 100) of the results, in both runs. These are exact distance ties. Reviewed By: alibeklfc Differential Revision: D121990149 fbshipit-source-id: ad68d32289da529356fc77a0737d3c637600f976 |
||
|
Fadi Arafeh
|
a2f7943005 |
Optimize 4-bit PQ fastscan accumulation on Arm CPUs (#5709)
Summary: - FastScan's pq4 kernel uses vector abstractions that are 256-bit wide - e.g. `simd32uint8` and `simd16uint16` - These are performant for processors whose SIMD registers are 256-bits - However, on Arm, these are implemented using 2 128-bit NEON registers - which leads to register pressure - For example, the original algorithm which accumulates NQ queries x 32 db elements uses these accumulators: `simd16uint16 accu[NQA][4]` which add up to 24 Neon registers (for the common case where NQA=3) - out of a total of 32 avaliable NEON registers. - With other temp registers for code vectors and LUT, the compiler spills registers to stack This change: - Adds a native NEON kernel equivalent for `pq4_kernel_qbs_256` which accumulates NQ queries for a single basic block of 32 database vectors (it uses 12 accumulators for NQA=3) --- (we'll raise another PR for speeding up `kernel_accumulate_block` which accumulates NQ queries for multiple 32-vectoer DB blocks.) - keeps the existing QBS decomposition, PQ code packing, LUT packing and the PQ4 accumulate loop - this is now shared between the neon kernel and the existing simd256 kernel - removes 126 Lines of deadcode from `decompose_qbs.cpp` - please let me know if these were left for a reason. ## Tests: This change is covered by existing tests: `test_fast_scan`, `test_fast_scan_ivf`, `test_sq_fastscan`, `test_ivf_sq_fastscan` - all these tests path. Also measured R@1, R@10 and R@100 for index types below for baseline and this PR and made sure they're identical. ## End to End Performance: with topk=10, nprobe=64, Neoverse-V3 R@1, R@10 and R@100 match exactly with baseline | Dataset | Index | Threads | Speedup | |---|---|---:|---:| | sift1M | `PQ32x4fs` | 32 | **1.412x** | | sift1M | `PQ32x4fs` | 96 | **1.415x** | | sift1M | `PQ64x4fs` | 32 | **1.353x** | | sift1M | `PQ64x4fs` | 96 | **1.351x** | | sift1M | `PQ128x4fs` | 32 | **1.310x** | | sift1M | `PQ128x4fs` | 96 | **1.316x** | | sift1M | `IVF4096,PQ32x4fs` | 32 | **1.104x** | | sift1M | `IVF4096,PQ32x4fs` | 96 | **1.114x** | | sift1M | `IVF4096,PQ64x4fs` | 32 | **1.132x** | | sift1M | `IVF4096,PQ64x4fs` | 96 | **1.144x** | | sift1M | `IVF4096,PQ128x4fs` | 32 | **1.153x** | | sift1M | `IVF4096,PQ128x4fs` | 96 | 1.095x | | sift1M | `IVF4096,SQ4fs` | 32 | **1.156x** | | sift1M | `IVF4096,SQ4fs` | 96 | 1.082x | | sift1M | `IVF4096,RQ30x4fs_Nrq2x4` | 32 | **1.102x** | | sift1M | `IVF4096,RQ30x4fs_Nrq2x4` | 96 | 1.047x | | sift1M | `IVF4096,RaBitQfs` | 32 | 1.023x | | sift1M | `IVF4096,RaBitQfs` | 96 | 1.007x | | bigann10M | `IVF16384,PQ128x4fs` | 32 | 1.087x | | bigann10M | `IVF16384,PQ128x4fs` | 96 | 1.007x | Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5709 Reviewed By: junjieqi Differential Revision: D123883104 Pulled By: mnorris11 fbshipit-source-id: a97fa22b42c5ea238cc4220190a4e775a0a30eac |
||
|
Alibek Zhakubayev
|
7069478c3f |
Numeric kernels
Summary: We add the numeric kernels of the PiPNN build. **Motivation** The PiPNN build spends its compute in three dense operations: assigning points to partition leaders, finding the k nearest neighbours inside each leaf, and computing per-point distance matrices for the final prune. Each one is a single BLAS product on a fixed block followed by a selection. The build must be deterministic across thread counts, so the output of each kernel must depend only on its inputs: the BLAS call must not thread internally, and every selection must use a strict total order. **Implementation** - Norms come from Faiss's `fvec_norm_L2sqr`, which gives a vector bitwise the same norm at any address. - `stripe_assign`: assigns each point of a stripe to its `fanout` nearest leaders under the L2, IP or Angle ranking. One `sgemm_` over rows pre-filled with leader norms, then a top-fanout in `(dist, leader_index)` order on a Faiss max-heap (`heap_replace_top` and `heap_reorder` with `CMax::cmp2`). NaN counts as +inf, no slot is ever skipped, and the output is `uint16` leader indices. Under Angle, a leader with a zero norm (all zeros, or underflowed in float) ranks +inf, after every leader with a nonzero norm. - `leaf_knn`: the k nearest neighbours of every point inside a leaf. One `ssyrk_` fills the lower triangle of the Gram matrix, distances are `max(0, ni + nj - 2G)` for L2 and `-G` for IP, and a symmetric pair scan selects in `(dist, local_index)` order without self pairs. Unfilled slots are -1 / +inf. - The top-k slots start as (+inf, `INT32_MAX`) rather than Faiss's (`FLT_MAX`, -1), so that +inf candidates still fill empty slots in index order; slots left empty become -1. - `pairwise_distances`: the full symmetric distance matrix for the final prune, with the same `ssyrk_` call and post-processing as `leaf_knn`. It uses its output as the Gram scratch and ignores its prior contents. - `kernels.h` states the determinism contract: callers invoke the kernels inside an active OpenMP parallel region, or from serial code only when `omp_get_max_threads() == 1` or OpenMP is disabled, so that each BLAS call runs single-threaded. It also lists the BLAS configurations that keep BLAS from threading on its own. The kernels never change BLAS threading settings. - No caller yet. The partition and the graph build use this code in later diffs of the stack. ___ Differential Revision: D123088771 fbshipit-source-id: 065e95c53321e1d74d377a5c8cd972bdc9cb024b |
||
|
Alibek Zhakubayev
|
7a057952fd |
HashPrune reservoir and sketch kernel (#5708)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5708 We add the HashPrune reservoir and its sketch kernel, the first building block of a PiPNN graph index (Rubel et al., KDD 2026, arXiv:2602.21247). **Motivation** PiPNN builds a navigable graph without beam searches during construction: it partitions the data into overlapping leaves, picks candidate edges inside each leaf, and keeps a bounded set of candidates per point with HashPrune. This diff adds only that per-point candidate set and the hash it buckets by. Its result must not depend on the order of offers, so that the build in a later diff can process leaves in parallel and stay deterministic. The rest of the stack adds, in order, the numeric kernels, the partition into leaves, the graph build, `IndexPiPNN` with search, and serialization with `index_factory` support. **Implementation** - `distance_key`: an order-preserving 16-bit key built from the scalar bf16 encoding. NaN maps to +inf and -0 to +0 on the bit pattern, which also holds under `-ffast-math`; the sign-magnitude to unsigned mapping makes signed inner-product distances compare correctly. - `ReservoirRef::offer`: the HashPrune insert over 8-byte slots kept sorted by hash. Bucket replacement, eviction and the farthest-slot scan all use the strict `(key, id)` order, so the final reservoir is a function of the set of offers, whatever their order. A full reservoir rejects an offer that is not below its cached maximum before the binary search, which is expected to be the common case at steady state. - `Hyperplanes` and `Hyperplanes::sketch`: Gaussian hyperplanes stored transposed and zero-padded, and a fixed-order `FAISS_NOINLINE` sketch kernel, so sketches computed on the fly are bitwise identical within one build. `residual_hash` derives the bucket bits. - `FAISS_NOINLINE` in `impl/platform_macros.h`. - No caller yet. The graph build uses this code in a later diff of the stack. Reviewed By: mnorris11 Differential Revision: D123079760 fbshipit-source-id: f4278cf1d960b1756cdd54b6fbb14dec6eca3b3c |
||
|
Michael Norris
|
83ae8b0908 |
Move the RVV distance kernels into free-standing headers (#5697)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5697 This diff moves the leaf RISC-V Vector (RVV) distance kernels into three free-standing headers. A caller that cannot include the full Faiss headers can then run the same arithmetic. The diff also makes `utils/simd_impl/distances_rvv.cpp` compile with clang, and it removes a duplicate gather loop. The CPU paths do not change behavior. ## The headers | header | caller | | --- | --- | | `impl/scalar_quantizer/sq8_rvv_kernel.h` | `sq-rvv.cpp` | | `impl/pq_code_distance/pq_rvv_kernel.h` | `pq_code_distance/rvv.cpp` | | `utils/simd_impl/distances_rvv_kernel.h` | `utils/simd_impl/distances_rvv.cpp` | Each header holds only the innermost distance loops. It needs no exceptions, no heap and no threads, so a freestanding RISC-V target can compile it. `impl/scalar_quantizer/sq8_coefficients.h` holds the QT_8bit and QT_4bit scale and offset, which any architecture can use. The scalar quantizer header also holds block, two-block, strided and 4-bit forms of the loop, for callers that store codes transposed in blocks of 64. ## The clang fix Clang gave 14 instances of `error: builtin functions must be directly called` for `utils/simd_impl/distances_rvv.cpp`, because `rvv_reduce` takes the reduction intrinsic as a template argument. `FAISS_RVV_REDUCE_OP` now wraps the intrinsic in a lambda. GCC still accepts the code. ## The duplicate `pq_code_distance_8bit_single_impl` held its own copy of the gather loop. It now calls `pq_rvv_kernel::distance_8bit`. The four-code entry point keeps its own loop, because it computes the row term once for four codes. `xplat.bzl` and `CMakeLists.txt` register the four new headers. Differential Revision: D122938441 fbshipit-source-id: 88e59f674a82d25a60abc18ab330904d6716566b |
||
|
Alibek Zhakubayev
|
d380b7d96c |
Fix IndexFlatCodes::reset on mmap-loaded codes (#5707)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5707 `IndexFlatCodes::reset()` called `codes.clear()`. When the index was read with `IO_FLAG_MMAP_IFC` (or through a zero-copy reader), `codes` is a non-owning view, and `MaybeOwnedVector::clear()` asserts `is_owned`, so `reset()` aborted the process. This hits `IndexFlat`, `IndexScalarQuantizer` and every index that resets a flat-codes storage, e.g. `IndexHNSWFlat` and `IndexNSGFlat`. `reset()` now keeps `clear()` for owned codes (capacity is kept, as before) and replaces a view with an empty owned vector. The index can then be refilled with `add()`. ___ Differential Revision: D123073895 fbshipit-source-id: 892e07eaa81d0176e34769714292c036c772a4d7 |
||
|
Jaeyoon Jeong
|
b0074a3fa4 |
Add fp16 support to SuperKMeans (#5692)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5692 Accept packed IEEE fp16 rows through `SuperKMeans::train_ex`, widening bounded blocks directly into the existing fp32 rotated workspace. Route raw Float16 IVF training through SuperKMeans while preserving codec, mode, and metric boundaries, and expose the typed input through the low-level Python wrapper. Add direct, subsampling, multi-block, spherical, validation, IVF, codec-boundary, metric-boundary, and Python parity coverage. Reviewed By: mnorris11 Differential Revision: D122781442 fbshipit-source-id: fa31ef48ed32b6c7fedfad2dffe5dcef794cb618 |
||
|
Jaeyoon Jeong
|
1dab0c1cdf |
Quarantine unstable cuVS Python GPU tests (#5699)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5699 The cuVS GitHub Actions job can hang for five to six hours in nondeterministic GpuIndexBinaryCagra Python searches. Repeated remote-GPU runs also found the inner-product IndexIDMap CAGRA case hanging during process teardown. Skip the unstable Python search cases while retaining the dedicated binary-CAGRA C++ tests and the neighboring Python CAGRA coverage. ___ landed-with-radar-review Differential Revision: D123143371 fbshipit-source-id: 279678123d756ce122bc984c605cf7d4acf25e9a |
||
|
Jaeyoon Jeong
|
e7c44eb000 |
Add AVX-512 fp16 conversion kernels (#5694)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5694 Add exact AVX-512 widening and fp32 accumulation specializations for packed fp16 data. Reuse the existing AVX-512 SIMD translation unit, expand runtime dispatch to the AVX-512 level, and cover conversion tails, large blocks, weighted and unweighted centroid updates, and architecture fallbacks. Reviewed By: mnorris11 Differential Revision: D122781509 fbshipit-source-id: 67cbc4546149f069706e80dd25cae25d3588b0cc |
||
|
Jaeyoon Jeong
|
ae4466d57e |
Avoid widening fp16 data for k-means++ initialization (#5693)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5693 Run `KMEANS_PLUS_PLUS` and `AFK_MC2` initialization directly from packed fp16 rows. Decode bounded per-thread row blocks, dispatch conversion once, and preserve the existing fp32 distance, RNG, and accumulation behavior without an `nx * d` fp32 copy. Reviewed By: mnorris11 Differential Revision: D122781508 fbshipit-source-id: d3ed17ff9903fd08eb0d1221a6c562c46af82ff8 |
||
|
Michael Norris
|
ea9151d71b |
RaBitQ: broadcast one sign word per 32 dims in the AVX2 RBQ9 kernel (#5696)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5696 `compute_inner_product<SIMDLevel::AVX2>` scores 9-bit RaBitQ codes (`ex_bits == 8`) in groups of 8 dimensions. Before this change, each group loaded one sign byte and broadcast it. The broadcast uses the shuffle port, which limits the loop. This change makes these changes to the loop: - The loop loads one 32-bit sign word and broadcasts it once for each 32 dimensions. - Each group of 8 dimensions ANDs the word with `positions << 8k` and compares the result with `cmpeq`. A `cmpgt` against zero is not correct here, because bit 31 of the shifted positions is a sign bit. - The loop uses two accumulators. - An 8-dimension loop handles the remaining full groups. `ip_scalar` handles the tail, as before. The two accumulators change the float summation order. The benchmark checksums agree to 6 significant digits. AI explanation of why: ``` What limits a loop like this A loop runs no faster than its tightest limit. This loop has three possible limits: 1. Micro-op count. The core issues about 4 micro-ops per cycle. 2. Port 5, the shuffle port. Broadcasts and byte-to-int expansions can run only there. 3. The FMA chain. With one accumulator, each FMA must wait for the previous one. Each FMA takes 4 cycles, so one group of 8 dims takes at least 4 cycles. Measured values, per group of 8 dims (d=768, codes in L2) ┌────────────────────────────────────────┬────────┬──────────────┬─────────────┬─────────────────┐ │ loop │ cycles │ instructions │ port 5 µops │ FMA chain floor │ ├────────────────────────────────────────┼────────┼──────────────┼─────────────┼─────────────────┤ │ V1 (contributor), 1 accumulator │ 5.53 │ 18.4 │ 4.12 │ 4.0 │ ├────────────────────────────────────────┼────────┼──────────────┼─────────────┼─────────────────┤ │ V1, 2 accumulators │ 5.63 │ 15.4 │ 4.78 │ 2.0 │ ├────────────────────────────────────────┼────────┼──────────────┼─────────────┼─────────────────┤ │ sign word, 1 accumulator │ 4.43 │ 10.4 │ 2.95 │ 4.0 │ ├────────────────────────────────────────┼────────┼──────────────┼─────────────┼─────────────────┤ │ sign word, 2 accumulators (D122893433) │ 3.77 │ 10.5 │ 2.99 │ 2.0 │ └────────────────────────────────────────┴────────┴──────────────┴─────────────┴─────────────────┘ With 4,096 codes, which do not fit in L2, the values are 6.20, 5.96, 5.15 and 4.66 cycles. The new loop is 1.33x faster than V1 there, which agrees with the faiss benchmark (1.33x–1.36x). Step 1: the sign-word broadcast removes micro-ops In V1, each group of 8 dims gets its sign byte in four instructions: movzx eax, BYTE PTR [sign + i/8] ; load one byte vmovd xmm1, eax ; copy it into a vector register (port 5) vpbroadcastd ymm1, xmm1 ; copy it into all 8 lanes (port 5) The loop also does its index and loop-control work (shr, mov, add, cmp, jae) once per 8 dims. In total, each group needs 18 instructions. The new loop loads a 32-bit sign word once per 32 dims. The compiler turns the memcpy plus _mm256_set1_epi32 into one instruction: vpbroadcastd ymm0, DWORD PTR [sign + i/8] A broadcast that reads directly from memory runs on the load port only. It does not use port 5. Each of the four groups then needs only vpand and vpcmpeqd against its shifted position constant. The compiler loads these constants before the loop, so they cost nothing per pass. The loop-control work also runs once per 32 dims, not once per 8. Result: instructions per group go from 18.4 to 10.4, and port 5 micro-ops from 4.12 to 2.95. Cycles go from 5.53 to 4.43, which is 1.25x. Step 2: the second accumulator shortens the FMA chain After step 1, the micro-op limit is about 2.6 cycles and the port 5 limit is about 3.0 cycles. But one accumulator still forces 4 cycles per group. The measured 4.43 cycles is close to that floor, so the FMA chain is now the limit. With two accumulators, two chains run at the same time, and the floor falls to 2.0 cycles. The next limit is port 5 at about 3 cycles. Cycles go from 4.43 to 3.77, which is 1.18x. Why the second accumulator alone did not help V1 V1 needs 5.53 cycles because of its micro-op count and port 5, not because of the FMA chain: 5.53 is well above the 4-cycle floor. A second accumulator removes a limit that V1 does not reach. My earlier standalone test found the same result. Thus each change helps only together with the other: - The broadcast change brings the loop down to the FMA floor. - The second accumulator then lowers the floor. The cmpeq change cmpeq is not faster than cmpgt; both cost the same. It is necessary for correctness: the group that tests bits 24–31 uses 128 << 24 = 0x80000000. As a signed integer this value is negative, so cmpgt(x, 0) would give the wrong result for that lane. ``` Reviewed By: junjieqi Differential Revision: D122893433 fbshipit-source-id: e6c42d33e138614589e8f80c059df3652a7ddfcd |
||
|
ChenLiqing
|
ea29bac75d |
RaBitQ: add batch-four estimates and 9-bit SIMD scoring (#5647)
Summary: Extend RaBitQ's distance-computation API with four independent one-bit estimates and add optimized kernels for standard RaBitQ codes. - Add `RaBitQDistanceComputer::distance_to_code_1bit_batch_4`, with a default implementation that delegates to four single-code evaluations. - For non-centered, four-bit query quantization, reuse query bit planes across four database codes. The optimized kernel uses the existing `AVX512_VPOPCNT` dispatch level; other SIMD levels and query modes retain fallbacks. - Add AVX2 and AVX-512 full-distance kernels for 9-bit database codes, exploiting byte-aligned extra codes rather than scalar extraction. The scalar tail reads only the required extra bytes. - Add `-mbmi2` to the x86 SIMD compile flags in `xplat.bzl` and `CMakeLists.txt`. The `AVX2` and higher SIMD levels now require CPUID BMI2. The RaBitQ kernels call `_pext_u64` without `__BMI2__` guards. - Use local fixed-size `memcpy` for byte-aligned scalar bit-plane loads. ## API contract and scope Call `set_query()` before evaluating a batch. The four row pointers may be non-contiguous or repeated. Results are returned in input order. The method computes estimates only: it does not refine candidates, update thresholds, or increment search counters. Existing query modes and database precisions remain supported. No changes to HNSW traversal, filtering, graph construction, defaults, or serialized code layout are included. This is an opt-in batch API; existing search call sites are unchanged. ## Tests and benchmark New standalone tests cover batch/single agreement for database bits 1–9, query bits 0–8, both centering modes, L2/IP, available SIMD overrides, repeated/non-contiguous row pointers, query reuse, and unchanged statistics. Independent references check packed multi-bit values and unaligned/tail buffers, including exactly sized RBQ9 extra codes. A round-trip test checks stored codes and distances. `bench_rabitq_batch_estimates` compares four single-code estimates with the batch API at dimensions 128, 768, 960, and 1536. It prepares queries outside timing, shuffles code pointers, warms both paths, alternates measurement order, and prints per-code times and checksums. It is a scorer microbenchmark, not an end-to-end search benchmark. Local validation (GCC 12, Release dynamic-dispatch build, Intel Xeon Platinum 8375C): - Built `faiss_test` and `bench_rabitq_batch_estimates`. - 61 tests passed with `--gtest_filter='TestLowLevelIVF.*:*RaBitQ*:*HNSW*'`, including all five new tests. - 47 individual-process tests passed with `ctest -R 'RaBitQ|HNSW'`. - All five new tests passed with the changed RaBitQ translation units and test file instrumented by ASan/UBSan, including leak detection. Unchanged dependencies were linked from the Release build; this was not a fully instrumented library build. - Checked NONE, AVX2, AVX512 and AVX512_VPOPCNT on the local host. Clang 15 syntax checks passed for the three affected SIMD units, with baseline BMI2 disabled for the AVX2/AVX512 checks. ARM, non-BMI2 hardware, and native SPR execution were not performed locally. A CPU without BMI2 now uses the `NONE` level. - No on-disk format changes; code and distance round-trip checks passed. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5647 Reviewed By: junjieqi Differential Revision: D122390129 Pulled By: mnorris11 fbshipit-source-id: f3f1b1817e3fbcbf7896f3b4cf86eebcbba6f6b2 |
||
|
Evan Haque
|
76c0e01e0f |
Add GPU-accelerated IVFPQ search to the Metal backend (#5449)
Summary: This is a follow-up to https://github.com/facebookresearch/faiss/issues/5288, which added `MetalIndexIVFPQ` with GPU-resident storage while delegating search to the CPU. Adds GPU-accelerated IVFPQ search to the Metal backend, including optimized scanning through `M <= 64`. - Add Metal kernels for 8-bit PQ distance computation, inverted-list scanning, and top-k merging - Support optimized GPU scanning through `M <= 64` - Compute distance contributions only for PQ codes encountered in each list when `d <= 256` - Add a 32-thread cooperative kernel for lists containing at most 128 vectors - Retain the cached precomputed-LUT kernel for suitable `M <= 16` workloads - Stream precomputed terms for larger dimensions without allocating an `M * 256` threadgroup LUT - Support both L2 and inner product metrics - Add exact segmented top-k selection for inverted lists of any length - Add grouped multi-round merging without a fixed `nprobe * k` candidate limit - Compact invalid per-list padding before merging when lists contain fewer than `k` results - Reuse dynamically sized Metal scratch buffers across searches - Retain the legacy per-probe LUT path with optional FP16 lookup tables - Fall back to CPU search for unsupported configurations, search parameters, or Metal failures ## Changes - **Modified:** `MetalDistance.metal` - on demand PQ scans, large-M precomputed scan, short-list specialization, segmented top-k, and compacting grouped merge - **Modified:** `MetalDistance.h/.mm` - IVFPQ search orchestration and support for `M <= 64` - **Modified:** `MetalKernels.h/.mm` - dispatch for cached, on-demand, short-list, and large-M scan kernels - **Modified:** `MetalIndexIVFPQ.h/.mm` - GPU scan selection, reusable buffers, centroid uploads, precomputed terms, and CPU fallback - **Modified:** `MetalIndex.h` - add the `useFloat16` LUT configuration - **Modified:** `TestMetalIndexIVFPQ.mm` - direct-GPU scan validation and search-parameter fallback coverage ## Differences from CUDA IVFPQ **Training:** `MetalIndexIVFPQ::train` delegates training to its CPU index, as introduced in https://github.com/facebookresearch/faiss/issues/5288. CUDA can train the coarse and product quantizers on GPU. Training is a one-time cost. **Add path:** Coarse assignment, residual computation, and PQ encoding remain on the CPU. The encoded PQ codes are stored in GPU-resident Metal buffers. CUDA performs these operations on GPU. **Coarse quantization:** The coarse quantizer search runs on the CPU. The selected lists and coarse distances are passed to the Metal scan. **Distance computation:** For `d <= 256`, the preferred Metal path evaluates only the PQ codes encountered while scanning a list. This avoids constructing or loading all 256 lookup entries for every subquantizer, which is especially beneficial for short IVF lists. For other supported dimensions, Metal uses the CPU IVFPQ precomputed-table decomposition. The query-independent centroid/PQ term is computed once per trained index and the query term once per batch. **Threadgroup memory:** The existing cached lookup-table kernel remains available for suitable `M <= 16` workloads. Larger `M` values do not expand its `M * 256` threadgroup LUT, which would exceed Metal threadgroup-memory limits. Instead, they use the on-demand or streamed-precomputed scan paths. **List scanning:** Short lists use a 32-thread cooperative kernel with approximately 2 KiB of threadgroup scratch. Longer lists use segmented selection to maintain an exact running top-k. **Top-k merge:** Per-list results are merged in groups over multiple rounds. Invalid padding is compacted when lists contain fewer than `k` results. **Fallback:** The optimized scan supports `M <= 64`, `d / M <= 256`, and `k <= 512`. Unsupported configurations fall back to the legacy Metal path or CPU search. Search options that the GPU path cannot preserve, including selectors, scan budgets, and polysemous filtering, are forwarded to the CPU with their original parameters. ## Build and test ```bash cmake -B build \ -DFAISS_ENABLE_GPU=OFF \ -DFAISS_ENABLE_METAL=ON \ -DBUILD_TESTING=ON \ -DCMAKE_BUILD_TYPE=Release \ -DCMAKE_PREFIX_PATH="$(brew --prefix libomp)" \ . cmake --build build \ --target faiss faiss_metal TestMetalIndexIVFPQ \ -j$(sysctl -n hw.logicalcpu) cd build && ctest -R TestMetalIndexIVFPQ --output-on-failure ``` All six IVFPQ tests pass. Direct-GPU regression coverage exercises 800 combinations across `M=8,16,17,32,48,64`, L2 and inner product, `k` through 512, short and long lists, both merge modes, and 64-bit IDs. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5449 Reviewed By: junjieqi Differential Revision: D113864779 Pulled By: mnorris11 fbshipit-source-id: 741c12b2b014ef28a82569c6b0344352351a7325 |
||
|
lyang24
|
0db2f30886 |
rabitq neon kernels (#5532)
Summary: This diff adds native ARM NEON kernels for the RaBitQ bitwise popcount operations and for the multi-bit inner product. The kernels replace the scalar fallbacks on ARM. They handle every supported bit width and every unaligned dimension. - `tests/test_rabitq_simd_neon.cpp` holds the correctness test, and `tests/BUCK` holds its `cpp_unittest` target. The target carries `target_compatible_with` on `ovr_config//cpu:arm64`, which mirrors the x86_64 gate on `test_rabitq_simd`. - `tests/test_rabitq_simd_util.h` holds the shared `kDims` list and the shared `random_bytes` helper. `test_rabitq_simd.cpp` and `test_rabitq_simd_dd.cpp` now use them too. - The three kernels that index a fixed array of eight accumulators assert `qb <= kMaxQueryBits`. `RaBitQuantizer::set_query` caps `qb` at 8, but the kernels are public templates and carry no other bound. The scalar kernel and the AVX-512 kernel need no such assertion, because they shift inside the loop and hold one accumulator. The multi-bit test compares with a relative tolerance of `2e-5`. The NEON kernel accumulates in eight lanes, so it does not reproduce the scalar sum bit for bit. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5532 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`. The host holds Neoverse V2 cores with ASIMDDP, so `test_rabitq_simd_neon` runs its kernels natively rather than skipping. Reviewed By: alibeklfc Differential Revision: D121846717 Pulled By: mnorris11 fbshipit-source-id: de079613a52ced326045830fb799dfc9b169fe2e |
||
|
lyang24
|
6c51305e64 |
Avoid double-advancing HNSW visited tables (#5596)
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 |
||
|
lyang24
|
76978eee4a |
Fix selector handling for IVF iterator scans (#5592)
Summary: Iterator-backed IVF scans ignored the configured `IDSelector`, and array-backed scans applied it. An iterator-backed scan therefore returned IDs that the selector excludes. `InvertedListScanner::iterate_codes` and `InvertedListScanner::iterate_codes_range` now test `sel` for every entry. `search_preassigned` also keeps the selector for an iterable list. The function clears `sel` when the selector is an `IDSelectorRange` that sets `assume_sorted`, because an array-backed list bounds a sorted section instead of testing every entry. An iterable list holds no contiguous section to bound, so it keeps the selector and takes the generic path. `range_search` holds no sorted-range shortcut and needs no equivalent change. The test loops over both values of `assume_sorted`, and it checks the KNN search and the range search. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5592 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: D121846696 Pulled By: mnorris11 fbshipit-source-id: 09c8a3673fea6cc53f3370f05f3b6d399dfb4548 |
||
|
lyang24
|
41023120df |
Defer IVF list scan setup until needed (#5595)
Summary: The IVF list scan prepared state that an early return then discarded. This diff moves `scanner->set_list`, the `ScopedCodes` fetch and the `ScopedIds` allocation after every check that can return first. A list that an `IDSelectorRange` excludes no longer builds a lookup table and no longer fetches its codes. The diff also folds the `jmin` offset into the initial codes pointer, and it replaces `std::unique_ptr<ScopedIds>` with `std::optional<ScopedIds>`. The diff also fixes a null-pointer dereference. `search_preassigned` cleared `sel` for a sorted `IDSelectorRange` before it tested `!(sel && store_pairs)`. That combination then reached `IDSelectorRange::find_sorted_ids_bounds`, which reads `ids[0]`. The `ids` pointer is null when the caller sets `store_pairs`. The test now runs before the code clears `sel`, so the combination throws. `IVF.sorted_range_selector_rejects_store_pairs` covers it. **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. `IndexIVFPQ`, `d=64`, `nlist=1024`, 100k vectors, `nprobe=1024`, sorted `IDSelectorRange`. | ids that pass the range | before | after | ratio | |---|---|---|---| | 1% | 836 us | 587 us | **1.43x** | | 10% | 894 us | 926 us | 0.97x | The gain grows with the number of lists that the range excludes. At 10% the saving sits inside the noise. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5595 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: D121846650 Pulled By: mnorris11 fbshipit-source-id: aa3d1d3e6f903ef9e57be5c3dd824a5b1a090228 |
||
|
Jaeyoon Jeong
|
38460ee969 |
Fix Faiss fp16 parity tests across architectures (#5695)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5695 Correct GPU tests to decode the exact packed fp16 values passed to `search_ex`; the generic software converter and legacy `roundToHalf` disagree on half-way ties. Keep labels exact while comparing CPU distances with the normal scaled `1e-5` BLAS/SIMD tolerance. ___ Differential Revision: D122785161 fbshipit-source-id: 057ded12bdc018add4bef39e514217b83b59c2cb |
||
|
Jaeyoon Jeong
|
430a41ee4c |
Native fp16 k-means training for Faiss IVF (#5671)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5671 Train IVF coarse quantizers from packed fp16 (IEEE binary16) data without an fp32 copy of the training set, and let the k-means assignment step consume fp16 natively. **k-means: `Clustering::train_ex(n, x, NumericType, index, weights)`** Float16 runs k-means directly on the fp16 rows, without a codec: - NaN/Inf check on the fp16 bit patterns - subsampling and random initialization copy fp16 rows - the centroid update accumulates fp16 rows into the fp32 centroids with F16C/NEON (`compute_centroids_fp16`) - the assignment step passes blocks of at most `decode_block_size` fp16 rows to `Index::search_ex(Float16)` Only k-means++ / AFK-MC2 initialization still widens the (subsampled) training set. **Assignment: `Index::search_ex(Float16)`** - Default for every index: widen bounded blocks and call `search()`. - `IndexFlat` (L2 / IP): the BLAS kernels take fp16 queries (`knn_L2sqr_fp16`, `knn_inner_product_fp16`). Queries are widened inside the kernel in chunks of at most 16 MiB, each reused for all database tiles; results are bit-identical to the fp32 path on the rounded queries. The AVX2 / AVX512 / SVE top-1 kernels share one templated body. Selectors, small inputs, d <= 32 and database-parallel searches widen chunks and use the fp32 path. `IndexFlat1D` and `IndexFlatPanorama` keep their own search. - GPU: every `GpuIndex` accepts Float16 (queries are copied to the device as fp16 and widened there); `GpuIndexFlat` with `useFloat16` storage searches fp16 queries directly with the fp16 GEMM. **IVF** - `IndexIVF::train_ex(Float16)` and `Level1Quantizer::train_q1_ex` use the native path; only the `train_encoder_num_vectors()` rows sampled for the encoder are widened. `IndexIVFFlat` trains only the coarse quantizer; `IndexIVFFlatDedup` rejects Float16. - `train_encoded` (IVF and Clustering) remains the generic codec path, e.g. for decode-time normalization. - `faiss::fp16_to_fp32` (faiss/utils/utils.h) is the shared bulk widening helper. **Performance** (opt build, AMD Genoa: F16C conversion only, no fp16 arithmetic) - top-1 knn, d=256, 65536 queries x 1024 centroids: fp32 22.2 ms, fp16 25.3 ms - k-means, 1024 centroids, 10 iterations: fp32 270 ms, fp16 319 ms, identical centroids On CPUs without fp16 arithmetic the GEMM still runs in fp32 on widened tiles, so fp16 is not faster than fp32 there. The gains are memory (fp16 data plus a bounded fp32 tile instead of a full fp32 copy) and a single hook (`search_ex`) for fp16-capable backends; GPU `useFloat16` already runs the fp16 GEMM directly. Reviewed By: mnorris11 Differential Revision: D121848262 fbshipit-source-id: 1400d3eeb7c713359895923dcb86c544570cba69 |
||
|
Junjie Qi
|
88a28bcd80 |
Faiss OSS nightly autofix (#5686)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5686 Automated fix for the Faiss OSS nightly build. ___ Differential Revision: D121930308 fbshipit-source-id: 357958ce1d0b70e175ac3f7d381ec588575809da |
||
|
|
6c8378e4f1 |
Add RVV implementation for decode_bf16_simd (#5641)
Summary: Add a RISC-V Vector (RVV) implementation to `decode_bf16_simd()`. The RVV path preserves the existing bit-level conversion semantics: 1. load BF16 values as unsigned 16-bit integers; 2. zero-extend them to unsigned 32-bit integers; 3. shift left by 16 bits; 4. reinterpret the resulting bits as FP32. Inputs shorter than 16 elements retain the scalar path to avoid short-vector overhead. Larger inputs use fixed-VL RVV chunks followed by a runtime-VL tail. ## Validation Tested on native RISC-V hardware with GCC 15.3.0 and `-march=rv64gcv -mabi=lp64d`, based on Faiss commit `b5a14632a6f2bfdc824c86d683b9d6e9205c2604`. Correctness: - exhaustively tested all 65,536 BF16 bit patterns; - tested 31 input sizes, including zero, short inputs, vector boundaries, tails, and large arrays; - checked guard elements for output overwrites; - zero correctness failures. Representative microbenchmark speedups over the scalar implementation: | Elements | Speedup | |---:|---:| | 7 | 1.01x | | 16 | 1.58x | | 31 | 2.43x | | 64 | 3.46x | | 128 | 3.88x | | 1024 | 4.38x | | 4096 | 4.37x | | 65536 | 4.30x | ## Scope This change only modifies `faiss/utils/bf16.h`. It is independent of the active ScalarQuantizer RVV changes in PRs https://github.com/facebookresearch/faiss/issues/5535 and https://github.com/facebookresearch/faiss/issues/5539. ## Notes - The `n == 1` fast path and the `n < 16` scalar loop exist because at VLEN=128 an `e16m1` chunk covers only 8 elements, and for very short inputs the `vsetvl`/load/extend/store sequence costs more than the equivalent scalar work. The measured crossover is at 16 elements. - The bulk loop uses a hoisted `vsetvlmax_e16m1()` so `vsetvl` is not re-executed per iteration; only the final partial chunk calls `vsetvl` again. - `vuint16m1` → `vuint32m2` uses `vzext.vf2` (LMUL widening), so the 32-bit shift and the FP32 store run at `m2`. This keeps register pressure low while doubling the elements per chunk. - No rounding or saturation is involved: BF16 → FP32 is an exact bit widening, so the vector path is bit-identical to the scalar path for every input, including NaN payloads and subnormals. - The guard is `#elif defined(__riscv_vector)` inside the existing arch dispatch, so the AVX2/AVX512 paths are untouched and a build without RVV falls through to the scalar loop unchanged. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5641 Reviewed By: alibeklfc Differential Revision: D121445956 Pulled By: mnorris11 fbshipit-source-id: 4b4ec0bad6473030849ae9275cbdad0bc3e087ee Co-authored-by: ihb2032 <[email protected]> Co-authored-by: lyd1992 <[email protected]> Co-authored-by: Yuansheng <[email protected]> |
||
|
Michael Norris
|
fdb9535c15 |
Make search stats collection configurable (#5670)
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 |
||
|
Zhang Jinhan
|
e24a371a70 |
feat(rvv): add vector arithmetic kernels (#5655)
Summary: On RISC-V, `fvec_add` and `fvec_sub` dispatch through `with_simd_level_256bit`. The level mask of that dispatcher (`AVAILABLE_SIMD_LEVELS_AVX2_NEON`) holds no `RISCV_RVV` bit. RVV hosts therefore use the scalar NONE implementation. This PR adds native RVV kernels for the two functions and fixes the dispatch. The kernels follow the vector-length-agnostic approach of the RVV kernels in the tree. The kernels use `__riscv_vsetvl` (m8) and adapt to any VLEN at runtime. The kernels assume no fixed vector width. ## Changes - Add RVV kernels in `faiss/utils/simd_impl/distances_rvv.cpp` for: - `fvec_add` (vector plus vector, and vector plus scalar) - `fvec_sub` - Add the `AVAILABLE_SIMD_LEVELS_BASE_NO_AVX512` mask in `faiss/impl/simd_dispatch.h`. - The mask holds NONE, AVX2, ARM_NEON, and RISCV_RVV. - The mask holds no AVX512 bit, so AVX512 machines keep the AVX2 path. - Route the three dispatchers (`fvec_sub`, `fvec_add`, scalar `fvec_add`) in `faiss/utils/distances_dispatch.h` through the new mask. - Stable already provides the `compute_PQ_dis_tables_dsub2` RVV kernel and the `ProductQuantizer` RISC-V path, so this PR does not change them. - This PR changes no behavior on other platforms. ## Performance The benchmark ran on the original patch. The original patch also held the `compute_PQ_dis_tables_dsub2` kernel. Measured on SG2044 (64-core RISC-V, RVV 1.0), Faiss C++ benchmark suite, rcq-search case: | Metric | Baseline | Patched | Change | |---|---|---|---| | instructions | 7.25 T | 6.87 T | -5.2% | | cycles | 4.60 T | 4.30 T | -6.5% | | wall time | 238.1 s | 223.6 s | -6.1% | | branches | 334.6 G | 305.0 G | -8.8% | The `fvec_add` hotspot in the perf record drops from 1.06% (scalar NONE) to 0.18% (RVV) of samples. ## Correctness - `sq-accuracy` reconstruction errors match the baseline on all 9 quantizer types. - `ndiff_for_idempotence` is 0. - The correctness run used the original patch. ### Co-authors - ihb2032 <[email protected]> - lyd1992 <[email protected]> - Yuansheng <[email protected]> Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5655 Test Plan: `buck2 build fbcode//faiss:faiss` passes. `buck2 test` passes on the distance tests `test_distances_dispatch` and `test_distances_simd`: 9 pass, 0 fail, 8 skip. The skips occur because the host provides one SIMD level. `buck2 test` passes on the PQ tests `test_pq_encoding`, `test_pq_code_distance`, `test_ivfpq_indexing`, and `test_disable_pq_sdc_tables`: 17 pass, 0 fail. Buck does not compile `faiss/utils/simd_impl/distances_rvv.cpp`. The host has no RISC-V toolchain. The new kernels still await review on RVV hardware. Reviewed By: alibeklfc Differential Revision: D121445525 Pulled By: mnorris11 fbshipit-source-id: ae3c1685e319bbb9523d87a3cbce8b1fd5310ce3 |
||
|
Michael Norris
|
7f6bf10b1c |
Halve IndexSQFastScan rerank memory with a split-nibble layout (#5662)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5662 `IndexIVFSQFastScan` kept whole original codes in a parallel inverted list, so an 8-bit quantizer cost 12 bits per dimension against 8 for plain SQ8. It now keeps only the bits the scan does not read, which is the same split the flat index uses in the diff below. ## The split is bit-width generic An 8-bit code keeps 4 leftover bits. A 6-bit code keeps 2. `sq_fastscan_utils.h` packs the remainder with `BitstringWriter`, which lays bits out exactly as `Codec6bit` and `Codec8bit` do. The LUT reconstruction collapses to one formula: `step = 2^(bits-4)`, `offset = step / 2`, `scale = 2^bits - 1`. At 4 bits this reduces to the native `(v + 0.5) / 15`, so the native and split paths no longer need separate constants. This also corrects a small bias, because the 8-bit case previously used an offset of 7.5 where the true band midpoint is 8.0. ## `IndexIVFSQFastScan` splits as well The IVF form kept whole codes in a parallel inverted list. It now keeps only the leftover bits. ## Measured results, flat index, 200k vectors | index | before | after | | --- | --- | --- | | `SQ8fs` | 12 bits/dim | **8.00 bits/dim** | | `SQ6fs` | 10 bits/dim | **6.00 bits/dim** | The IVF form reaches 1.37x `SQ8` at d=64 and 1.10x at d=512, against 1.79x before. The remainder is the ids duplicated into the parallel list and the block padding. Both are per-vector, so the ratio falls as `d` grows. Recall does not drop. The split reaches 0.914 to 0.932 for `SQ6fs` and 0.969 to 0.980 for `SQ8fs` at `rerank_factor=4`, measured against exact neighbours restricted to the admitted set. Also fixes a double-append in `add()`. `IndexFastScan::add` blocks adds over 65536 and calls `add()` virtually. The override therefore re-enters once per chunk, and every side-table entry was written twice for a large index. ## Serialization The `ISfs` payload now carries the leftover bits instead of whole original codes. The fourcc does not change, because `ISfs` has not been released with rerank state and no stored index is affected. Reviewed By: junjieqi Differential Revision: D121092769 fbshipit-source-id: d6e8a4f541ce73057eba86215a83a0a80f7e106d |
||
|
Michael Norris
|
94a4331fee |
Add reranked types to IndexSQFastScan and fix flat RaBitQ filtering (#5661)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5661 Two gaps in the flat fast-scan indexes, both found while benchmarking IDSelector filtering. `IndexSQFastScan` accepted only the native 4-bit quantizers. It now accepts the reranked types as well, the same set `IndexIVFSQFastScan` handles: QT_6bit, QT_8bit, QT_8bit_uniform, QT_8bit_direct and QT_8bit_direct_signed. Each code is SPLIT: the SIMD scan reads the top 4 bits, and `lo_codes` keeps the rest for rerank. The total is the quantizer's own width, so `SQ8fs` holds 8 bits per dimension, the same as plain `SQ8`. A flat index needs no direct map for this, unlike the IVF form, because the position is the id. `SQ8fs` and `SQ6fs` now resolve in `index_factory`. `IndexRaBitQFastScan` forwarded an `IDSelector` through every layer but its kernel never applied it, so a filtered search returned ids outside the admitted set. `RaBitQHeapHandler::handle` now tests the selector per code, after the SIMD block, which is where the PQ and SQ handlers test theirs. The entry point no longer refuses a parameter object. The type predicates and the nibble packing move to `impl/sq_fastscan_utils.h`. The flat and IVF classes then cannot disagree about which quantizers rerank, or about how a nibble is laid out. The `ISfs` payload gains the rerank factor and the original codes. Both are written for every quantizer, and the codes are empty for a native 4-bit index. `ISfs` has not been released, so no stored index is affected. Reviewed By: junjieqi Differential Revision: D121036639 fbshipit-source-id: 40e51fc348a483cf5da947fa7db56ff10f1af773 |
||
|
Michael Norris
|
dcf8ebb346 |
Support IDSelector in flat fast-scan search (#5660)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5660 `IndexFastScan::search` rejected every `SearchParameters` object, so a flat fast-scan index could not take an `IDSelector` at all. `IndexSQFastScan` avoided this by unpacking all `ntotal` codes into a fresh buffer on every call, then running the generic scanner. That allocates and rewrites 12.8 MB per query at 200k vectors and d=128. The kernel already supports a selector. `make_fast_scan_knn_scanner` takes an `IDSelector*`, and the result handlers test it after computing a 32-code SIMD block. The flat path passed `nullptr` in that slot while the IVF path passed the real selector. This forwards it instead, and deletes the unpack fallback. `adjust_id` returns `j0 + 32 * b + j` and applies `id_map` when one is set, so the id the selector tests is correct for the flat layout with no change. Two paths still refuse a selector, both deliberately: - `implem` 2, 3 and 4 have no scanner and cannot apply one. The default `implem` of 0 never selects them. - `IndexRaBitQFastScan` keeps its refusal here. The next diff adds the selector test to its kernel and removes the refusal. Reviewed By: junjieqi Differential Revision: D121036637 fbshipit-source-id: d199debb81244275b96a540bdfb8d8dd5fc31c18 |
||
|
Michael Norris
|
ec94295adc |
Bound the fast scan LUT scale by the accumulated sum (#5658)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5658 A fast scan kernel sums `M` uint8 table entries into a uint16 that can wrap around to 0. The scale that quantizes the table must therefore bound the whole sum that gets accumulated, not only one entry. Seven call sites each held their own copy of that rule. Only four applied it. This adds `quantize_lut::fastscan_lut_scale` and routes all seven through it. The bound also reserves a margin for `round_tab`, which rounds half up, so `n` terms can gain `n/2` over the unrounded sum. `IndexIVFRaBitQFastScan` also folds its per-probe bias into the bound, because that bias is rounded into the same accumulator. `IndexPQFastScan` only reaches the bound when a sub-vector holds one dimension. A nearest centroid keeps the selected entries near the bottom of each column. `IndexSQFastScan` sets `M = d`, so it fails above about `d = 512`. At `d = 1024` it goes from R@1 0.00 to 1.00. Search speed does not change. The scale is computed once per query, and the inner loop is untouched. An index at `M <= 256` quantizes to the same bytes as before, because the sum term does not bind there. Reviewed By: junjieqi Differential Revision: D120638521 fbshipit-source-id: 27d5dd15f5a60a9c80cec1f63f53ac9c6c51b8ff |
||
|
marcelo-cjl
|
3f08095cee |
fix: release SuperKMeans sample buffer after rotation (#5648)
Summary: - release the temporary subsampled training buffer as soon as rotation has populated `X_tilde` - avoid retaining that buffer during Forgy initialization and the SuperKMeans iteration loop - preserve the existing algorithm and rotation-time peak-memory behavior ## Memory result One build run on Cohere 1M x 768 FP32 with SCANN (`nlist=1024`, `sub_dim=2`, `with_raw_data=false`, 16 threads): - SuperKMeans before this change: 6749.1 MiB average RSS - SuperKMeans with this change: 6425.4 MiB average RSS - reduction: 323.7 MiB (4.8% of total average RSS; 8.5% of build RSS above baseline) The released sample buffer is 768 MiB. The measured reduction is smaller because average RSS is time-weighted over the full build; the buffer is still required during sampling and rotation. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5648 Test Plan: - built the AVX2 CPU `faiss_test` target in Release mode - `faiss_test --gtest_filter='AdSampling.*:PdxLayout.*:BlockL2.*:SuperKMeansAssignIteration.*'` (13 tests passed) - Knowhere vendored integration test for SuperKMeans (3 cases, 44 assertions passed) Closes https://github.com/facebookresearch/faiss/issues/5650 Reviewed By: mnorris11 Differential Revision: D121294074 Pulled By: alibeklfc fbshipit-source-id: c8e6f35f1421907887f9756661912df6ee4c2b87 |
||
|
anthony-zy
|
1768a5a8e9 |
Add RVV SIMD specialization for product quantizer distance-table computation (#5543)
Summary:
Add a RISC-V Vector Extension implementation for the product-quantizer
distance-table computation, and wire it into the SIMD dispatch path. The
kernels are runtime vector-length aware (vsetvl-driven, e32m1) rather than
assuming a fixed vector width.
Changes
- compute_PQ_dis_tables_dsub2<RISCV_RVV> (utils/distances_rvv.cpp): RVV
kernel for both inner-product and L2 dsub=2 distance tables. Centroids are
first split into even/odd dimension planes (c0_all / c1_all) so each
subquantizer's ksub entries load as contiguous vectors; the hot loop
processes two subquantizers per iteration:
IP: r = c0*x0 + c1*x1 (vfmul + vfmacc)
L2: r = (c0-x0)^2 + (c1-x1)^2 (vfsub + vfmul + vfadd)
- Add RVV specializations for the accompanying distance primitives:
fvec_norm_L2sqr, fvec_L2sqr_ny, fvec_L2sqr_ny_transposed and
fvec_inner_products_ny are vectorized (strided vlse32 over ny); the
remaining fvec_* and VectorDistance specializations fall back to
SIMDLevel::NONE.
- compute_distance_tables / compute_inner_prod_tables: route dsub == 2 &&
nbits >= 3 && nbits < 8 through compute_PQ_dis_tables_dsub2 when
COMPILE_SIMD_RISCV_RVV is defined, matching the AVX2 / ARM_NEON fast path.
- compute_PQ_dis_tables_dsub2_dispatch: extend the dispatch mask to include
RISCV_RVV.
### Review fixes
The AI reviewers reported 6 valid defects. This version corrects all of them.
- The RVV `compute_PQ_dis_tables_dsub2` unrolled the subquantizer loop by 2
and had no tail. An odd `M` left the last `ksub` table entries unwritten.
The kernel now writes the last subquantizer in a tail loop.
- `fvec_inner_products_ny<RISCV_RVV>` loaded every chunk from `y + j`. The
base pointer missed the `i * d` offset. Each chunk after the first repeated
the first vectors. The kernel now loads from `y + i * d + j`.
- `fvec_norm_L2sqr<RISCV_RVV>` ran one `vfredusum` per vector chunk. A
`d=768` input at VLEN=128 cost 24 serialized reductions. The function again
keeps a tail-undisturbed accumulator, and it reduces once after the loop.
- The `dsub2` kernels require `ksub % 8 == 0`. The dispatch condition accepted
every `nbits < 8`, so an `nbits` of 1 or 2 made `compute_distance_tables`
throw. The condition now also requires `nbits >= 3`. This defect also
affected the AVX2 and the ARM NEON paths.
- `search_sdc` dropped the per-thread `q_row` pointer precomputation. That
change added `M` multiplications per database vector on every architecture.
This version restores the precomputation.
- The `ny` kernels fixed the chunk width at the VLEN=128 value. They now read
`VLMAX` with `vsetvlmax`. Hardware with a larger VLEN uses the whole vector
register.
The diff also removes 2 unreadable comments from the RVV kernel.
Caveat: the benchmark below ran on the previous version. That version included
the `search_sdc` change that this version reverts.
### Performance (sg2044)
Cmd: 1M 768 <PQ> 32 100 16 1 1000 1 <metric> (search ns/query, lower is better)
| # | CONFIG | M | NPROBE | METRIC | F1(ns) | PQ1(ns) | F2(ns) | PQ2(ns) | Δ_PQ% | Δ_F% |
|----|----------|-----|--------|--------|---------|---------|---------|---------|---------|--------|
| 01 | PQ8x4 | 4 | 8 | L2 | 6656870 | 536988 | 6582134 | 495970 | -7.64% | -1.12% |
| 02 | PQ8x4 | 4 | 8 | IP | 6228497 | 475320 | 6164081 | 481118 | +1.22% | -1.03% |
| 03 | PQ8x8 | 8 | 8 | L2 | 6626171 | 545230 | 6580586 | 500343 | -8.23% | -0.69% |
| 04 | PQ8x8 | 8 | 8 | IP | 6228452 | 519710 | 6165707 | 479864 | -7.67% | -1.01% |
| 05 | PQ8x16 | 16 | 8 | L2 | 6615305 | 697070 | 6582239 | 624059 | -10.47% | -0.50% |
| 06 | PQ8x16 | 16 | 8 | IP | 6227067 | 642949 | 6164572 | 587271 | -8.66% | -1.00% |
| 07 | PQ8x32 | 32 | 8 | L2 | 6624323 | 1185655 | 6581329 | 902298 | -23.90% | -0.65% |
| 08 | PQ8x32 | 32 | 8 | IP | 6239930 | 1155545 | 6164198 | 785403 | -32.03% | -1.21% |
| 09 | PQ8x64 | 64 | 8 | L2 | 6624196 | 2006275 | 6578815 | 1687191 | -15.90% | -0.69% |
| 10 | PQ8x64 | 64 | 8 | IP | 6225719 | 1800678 | 6164767 | 1512760 | -15.99% | -0.98% |
| 11 | PQ8x96 | 96 | 8 | L2 | 6617525 | 3108377 | 6582946 | 2701758 | -13.08% | -0.52% |
| 12 | PQ8x96 | 96 | 8 | IP | 6239711 | 2657958 | 6170006 | 2320803 | -12.68% | -1.12% |
| 13 | PQ8x384 | 384 | 8 | L2 | 6620602 | 14029275| 6583820 | 12318712| -12.19% | -0.56% |
| 14 | PQ8x384 | 384 | 8 | IP | 6228776 | 12089134| 6166143 | 10509785| -13.06% | -1.01% |
| 15 | PQ8x32 | 32 | 4 | L2 | 3321625 | 773663 | 3298874 | 491225 | -36.51% | -0.68% |
| 16 | PQ8x32 | 32 | 16 | L2 |13223858 | 2184906 |13152640 | 1645444 | -24.69% | -0.54% |
| 17 | PQ8x32 | 32 | 32 | L2 |26430233 | 3405062 |26331426 | 3138563 | -7.83% | -0.37% |
| 18 | PQ8x64 | 64 | 4 | L2 | 3320850 | 1191054 | 3298426 | 969309 | -18.62% | -0.68% |
| 19 | PQ8x64 | 64 | 16 | L2 |13207340 | 3944868 |13149902 | 3252654 | -17.55% | -0.43% |
| 20 | PQ8x64 | 64 | 32 | L2 |26467696 | 6725098 |26335327 | 6667493 | -0.86% | -0.50% |
| 21 | PQ8x16 | 16 | 4 | L2 | 3316496 | 427653 | 3304051 | 367407 | -14.09% | -0.38% |
| 22 | PQ8x16 | 16 | 16 | L2 |13203491 | 1198002 |13150061 | 1121421 | -6.39% | -0.40% |
| 23 | PQ8x16 | 16 | 32 | L2 |26438401 | 2199527 |26280149 | 2143973 | -2.53% | -0.60% |
Δ_PQ%: PQ baseline -> RVV; Δ_F%: Flat baseline -> RVV.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5543
Test Plan:
`buck build fbcode//faiss:faiss` passes.
`buck2 test` passes on the PQ and the distance C++ tests:
`test_disable_pq_sdc_tables`, `test_distances_dispatch`, `test_distances_simd`,
`test_ivfpq_codec`, `test_ivfpq_indexing`, `test_pq_encoding` and
`test_pq_code_distance`. The result is 27 pass and 0 fail. The host is aarch64,
so 8 tests skip. Those tests need a second SIMD level to compare against.
This diff adds 2 tests to `faiss/tests/test_product_quantizer.py`:
- `test_dsub2_4bit` covers `dsub=2` with `nbits=4`. `ksub` is 16, so the SIMD
`dsub2` kernel runs.
- `test_dsub2_2bit` covers `dsub=2` with `nbits=2`. `ksub` is 4, so the generic
path must run instead.
I checked the `nbits >= 3` fix with a temporary C++ test on ARM NEON. The test
compares `compute_distance_tables` and `compute_inner_prod_tables` against
`compute_distance_table` and `compute_inner_prod_table`, for `nbits` of 1, 2, 3
and 4. The test fails with a `ksub % 8 == 0` assertion before the fix. The test
passes after the fix. I removed the temporary test before submit.
Limits of the local verification:
- I did not run `faiss/tests/test_product_quantizer.py` on this devserver. The
`fbcode//faiss/python:pyfaiss-py-gen` SWIG step fails on aarch64 with
`Exec format error`. The failure also reproduces without my changes. CI runs
the Python tests on x86.
- I did not compile `utils/simd_impl/distances_rvv.cpp`. This devserver has no
RISC-V toolchain. `xplat.bzl` registers no RVV sources, so Buck and internal
CI do not build that file either. Only the OSS CMake build on rv64 compiles
it. A reviewer with RVV hardware should confirm the 4 RVV kernel fixes.
Reviewed By: juancarpio27
Differential Revision: D117914440
Pulled By: mnorris11
fbshipit-source-id: 3539a116d47f4a96c1051bc10e6440deae8c5302
|
||
|
Yedidya Feldblum
|
b1c1496545 |
migrate from bit-manipulation builtins in fbcode/faiss (#5667)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5667 Replaces `__builtin_ctz` with `std::countr_zero` in `impl/fast_scan/simd_result_handlers.h`'s per-lane result-scanning loops. `utils/popcount.h` and `impl/platform_macros.h` are portability wrappers (their sole purpose is bridging MSVC/GCC-Clang builtins), so they're left out of scope here. ___ Differential Revision: D121529297 fbshipit-source-id: e42b3fb70eacc5fc4d2e2ffe7dfca64662ef2016 |
||
|
|
f323c18d5a |
Add RVV encoding for QT_8bit_direct (#5640)
Summary: RVV `QT_8bit_direct` currently inherits scalar encoding. This adds an RVV encoder using `e32m4`, explicit round-toward-zero float-to-unsigned conversion, and two narrowing operations before storing bytes. The generic encoder becomes overridable so the RVV specialization can provide the implementation. The portable scalar conversion domain is finite inputs in `(-1, 256)`, whose truncated values are representable in `uint8_t`; negative fractions greater than -1 produce zero. The new regression test covers that domain, including signed zero, subnormals, values around integer boundaries, the largest float below 256, short tails, and output guards. This PR is independent of the FP16 and direct-signed-distance changes. ### Performance Measured on a native SG2044 RISC-V host (VLEN=128), GCC 15.1, Release `-O3`, dynamic dispatch (`FAISS_OPT_LEVEL=dd`), `rv64gcv_zvfhmin/lp64d`, one thread pinned to CPU 2. The baseline is official commit `80a16564f86530dbf0bfaf96c2b71feffeb5093f`; the candidate is that same baseline plus only this kernel change. These measurements were not collected on the newer PR base `2ed4c106e9fb9686e7727e5daf8ad6ad1e164109`. The affected scalar-quantizer source files are unchanged between those bases, and the submitted kernel differs from the measured one only in comments/formatting. | Public path | Dimension | Baseline ns/element | Candidate ns/element | Paired speedup | 95% interval | |---|---:|---:|---:|---:|---:| | Direct-u8 encode | 16 | 1.839 | 1.345 | 1.366x | [1.343, 1.379] | | Direct-u8 encode | 32 | 1.839 | 1.061 | 1.750x | [1.690, 1.775] | | Direct-u8 encode | 128 | 1.640 | 0.823 | 1.937x | [1.901, 1.992] | | Direct-u8 encode | 768 | 1.530 | 0.740 | 2.059x | [1.883, 2.105] | Geometric mean of the dimension-specific speedups at d=32/128/768: Direct-u8 encode **1.911x**. There are three consecutive sessions, each with four alternating ABBA/BAAB blocks per dimension/path: **48 paired blocks** for this candidate. A is the baseline and B is the candidate. Each call is calibrated to at least 0.1 s (the shortest formal call in the full campaign was 0.192 s), with three warm-up batches and `n = max(32, floor(32768/d))`. Each block uses the ratio of the two-call geometric mean times. Reported speedup is the median of the three session medians; intervals use 5,000 hierarchical bootstrap resamples, resampling sessions and then blocks within each ABBA/BAAB order stratum. The timing columns are separate medians, so their quotient need not equal the paired speedup. All 48 paired blocks favored this candidate. The timed operation is public `ScalarQuantizer::compute_codes`, using fixed-seed (718) finite input batches. Direct-u8 input values are `float(rng()%16777216)/65536.f`. These results describe public encoding/distance throughput on one non-exclusive host, not end-to-end ANN search speedup. The intervals describe these sessions only, with no multiple-comparison correction; they do not establish portability across machines or vector lengths. ### Validation - Native public encoding oracle: **7,724,670** legal-domain input elements across the five RISC-V rounding modes; zero differing output bytes or write-guard failures. Inputs include negative fractions, signed zeros, subnormals, all byte-value boundaries, and values just below 256. - Original benchmark baseline full C++ suite: **273 passed, 7 skipped, 0 failed**. - Submission version on `2ed4c106e9fb9686e7727e5daf8ad6ad1e164109`: all three independent candidate builds succeeded; this PR's focused C++ suite (`NONE`: 11 passed, 5 skipped, 0 failed; `RISCV_RVV`: 12 passed, 4 skipped, 0 failed) and the public-path oracle above pass on native RISC-V. The newly added RVV regression test is executed and passed in the RVV run, and skipped when RVV is disabled in the NONE run. - All touched C++ files pass clang-format 21.1.8; `git diff --check` clean. ### Notes - Touches three files: `faiss/impl/scalar_quantizer/quantizers.h` (one-line `final` → `override` so the generic encoder can be specialized), `faiss/impl/scalar_quantizer/sq-rvv.cpp` (the RVV encoder), and `tests/test_scalar_quantizer.cpp` (one regression test). - The conversion uses `vfcvt.rtz.xu.f.v` (round toward zero, float to unsigned) rather than a signed conversion. The generic encoder is `code[i] = (uint8_t)x[i]`, which is a C++ float-to-unsigned-integral truncation, so round-toward-zero is the matching mode. Negative fractions greater than -1 truncate to 0 in both paths. - Two narrowing shifts (`vnsrl` by 0) are used to go `u32m4 → u16m2 → u8m1` before the byte store, avoiding a separate saturating narrow instruction. - The kernel is VLEN-agnostic: `e32m4` lanes with `vsetvl`-driven loop bounds. At VLEN=128 this processes 16 elements per iteration. - Quantization is not clamped. Inputs outside `(-1, 256)` are outside the portable domain — the scalar path casts out-of-range floats to `uint8_t`, which is undefined behavior for values outside that range, so no portable contract exists to preserve there. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5640 Reviewed By: trang-nm-nguyen Differential Revision: D121445607 Pulled By: mnorris11 fbshipit-source-id: 16f34cf77aa0cac2fd99ccb245f2ffbc2047d6c4 Co-authored-by: ihb2032 <[email protected]> Co-authored-by: lyd1992 <[email protected]> Co-authored-by: Yuansheng <[email protected]> |
||
|
Lucian Grijincu
|
2496f63f76 |
Avoid search stats contention during concurrent search (#5663)
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 |
||
|
ihb2032
|
5e74b1bdde |
feat: implement RVV optimized scalar quantizer codecs and distance computation (#5535)
Summary:
This PR adds RISC-V Vector Extension SIMD support for Faiss scalar quantizer.
The implementation introduces runtime vector-length aware RVV kernels using the m8 vector configuration, instead of assuming a fixed vector width. This matches the variable-length nature of RVV hardware and allows the implementation to scale across different RISC-V vector implementations.
## Changes
- Add RVV implementations for scalar quantizer codecs:
- 8-bit codec decoding
- 4-bit codec decoding
- (6-bit stays scalar: the RVV gather decoder measured 12-22% slower
than the scalar path, so QT_6bit falls back until a faster decoder
exists)
- Add RVV quantizer reconstruction support for:
- Uniform quantizers
- Non-uniform quantizers
- FP16 (Zvfhmin is the enforced minimum ISA of the RISCV_RVV level; a
build without it fails compilation rather than silently falling back)
- BF16
- Direct 8-bit quantization
- Signed 8-bit quantization
- LloydMax quantizers (1/2/3/4/8-bit)
- Add RVV optimized similarity implementations:
- L2 distance
- Inner product
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5535
Reviewed By: mnorris11
Differential Revision: D116996553
Pulled By: juancarpio27
fbshipit-source-id: dc726948fa602a04a757d8f9cab8eea41ac1979a
|
||
|
Jure Bajic
|
02cacc5293 |
Fix TSAN races in side hsnw_stats and rabitq_stats (#5657)
Summary:
These TSAN races can be detected when running a search in parallel over the IVF_HNSW index. This PR just wraps the updates of these inside `omp_critical` points.
```
WARNING: ThreadSanitizer: data race (pid=485)
Write of size 8 at 0xaaaadb3db920 by thread T1443:
#0 faiss::IndexHNSW::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/exception_ptr.h (arangod+0x7b95d44) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
Previous write of size 8 at 0xaaaadb3db920 by thread T59 (mutexes: write M0):
#0 faiss::IndexHNSW::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/exception_ptr.h (arangod+0x7b95d44) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/1 faiss::IndexIVF::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const::$_0::operator()(long, float const*, float*, long*, faiss::IndexIVFStats*) const /root/project/3rdParty/faiss/faiss/IndexIVF.cpp:351 (arangod+0x7ae5c04) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/2 faiss::IndexIVF::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const (.omp_outlined) /root/project/3rdParty/faiss/faiss/IndexIVF.cpp:391 (arangod+0x7ae5ae8) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/3 faiss::IndexIVF::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const /root/project/3rdParty/faiss/faiss/IndexIVF.cpp:384 (arangod+0x7ade660) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/4 faiss::IndexIVF::search(long, float const*, long, float*, long*, faiss::SearchParameters const*) const /root/project/3rdParty/faiss/faiss/IndexIVF.cpp:384 (arangod+0x7ade624) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
Location is global 'faiss::hnsw_stats' of size 32 at 0xaaaadb3db920 (arangod+0xa5eb920)
Mutex M0 (0xffff39ed9968) created at:
#0 pthread_mutex_lock <null> (arangod+0x2414098) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/1 __gthread_mutex_lock /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/aarch64-linux-gnu/c++/13/bits/gthr-default.h:749 (arangod+0x3820b80) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/2 lock /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/std_mutex.h:113 (arangod+0x3820b80)
https://github.com/facebookresearch/faiss/issues/3 lock_guard /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/std_mutex.h:249 (arangod+0x3820b80)
Thread T1443 (tid=6126, running) created by thread T138 at:
#0 pthread_create <null> (arangod+0x2411d9c) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
https://github.com/facebookresearch/faiss/issues/1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State>>, void (*)()) <null> (libstdc++.so.6+0xe1c64) (BuildId: 7c239d1743727054caa3df1ab866bfa72cd4dd93)
Thread T59 'SchedWorker' (tid=812, running) created by thread T56 at:
#0 pthread_create <null> (arangod+0x2411d9c) (BuildId: 6c4d32ad66c51d1f6946b33e752288fa07e2d2c8)
```
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5657
Reviewed By: alibeklfc
Differential Revision: D121097648
Pulled By: mnorris11
fbshipit-source-id: 55455e7dab133360d4aa193f3853e3ae12f2f881
|
||
|
anthony-zy
|
bf8be4a79b |
fix(ci): use GCC 14 riscv64 cross-compiler for RVV tuple/zvfhmin intrinsics (#5653)
Summary: fix(ci): use GCC 14 riscv64 cross-compiler for RVV tuple/zvfhmin intrinsics The linux-riscv64-DD CI job installs the default cross-compiler from Ubuntu noble, which resolves to GCC 13.3. GCC 13's <riscv_vector.h> does not export the RVV tuple types (vuint8m1x3_t) nor the zvfhmin f16 intrinsics (vfloat16m1_t, __riscv_vle16_v_f16m1, __riscv_vfwcvt_f_f_v_f32m2) used by the SQ RVV kernels, so building sq-rvv.cpp failed with "'vuint8m1x3_t' was not declared in this scope" (and similar) in the Codec6bit software-pipelined loops and the QuantizerFP16 fast paths. The intrinsics used are all legal under -march=rv64gcv_zvfhmin (only vle16/vse16/vfwcvt/vfncvt on f16) and are fully supported starting with GCC 14, so no source changes are needed. Explicitly install gcc-14-riscv64-linux-gnu / g++-14-riscv64-linux-gnu and point the toolchain file at the versioned binaries, avoiding any reliance on update-alternatives defaults. A version self-check in the workflow makes the resolved compiler visible in the CI log. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5653 Reviewed By: alibeklfc Differential Revision: D120734761 Pulled By: mnorris11 fbshipit-source-id: d82cf2c99dfd6e8720f31bdadb718806f9e71044 |
||
|
Alibek Zhakubayev
|
98af2cf627 |
Fix osx-arm64 conda build: drop redundant openblas pin, allow single-platform release dispatch (#5652)
Summary: The `OSX arm64 packages` job failed in the v1.15.1 release run ([35131196327](https://github.com/facebookresearch/faiss/actions/runs/35131196327)), so `faiss-cpu` 1.15.1 is on the pytorch channel for linux-64, linux-aarch64 and win-64 but **not** osx-arm64. PyPI is unaffected. ### Root cause Upstream conda-forge inconsistency, not a faiss regression. On 2026-09-10 conda-forge published two new `libopenblas 0.3.34` builds for osx-arm64 without matching `openblas 0.3.34` metapackages: | `openblas 0.3.34` accepts | `libopenblas 0.3.34` available | |---|---| | `openmp_he657e61_0` | `openmp_he657e61_0` (07-17) | | `pthreads_hddb8425_0` | `pthreads_hddb8425_0` (07-17) | | `pthreads_h60d1960_1` | `pthreads_h60d1960_1` (08-30) | | `openmp_h4f80526_1` | `openmp_h4f80526_1` (08-30) | | — | `pthreads_hb42d564_1` (09-10) ← no `openblas` | | — | `openmp_h5e6e99c_1` (09-10) ← no `openblas` | `libfaiss` built fine against `openmp_h4f80526_1`. The failure came when solving the `faiss-cpu` env: the unpinned `libopenblas =0.3.34` resolves to the newest build `openmp_h5e6e99c_1`, which no `openblas 0.3.34` accepts: ``` package libfaiss-1.15.1-py3.12_hcb8d3e5_0_cpu requires openblas 0.3.34.*, but none of the providers can be installed ``` The recipe is vulnerable because the `libfaiss` output pins **both** `openblas` and `libopenblas` on osx-arm64 — `# [not x86_64]` was written for linux-aarch64 but also matches macOS ARM. The `faiss-cpu` output in the same file already pins only `libopenblas` on osx. ### Changes 1. **`conda/faiss/meta.yaml`** (lines 72, 86) — narrow the selector to `# [linux and not x86_64]`, so osx-arm64 constrains only `libopenblas` (what `libfaiss` actually links: `libopenblas.0.dylib`). linux-aarch64 and x86_64 behavior unchanged. 2. **`.github/workflows/build-release.yml`** — add `workflow_dispatch` with a `platforms` choice input. The workflow was `workflow_call`-only, so a single failed conda leg could not be rebuilt without pushing a tag. Each job gains an `if:` that is a no-op on tag pushes (`github.event_name` is `push`), preserving current release behavior. ### Recovery plan for 1.15.1 After this lands, dispatch `build-release.yml` from `main` with `platforms: osx-arm64`. The conda version comes from `git describe`, so this produces **1.15.1 build 1** — same version, next build number, no retagging and no PyPI involvement. ### Note If conda-forge publishes the missing `openblas` builds, the old recipe would start working again on its own. This change removes the coupling so the build no longer depends on that. Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5652 Test Plan: - [ ] CI passes - [ ] Dispatch `build-release.yml` with `platforms: osx-arm64` and confirm the conda solve succeeds - [ ] Confirm `faiss-cpu` 1.15.1 appears for osx-arm64 on the pytorch channel Reviewed By: mnorris11 Differential Revision: D120400090 Pulled By: alibeklfc fbshipit-source-id: 0c27e8244bfe25bea4a45466e4e2376c04e0c1f8 |
||
|
Mulugeta Mammo
|
b0d9e80288 |
Add fast scan variants of SQ indexes - IndexSQFastScan and IndexIVFSQFastScan (#5341)
Summary:
This PR introduces `IndexSQFastScan` and `IndexIVFSQFastScan`, fast scan variants of scalar quantized indexes.
**IndexSQFastScan** (33f2cb639bd7a888b2ab7578083b73753c2fd3d3)
Introduces `IndexSQFastScan`, a fast scan variant of `IndexScalarQuantizer` that leverages the PQ4 FastScan SIMD infrastructure (`vpshufb`) for accelerated search over scalar-quantized codes.
Three code paths depending on quantizer type:
- Native 4-bit (`QT_4bit`, `QT_4bit_uniform`): codes map directly onto the 16-level PQ4 fast scan. ~11x speedup, no precision loss.
- Rerank (`QT_6bit`, `QT_8bit`, `QT_8bit_uniform`, `QT_8bit_direct`, `QT_8bit_direct_signed`): re-quantize to 4-bit for a coarse fast scan first pass, then rerank top-k*rerank_factor candidates with exact original-precision distances. ~7-9x speedup, near-zero precision loss at rerank_factor=4.
- Fallback (`QT_fp16`, `QT_bf16`, `TurboQuant`, etc.): delegates to the ScalarQuantizer's own SIMD-optimized scanner. Same speed as IndexScalarQuantizer — no fast scan benefit, but provides a unified interface for all quantizer types.
**benchmark**: `benchs/bench_index_sq_fastscan.py`
```text
+---------------------+----------------------+---------+---------+--------+--------+
| Category | QType | Speedup | ms/q SQ | R@1 | R@10 |
+---------------------+----------------------+---------+---------+--------+--------+
| Native 4-bit (SIMD) | QT_4bit | 11.9x | 0.240 | 0.7714 | 0.9985 |
| | QT_4bit_uniform | 11.7x | 0.235 | 0.7180 | 0.9952 |
+---------------------+----------------------+----------+---------+--------+--------+
| Rerank (rf=4) | QT_6bit | 9.3x | 0.202 | 0.9371 | 1.0000 |
| | QT_8bit | 8.4x | 0.173 | 0.9783 | 1.0000 |
| | QT_8bit_uniform | 6.7x | 0.138 | 0.9728 | 1.0000 |
| | QT_8bit_direct | 4.7x | 0.101 | 0.9914 | 1.0000 |
| | QT_8bit_direct_signed| 4.9x | 0.101 | 0.5999 | 0.6591 |
+---------------------+----------------------+----------+---------+--------+--------+
| Fallback (~1.0x) | QT_fp16 | 0.9x | 0.373 | 0.9914 | 1.0000 |
| | QT_bf16 | 1.0x | 0.365 | 0.9914 | 1.0000 |
| | QT_8bit_tqmse | 1.0x | 0.261 | 0.6033 | 0.9561 |
| | QT_5bit_tq | 1.0x | 3.013 | 0.2680 | 0.6248 |
| | QT_4bit_tq | 1.0x | 2.416 | 0.1511 | 0.3994 |
| | QT_3bit_tq | 1.0x | 0.411 | 0.0487 | 0.1691 |
| | QT_2bit_tq | 1.1x | 0.231 | 0.0376 | 0.1532 |
| | QT_4bit_tqmse | 1.0x | 0.290 | 0.0012 | 0.0064 |
| | QT_3bit_tqmse | 1.0x | 0.345 | 0.0000 | 0.0001 |
| | QT_2bit_tqmse | 1.0x | 0.266 | 0.0000 | 0.0001 |
| | QT_1bit_tqmse | 1.0x | 0.280 | 0.0000 | 0.0001 |
+---------------------+----------------------+----------+---------+--------+--------+
Key: Speedup = IndexScalarQuantizer ms / IndexSQFastScan ms
R@1, R@10 = IndexSQFastScan recall (matches SQ for all fallback types)
Rerank shows rf=4 (rf=2 and rf=8 yield same recall, ~0.1x speedup variation)
Dataset: SIFT1M, k=32
```
**IndexIVFSQFastScan** (ebfa072816df2fbd80a6b463a913866f862587f6)
Similar to the above, this commit introduces `IndexIVFSQFastScan`, an IVF variant of scalar quantized fast scan that extends the PQ4 FastScan SIMD infrastructure (vpshufb) to inverted-list indexes with scalar quantization. Uses BlockInvertedLists for packed 4-bit codes scanned via SIMD. Will continue to update the PR until it's feature complete.
Three code paths depending on quantizer type:
- Native 4-bit (QT_4bit, QT_4bit_uniform): codes pack directly into the SIMD block layout with no precision loss. ~12x speedup.
- Rerank (QT_6bit, QT_8bit, QT_8bit_uniform, QT_8bit_direct, QT_8bit_direct_signed): re-quantized to 4-bit for the SIMD coarse pass, then reranked using exact original-precision codes stored in a parallel ArrayInvertedLists. ~8-10x speedup, near-zero precision loss at rerank_factor=2.
- Fallback (QT_fp16, QT_bf16, TurboQuant, etc.): delegates to IndexIVF's InvertedListScanner path. Same behavior as IndexIVFScalarQuantizer — no fast scan benefit, but provides a unified interface for all quantizer types.
**benchmark (SIFT1M, d=128, k=32, SapphireRapids)**: `benchs/bench_index_ivf_sq_fastscan.py`
```text
+---------------------+----------------------+--------+-------------------------------------------+
| Category | QType | nprobe | Speedup | ms/q SQ | R@1 FS | R@10 FS |
+---------------------+----------------------+--------+---------+---------+--------+-------------+
| Native 4-bit (SIMD) | QT_4bit | 1 | 7.1x | 0.007 | 0.4582 | 0.5456 |
| | | 4 | 10.4x | 0.007 | 0.6903 | 0.8667 |
| | | 16 | 12.9x | 0.022 | 0.7668 | 0.9885 |
| | | 64 | 12.1x | 0.070 | 0.7725 | 0.9983 |
| | | 256 | 11.3x | 0.230 | 0.7725 | 0.9983 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_4bit_uniform | 1 | 15.8x | 0.006 | 0.4397 | 0.5449 |
| | | 4 | 10.5x | 0.007 | 0.6419 | 0.8650 |
| | | 16 | 10.4x | 0.018 | 0.7113 | 0.9855 |
| | | 64 | 10.9x | 0.063 | 0.7162 | 0.9951 |
| | | 256 | 11.0x | 0.222 | 0.7162 | 0.9951 |
+---------------------+----------------------+--------+---------+---------+--------+-------------+
| Rerank (rf=4) | QT_6bit | 1 | 4.9x | 0.007 | 0.4582 | 0.5456 |
| | | 4 | 4.8x | 0.007 | 0.6903 | 0.8667 |
| | | 16 | 7.9x | 0.018 | 0.7668 | 0.9885 |
| | | 64 | 10.4x | 0.067 | 0.7725 | 0.9983 |
| | | 256 | 10.2x | 0.221 | 0.7725 | 0.9983 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_8bit | 1 | 17.1x | 0.007 | 0.4582 | 0.5456 |
| | | 4 | 12.5x | 0.008 | 0.6903 | 0.8667 |
| | | 16 | 8.9x | 0.015 | 0.7668 | 0.9885 |
| | | 64 | 8.4x | 0.049 | 0.7725 | 0.9983 |
| | | 256 | 9.3x | 0.188 | 0.7725 | 0.9983 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_8bit_uniform | 1 | 18.2x | 0.007 | 0.4397 | 0.5449 |
| | | 4 | 11.1x | 0.008 | 0.6419 | 0.8650 |
| | | 16 | 8.3x | 0.014 | 0.7113 | 0.9855 |
| | | 64 | 7.8x | 0.045 | 0.7162 | 0.9951 |
| | | 256 | 7.8x | 0.164 | 0.7162 | 0.9951 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_8bit_direct | 1 | 8.6x | 0.007 | 0.4083 | 0.5426 |
| | | 4 | 7.0x | 0.008 | 0.5987 | 0.8587 |
| | | 16 | 6.8x | 0.013 | 0.6550 | 0.9756 |
| | | 64 | 6.1x | 0.035 | 0.6581 | 0.9850 |
| | | 256 | 7.4x | 0.150 | 0.6581 | 0.9850 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_8bit_direct_signed| 1 | 16.5x | 0.006 | 0.4257 | 0.5447 |
| | | 4 | 10.1x | 0.007 | 0.6286 | 0.8633 |
| | | 16 | 7.1x | 0.012 | 0.6919 | 0.9831 |
| | | 64 | 5.7x | 0.033 | 0.6963 | 0.9923 |
| | | 256 | 7.1x | 0.145 | 0.6963 | 0.9923 |
+---------------------+----------------------+--------+---------+---------+--------+-------------+
| Fallback (~1.0x) | QT_fp16 | 1 | 1.0x | 0.007 | 0.5434 | 0.5462 |
| | | 4 | 1.1x | 0.013 | 0.8607 | 0.8678 |
| | | 16 | 0.9x | 0.035 | 0.9814 | 0.9902 |
| | | 64 | 0.9x | 0.115 | 0.9912 | 1.0000 |
| | | 256 | 0.9x | 0.481 | 0.9912 | 1.0000 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_bf16 | 1 | 1.0x | 0.008 | 0.5427 | 0.5462 |
| | | 4 | 1.1x | 0.013 | 0.8581 | 0.8678 |
| | | 16 | 1.0x | 0.035 | 0.9778 | 0.9902 |
| | | 64 | 1.0x | 0.115 | 0.9876 | 1.0000 |
| | | 256 | 1.0x | 0.487 | 0.9876 | 1.0000 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_5bit_tq | 1 | 1.0x | 0.016 | 0.1866 | 0.3827 |
| | | 64 | 1.0x | 0.794 | 0.2680 | 0.6248 |
| | | 256 | 1.0x | 2.885 | 0.2680 | 0.6248 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_4bit_tq | 1 | 1.0x | 0.013 | 0.1182 | 0.2841 |
| | | 64 | 0.9x | 0.618 | 0.1511 | 0.3994 |
| | | 256 | 0.9x | 2.298 | 0.1511 | 0.3994 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_3bit_tq | 1 | 1.1x | 0.008 | 0.0526 | 0.1599 |
| | | 64 | 0.8x | 0.092 | 0.0488 | 0.1696 |
| | | 256 | 0.8x | 0.357 | 0.0487 | 0.1691 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_2bit_tq | 1 | 1.2x | 0.008 | 0.0450 | 0.1526 |
| | | 64 | 1.1x | 0.072 | 0.0377 | 0.1534 |
| | | 256 | 1.1x | 0.224 | 0.0376 | 0.1532 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_4bit_tqmse | 1 | 1.0x | 0.007 | 0.0619 | 0.1851 |
| | | 64 | 1.0x | 0.072 | 0.0002 | 0.0010 |
| | | 256 | 0.9x | 0.275 | 0.0000 | 0.0000 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_3bit_tqmse | 1 | 1.0x | 0.007 | 0.0621 | 0.1852 |
| | | 64 | 1.0x | 0.090 | 0.0006 | 0.0032 |
| | | 256 | 1.0x | 0.350 | 0.0000 | 0.0000 |
| +----------------------+--------+---------+---------+--------+-------------+
| | QT_2bit_tqmse | 1 | 1.1x | 0.007 | 0.0621 | 0.1852 |
| | | 64 | 1.0x | 0.068 | 0.0015 | 0.0080 |
| | | 256 | 1.0x | 0.244 | 0.0000 | 0.0000 |
+---------------------+----------------------+--------+---------+---------+--------+-------------+
Key: Speedup = IndexIVFScalarQuantizer ms / IndexIVFSQFastScan ms
R@1, R@10 = IVFSQFastScan recall (matches IVF-SQ for all fallback types)
Rerank shows rf=4 only (rf=2,8 yield similar results)
Fallback shows nprobe=1,64,256 only (abbreviated for low-recall types)
Dataset: SIFT1M, nlist=256, k=32
```
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5341
Reviewed By: junjieqi
Differential Revision: D117259284
Pulled By: mnorris11
fbshipit-source-id: 41455097ff3ae1285aeb4cf88e07abc5b5b13171
|
||
|
Mihai Capotă
|
4864f4d420 |
SVS: Add ParameterSpace.set_index_parameter support for Vamana (#5644)
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5644 Reviewed By: alibeklfc Differential Revision: D120290334 Pulled By: mnorris11 fbshipit-source-id: c947484d0704789553a7d4d80a0ef7185e59962a |
||
|
Aaryan Mehta
|
3f4838ead3 |
Batch the IVF ScalarQuantizer scan four codes at a time (#5456)
Summary:
The IVF ScalarQuantizer inverted-list scan distances one code at a time through `run_scan_codes1`, even though the SQ distance computers already expose a four-at-a-time kernel, `query_to_codes_batch_4` (the one HNSW uses through `distances_batch_4`). This adds `run_scan_codes4`, a batched inner loop that distances four consecutive codes per step and then applies the same threshold compare, `add_result`, and threshold refresh as `run_scan_codes1`, in id order, so the sequence of heap updates is identical. The two SQ scanners route their no-selector path through it; the selector path stays on `run_scan_codes1`.
Four independent accumulator chains let the out-of-order core overlap the latency-bound reduction that a single code cannot hide. Results are unchanged: the batched kernel reconstructs each code, which is bit-identical to the single-code path for every quantizer except the uniform ones, whose single-code path predecodes the query, so a compile-time check keeps those on the scalar scan. Verified bit-identical distances and ids against the scalar scan for QT_8bit, QT_8bit_uniform, QT_6bit, QT_4bit, QT_fp16, and QT_8bit_direct, in both metrics, at d in {64, 128, 256}.
Measured on AVX2, end-to-end `IndexIVFScalarQuantizer` search of QT_8bit, single thread, batched against the scalar scan:
| metric | d | scalar | batched | speedup |
| --- | --- | --- | --- | --- |
| L2 | 128 | 60.4 ms | 40.3 ms | 1.50x |
| L2 | 256 | 170.9 ms | 105.7 ms | 1.62x |
| L2 | 256, out of cache | 403.5 ms | 262.3 ms | 1.54x |
| IP | 128 | 46.5 ms | 38.4 ms | 1.21x |
| IP | 256 | 108.7 ms | 83.8 ms | 1.30x |
The L2 gain is the larger one, around 1.5-1.6x, and it holds when the index spills out of cache. Inner product gains less since its shorter chain is already partly overlapped by the core. When batching does not help it matches the scalar scan, so there is no regression.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5456
Reviewed By: junjieqi
Differential Revision: D118857126
Pulled By: mnorris11
fbshipit-source-id: df7b02c2ede8699c599956370b87a949f1b7db9d
|
||
|
郑紫阳10295048
|
0f23e6a2ef |
Add RVV SIMD specialization for scalar quantizer distance compute (#5539)
Summary: This PR adds RISC-V Vector Extension SIMD specialization for the scalar quantizer distance computation, following the codec/quantizer/similarity specialization already present for other SIMD levels. The kernels use the runtime vector-length aware m8 vector configuration and are shared across all RVV hardware widths, instead of assuming a fixed vector length. Changes Add RVV specialized L2 / inner-product distance kernels for the scalar quantizer codecs: - QT_4bit / QT_4bit_uniform - QT_6bit - QT_8bit / QT_8bit_uniform - QT_8bit_direct / QT_8bit_direct_signed - QT_bf16 - QT_fp16 Each kernel reuses the reconstructed (quantizer) L2 / IP formulation that avoids per-dimension reconstruction, keeping the hot loop in the integer domain and applying the final scale at the tail. Performance Cmd: 1M 768 <SQ> 32 100 16 1 1000 1 <metric> (search ms/query, lower is better) Δ_SQ%: SQ scalar baseline -> RVV; Δ_F%: Faiss flat baseline -> RVV. | 序号 | QT_TYPE | Metric | F1(ms) | SQ1(ms) | F2(ms) | SQ2(ms) | Δ_SQ% | Δ_F% | |------|-----------------------|--------|--------|---------|--------|---------|---------|--------| | 01 | QT_4bit | L2 | 1.841 | 6.231 | 1.824 | 1.450 | -76.73% | -0.92% | | 02 | QT_4bit | IP | 1.652 | 6.086 | 1.674 | 1.273 | -79.08% | +1.33% | | 03 | QT_4bit_uniform | L2 | 1.806 | 2.560 | 1.806 | 1.135 | -55.66% | +0.00% | | 04 | QT_4bit_uniform | IP | 1.612 | 6.007 | 1.597 | 1.244 | -79.29% | -0.93% | | 05 | QT_6bit | L2 | 1.801 | 5.701 | 1.805 | 1.500 | -73.69% | +0.22% | | 06 | QT_6bit | IP | 1.608 | 5.706 | 1.619 | 1.249 | -78.11% | +0.68% | | 07 | QT_8bit | L2 | 1.821 | 3.736 | 1.907 | 1.394 | -62.69% | +4.72% | | 08 | QT_8bit | IP | 1.704 | 3.378 | 1.730 | 1.277 | -62.20% | +1.53% | | 09 | QT_8bit_direct | L2 | 1.977 | 0.280 | 1.947 | 0.054 | -80.71% | -1.52% | | 10 | QT_8bit_direct | IP | 1.709 | 0.458 | 1.740 | 0.099 | -78.38% | +1.81% | | 11 | QT_8bit_direct_signed | L2 | 1.581 | 3.234 | 1.572 | 0.761 | -76.47% | -0.57% | | 12 | QT_8bit_direct_signed | IP | 1.740 | 0.414 | 1.748 | 0.148 | -64.25% | +0.46% | | 13 | QT_8bit_uniform | L2 | 1.943 | 3.204 | 1.928 | 0.927 | -71.07% | -0.77% | | 14 | QT_8bit_uniform | IP | 1.727 | 3.121 | 1.744 | 0.947 | -69.66% | +0.98% | | 15 | QT_bf16 | L2 | 1.862 | 2.889 | 1.894 | 1.466 | -49.26% | +1.72% | | 16 | QT_bf16 | IP | 1.619 | 2.846 | 1.793 | 1.204 | -57.70% | +10.75% | | 17 | QT_fp16 | L2 | 2.011 | 5.691 | 1.950 | 1.570 | -72.41% | -3.03% | | 18 | QT_fp16 | IP | 1.797 | 5.584 | 1.790 | 1.189 | -78.71% | -0.39% | Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5539 Reviewed By: mnorris11 Differential Revision: D117914328 Pulled By: juancarpio27 fbshipit-source-id: 879863b9ab4da6d1c8685892ccc3d64190975181 |