Faiss

- Main Page
- Namespaces
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
Classes | Public Member Functions | Public Attributes | List of all members
faiss::OnDiskInvertedLists Struct Reference

`#include <OnDiskInvertedLists.h>`

Inheritance diagram for faiss::OnDiskInvertedLists:

## Classes
struct | List
struct | OngoingPrefetch
struct | Slot

## Public Member Functions
| OnDiskInvertedLists (size_t nlist, size_t code_size, const char *filename)
| are inverted lists mapped read-only
size_t | list_size (size_t list_no) const override
| get the size of a list
const uint8_t * | get_codes (size_t list_no) const override
const idx_t * | get_ids (size_t list_no) const override
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
void | resize (size_t list_no, size_t new_size) override
size_t | merge_from (const InvertedLists **ils, int n_il, bool verbose=false)
void | crop_invlists (size_t l0, size_t l1)
| restrict the inverted lists to l0:l1 without touching the mmapped region
void | prefetch_lists (const idx_t *list_nos, int nlist) const override
void | do_mmap ()
void | update_totsize (size_t new_totsize)
void | resize_locked (size_t list_no, size_t new_size)
size_t | allocate_slot (size_t capacity)
void | free_slot (size_t offset, size_t capacity)
Public Member Functions inherited from faiss::InvertedLists
| InvertedLists (size_t nlist, size_t code_size)
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
virtual const uint8_t * | get_single_code (size_t list_no, size_t offset) const
virtual size_t | add_entry (size_t list_no, idx_t theid, const uint8_t *code)
| add one entry to an inverted list
virtual void | update_entry (size_t list_no, size_t offset, idx_t id, const uint8_t *code)
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 Attributes
std::vector< List > | lists
std::list< Slot > | slots
std::string | filename
size_t | totsize
uint8_t * | ptr
bool | read_only
LockLevels * | locks
OngoingPrefetch * | pf
int | prefetch_nthread
Public Attributes inherited from faiss::InvertedLists
size_t | nlist
| number of possible key values
size_t | code_size
| code size per vector in bytes

## Additional Inherited Members
Public Types inherited from faiss::InvertedLists
typedef Index::idx_t | idx_t

## Detailed Description

On-disk storage of inverted lists.

The data is stored in a mmapped chunk of memory (base ptointer ptr, size totsize). Each list is a range of memory that contains (object List) that contains:

- uint8_t codes[capacity * code_size]
- followed by idx_t ids[capacity]

in each of the arrays, the size <= capacity first elements are used, the rest is not initialized.

Addition and resize are supported by:

- roundind up the capacity of the lists to a power of two
- maintaining a list of empty slots, sorted by size.
- resizing the mmapped block is adjusted as needed.

An OnDiskInvertedLists is compact if the size == capacity for all lists and there are no available slots.

Addition to the invlists is slow. For incremental add it is better to use a default ArrayInvertedLists object and convert it to an OnDisk with merge_from.

When it is known that a set of lists will be accessed, it is useful to call prefetch_lists, that launches a set of threads to read the lists in parallel.

Definition at line 51 of file OnDiskInvertedLists.h.

## Member Function Documentation

const uint8_t * faiss::OnDiskInvertedLists::get_codes | ( | size_t | list_no | ) | const
| override virtual

get the codes for an inverted list must be released by release_codes

Returns
  codes size list_size * code_size

Implements faiss::InvertedLists.

Definition at line 404 of file OnDiskInvertedLists.cpp.

const Index::idx_t * faiss::OnDiskInvertedLists::get_ids | ( | size_t | list_no | ) | const
| override virtual

get the ids for an inverted list must be released by release_ids

Returns
  ids size list_size

Implements faiss::InvertedLists.

Definition at line 413 of file OnDiskInvertedLists.cpp.

void faiss::OnDiskInvertedLists::prefetch_lists | ( | const idx_t * | list_nos,
|  | int | nlist
| ) |  | const
| override virtual

prepare the following lists (default does nothing) a list can be -1 hence the signed long

Reimplemented from faiss::InvertedLists.

Definition at line 260 of file OnDiskInvertedLists.cpp.

The documentation for this struct was generated from the following files:

- /data/users/hoss/faiss/OnDiskInvertedLists.h
- /data/users/hoss/faiss/OnDiskInvertedLists.cpp