Struct faiss::BlockInvertedLists
-
struct faiss::BlockInvertedLists : public faiss::InvertedLists
Inverted Lists that are organized by blocks.
Different from the regular inverted lists, the codes are organized by blocks of size block_size bytes that reprsent a set of n_per_block. Therefore, code allocations are always rounded up to block_size bytes. The codes are also aligned on 32-byte boundaries for use with SIMD.
To avoid misinterpretations, the code_size is set to (size_t)(-1), even if arguably the amount of memory consumed by code is block_size / n_per_block.
The writing functions add_entries and update_entries operate on block-aligned data.
Public Functions
-
BlockInvertedLists(size_t nlist, size_t vec_per_block, size_t block_size)
-
BlockInvertedLists()
-
virtual size_t list_size(size_t list_no) const override
get the size of a list
-
virtual const uint8_t *get_codes(size_t list_no) const override
get the codes for an inverted list must be released by release_codes
- Returns
codes size list_size * code_size
-
virtual const idx_t *get_ids(size_t list_no) const override
get the ids for an inverted list must be released by release_ids
- Returns
ids size list_size
-
size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
-
void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
not implemented
-
virtual void resize(size_t list_no, size_t new_size) override
-
~BlockInvertedLists() override
-
virtual void release_codes(size_t list_no, const uint8_t *codes) const
release codes returned by get_codes (default implementation is nop
-
virtual void release_ids(size_t list_no, const idx_t *ids) const
release ids returned by get_ids
-
virtual idx_t get_single_id(size_t list_no, size_t offset) const
- Returns
a single id in an inverted list
-
virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const
- Returns
a single code in an inverted list (should be deallocated with release_codes)
-
virtual void prefetch_lists(const idx_t *list_nos, int nlist) const
prepare the following lists (default does nothing) a list can be -1 hence the signed long
-
virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)
add one entry to an inverted list
-
virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
-
virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
-
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
-
virtual void reset()
-
void merge_from(InvertedLists *oivf, size_t add_id)
move all entries from oivf (empty on output)
-
double imbalance_factor() const
1= perfectly balanced, >1: imbalanced
-
void print_stats() const
display some stats about the inverted lists
-
size_t compute_ntotal() const
sum up list sizes
Public Members
-
size_t n_per_block
-
size_t block_size
-
std::vector<AlignedTable<uint8_t>> codes
-
std::vector<std::vector<idx_t>> ids
-
size_t nlist
number of possible key values
-
size_t code_size
code size per vector in bytes
Public Static Attributes
-
static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)
used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless
-
BlockInvertedLists(size_t nlist, size_t vec_per_block, size_t block_size)