mirror of
https://github.com/facebookresearch/faiss.git
synced 2026-10-11 22:50:00 +00:00
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
110 lines
3.1 KiB
C
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
|