18543058803

Committed 15 Oct 2025 09:22PM UTC coverage: 64.418% (-0.7%) from 65.126%

Build # 18543058803

Build Type

push

github

Committed by

vigna

Commit Message

Docs

Run Details

3628 of 5632 relevant lines covered (64.42%)

119122797.27 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

38.89

/src/func/vfunc.rs

/*
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use std::borrow::Borrow;

use super::shard_edge::FuseLge3Shards;
use crate::bits::BitFieldVec;
use crate::func::shard_edge::ShardEdge;
use crate::traits::bit_field_slice::*;
use crate::utils::*;
use mem_dbg::*;
use value_traits::slices::SliceByValue;

/// 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`](VFunc::get) method. On
/// some architectures, and with some constraints,
/// [`get_unaligned`](VFunc::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](https://arxiv.org/abs/2503.18397)”. 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`](crate::func::shard_edge) module documentation.
///
/// Instances of this structure are immutable; they are built
/// using a [`VBuilder`](crate::func::VBuilder) and can be serialized using
/// [ε-serde](https://crates.io/crates/epserde). Please see the documentation of
/// [`VBuilder`](crate::func::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>`](crate::bits::BitFieldVec) 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](VFunc::get_unaligned) to get faster queries.
/// * `S`: The signature type. The default is `[u64; 2]`. You can switch to
///   `[u64; 1]` (and possibly
///   [`FuseLge3NoShards`](crate::func::shard_edge::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`](crate::func::shard_edge::FuseLge3NoShards), possibly
///   coupled with `[u64; 1]` signatures. For functions with more than a few
///   dozen billion keys, you might try
///   [`FuseLge3FullSigs`](crate::func::shard_edge::FuseLge3FullSigs).
#[derive(Debug, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct VFunc<
    T: ?Sized + ToSig<S>,
    W: Word + BinSafe = usize,
    D: SliceByValue<Value = W> = Box<[W]>,
    S: Sig = [u64; 2],
    E: ShardEdge<S, 3> = FuseLge3Shards,
> {
    pub(crate) shard_edge: E,
    pub(crate) seed: u64,
    pub(crate) num_keys: usize,
    pub(crate) data: D,
    pub(crate) _marker_t: std::marker::PhantomData<T>,
    pub(crate) _marker_w: std::marker::PhantomData<W>,
    pub(crate) _marker_s: std::marker::PhantomData<S>,
}

impl<
    T: ?Sized + ToSig<S>,
    W: Word + BinSafe,
    D: SliceByValue<Value = W>,
    S: Sig,
    E: ShardEdge<S, 3>,
> VFunc<T, W, D, S, E>
{
    /// 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.
    #[inline]
    pub fn get_by_sig(&self, sig: S) -> W {
        let edge = self.shard_edge.edge(sig);
        unsafe {
            self.data.get_value_unchecked(edge[0])
                ^ self.data.get_value_unchecked(edge[1])
                ^ self.data.get_value_unchecked(edge[2])
        }
    }

    /// Returns the value associated with the given key, or a random value if the
    /// key is not present.
    #[inline(always)]
    pub fn get(&self, key: impl Borrow<T>) -> W {
        self.get_by_sig(T::to_sig(key.borrow(), self.seed))
    }

    /// Returns the number of keys in the function.
    pub fn len(&self) -> usize {
        self.num_keys
    }

    /// Returns whether the function has no keys.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T: ?Sized + ToSig<S>, W: Word + BinSafe, S: Sig, E: ShardEdge<S, 3>>
    VFunc<T, W, BitFieldVec<W>, S, E>
{
    /// 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](BitFieldVec::get_unaligned).
    ///
    /// This method uses [`BitFieldVec::get_unaligned`], and has
    /// the same constraints.
    ///
    /// This method is mainly useful in the construction of compound functions.
    #[inline]
    pub fn get_by_sig_unaligned(&self, sig: S) -> W {
        let edge = self.shard_edge.edge(sig);
        unsafe {
            self.data.get_unaligned_unchecked(edge[0])
                ^ self.data.get_unaligned_unchecked(edge[1])
                ^ self.data.get_unaligned_unchecked(edge[2])
        }
    }

    /// Returns the value associated with the given key, or a random value if
    /// the key is not present, using [unaligned
    /// reads](BitFieldVec::get_unaligned).
    ///
    /// This method uses [`BitFieldVec::get_unaligned`], and has
    /// the same constraints.
    #[inline(always)]
    pub fn get_unaligned(&self, key: impl Borrow<T>) -> W {
        self.get_by_sig_unaligned(T::to_sig(key.borrow(), self.seed))
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use std::borrow::Borrow;
8
9	use super::shard_edge::FuseLge3Shards;
10	use crate::bits::BitFieldVec;
11	use crate::func::shard_edge::ShardEdge;
12	use crate::traits::bit_field_slice::*;
13	use crate::utils::*;
14	use mem_dbg::*;
15	use value_traits::slices::SliceByValue;
16
17	/// Static functions with low space overhead, fast parallel construction, and
18	/// fast queries.
19	///
20	/// Static functions map keys to values, but they do not store the keys:
21	/// querying a static function with a key outside of the original set will lead
22	/// to an arbitrary result. Another name for static functions *retrieval data
23	/// structure*. Values are retrieved using the [`get`](VFunc::get) method. On
24	/// some architectures, and with some constraints,
25	/// [`get_unaligned`](VFunc::get_unaligned) might be faster.
26	///
27	/// In exchange, static functions have a very low space overhead, and make it
28	/// possible to store the association between keys and values just in the space
29	/// required by the values (with a small overhead).
30	///
31	/// This structure is based on “[ε-Cost Sharding: Scaling Hypergraph-Based
32	/// Static Functions and Filters to Trillions of
33	/// Keys](https://arxiv.org/abs/2503.18397)”. Space overhead with respect to the
34	/// optimum depends on the [`ShardEdge`] type. The default is
35	/// [`FuseLge3Shards`], which provides 10.5% space overhead for large key sets
36	/// (above a few million keys), which grow up to 12% going towards smaller key
37	/// sets. Details on other possible [`ShardEdge`] implementations can be found
38	/// in the [`shard_edge`](crate::func::shard_edge) module documentation.
39	///
40	/// Instances of this structure are immutable; they are built
41	/// using a [`VBuilder`](crate::func::VBuilder) and can be serialized using
42	/// [ε-serde](https://crates.io/crates/epserde). Please see the documentation of
43	/// [`VBuilder`](crate::func::VBuilder) for examples.
44	///
45	/// # Generics
46	///
47	/// * `T`: The type of the keys.
48	/// * `W`: The word used to store the data, which is also the output type. It
49	/// can be any unsigned type.
50	/// * `D`: The backend storing the function data. It can be a
51	/// [`BitFieldVec<W>`](crate::bits::BitFieldVec) or a `Box<[W]>`. In the first
52	/// case, the data is stored using exactly the number of bits needed, but
53	/// access is slightly slower, while in the second case the data is stored in
54	/// a boxed slice of `W`, thus forcing the number of bits to the number of
55	/// bits of `W`, but access will be faster. Note that for most bit sizes in
56	/// the first case on some architectures you can use [unaligned
57	/// reads](VFunc::get_unaligned) to get faster queries.
58	/// * `S`: The signature type. The default is `[u64; 2]`. You can switch to
59	/// `[u64; 1]` (and possibly
60	/// [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards)) for
61	/// slightly faster construction and queries, but the construction will not
62	/// scale beyond 3.8 billion keys.
63	/// * `E`: The sharding and edge logic type. The default is [`FuseLge3Shards`].
64	/// For small sets of keys you might try
65	/// [`FuseLge3NoShards`](crate::func::shard_edge::FuseLge3NoShards), possibly
66	/// coupled with `[u64; 1]` signatures. For functions with more than a few
67	/// dozen billion keys, you might try
68	/// [`FuseLge3FullSigs`](crate::func::shard_edge::FuseLge3FullSigs).
69	#[derive(Debug, MemDbg, MemSize)]
70	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
71	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
72	pub struct VFunc<
73	T: ?Sized + ToSig<S>,
74	W: Word + BinSafe = usize,
75	D: SliceByValue<Value = W> = Box<[W]>,
76	S: Sig = [u64; 2],
77	E: ShardEdge<S, 3> = FuseLge3Shards,
78	> {
79	pub(crate) shard_edge: E,
80	pub(crate) seed: u64,
81	pub(crate) num_keys: usize,
82	pub(crate) data: D,
83	pub(crate) _marker_t: std::marker::PhantomData<T>,
84	pub(crate) _marker_w: std::marker::PhantomData<W>,
85	pub(crate) _marker_s: std::marker::PhantomData<S>,
86	}
87
88	impl<
89	T: ?Sized + ToSig<S>,
90	W: Word + BinSafe,
91	D: SliceByValue<Value = W>,
92	S: Sig,
93	E: ShardEdge<S, 3>,
94	> VFunc<T, W, D, S, E>
95	{
96	/// Returns the value associated with the given signature, or a random value
97	/// if the signature is not the signature of a key.
98	///
99	/// This method is mainly useful in the construction of compound functions.
100	#[inline]
101	pub fn get_by_sig(&self, sig: S) -> W {	23,010,100✔
102	let edge = self.shard_edge.edge(sig);	92,040,400✔
103	unsafe {
104	self.data.get_value_unchecked(edge[0])	115,050,500✔
105	^ self.data.get_value_unchecked(edge[1])	69,030,300✔
106	^ self.data.get_value_unchecked(edge[2])	46,020,200✔
107	}
108	}
109
110	/// Returns the value associated with the given key, or a random value if the
111	/// key is not present.
112	#[inline(always)]
113	pub fn get(&self, key: impl Borrow<T>) -> W {	12,606,060✔
114	self.get_by_sig(T::to_sig(key.borrow(), self.seed))	75,636,360✔
115	}
116
117	/// Returns the number of keys in the function.
118	pub fn len(&self) -> usize {	×
119	self.num_keys	×
120	}
121
122	/// Returns whether the function has no keys.
123	pub fn is_empty(&self) -> bool {	×
124	self.len() == 0	×
125	}
126	}
127
128	impl<T: ?Sized + ToSig<S>, W: Word + BinSafe, S: Sig, E: ShardEdge<S, 3>>
129	VFunc<T, W, BitFieldVec<W>, S, E>
130	{
131	/// Returns the value associated with the given signature, or a random value
132	/// if the signature is not the signature of a key, using [unaligned
133	/// reads](BitFieldVec::get_unaligned).
134	///
135	/// This method uses [`BitFieldVec::get_unaligned`], and has
136	/// the same constraints.
137	///
138	/// This method is mainly useful in the construction of compound functions.
139	#[inline]
140	pub fn get_by_sig_unaligned(&self, sig: S) -> W {	×
141	let edge = self.shard_edge.edge(sig);	×
142	unsafe {
143	self.data.get_unaligned_unchecked(edge[0])	×
144	^ self.data.get_unaligned_unchecked(edge[1])	×
145	^ self.data.get_unaligned_unchecked(edge[2])	×
146	}
147	}
148
149	/// Returns the value associated with the given key, or a random value if
150	/// the key is not present, using [unaligned
151	/// reads](BitFieldVec::get_unaligned).
152	///
153	/// This method uses [`BitFieldVec::get_unaligned`], and has
154	/// the same constraints.
155	#[inline(always)]
156	pub fn get_unaligned(&self, key: impl Borrow<T>) -> W {	×
157	self.get_by_sig_unaligned(T::to_sig(key.borrow(), self.seed))	×
158	}
159	}

vigna / sux-rs / 18543058803

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous