Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5587
**TL;DR:** Adds a batched 20-byte Hamming kernel that measures eight codes per call, the only thing that helps the 160-bit width, worth 1.21x end to end.
A 20-byte code has no vector kernel at any x86 SIMD level. `HammingComputer20` measures one distance with three scalar popcounts at every level, including `AVX512_VPOPCNT`, so a scan of 160-bit codes runs the same code everywhere.
Vectorizing a single 20-byte distance does not help. A masked 256-bit load plus `vpopcntq` plus a horizontal reduction measures the same as the scalar body, because the reduction costs more than the three popcounts it replaces.
Measuring several codes per call does help, because it amortizes that reduction. This adds `hamming_batch()` to `HammingComputer20` at `AVX512_VPOPCNT`, which measures eight codes at once:
- Eight codes span 160 bytes. `_mm512_popcnt_epi8` gives a count per byte.
- `_mm512_sad_epu8` sums each aligned 8-byte group.
- A 20-byte code covers two whole groups plus half of a group it shares with its neighbour, so each code needs one scalar popcount for its half.
`IVFBinaryScannerL2::scan_codes` and `IVFBinaryScannerL2::scan_codes_range` call `hamming_batch()` when the computer declares a `batch_size`, then measure the remaining codes one at a time. A computer without a `batch_size` keeps the existing loop, so no other code size changes.
The scanner holds the tiled query, and the constructor rejects a code size that does not match the computer. A caller therefore cannot reach the batch kernel with a stride the kernel does not read.
The byte-wise popcount needs `AVX512_BITALG`, which is a separate CPUID bit from `AVX512_VPOPCNTDQ`. This adds the flag to the `AVX512_VPOPCNT` level and requires both bits to select it. Every CPU that has VPOPCNTDQ also has BITALG, so no CPU loses the level.
An alternative byte-wise popcount built from `vpshufb`, which needs neither bit and would run at the plain `AVX512` level, measures only 1.08x against 1.54x, so it is not worth the wider reach.
Reviewed By: alibeklfc
Differential Revision: D118971285
fbshipit-source-id: 5fd4637c972e5c55e2695b32b9b15fba8181a242
Summary:
Expose the `set_direct_map_type` method of binary IVF indexes via the C API. This enables support for the `index.set_direct_map_type` API in languages other than Python.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5451
Reviewed By: alibeklfc
Differential Revision: D114681970
Pulled By: mnorris11
fbshipit-source-id: 1342eeb225d6fd9fdea76c6b9417cedde55c1d3a
Summary:
# Introduce early-stop controls for IVF search
This PR adds optional early-stop controls to IVF search through `SearchParametersIVF`.
IVF search looks in a sequence of buckets. Normally it keeps looking until it has checked all requested buckets. This PR adds a few ways to stop earlier:
- stop after enough candidate vectors have been checked,
- stop FastScan after enough buckets have been checked,
- stop range search after several nearby buckets produce no results.
All new fields default to disabled, so existing searches keep their current behavior unless callers opt in.
## New SearchParametersIVF fields
Default values:
| Field | Default | Effect |
|---|---:|---|
| `ensure_topk_full` | `false` | disabled; keep the existing hard `max_codes` behavior |
| `max_lists_num` | `0` | disabled; FastScan is bounded only by `nprobe` |
| `max_empty_result_buckets` | `0` | disabled; range search scans all requested probes |
`ensure_topk_full`
For k-NN search, `max_codes` limits how many candidate vectors are scanned. With `ensure_topk_full=false`, the search stops when the budget is reached.
With `ensure_topk_full=true`, very small budgets become less aggressive: `max_codes` is treated as at least `k` post-filter scans. This helps when `max_codes < k`, or when an `IDSelector` filters out many candidates before a distance is computed.
In the generic IVF path this is supported for `parallel_mode` 0 and 3. In FastScan k-NN it is supported by the per-query implementations 10 and 11.
`max_lists_num`
FastScan k-NN can also stop after visiting a limited number of inverted lists. `0` means disabled. With `ensure_topk_full`, this list budget is treated as at least `k` lists. This is only used by the FastScan per-query path (`search_implem_10`, also used for implementation 11).
When FastScan is left on `implem = 0`, setting an early-stop k-NN option makes the dispatcher choose the per-query implementation automatically. If an incompatible FastScan implementation is selected explicitly, Faiss throws instead of ignoring the option.
`max_empty_result_buckets`
This is for range search. It stops probing a query after that many consecutive probed lists add no in-radius results. The counter resets as soon as a list adds at least one result.
`0` means disabled. Setting this trades recall for less work: once nearby buckets repeatedly produce no hits, farther buckets are less likely to help.
The generic IVF range path supports this in `parallel_mode == 0`. FastScan range search also supports it through implementation 10. With `implem = 0`, FastScan selects implementation 10 automatically when this option is set; explicit incompatible implementations throw.
## Selector-aware scan accounting
This PR adds `InvertedListScannerStats`, returned by inverted-list scanner methods. It currently reports:
- `scan_cnt`: number of distances actually computed,
- `nheap_updates`: number of result updates.
The important behavior change is that `IndexIVFStats::ndis` now uses `scan_cnt`. With an `IDSelector`, candidates rejected by the selector are not counted as computed distances. Without a selector, this matches the previous count because every scanned code reaches distance computation.
This same post-filter count is used by `ensure_topk_full`, so a restrictive selector no longer consumes the search budget with candidates that were never eligible for the result heap.
## FastScan behavior
FastScan k-NN now applies `max_codes`, `max_lists_num`, and `ensure_topk_full` in the per-query implementation. The code keeps separate counters per query, so multi-query batches have independent budgets.
For `max_codes`, FastScan uses the result handler's scanned-row count. This means filtered-out rows do not consume the code budget.
FastScan range search rejects k-NN-only options (`max_codes`, `max_lists_num`, and `ensure_topk_full`). It accepts `max_empty_result_buckets` when the selected implementation can preserve per-query probe order.
## API exposure
The new fields are exposed through:
- C++ `SearchParametersIVF`,
- Python bindings,
- the C API.
The statistics is tracked via `InvertedListScanner::scan_codes(..., ResultHandler& handler)` call. In order to make it work inside `IndexIVF::search()`, it has been decided to transition it into this particular override of `InvertedListScanner::scan_codes()`. As a result, non-`ResultHandler` version of `scan_codes()` has been marked as non-virtual, so the custom `InvertedListScanner` implementations should override `ResultHandler`-based versions only. Another consequence is that `IndexIVFPQFastScanScanner` and `IndexIVFRaBitQFastScanScanner` accept only `HeapResultHandler` types of `ResultHandler`. These are the compromises that had to be made.
## Tests
The tests cover:
- default parameters preserving baseline k-NN and range-search results,
- `ensure_topk_full` filling more result slots under tight budgets,
- selector-aware `IndexIVFStats::ndis`,
- range-search early exit and counter reset behavior,
- unsupported parallel modes and FastScan implementations,
- FastScan k-NN and range-search early-stop behavior,
- Python and C API field exposure.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5160
Reviewed By: limqiying
Differential Revision: D103044128
Pulled By: mnorris11
fbshipit-source-id: 80f1241c13ffc8173a3da0f2974fa9b6dd318890
Summary:
Primarily for the sake of completeness, we could expose an IndexBinaryFlat to the C API.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4834
Reviewed By: junjieqi
Differential Revision: D94736003
Pulled By: gtwang01
fbshipit-source-id: 563a0b2b6684bead170ace6df08cc8ddd29c77d5
Summary:
- Add support ParameterSpace for IndexBinaryHNSW and IndexBinaryIVF
- Add support SearchParameters in search() method for IndexBinaryHNSW and IndexBinaryIVF
- Add support for passing parameters to IndexBinaryHNSW and IndexBinaryIVF from CAPI
fixes https://github.com/facebookresearch/faiss/issues/3503
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4761
Reviewed By: mdouze
Differential Revision: D91060658
Pulled By: juancarpio27
fbshipit-source-id: f8cd87fc020d410bf2982636d2aa393e6d7e3410
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4485
hipify.sh currently generates .hip files into a separate directory called `gpu-rocm`. The swigfaiss.swig file expects them there too. But to use internal hipification, it needs to be generated into the same directory `gpu`. That means swigfaiss.swig has to change `gpu-rocm` to just `gpu`, same directory as .cu files. If swigfaiss.swig changes, then the hipify.sh has to change as well, otherwise OSS CI breaks.
OSS changes
- Requires changing `swigfaiss.swig`, because the internal BUCK approach builds in the same directory as `.cu` files, aka `gpu/`.
- Because it builds in same `gpu/` directory, we need to change the OSS side `hipify.sh`. After this diff, it just builds in `gpu/`. The rocm CI still passes.
Reviewed By: junjieqi
Differential Revision: D79145713
fbshipit-source-id: a83b805c8a7bf286a7e6cff50c8eb2ddd72f518c
Summary:
This PR implements the C API for IndexBinaryIVF.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4302
Reviewed By: mnorris11
Differential Revision: D73885352
Pulled By: satymish
fbshipit-source-id: a67b37fc7b75dde9e83a367c4352970aadc43119
Summary:
### Description
- Create custom readers and writers for index IO, which take function pointers as input
- Also expose these from the C_API
This is helpful for FFI use, where calling processes would pass upcall stubs for streamlined IO
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4180
Reviewed By: gtwang01
Differential Revision: D71208266
Pulled By: mnorris11
fbshipit-source-id: ab82397d4780a2a07c7bfdc52329968377f42af4
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3716
Renaming `USE_ROCM` to `FAISS_ENABLE_ROCM` in CMake files, `FAISS_ENABLE_ROCM` in SWIG files, and `USE_AMD_ROCM` in other source files to follow the existing naming convention.
Reviewed By: mnorris11
Differential Revision: D60673731
fbshipit-source-id: 1aaa3f2ff6836830c4eb733ee7f41554f79f9695
Summary:
* add hipify at configure time
* ROCm specific code paths behind USE_ROCM guards
* support for wavefront 32 (Navi) and 64 (MI)
* use builtins to match inline PTX
* support C API on ROCm
* support Python API on ROCm
---------
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3462
Reviewed By: asadoughi
Differential Revision: D60431193
Pulled By: ramilbakhshyiev
fbshipit-source-id: ac82d5ecb38f995c467e100ed583d5178ae489ee
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3688
Looks like our previous changes only modified the cpp API. Not the c_api like the request wanted. This attempts to add faiss_get_version to c_api
Reviewed By: ramilbakhshyiev
Differential Revision: D60207739
fbshipit-source-id: 07184aeae92a154bb3f440279595077f002851f3
Michael Norris