Files
Michael Norris 8d8881ee3f Make distance_compute_blas_threshold dimension-aware (#5022)
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
2026-04-04 10:02:07 -07:00

110 lines
3.1 KiB
C

/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/
// -*- c -*-
#ifndef FAISS_DISTANCES_C_H
#define FAISS_DISTANCES_C_H
#include <stdint.h>
#include <stdlib.h>
#ifdef __cplusplus
extern "C" {
#endif
/*********************************************************
* Optimized distance/norm/inner prod computations
*********************************************************/
/// Compute pairwise distances between sets of vectors
void faiss_pairwise_L2sqr(
int64_t d,
int64_t nq,
const float* xq,
int64_t nb,
const float* xb,
float* dis,
int64_t ldq,
int64_t ldb,
int64_t ldd);
/// Compute pairwise distances between sets of vectors
/// arguments from "faiss_pairwise_L2sqr"
/// ldq equal -1 by default
/// ldb equal -1 by default
/// ldd equal -1 by default
void faiss_pairwise_L2sqr_with_defaults(
int64_t d,
int64_t nq,
const float* xq,
int64_t nb,
const float* xb,
float* dis);
/// compute the inner product between nx vectors x and one y
void faiss_fvec_inner_products_ny(
float* ip, /* output inner product */
const float* x,
const float* y,
size_t d,
size_t ny);
/// compute ny square L2 distance between x and a set of contiguous y vectors
void faiss_fvec_L2sqr_ny(
float* dis,
const float* x,
const float* y,
size_t d,
size_t ny);
/// squared norm of a vector
float faiss_fvec_norm_L2sqr(const float* x, size_t d);
/// compute the L2 norms for a set of vectors
void faiss_fvec_norms_L2(float* norms, const float* x, size_t d, size_t nx);
/// same as fvec_norms_L2, but computes squared norms
void faiss_fvec_norms_L2sqr(float* norms, const float* x, size_t d, size_t nx);
/// L2-renormalize a set of vector. Nothing done if the vector is 0-normed
void faiss_fvec_renorm_L2(size_t d, size_t nx, float* x);
/// Setter of threshold value on nx * d above which we switch to BLAS to compute
/// distances
void faiss_set_distance_compute_blas_threshold(int value);
/// Getter of threshold value on nx * d above which we switch to BLAS to compute
/// distances
int faiss_get_distance_compute_blas_threshold();
/// Setter of block sizes value for BLAS distance computations
void faiss_set_distance_compute_blas_query_bs(int value);
/// Getter of block sizes value for BLAS distance computations
int faiss_get_distance_compute_blas_query_bs();
/// Setter of block sizes value for BLAS distance computations
void faiss_set_distance_compute_blas_database_bs(int value);
/// Getter of block sizes value for BLAS distance computations
int faiss_get_distance_compute_blas_database_bs();
/// Setter of number of results we switch to a reservoir to collect results
/// rather than a heap
void faiss_set_distance_compute_min_k_reservoir(int value);
/// Getter of number of results we switch to a reservoir to collect results
/// rather than a heap
int faiss_get_distance_compute_min_k_reservoir();
#ifdef __cplusplus
}
#endif
#endif