Struct VFunc

pub struct VFunc<T: ?Sized + ToSig<S>, W: ZeroCopy + Word = usize, D: BitFieldSlice<W> = Box<[W]>, S: Sig = [u64; 2], E: ShardEdge<S, 3> = FuseLge3Shards> { /* private fields */ }

Static functions with low space overhead, fast parallel construction, and fast queries.

Static functions map keys to values, but they do not store the keys: querying a static function with a key outside of the original set will lead to an arbitrary result. Another name for static functions retrieval data structure. Values are retrieved using the get method. On some architectures, and with some constraints, get_unaligned might be faster.

In exchange, static functions have a very low space overhead, and make it possible to store the association between keys and values just in the space required by the values (with a small overhead).

This structure is based on “ε-Cost Sharding: Scaling Hypergraph-Based Static Functions and Filters to Trillions of Keys”. Space overhead with respect to the optimum depends on the ShardEdge type. The default is FuseLge3Shards, which provides 10.5% space overhead for large key sets (above a few million keys), which grow up to 12% going towards smaller key sets. Details on other possible ShardEdge implementations can be found in the shard_edge module documentation.

Instances of this structure are immutable; they are built using a VBuilder and can be serialized using ε-serde. Please see the documentation of VBuilder for examples.

Generics

• T: The type of the keys.
• W: The word used to store the data, which is also the output type. It can be any unsigned type.
• D: The backend storing the function data. It can be a BitFieldVec<W> or a Box<[W]>. In the first case, the data is stored using exactly the number of bits needed, but access is slightly slower, while in the second case the data is stored in a boxed slice of W, thus forcing the number of bits to the number of bits of W, but access will be faster. Note that for most bit sizes in the first case on some architectures you can use unaligned reads to get faster queries.
• S: The signature type. The default is [u64; 2]. You can switch to [u64; 1] (and possibly FuseLge3NoShards) for slightly faster construction and queries, but the construction will not scale beyond 3.8 billion keys.
• E: The sharding and edge logic type. The default is FuseLge3Shards. For small sets of keys you might try FuseLge3NoShards, possibly coupled with [u64; 1] signatures. For functions with more than a few dozen billion keys, you might try FuseLge3FullSigs.

Implementations

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D: BitFieldSlice<W>, S: Sig, E: ShardEdge<S, 3>> VFunc<T, W, D, S, E>

pub fn get_by_sig(&self, sig: S) -> W

Returns the value associated with the given signature, or a random value if the signature is not the signature of a key.

This method is mainly useful in the construction of compound functions.

pub fn get(&self, key: impl Borrow<T>) -> W

Returns the value associated with the given key, or a random value if the key is not present.

pub fn len(&self) -> usize

Returns the number of keys in the function.

pub fn is_empty(&self) -> bool

Returns whether the function has no keys.

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, S: Sig, E: ShardEdge<S, 3>> VFunc<T, W, BitFieldVec<W>, S, E>

pub fn get_by_sig_unaligned(&self, sig: S) -> W

Returns the value associated with the given signature, or a random value if the signature is not the signature of a key, using unaligned reads.

This method uses BitFieldVec::get_unaligned, and has the same constraints.

This method is mainly useful in the construction of compound functions.

pub fn get_unaligned(&self, key: impl Borrow<T>) -> W

Returns the value associated with the given key, or a random value if the key is not present, using unaligned reads.

This method uses BitFieldVec::get_unaligned, and has the same constraints.

Trait Implementations

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> AlignHash for VFunc<T, W, D, S, E>

where E: AlignHash + ShardEdge<S, 3>, D: AlignHash + BitFieldSlice<W>, PhantomData<T>: AlignHash, PhantomData<W>: AlignHash, PhantomData<S>: AlignHash,

fn align_hash(hasher: &mut impl Hasher, _offset_of: &mut usize)

Accumulate alignment information in hasher assuming to be positioned at offset_of.

fn align_hash_val(&self, hasher: &mut impl Hasher, offset_of: &mut usize)

Call AlignHash::align_hash on a value.

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D: BitFieldSlice<W>, S: Sig, E: ShardEdge<S, 3>> CopyType for VFunc<T, W, D, S, E>

type Copy = Deep

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> CopyType for VFunc<T, W, D, S, E>

where E: MemSize + ShardEdge<S, 3>, u64: MemSize, usize: MemSize, D: MemSize + BitFieldSlice<W>, PhantomData<T>: MemSize, PhantomData<W>: MemSize, PhantomData<S>: MemSize,

type Copy = False

impl<T: Debug + ?Sized + ToSig<S>, W: Debug + ZeroCopy + Word, D: Debug + BitFieldSlice<W>, S: Debug + Sig, E: Debug + ShardEdge<S, 3>> Debug for VFunc<T, W, D, S, E>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> DeserializeInner for VFunc<T, W, D, S, E>

where E: DeserializeInner + ShardEdge<S, 3>, u64: DeserializeInner, usize: DeserializeInner, D: DeserializeInner + BitFieldSlice<W>, PhantomData<T>: DeserializeInner, PhantomData<W>: DeserializeInner, PhantomData<S>: DeserializeInner, for<'epserde_desertype> <D as DeserializeInner>::DeserType<'epserde_desertype>: BitFieldSlice<W>, for<'epserde_desertype> <E as DeserializeInner>::DeserType<'epserde_desertype>: ShardEdge<S, 3>,

type DeserType<'epserde_desertype> = VFunc<T, W, <D as DeserializeInner>::DeserType<'epserde_desertype>, S, <E as DeserializeInner>::DeserType<'epserde_desertype>>

The deserialization type associated with this type. It can be retrieved conveniently with the alias DeserType.

fn _deserialize_full_inner( backend: &mut impl ReadWithPos, ) -> Result<Self, Error>

fn _deserialize_eps_inner<'deserialize_eps_inner_lifetime>( backend: &mut SliceWithPos<'deserialize_eps_inner_lifetime>, ) -> Result<Self::DeserType<'deserialize_eps_inner_lifetime>, Error>

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> MemDbgImpl for VFunc<T, W, D, S, E>

where E: MemDbgImpl + ShardEdge<S, 3>, u64: MemDbgImpl, usize: MemDbgImpl, D: MemDbgImpl + BitFieldSlice<W>, PhantomData<T>: MemDbgImpl, PhantomData<W>: MemDbgImpl, PhantomData<S>: MemDbgImpl,

fn _mem_dbg_rec_on( &self, _memdbg_writer: &mut impl Write, _memdbg_total_size: usize, _memdbg_max_depth: usize, _memdbg_prefix: &mut String, _memdbg_is_last: bool, _memdbg_flags: DbgFlags, ) -> Result

fn _mem_dbg_depth_on( &self, writer: &mut impl Write, total_size: usize, max_depth: usize, prefix: &mut String, field_name: Option<&str>, is_last: bool, padded_size: usize, flags: DbgFlags, ) -> Result<(), Error>

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> MemSize for VFunc<T, W, D, S, E>

where E: MemSize + ShardEdge<S, 3>, u64: MemSize, usize: MemSize, D: MemSize + BitFieldSlice<W>, PhantomData<T>: MemSize, PhantomData<W>: MemSize, PhantomData<S>: MemSize,

fn mem_size(&self, _memsize_flags: SizeFlags) -> usize

Returns the (recursively computed) overall memory size of the structure in bytes.

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> SerializeInner for VFunc<T, W, D, S, E>

where E: SerializeInner + ShardEdge<S, 3>, u64: SerializeInner, usize: SerializeInner, D: SerializeInner + BitFieldSlice<W>, PhantomData<T>: SerializeInner, PhantomData<W>: SerializeInner, PhantomData<S>: SerializeInner, <D as SerializeInner>::SerType: BitFieldSlice<W>, <E as SerializeInner>::SerType: ShardEdge<S, 3>,

const IS_ZERO_COPY: bool

Inner constant used by the derive macros to keep track recursively of whether the type satisfies the conditions for being zero-copy. It is checked at runtime against the trait implemented by the type, and if a ZeroCopy type has this constant set to false serialization will panic.

const ZERO_COPY_MISMATCH: bool

Inner constant used by the derive macros to keep track of whether all fields of a type are zero-copy but neither the attribute #[zero_copy] nor the attribute #[deep_copy] was specified. It is checked at runtime, and if it is true a warning will be issued, as the type could be zero-copy, which would be more efficient.

type SerType = VFunc<T, W, <D as SerializeInner>::SerType, S, <E as SerializeInner>::SerType>

This is the type that will be written in the header of the file, and thus the type that will be deserialized. In most cases it is Self, but in some cases, as for references to slices, it is customized.

fn _serialize_inner(&self, backend: &mut impl WriteWithNames) -> Result<()>

Serialize this structure using the given backend.

impl<T: ?Sized + ToSig<S>, W: ZeroCopy + Word, D, S: Sig, E> TypeHash for VFunc<T, W, D, S, E>

where E: TypeHash + ShardEdge<S, 3>, D: TypeHash + BitFieldSlice<W>, PhantomData<T>: TypeHash, PhantomData<W>: TypeHash, PhantomData<S>: TypeHash,

fn type_hash(hasher: &mut impl Hasher)

Accumulate type information in hasher.

fn type_hash_val(&self, hasher: &mut impl Hasher)

Call TypeHash::type_hash on a value.