File utils.h

namespace faiss

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree.

Throughout the library, vectors are provided as float * pointers. Most algorithms can be optimized when several vectors are processed (added/searched) together in a batch. In this case, they are passed in as a matrix. When n vectors of size d are provided as float * x, component j of vector i is

x[ i * d + j ]

where 0 <= i < n and 0 <= j < d. In other words, matrices are always compact. When specifying the size of the matrix, we call it an n*d matrix, which implies a row-major storage.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. I/O functions can read/write to a filename, a file handle or to an object that abstracts the medium.

The read functions return objects that should be deallocated with delete. All references within these objectes are owned by the object.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Definition of inverted lists + a few common classes that implement the interface.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Since IVF (inverted file) indexes are of so much use for large-scale use cases, we group a few functions related to them in this small library. Most functions work both on IndexIVFs and IndexIVFs embedded within an IndexPreTransform.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. In this file are the implementations of extra metrics beyond L2 and inner product

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Defines a few objects that apply transformations to a set of vectors Often these are pre-processing steps.

Functions

std::string get_compile_options()

get compile options

double getmillisecs()

ms elapsed since some arbitrary epoch

size_t get_mem_usage_kb()

get current RSS usage in kB

uint64_t get_cycles()
void fvec_madd(size_t n, const float *a, float bf, const float *b, float *c)

compute c := a + bf * b for a, b and c tables

Parameters
  • n – size of the tables

  • a – size n

  • b – size n

  • c – restult table, size n

int fvec_madd_and_argmin(size_t n, const float *a, float bf, const float *b, float *c)

same as fvec_madd, also return index of the min of the result table

Returns

index of the min of table c

void reflection(const float *u, float *x, size_t n, size_t d, size_t nu)
void matrix_qr(int m, int n, float *a)

compute the Q of the QR decomposition for m > n

Parameters

a – size n * m: input matrix and output Q

void ranklist_handle_ties(int k, int64_t *idx, const float *dis)

distances are supposed to be sorted. Sorts indices with same distance

size_t ranklist_intersection_size(size_t k1, const int64_t *v1, size_t k2, const int64_t *v2)

count the number of common elements between v1 and v2 algorithm = sorting + bissection to avoid double-counting duplicates

size_t merge_result_table_with(size_t n, size_t k, int64_t *I0, float *D0, const int64_t *I1, const float *D1, bool keep_min = true, int64_t translation = 0)

merge a result table into another one

Parameters
  • I0, D0 – first result table, size (n, k)

  • I1, D1 – second result table, size (n, k)

  • keep_min – if true, keep min values, otherwise keep max

  • translation – add this value to all I1’s indexes

Returns

nb of values that were taken from the second table

double imbalance_factor(int n, int k, const int64_t *assign)

a balanced assignment has a IF of 1

double imbalance_factor(int k, const int *hist)

same, takes a histogram as input

void fvec_argsort(size_t n, const float *vals, size_t *perm)
void fvec_argsort_parallel(size_t n, const float *vals, size_t *perm)
int ivec_hist(size_t n, const int *v, int vmax, int *hist)

compute histogram on v

void bincode_hist(size_t n, size_t nbits, const uint8_t *codes, int *hist)

Compute histogram of bits on a code array

Parameters
  • codes – size(n, nbits / 8)

  • hist – size(nbits): nb of 1s in the array of codes

size_t ivec_checksum(size_t n, const int *a)

compute a checksum on a table.

const float *fvecs_maybe_subsample(size_t d, size_t *n, size_t nmax, const float *x, bool verbose = false, int64_t seed = 1234)

random subsamples a set of vectors if there are too many of them

Parameters
  • d – dimension of the vectors

  • n – on input: nb of input vectors, output: nb of output vectors

  • nmax – max nb of vectors to keep

  • x – input array, size *n-by-d

  • seed – random seed to use for sampling

Returns

x or an array allocated with new [] with *n vectors

void binary_to_real(size_t d, const uint8_t *x_in, float *x_out)

Convert binary vector to +1/-1 valued float vector.

Parameters
  • d – dimension of the vector (multiple of 8)

  • x_in – input binary vector (uint8_t table of size d / 8)

  • x_out – output float vector (float table of size d)

void real_to_binary(size_t d, const float *x_in, uint8_t *x_out)

Convert float vector to binary vector. Components > 0 are converted to 1, others to 0.

Parameters
  • d – dimension of the vector (multiple of 8)

  • x_in – input float vector (float table of size d)

  • x_out – output binary vector (uint8_t table of size d / 8)

uint64_t hash_bytes(const uint8_t *bytes, int64_t n)

A reasonable hashing function

bool check_openmp()

Whether OpenMP annotations were respected.