Summary:
- initialize result handlers when an exhaustive search has no database vectors
- process empty results in the configured query block size, preserving bounded temporary memory for large query batches
- cover L2 and inner-product search across top-1, heap, and reservoir result handlers
## Problem
Searching an empty `IndexFlat` produced correct sentinel values for small query batches, but could leave the caller's distance and label buffers untouched once `nq * d` selected the BLAS path. The BLAS helpers return early for `ny == 0` before the result handler's `begin_multiple` / `end_multiple` lifecycle initializes and finalizes the output.
This change handles an empty database before choosing the sequential or BLAS implementation. It uses the existing result-handler lifecycle so each handler supplies its own correct neutral distance and `-1` label semantics.
Fixes https://github.com/facebookresearch/faiss/issues/3830.
## Validation
- `python -m unittest test_index.TestIndexFlat_ARM_NEON.test_empty_index_with_blas`
- `python -m unittest test_index` (49 tests passed)
- `faiss_test --gtest_brief=1` (290 passed, 1 platform-specific skip)
- `clang-format 21 --dry-run --Werror faiss/utils/distances.cpp`
## Verification of the regression test
We confirmed `test_empty_index_with_blas` is a true regression test by running it with and without the `utils/distances.cpp` change:
| State | Result |
|-------|--------|
| Fix applied | 1 passed, 0 failed |
| `utils/distances.cpp` reverted to parent, test retained | 6 failed |
The 6 failures are every subtest (2 metrics x 3 values of `k`), covering the `Top1`, `Heap`, and `Reservoir` result handlers. The failure output reports `ACTUAL: array([[42., 42., ...` against `DESIRED: array(-3.402823e+38)`. The test pre-fills `D` with `42` and `I` with `99`, so this confirms the output buffers are never written without the fix, rather than written with incorrect values. The passing run is clean under ASan and UBSan.
## Note for issue #3830
The repro in the issue (`d=1`, `nq=20`) no longer reproduces on `main`. When the issue was filed, `distance_compute_blas_threshold` defaulted to `20` and the branch condition was `nx < threshold`, which put `nq=19` on the sequential path (correct sentinels) and `nq=20` on the BLAS path (uninitialized output). The threshold is now dimension-aware (`nx * d < distance_compute_blas_threshold`, default `128000`), so `d=1` requires `nq >= 128000` to select BLAS. The defect was relocated, not fixed. A repro that still holds today is:
```
faiss.IndexFlatL2(128).search(np.random.random((1000, 128)).astype('float32'), 1) # nx * d == 128000
```
This change removes the defect at its source, for all `nx`, all `d`, both metrics, and all three result handlers. The `k > ntotal` case with `ntotal > 0` was never affected: `begin_multiple` already initializes all `k` slots, so the unfilled tail is correctly padded.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5528
Reviewed By: mnorris11, trang-nm-nguyen
Differential Revision: D116650117
Pulled By: alibeklfc
fbshipit-source-id: b40bdf7ade7640b2e433765b3877e2cea3546cf2
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5445
Found while self-reviewing the sibling IndexFlatPanorama fix in this
stack: `exhaustive_inner_product_seq` and `exhaustive_L2sqr_seq` in
`utils/distances.cpp` compute
`int nt = std::min(int(nx), omp_get_max_threads())` and then open
`#pragma omp parallel num_threads(nt)`, with no `nx > 0` guard -- the
identical bug class just fixed for `IndexFlatPanorama`, but here backing
plain `IndexFlat::search`/`IndexFlat::range_search` (`IndexFlatL2`,
`IndexFlatIP`, and anything composing them: `IndexIDMap`,
`IndexPreTransform`, `IndexRefineFlat`, etc.) -- the single most widely
used search path in FAISS.
`IndexFlat::search` has no `n > 0` guard before dispatching to
`knn_inner_product`/`knn_L2sqr` (`IndexFlat.cpp:29-59`). Those route to
`Run_search_inner_product::f`/`Run_search_L2sqr::f`
(`utils/distances.cpp:545-580`), which call the `_seq` (non-BLAS) path
whenever `res.sel` is set (any ID selector) OR `nx * d` is below
`distance_compute_blas_threshold` (default 128000) -- always true when
`nx == 0`. So `IndexFlat::search(0, x, k, ...)` reaches `nt =
std::min(0, omp_get_max_threads()) == 0` and
`#pragma omp parallel num_threads(0)` unconditionally, every time.
Per the OpenMP specification, `num_threads` "must evaluate to a positive
integer" -- 0 is unspecified behavior. This devserver's runtime tolerates
it (see below), but is not guaranteed to on every OpenMP implementation
FAISS's production toolchain may link.
Fix: add `if (nx == 0) { return; }` before `nt` is computed, in both
functions -- mirroring the exact guard style already used two functions
below in the same file, in the BLAS counterparts
`exhaustive_inner_product_blas`/`exhaustive_L2sqr_blas_default_impl`
("BLAS does not like empty matrices", `nx == 0 || ny == 0`). Deliberately
NOT copying the `ny == 0` half of that guard here: the BLAS path's
`ny == 0` early return is itself a separate, already-tracked bug (see
finding #6 in the improver findings log -- it skips `begin_multiple`/
`end_multiple` entirely, leaving `distances`/`labels` uninitialized for
`nx > 0, ny == 0`). The `_seq` path does not have that problem: each
query's `resi.begin(i)` already heap-heapifies (or reservoir/range-inits)
to neutral/-1 values per query regardless of `ny`, so `ny == 0` with
`nx > 0` already produces correct "no results" output today. Only the
`nx == 0` case needed a guard, and it needed one specifically to avoid
`num_threads(0)`, not to fix an output-correctness gap.
Verified empirically (temporarily reverted both guards, rebuilt, reran
the new test): on this devserver's OpenMP runtime, `num_threads(0)` does
not crash and the test passes either way -- consistent with the sibling
Panorama diff in this stack. Recording this explicitly rather than
claiming a crash we did not observe; the fix closes real, spec-defined
undefined behavior on FAISS's single most-used search entry point
regardless of whether it reproduces on this specific box.
Swept the rest of the tree for the same `std::min(int(n...),
omp_get_max_threads())` -> `num_threads(nt)` pattern: only two other
sites exist in all of fbcode/faiss/, both in `IndexFlat.cpp`, both
already fixed by the previous diff in this stack. Two adjacent
`num_threads(nt)` sites with different `nt` derivations
(`impl/PolysemousTraining.cpp`, `utils/sorting.cpp`'s
`fvec_argsort_parallel`/`parallel_merge`) were also inspected; both
derive `nt` from internal, not directly user-controlled, values (`pq.M`,
recursive thread-count splitting) and are lower-confidence/harder to
reach -- logged in the findings log for future investigation rather than
folded into this diff.
Reviewed By: trang-nm-nguyen
Differential Revision: D112314349
fbshipit-source-id: 17663f626b27886e43d71f3dd660f706f76c6bd2
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5444
We fix every remaining flake8 E501 (line > 80 chars) violation in
fbcode/faiss/ (excluding gpu/), closing out a lint-cleanup initiative that a
June 29, 2026 diff stack (9a05463576 -> d304e29b9a -> 7d140d86ca) explicitly
promised but left 41% incomplete. The middle diff in that stack aligned
.flake8's max-line-length to black's 80-char width and stated the remaining
277 violations after the config change were "genuine lint (E501 long
strings/URLs, F401/F841/B011, etc.), addressed in later commits in this
stack." The follow-up commit fixed only the F401/F403/F841/B011 categories
(45 issues) and never touched E501, leaving 192 violations across 53 files
live in trunk. A direct re-scan today found 201 violations across 54 files
(two files gained lines since the original count).
We fixed 183 violations across 52 files. Two of the originally-flagged
files, benchs/bench_rabitq.py and
demos/index_pq_flat_separate_codes_from_codebook.py, already carry a
file-level `# flake8: noqa` directive (the second is a Bento/Grimaldi
notebook export that also fails standalone py_compile due to embedded shell
magic) -- flake8 ignores both files entirely, so no changes were needed
there and they are excluded from this diff.
Fix approach, by category:
- The large majority of violations are prose: docstrings and comments
rewrapped at word boundaries, preserving each file's existing indentation
and docstring conventions. No wording was changed.
- Code lines (function calls, f-strings, assert messages, long argument
lists) were reflowed in black-compatible style: parenthesization, comma
breaks, or implicit adjacent string-literal concatenation. Every touched
file is confirmed unchanged by `black --line-length 80 --diff` after the
edit.
- A small number of genuinely unwrappable long URLs (no reasonable break
point) were suppressed with `# noqa: E501` rather than force-wrapped,
matching the precedent set by the original black-format diff stack.
- demos/offline_ivf/offline_ivf.py: a repeated, non-trivial ratio expression
used in both an assert condition and its (lazily-evaluated) failure
message was hoisted into a single local variable, eliminating the
duplicate computation. The expression is pure and deterministic (built
from already-computed arrays), so this is behaviorally identical to the
original -- not a functional change.
- `arc lint -a` additionally auto-fixed a real bug it detected while
processing these files: `raise NotImplemented` -> `raise
NotImplementedError` in contrib/evaluation.py (the sentinel object
NotImplemented is not an exception type; raising it produces a TypeError
masking the intended NotImplementedError). It also added a missing
trailing newline in benchs/fb/bench_index_binary_from_float.py and, in
the same file, rewrote the `#!/usr/bin/env python2` shebang to
`#!/usr/bin/env fbpython` -- that rewrite was reverted by hand, since the
file still does `import cPickle` (a Python 2-only module), so the
auto-fix would have made the shebang describe an interpreter the script
cannot actually run under. Fixing the underlying py2-to-py3 migration is
out of scope for this line-length-only sweep.
- Rebasing onto master (this diff's base commit had drifted) surfaced two
concurrent upstream fixes to `check_ref_knn_with_draws(...)` calls in
tests/test_ivf_flat_panorama.py and tests/test_refine_panorama.py (an
unrelated in-flight correctness fix passing `D_panorama`/`atol` instead
of a stale `D_regular` arg with no `atol`). The rebase took upstream's
corrected arguments and re-applied only this diff's line-wrap on top.
We verified zero functional change with an AST-level check: every string
and f-string literal in every touched file was extracted before and after
the edit and compared with whitespace normalized, confirming no wording,
value, or expression was altered beyond the intended `# noqa: E501`
suffixes and the one documented ratio-hoisting simplification above.
Reviewed By: mnorris11
Differential Revision: D112525458
fbshipit-source-id: e4b85d73dafcaac779f3522a383a66e490fa942a
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5349
# this is a no-op change
Ran `black -l 80` over all tracked Python files under `fbcode/faiss/`, using line length 80 to match faiss's documented coding style (`CONTRIBUTING.md`: "80 character line length (both for C++ and Python)"). 172 files were reformatted; 28 were already compliant.
This is a pure-formatting change. `black` runs its AST-equivalence safety check on every file, so no identifiers, string/numeric values, operators, or control flow were altered — only whitespace, indentation, line wrapping, blank lines, trailing commas, and string-quote normalization (single to double quotes).
`fbcode/faiss/` is intentionally excluded from Meta's standard Python autoformatter (`arc f` / `arc lint -a` report no formatter for these paths) because it mirrors to public GitHub, so the Python had drifted out of any consistent style. The C++ is already clang-format-clean (0 of 807 files change), so this effort is Python-only. This diff brings the Python to canonical `black` formatting.
Excluded `demos/index_pq_flat_separate_codes_from_codebook.py`: it contains a Jupyter `!rm` shell-magic line and is not valid Python, so `black` cannot parse it.
This is the base of a 3-diff stack: (1) this black reformat; (2) `.flake8` alignment (max-line-length 80 + black-compatible ignores E203/W503); (3) genuine lint fixes (F401/F403/F841/B011).
Reviewed By: mnorris11
Differential Revision: D109736099
fbshipit-source-id: 9a054635766ed11aa3760a788395babd3d198abf
Summary:
When the number of queries (`nx`) is smaller than the available thread count, the current flat search underutilizes CPU cores — each thread scans the entire database for a single query. This PR adds a database-parallel code path that divides the database across threads instead, with per-thread BLAS calls and heap merging.
- Activates automatically when `nx < omp_get_max_threads()` and the database is large enough
- Falls back to the existing path when an `IDSelector` is active or the database is too small to benefit
- Works for both `METRIC_INNER_PRODUCT` (CMin) and `METRIC_L2` (CMax)
## Benchmarks
12 threads, `d=128`, `k=10`:
| Index | ny | nx | Before | After | Speedup |
|-------|------|------|--------|-------|---------|
| FlatIP | 1,000,000 | 4 | 56.7 ms | 8.4 ms | **6.7x** |
| FlatIP | 1,000,000 | 1 | 14.1 ms | 5.0 ms | **2.8x** |
| FlatL2 | 1,000,000 | 4 | 56.7 ms | 14.0 ms | **4.0x** |
| FlatL2 | 1,000,000 | 1 | 14.1 ms | 9.5 ms | **1.5x** |
| FlatIP | 200,000 | 4 | 11.5 ms | 1.6 ms | **7.0x** |
| FlatL2 | 200,000 | 4 | 11.4 ms | 2.8 ms | **4.2x** |
No regression for `nx >= nthreads` (existing path is unchanged).
## Motivation
Addresses https://github.com/facebookresearch/faiss/issues/4121. The original issue demonstrated that for few-query workloads over large databases, parallelizing over database segments instead of queries can yield multi-fold speedups. This is especially relevant for serving workloads where queries arrive one at a time.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5000
Test Plan:
- [x] All existing `TestIndexFlat` tests pass (15/15)
- [x] Full `test_index.py` passes (47/47 including 9 new tests)
- [x] `test_search_params.py` + `test_index_composite.py` pass (81/81)
- [x] New `TestDbParallelSearch` covers: IP, L2, k=1, k=200, single query, few queries, thread scaling consistency
- [x] Cross-validated against NumPy brute-force for IP and L2
Reviewed By: mdouze
Differential Revision: D99676059
Pulled By: mnorris11
fbshipit-source-id: 3fbd17a71b446a4b4932d53d9ebc254c4510a0ca
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5134
Expand DD test coverage by applying for_all_simd_levels to existing test
classes that exercise DD-dispatched code paths but were previously pinned
to a single SIMD level.
This is the "mega decorator" diff from the DD test coverage gaps plan --
pure decorator additions, no new test logic. Follow-up diffs add new
test files and numerical cross-level assertions for gaps the decorator
alone cannot close.
Classes decorated (grouped by area):
* Binary Hamming non-IVF: TestRange and TestKnn in
test_binary_hashindex.py; TestBinarySearchParams in
test_binary_search_params.py; TestIndexBinaryFromFloat in
test_index_binary_from_float.py; TestSpectralHash in
test_index_accuracy.py.
* IVFPQ / search: EvalIVFPQAccuracy in test_index.py;
TestSelector and TestSearchParams in test_search_params.py.
* Flat / refine / Panorama: TestIndexFlat, TestIndexFlatL2,
TestIndexFlatL2Panorama, TestScalarQuantizer in test_index.py;
TestDistanceComputer, TestIndexRefineSearchParams,
TestIndexRefineRangeSearch in test_refine.py;
TestIndexRefinePanorama, TestIndexFlatPanorama,
TestIndexHNSWFlatPanorama, TestIndexIVFFlatPanorama in their
respective files.
* Quantizer encode: TestResidualQuantizer,
TestIndexResidualQuantizerSearch in test_residual_quantizer.py;
TestComponents, TestLocalSearchQuantizer in
test_local_search_quantizer.py.
* Fast scan: TestFastScanFiltering, TestBlockSkipConsistency,
TestFastScanRangeSearchFilter in test_fastscan_filter.py.
* Broader index tests (search-exercising classes only):
TestParameterSpace in test_autotune.py; TestSpectralHash in
test_factory.py; TestMerge1, TestMerge2, TestRemoveFastScan in
test_merge_index.py.
BUCK changes move decorated tests from the legacy-listing lists to the
simd_levels lists (which use supports_static_listing = False, required
for dynamic class name generation), and add the new entries
test_binary_search_params, test_fastscan_filter, test_refine_panorama,
test_hnsw_panorama.
___
overriding_review_checks_triggers_an_audit_and_retroactive_review
Oncall Short Name: fair_umami_cluster
Differential Revision: D101822335
fbshipit-source-id: 9a432c6d6bee201c3731713226405a8c8ecebbe6
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5022
I used the C++ benchmark in https://github.com/facebookresearch/faiss/pull/4971 but modified it a lot to measure on my machine.
```
The BLAS threshold for flat distance computation was a fixed query count (nq < 20), regardless of vector dimension. This meant BLAS was
used for as few as 20 queries even at d=128, where the sequential SIMD path is 10-25x faster.
The optimal crossover between sequential and BLAS depends on the total work in the query matrix (nq × d), not just query count.
Benchmarking across dimensions shows the crossover at roughly nq × d ≈ 128,000:
┌──────┬────────────────────┬──────────────────────────────┐
│ d │ Old threshold (nq) │ New effective threshold (nq) │
├──────┼────────────────────┼──────────────────────────────┤
│ 128 │ 20 │ 1000 │
├──────┼────────────────────┼──────────────────────────────┤
│ 256 │ 20 │ 500 │
├──────┼────────────────────┼──────────────────────────────┤
│ 512 │ 20 │ 250 │
├──────┼────────────────────┼──────────────────────────────┤
│ 1024 │ 20 │ 125 │
├──────┼────────────────────┼──────────────────────────────┤
│ 2048 │ 20 │ 63 │
└──────┴────────────────────┴──────────────────────────────┘
This change replaces the comparison nq < threshold with nq * d < threshold and sets the default to 128,000.
Speedup vs old default (nb=100,000, L2 (same as IP for me), compiled with optimizations):
nq | d=128 | d=256 | d=512 | d=1024 | d=2048
----|-------|-------|-------|--------|-------
20 | 22.8x | 9.3x | 4.5x | 2.6x | 1.4x
50 | 19.4x | 9.3x | 4.7x | 2.0x | 1.2x
100 | 13.3x | 5.6x | 2.1x | 1.0x | 1.0x
200 | 8.2x | 2.7x | 1.1x | 1.0x | 1.0x
500 | 3.2x | 1.0x | 1.0x | 1.0x | 1.0x
1000 | 1.0x | 1.0x | 1.0x | 1.0x | 1.0x
No regressions observed — the worst case is d=1024, nq=100 at 0.99x (within noise).
```
Reviewed By: mdouze
Differential Revision: D99032435
fbshipit-source-id: 45153e1d5add3ab20efa0e1e90cfc18533f4ac97
Summary:
This PR adds `IndexFlatL2Panorama`, integrating Panorama (as specified in the [paper](https://arxiv.org/abs/2510.00566)) into `IndexFlatL2`. This is the first step in creating an [`IndexRefinePanorama`](https://github.com/aknayar/faiss-pano/compare/aknayar:faiss-pano:l2flat-pano...aknayar:faiss-pano:refine-pano), which will use `IndexFlatL2Panorama` (or an `IndexPreTransform` with an `IndexFlatL2Panorama`) as its `refine_index`.
## Refactoring
Since the bulk of Panorama's refinement logic would be duplicated between `IndexFlatL2Panorama` and `IndexIVFFlatPanorama`, it has been factored out into a new `Panorama` struct. This struct contains key parameters (`batch_size`, `d`, etc.) and the following utility functions:
- `copy_codes_to_level_layout`: Writes new vectors to `codes` following Panorama's storage layout
- `compute_cumulative_sums`: Computes the cumulative sums for new vectors
- `compute_query_cum_sums`: Computes the cumulative sums for a new query
- `progressive_filter_batch`: Performs Panorama refinement on a batch of vectors
These utilities will be shared by most Panorama indexes, which is why I have refactored them into their own utility.
## IndexRefinePanorama
While the `IndexFlatL2Panorama` implemented in this PR technically contains all the functionality needed to implement `IndexRefinePanorama` (performing `search` on a subset of indices), it is not ready to be used as a `refine_index`. The current implementation is not optimized for the case of `IndexRefine`, where we perform search on a very small subset of the datapoints. This leads to vastly scattered memory accesses during the `search`, to the point where the overhead of maintaining `active_indices` and `exact_distances` can thwart Panorama's speedups.
As such, to optimize for `IndexRefine` we will need a standalone implementation of `search_subset` which instead does the following:
1. Iterate over the subset of indices (rather than batches of codes)
2. For each index `i`, compute its distance alone by Panorama refinement (essentially having `batch_size` = 1. In fact, for this very reason I have made `batch_size` a parameter in the constructor—`IndexRefine` will require it to be 1 due to noncontiguous memory accesses, but typical workloads would benefit from 128-1024.)
This will unfortunately mean we cannot reuse the search utilities in the `Panorama` struct in this specific case, but will allow us to squeeze 2-5x speedups during the reordering phase of `IndexRefine`.
## Testing
1. Unit tests can be found in `tests/test_flat_l2_panorama.py`
2. A benchmark can be found in `benchs/bench_flat_l2_panorama.py`, yielding the following results:
```
======Flat
Recall@10: 0.980000, speed: 263.214254 ms/query, dims scanned: 100.00%
======PCA960,FlatL2Panorama8_512
Recall@10: 0.980000, speed: 37.080264 ms/query, dims scanned: 12.62%
```
The recall being less than 1.0 is perhaps due to discrepancies between faiss results and the `ground_truth` values.
<img width="632" height="472" alt="bench_flat_l2_panorama" src="https://github.com/user-attachments/assets/57b44fbb-67c3-447e-8532-d13bf28ac7e0" />
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4645
Reviewed By: limqiying
Differential Revision: D86234773
Pulled By: mnorris11
fbshipit-source-id: eda5b654f2657162488511c7742ca0b1456965f6
Summary:
# Panorama: Fast-Track Nearest Neighbors for IVFFlat
This PR integrates [Panorama](https://arxiv.org/abs/2510.00566) into Faiss' `IndexIVFFlat`, as a new index called `IndexIVFFlatPanorama`.
## What is Panorama?
Panorama is a machine learning-driven approach that accelerates the verification/refinement bottleneck in Approximate Nearest Neighbor Search (ANNS) through learned orthogonal transforms and incremental distance computation. It uses data-adaptive transforms that concentrate over 90% of signal energy into the first half of dimensions, enabling early candidate pruning with partial distance computations.
## How it benefits IVFFlat
Panorama addresses a critical issue: in modern high-dimensional neural embeddings, the refinement phase accounts for 75-99% of query latency. By incrementally computing distances and pruning candidates whose lower bound exceeds the running threshold, Panorama dramatically reduces wasted computation.
The integration uses a level-major memory layout that processes candidates in batches, improving cache locality and reducing branch mispredictions. This reorganization groups vectors into batches and processes them level-by-level rather than vector-by-vector, consolidating pruning decisions and regularizing control flow.
## Expected speedups
On IVFFlat specifically, Panorama achieves dramatic speedups of **5-20×** across diverse datasets with **no recall loss**, thanks to the contiguous memory access patterns and efficient SIMD utilization.
The following graph is generated by running the demo in the PR:
<img width="777" height="435" alt="image" src="https://github.com/user-attachments/assets/9cfe427f-9daa-42af-a7bf-4ab88705f030" />
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4606
Reviewed By: subhadeepkaran
Differential Revision: D84715268
Pulled By: mnorris11
fbshipit-source-id: fc167e99d591b34354decce26f8b6582d80ab2b6
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4541
Per PEP 8 style guide (https://pep8.org/#blank-lines), top-level class
definitions should be surrounded by two blank lines. This commit addresses
\E302 lint violations across the faiss codebase by ensuring all class
definitions have exactly 2 blank lines before them.
Changes:
- Fixed \E302 errors in 28 Python files across tests, benchmarks, contrib,
and GPU modules
- Applied consistent PEP 8 formatting for class definitions
- No functional changes - formatting only
Files affected include test files, benchmark scripts, contrib modules,
and GPU test utilities. All changes maintain existing functionality
while improving code style compliance.
Reviewed By: junjieqi
Differential Revision: D80682723
fbshipit-source-id: 6ad5458c3bf1e5c06f35dc8fcdbea2ac4ba83c5f
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4075
`TestScalarQuantizer.test_4variants_ivf` shouldn't mix IVF probing misses in with its evaluation. As is, it probes 4/64 centroids, so FP16 has only 73% recall. This fixes it to *still exercise residual encoding* and the resulting distributions, but exhaustively scan the index.
Reviewed By: junjieqi
Differential Revision: D66909687
fbshipit-source-id: f4ec32b59fe7885415489f82e6a17ce03eb10916
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3809
test_IndexIVFRQ is failing nightly GPU w/RAFT builds. These are false positive failures for the edge cases when the distance of a query vector to two candidate vectors is identical. In such cases, the search and search_and_reconstruct return these candidate vectors in a different order (on GPU w/Raft).
Current fix is to ignore the order of such ids with identical distances by sorting on distance and use id as tiebreaker. There is negligible performance implication (5ms extra), given the test candidate size is low.
Reviewed By: mengdilin, ramilbakhshyiev
Differential Revision: D61977915
fbshipit-source-id: 5f7a81c51c91a967013fb5e69e2bfee59be341c7
Summary:
mdouze Please let me know if any additional unit tests are needed
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3444
Reviewed By: algoriddle
Differential Revision: D57665641
Pulled By: mdouze
fbshipit-source-id: 9bec91306a1c31ea4f1f1d726c9d60ac6415fdfc
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3455
Code quality control by reducing the number of prints
Reviewed By: junjieqi
Differential Revision: D57502194
fbshipit-source-id: a6cd65ed4cc49590ce73d2978d41b640b5259c17
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3190
This diff adds more result handlers in order to expose them externally.
This enables range search for HSNW and Fast Scan, and nprobe parameter support for FastScan.
Reviewed By: pemazare
Differential Revision: D52547384
fbshipit-source-id: 271da5ffea6411df3d8e50641abade18bd7b774b
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/2986
A NaN vector is a vector with at least one NaN (not-a-number) entry.
After discussion in the Faiss team we decided that:
- training should throw an exception on NaN vectors
- added NaN vectors should be ignored (never returned)
- searched NaN vectors should return only -1s
This diff implements this for a few common index types + adds relevant tests.
Reviewed By: algoriddle
Differential Revision: D48031390
fbshipit-source-id: 99e7786582e91950e3a53c1d8bcffdd00b6afd24
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/2860
Optimized range search function where the GPU computes by default and falls back on gpu for queries where there are too many results.
Parallelize the CPU to GPU cloning, it seems to work.
Support range_search_preassigned in Python
Fix long-standing issue with SWIG exposed functions that did not release the GIL (in particular the MapLong2Long).
Adds a MapInt64ToInt64 that is more efficient than MapLong2Long.
Reviewed By: algoriddle
Differential Revision: D45672301
fbshipit-source-id: 2e77397c40083818584dbafa5427149359a2abfd
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/2618
The Faiss tests run in dev mode are very slow
The PQ polysemous training is particularly sensitive to this with the default settings.
This diff adds a "np" suffix to two PQ factory strings to disable polysemous training. The tests that are detected as flaky because they occasionally time out.
Reviewed By: alexanderguzhva
Differential Revision: D41955699
fbshipit-source-id: b1e0382a0142a3ed28b498c5ea6f5499de2c1b3f
Summary:
Adds:
- a sparse update function to the heaps
- bucket sort functions
- an IndexRandom index to serve as a dummy coarse quantizer for testing
Reviewed By: algoriddle
Differential Revision: D41804055
fbshipit-source-id: 9402b31c37c367aa8554271d8c88bc93cc1e2bda
Summary:
IndexHNSW has a deadlock in the add() method, which is fixed by
temporarily releasing the lock on the current element while updating
its neighbors' adjacency lists.
This bug concerns multi-threaded insertion only, and seems to manifest
itself only with certain OpenMP configurations.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/2143
Reviewed By: mdouze
Differential Revision: D32919041
Pulled By: beauby
fbshipit-source-id: e515541c1b22bfcb79d29c0bde1843e63f5175fb
Summary:
The results returned by `NSG::search` are already sorted. Calling `maxheap_reorder` will make the results unorder.
Fixed https://github.com/facebookresearch/faiss/issues/2081.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/2086
Test Plan: buck test //faiss/tests/:test_index -- test_order
Reviewed By: beauby
Differential Revision: D32593924
Pulled By: mdouze
fbshipit-source-id: 794b94681610657bd2f305f7e3d6cd5d25c6bdba
Summary:
This diff fixes a serious bug in the range search implementation.
During range search in a flat index, (exhaustive_L2sqr_seq and exhaustive_inner_product_seq) when running in multiple threads, the per-thread results are collected into RangeSearchPartialResult structures.
When the computation is finished, they are aggregated into a RangeSearchResult. In the previous version of the code, this loop was nested into a second loop that is used to check for KeyboardInterrupts. Thus, at each iteration, the results were overwritten.
The fix removes the outer loop. It is most likely useless anyways because the sequential code is called only for a small number of queries, for a larger number the BLAS version is used.
Reviewed By: wickedfoo
Differential Revision: D28486415
fbshipit-source-id: 89a52b17f6ca1ef68fc5e758f0e5a44d0df9fe38
Summary:
## Description:
This diff implemented Navigating Spreading-out Graph (NSG) which accepts a KNN graph as input.
Here is the interface of building an NSG graph:
``` c++
void IndexNSG::build(idx_t n, const float *x, idx_t *knn_graph, int GK);
```
where `GK` is the nb of neighbors per node and `knn_graph[i * GK + j]` is the j-th neighbor of node i.
The `add` method is not implemented yet.
The unit tests could be found in `tests/test_nsg.cpp`.
mdouze beauby Maybe I need some advice on how to design the interface and support python.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/1707
Test Plan: buck test //faiss/tests/:test_index -- TestNSG
Reviewed By: beauby
Differential Revision: D26748498
Pulled By: mdouze
fbshipit-source-id: 3280f705fb1b5f9c8cc5efeba63b904c3b832544
Summary: Checking for invalid parameters (number of nearest neighbors and number of probes where applicable) in the indices and throwing. Along with unit tests.
Reviewed By: wickedfoo
Differential Revision: D26582467
fbshipit-source-id: e345635d2f0f44ddcecc3f3314b2b9113359a787
Summary:
This diff streamlines the code that collects results for brute force distance computations for the L2 / IP and range search / knn search combinations.
It introduces a `ResultHandler` template class that abstracts what happens with the computed distances and ids. In addition to the heap result handler and the range search result handler, it introduces a reservoir result handler that improves the search speed for large k (>=100).
Benchmark results (https://fb.quip.com/y0g1ACLEqJXx#OCaACA2Gm45) show that on small datasets (10k) search is 10-50% faster (improvements are larger for small k). There is room for improvement in the reservoir implementation, whose implementation is quite naive currently, but the diff is already useful in its current form.
Experiments on precomputed db vector norms for L2 distance computations were not very concluding performance-wise, so the implementation is removed from IndexFlatL2.
This diff also removes IndexL2BaseShift, which was never used.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/1502
Test Plan:
```
buck test //faiss/tests/:test_product_quantizer
buck test //faiss/tests/:test_index -- TestIndexFlat
```
Reviewed By: wickedfoo
Differential Revision: D24705464
Pulled By: mdouze
fbshipit-source-id: 270e10b19f3c89ed7b607ec30549aca0ac5027fe
Summary:
This diff fixes https://github.com/facebookresearch/faiss/issues/1412
There were various inconsistencies in how the shard and replica wrappers updated their internal state as the sub-indices were updated. This makes the two container classes work in the same way with similar synchronization functionality.
Reviewed By: beauby
Differential Revision: D23974186
fbshipit-source-id: c688c0c9124f823e4239aa2ff617b007b4564859
Summary:
`long` is 32 bits on windows and so is the default int type for numpy (eg. the one used for `np.arange`).
This diff explicitly specifies 64-bit ints for all occurrences where it matters.
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/1381
Reviewed By: wickedfoo
Differential Revision: D23371232
Pulled By: mdouze
fbshipit-source-id: 220262cd70ee70379f83de93561a4eae71c94b04
Changelog:
- changed license: BSD+Patents -> MIT
- propagates exceptions raised in sub-indexes of IndexShards and IndexReplicas
- support for searching several inverted lists in parallel (parallel_mode != 0)
- better support for PQ codes where nbit != 8 or 16
- IVFSpectralHash implementation: spectral hash codes inside an IVF
- 6-bit per component scalar quantizer (4 and 8 bit were already supported)
- combinations of inverted lists: HStackInvertedLists and VStackInvertedLists
- configurable number of threads for OnDiskInvertedLists prefetching (including 0=no prefetch)
- more test and demo code compatible with Python 3 (print with parentheses)
- refactored benchmark code: data loading is now in a single file
Facebook sync (Mar 2019)
- MatrixStats object
- option to round coordinates during k-means optimization
- alternative option for search in HNSW
- moved stats and imbalance_factor of IndexIVF to InvertedLists object
- range search for IVFScalarQuantizer
- direct unit8 codec in ScalarQuantizer
- renamed IndexProxy to IndexReplicas and moved to main Faiss
- better support for PQ code assignment with external index
- support for IMI2x16 (4B virtual centroids!)
- support for k = 2048 search on GPU (instead of 1024)
- most CUDA mem alloc failures throw exceptions instead of terminating on an assertion
- support for renaming an ondisk invertedlists
- interrupt computations with ctrl-C in python
tandede