facebookresearch/faiss
1
0
Fork 0
mirror of https://github.com/facebookresearch/faiss.git synced 2026-10-12 02:13:36 +00:00
Code Issues Packages Projects Releases Wiki Activity
2,354 Commits 268 Branches 33 Tags
main
Commit Graph
14 Commits
Author SHA1 Message Date
Tia Lim 0f0f728166 Format faiss Python files with black (line length 80) (#5349) 
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
 2026-06-29 17:29:05 -07:00
Mulugeta Mammo c000190dc0 Accelerate ScalarQuantizer::QT_bf16 with AVX512-BF16. (#4889) 
Summary:
This PR accelerates `ScalarQuantizer::QT_bf16` by vectorizing the BF16 encode/decode path with AVX-512 BF16 and integer instructions, targeting Intel® Sapphire Rapids and newer processors.

Distance computations are also optimized to operate directly on BF16 data, avoiding the overhead of FP32 conversion:
- **Inner product:** The query is encoded to BF16 once, and dot products are computed natively in BF16.
- **L2 distance:** Leverages the norm expansion identity, with all terms evaluated using the native BF16 dot-product instruction.

Scalar quantizer benchmarks demonstrate speedups of **1.42×** for encoding, **1.32×** for decoding, and **1.16×** for distance computation.

 ---

`perf_tests/bench_scalar_quantizer_encode --d=768 --n=2000 --iterations=20 --benchmark_filter="QT_bf16"`

```
Existing impl:
--------------------------------------------------------------------------------
Benchmark                      Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------
QT_bf16/iterations:20     689149 ns       689010 ns           20 code_size=1.536k

This PR:
--------------------------------------------------------------------------------
Benchmark                      Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------
QT_bf16/iterations:20     485337 ns       484511 ns           20 code_size=1.536k
```

`perf_tests/bench_scalar_quantizer_decode --d=768 --n=2000 --iterations=20 --benchmark_filter="QT_bf16"`

```
Existing impl:
--------------------------------------------------------------------------------
Benchmark                      Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------
QT_bf16/iterations:20     498607 ns       498539 ns           20 code_size=1.536k

This PR:
--------------------------------------------------------------------------------
Benchmark                      Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------
QT_bf16/iterations:20     376614 ns       374200 ns           20 code_size=1.536k
```

`perf_tests/bench_scalar_quantizer_distance --d=768 --n=2000 --iterations=20 --benchmark_filter="QT_bf16"`

```
Existing impl:
-----------------------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations UserCounters...
-----------------------------------------------------------------------------------
QT_bf16/L2/iterations:20  254155481 ns    253585062 ns           20 code_size=1.536k
QT_bf16/IP/iterations:20  221556582 ns    221156894 ns           20 code_size=1.536k

This PR:
-----------------------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations UserCounters...
-----------------------------------------------------------------------------------
QT_bf16/L2/iterations:20  226742244 ns    226270273 ns           20 code_size=1.536k
QT_bf16/IP/iterations:20  190916826 ns    190591678 ns           20 code_size=1.536k
```

Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4889

Reviewed By: mdouze

Differential Revision: D106149331

Pulled By: mnorris11

fbshipit-source-id: 114097d0597028c43c19727b677dcc494250be41
 2026-06-02 13:50:33 -07:00
Tom Jackson a3a7627009 VisitedTable -> unordered_set if ntotal is large (#4735) 
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4735

`VisitedTable` accounts for a huge portion of `HNSW::search()` for unbatched searches of large indices.

As demonstrated in the benchmarks shown below, the vector-based implementation is much faster for smaller `ntotal` values, but at ~2M and above, it becomes slower, often significantly so. E.g.: At 64M slots, without batching, a workload of 1000 `set()`/`get()`s is >100x slower. Even with batching, this workload is still 3x slower with vectors.

This is a very likely explanation for the poor performance of HNSW in a 2023 USearch blog post (https://www.unum.cloud/blog/2023-11-07-scaling-vector-search-with-intel), which shows the same high throughput below 1M docs, and the same O(n) slowdown as the size grows beyond >2M:

Reviewed By: mnorris11, mdouze

Differential Revision: D89515309

fbshipit-source-id: 08bc4a54faa311eeb9946f2a43482ae52b61566e
 2026-02-13 18:10:48 -08:00
ASHIK SHARON M 15a8e228ad Fix build pr 4761 (#4792) 
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4792

Reviewed By: junjieqi

Differential Revision: D92294287

Pulled By: trang-nm-nguyen

fbshipit-source-id: 1fa39a5319527f00214258c4c97bd718025d86ad
 2026-02-05 10:52:06 -08:00
generatedunixname89002005287564 8bb97aa85c Fix CQS signal readability-braces-around-statements in fbcode/faiss/perf_tests (#4458) 
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4458

Reviewed By: dtolnay

Differential Revision: D78955728

fbshipit-source-id: 2d944ea7c5dc7d4f284ecf918fb51859c610926a
 2025-07-25 03:54:59 -07:00
Tia Lim 2954f1f518 Fix CQS signal facebook-unused-include-check in fbcode/faiss/perf_tests (#4443) 
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4443

Reviewed By: pankajsingh88

Differential Revision: D78723469

fbshipit-source-id: 48946614b84bcc789f7d9177b6884f1e4e2ca3de
 2025-07-22 10:32:06 -07:00
Andrew Yooeun Chun 3ad3eec575 cmake: disable installing external documents under docs/faiss (#4406) 
Summary:
Related issue: https://github.com/facebookresearch/faiss/issues/4405

Building and installing faiss with CMake installs documents from `google/benchmark` under `docs/faiss/`.
Turning off the `BENCHMARK_INSTALL_DOCS` ([google/benchmark CMakeList.txt](https://github.com/google/benchmark/blob/main/src/CMakeLists.txt#L191)) option prevents this issue.

Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4406

Reviewed By: junjieqi

Differential Revision: D77176184

Pulled By: limqiying

fbshipit-source-id: 05e0d3e1e6b2e0bf09d92f0822b35be398d0f632
 2025-06-23 16:33:22 -07:00
Mulugeta Mammo 6c046992a7 Fix the order of parameters in bench_scalar_quantizer_distance. (#4159) 
Summary:
I believe the order of the parameters was not intended to be that way. This PR fixes it.

Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4159

Reviewed By: mengdilin

Differential Revision: D69073195

Pulled By: junjieqi

fbshipit-source-id: bfb62aa7536deeda73bee32f2de3cd7a8142bb13
 2025-02-04 09:45:44 -08:00
Nicholas Ormrod eb5e7341a6 facebook-unused-include-check in fbcode/faiss (#4029) 
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/4029

Remove headers flagged by facebook-unused-include-check over fbcode.faiss.

+ format and autodeps

This is a codemod. It was automatically generated and will be landed once it is approved and tests are passing in sandcastle.
You have been added as a reviewer by Sentinel or Butterfly.

Autodiff project: uif
Autodiff partition: fbcode.faiss
Autodiff bookmark: ad.uif.fbcode.faiss

Reviewed By: dtolnay

Differential Revision: D65957849

fbshipit-source-id: f6199250db595defd56f5e7b2828f838702e9a16
 2024-11-15 13:53:46 -08:00
Michael Norris eff0898a13 Enable linting: lint config changes plus arc lint command (#3966) 
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3966

This actually enables the linting.

Manual changes:
- tools/arcanist/lint/fbsource-licenselint-config.toml
- tools/arcanist/lint/fbsource-lint-engine.toml

Automated changes:
`arc lint --apply-patches --take LICENSELINT --paths-cmd 'hg files faiss'`

Reviewed By: asadoughi

Differential Revision: D64484165

fbshipit-source-id: 4f2f6e953c94ef6ebfea8a5ae035ccfbea65ed04
 2024-10-22 09:46:48 -07:00
Alexandr Guzhva 4d78137565 Place a useful cmake function 'link_to_faiss_lib' into a separate file (#3939) 
Summary:
Add `cmake/link_to_faiss_lib.cmake`, which exposes a useful and reusable CMake `link_to_faiss_lib()` function

Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3939

Reviewed By: mnorris11

Differential Revision: D64250261

Pulled By: mengdilin

fbshipit-source-id: bab5b7fab8effb33cb73024eb7eefd2319998e5b
 2024-10-14 14:00:13 -07:00
Mengdi Lin 0df5d24a90 clean up hnsw benchmark (#3901) 
Summary:
Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3901

1) remove system time from benchmark as this metric has extremely high jitter (50-100%) and is not useful for us

2) clean up command-line arguments and define a main function the external world can call

3) tweak default so microbenchmark runs fast by default (this does not the parameters we pass to microbenchmarks for servicelab)

Reviewed By: mnorris11

Differential Revision: D63650110

fbshipit-source-id: efc81563291f00701a0d1df1d27172adeb3ef231
 2024-09-30 19:35:31 -07:00
Facebook Community Bot c8d1474fc5 Re-sync with internal repository (#3885) 
The internal and external repositories are out of sync. This Pull Request attempts to brings them back in sync by patching the GitHub repository. Please carefully review this patch. You must disable ShipIt for your project in order to merge this pull request. DO NOT IMPORT this pull request. Instead, merge it directly on GitHub using the MERGE BUTTON. Re-enable ShipIt after merging.
 2024-09-24 07:49:31 -07:00
mengdilin 149c1f4b3c Add performance regression tests (#3793) 
Summary:
Add `CMakeList` compile `faiss/perf_tests` benchmarks. We will run the google benchmarks as part of CI so people can see benchmarking results (there is no diff-to-diff regression detection in open-sourced CI)

==== Test Plan =====

Sees logs in CI that looks like
```
Run on (4 X 3184.9 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 512 KiB (x2)
  L3 Unified 32768 KiB (x1)
Load Average: 2.69, 2.84, 1.56
----------------------------------------------------------------------------------------------
Benchmark                                    Time             CPU   Iterations UserCounters...
----------------------------------------------------------------------------------------------
QT_4bit/iterations:20                 53646755 ns     53643729 ns           20 code_size=1k
QT_4bit_uniform/iterations:20         52248603 ns     52246874 ns           20 code_size=1k
QT_6bit/iterations:20                 63697930 ns     63693459 ns           20 code_size=1.5k
QT_8bit/iterations:20                 43305175 ns     43303946 ns           20 code_size=2k
QT_8bit_direct/iterations:20          30771920 ns     30770261 ns           20 code_size=2k
QT_8bit_direct_signed/iterations:20   30744625 ns     30742891 ns           20 code_size=2k
QT_8bit_uniform/iterations:20         44227773 ns     44224242 ns           20 code_size=2k
QT_bf16/iterations:20                 32758794 ns     32758717 ns           20 code_size=4k
QT_fp16/iterations:20                 41068848 ns     41066492 ns           20 code_size=4k
2024-09-20T23:15:01+00:00
Running ./build/perf_tests/bench_scalar_quantizer_decode
Run on (4 X 3244.56 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 512 KiB (x2)
  L3 Unified 32768 KiB (x1)
Load Average: 2.43, 2.78, 1.56
----------------------------------------------------------------------------------------------
Benchmark                                    Time             CPU   Iterations UserCounters...
----------------------------------------------------------------------------------------------
QT_4bit/iterations:20                   338300 ns       338284 ns           20 code_size=64
QT_4bit_uniform/iterations:20           332928 ns       332914 ns           20 code_size=64
QT_6bit/iterations:20                   4[1568](https://github.com/facebookresearch/faiss/actions/runs/10966335129/job/30454475438?pr=3878#step:3:1585)3 ns       415674 ns           20 code_size=96
QT_8bit/iterations:20                   266034 ns       266026 ns           20 code_size=128
QT_8bit_direct/iterations:20             37552 ns        37553 ns           20 code_size=128
QT_8bit_direct_signed/iterations:20      39701 ns        39696 ns           20 code_size=128
QT_8bit_uniform/iterations:20           261535 ns       261529 ns           20 code_size=128
QT_bf16/iterations:20                    45518 ns        45506 ns           20 code_size=256
QT_fp16/iterations:20                   334602 ns       334584 ns           20 code_size=256
2024-09-20T23:15:02+00:00
Running ./build/perf_tests/bench_no_multithreading_rcq_search
Run on (4 X 3243.03 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 512 KiB (x2)
  L3 Unified 32768 KiB (x1)
Load Average: 2.43, 2.78, 1.56
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
WARNING clustering 65536 points to 65536 centroids: please provide at least 2555904 training points
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
search/iterations:20   12763792 ns     10367188 ns           20
2024-09-20T23:15:51+00:00
Running ./build/perf_tests/bench_scalar_quantizer_accuracy
Run on (4 X 3231.04 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 512 KiB (x2)
  L3 Unified 32768 KiB (x1)
Load Average: 2.85, 2.84, 1.65
----------------------------------------------------------------------------------------------
Benchmark                                    Time             CPU   Iterations UserCounters...
----------------------------------------------------------------------------------------------
QT_4bit/iterations:20                    0.000 ns        0.000 ns            0 code_size=64 code_size_two=128k ndiff_for_idempotence=0 sql2_recons_error=0.047396
QT_4bit_uniform/iterations:20            0.000 ns        0.000 ns            0 code_size=64 code_size_two=128k ndiff_for_idempotence=0 sql2_recons_error=0.0473931
QT_6bit/iterations:20                    0.000 ns        0.000 ns            0 code_size=96 code_size_two=192k ndiff_for_idempotence=0 sql2_recons_error=2.6899m
QT_8bit/iterations:20                    0.000 ns        0.000 ns            0 code_size=128 code_size_two=256k ndiff_for_idempotence=0 sql2_recons_error=164.317u
QT_8bit_direct/iterations:20             0.000 ns        0.000 ns            0 code_size=128 code_size_two=256k ndiff_for_idempotence=0 sql2_recons_error=42.5514
QT_8bit_direct_signed/iterations:20      0.000 ns        0.000 ns            0 code_size=128 code_size_two=256k ndiff_for_idempotence=0 sql2_recons_error=42.5494
QT_8bit_uniform/iterations:20            0.000 ns        0.000 ns            0 code_size=128 code_size_two=256k ndiff_for_idempotence=0 sql2_recons_error=164.152u
QT_bf16/iterations:20                    0.000 ns        0.000 ns            0 code_size=256 code_size_two=512k ndiff_for_idempotence=0 sql2_recons_error=92.8328u
QT_fp16/iterations:20                    0.000 ns        0.000 ns            0 code_size=256 code_size_two=512k ndiff_for_idempotence=0 sql2_recons_error=1.44838u
2024-09-20T23:15:51+00:00
Running ./build/perf_tests/bench_scalar_quantizer_encode
Run on (4 X 3243.72 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x2)
  L1 Instruction 32 KiB (x2)
  L2 Unified 512 KiB (x2)
  L3 Unified 32768 KiB (x1)
Load Average: 2.85, 2.84, 1.65
----------------------------------------------------------------------------------------------
Benchmark                                    Time             CPU   Iterations UserCounters...
----------------------------------------------------------------------------------------------
QT_4bit/iterations:20                   702046 ns       701319 ns           20 code_size=64
QT_4bit_uniform/iterations:20           595889 ns       595880 ns           20 code_size=64
QT_6bit/iterations:20                  1287503 ns      1287542 ns           20 code_size=96
QT_8bit/iterations:20                   511811 ns       511804 ns           20 code_size=128
QT_8bit_direct/iterations:20            152977 ns       152970 ns           20 code_size=128
QT_8bit_direct_signed/iterations:20     185578 ns       185572 ns           20 code_size=128
QT_8bit_uniform/iterations:20           454412 ns       454408 ns           20 code_size=128
QT_bf16/iterations:20                    51331 ns        51324 ns           20 code_size=256
QT_fp16/iterations:20                   390658 ns       390649 ns           20 code_size=256
```

Pull Request resolved: https://github.com/facebookresearch/faiss/pull/3793

Reviewed By: junjieqi

Differential Revision: D63147599

Pulled By: mengdilin

fbshipit-source-id: 03165b5acb3b0647a69f7db144ab76efda2fee11
 2024-09-23 15:58:31 -07:00