Struct idlset::v1::IDLBitRange
source · [−]pub struct IDLBitRange { /* private fields */ }
Expand description
An ID List of u64
values, that uses a compressed representation of u64
to
speed up set operations, improve cpu cache behaviour and consume less memory.
This is essentially a Vec<u64>
, but requires less storage with large values
and natively supports logical operations for set manipulation. Today this
supports And, Or, AndNot. Future types may be added such as xor.
How does it work?
The IDLBitRange
stores a series of tuples (IDRange) that represents a
range prefix u64
and a u64
mask of bits representing the presence of that
integer in the set. For example, the number 1
when inserted would create
an idl range of: IDRange { range: 0, mask: 2 }
. The mask has the “second”
bit set, so we add range and recieve 1
. (if mask was 1, this means the value
0 is present!)
Other examples would be IDRange { range: 0, mask: 3 }
. Because 3 means
“the first and second bit is set” this would extract to [0, 1]
IDRange { range: 0, mask: 38}
represents the set [1, 2, 5]
as the.
second, third and sixth bits are set. Finally, a value of IDRange { range: 64, mask: 4096 }
represents the set [76, ]
.
Using this, we can store up to 64 integers in an IDRange. Once there are
at least 3 bits set in mask, the compression is now saving memory space compared
to raw unpacked Vec<u64>
.
The set operations can now be performed by applying u64
bitwise operations
on the mask components for a given matching range prefix. If the range
prefix is not present in the partner set, we choose a correct course of
action (Or copies the range to the result, And skips the range entirely)
As an example, if we had the values IDRange { range: 0, mask: 38 }
([1, 2, 5]
) and
IDRange { range: 0, mask: 7 }
([0, 1, 2]
), and we were to perform an &
operation
on these sets, the result would be 7 & 38 == 6
. The result now is
IDRange { range: 0, mask: 6 }
, which decompresses to [1, 2]
- the correct
result of our set And operation.
The important note here is that with a single cpu &
operation, we were
able to intersect up to 64 values at once. Contrast to a Vec<u64>
where we
would need to perform cpu equality on each value. For our above example
this would have taken at most 4 cpu operations with the Vec<u64>
, where
as the IDLBitRange
performed 2 (range eq and mask &
).
Worst case behaviour is sparse u64 sets where each IDRange only has a single
populated value. This yields a slow down of approx 20% compared to the Vec<u64>
.
However, as soon as the IDRange contains at least 2 values they are equal
in performance, and three values begins to exceed. This applies to all
operation types and data sizes.
Examples
use idlset::v1::IDLBitRange;
use std::iter::FromIterator;
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
// Conduct an and (intersection) of the two lists to find commont members.
let idl_result = idl_a & idl_b;
let idl_expect = IDLBitRange::from_iter(vec![2]);
assert_eq!(idl_result, idl_expect);
Implementations
sourceimpl IDLBitRange
impl IDLBitRange
sourcepub fn from_u64(id: u64) -> Self
pub fn from_u64(id: u64) -> Self
Construct a set containing a single initial value. This is a special use case for database indexing where single value equality indexes are store uncompressed on disk.
sourcepub fn contains(&self, id: u64) -> bool
pub fn contains(&self, id: u64) -> bool
Returns true
if the id u64
value exists within the set.
sourcepub fn remove_id(&mut self, value: u64)
pub fn remove_id(&mut self, value: u64)
Remove an id from the set, leaving it correctly sorted.
If the value is not present, no action is taken.
sourcepub unsafe fn push_id(&mut self, value: u64)
pub unsafe fn push_id(&mut self, value: u64)
Push an id into the set. The value is appended onto the tail of the set.
You probably want insert_id
instead.
Safety
Failure to insert sorted data will corrupt the set, and cause subsequent set operations to yield incorrect and inconsistent results.
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of ids in the set. This operation iterates over
the set, decompressing it to count the ids, which MAY be slow. If
you want to see if the set is empty, us is_empty()
sourcepub fn below_threshold(&self, threshold: usize) -> bool
pub fn below_threshold(&self, threshold: usize) -> bool
Returns if the number of ids in this set exceed this threshold. While
this must iterate to determine if this is true, since we shortcut return
in the check, on long sets we will not iterate over the complete content
making it faster than len() < thresh
.
Returns true if the set is smaller than threshold.
Trait Implementations
sourceimpl AndNot<&IDLBitRange> for &IDLBitRange
impl AndNot<&IDLBitRange> for &IDLBitRange
sourcefn andnot(self, rhs: &IDLBitRange) -> IDLBitRange
fn andnot(self, rhs: &IDLBitRange) -> IDLBitRange
Perform an AndNot (exclude) operation between two sets. This returns a new set containing the results. The set on the right is the candidate set to exclude from the set of the left.
Examples
// Note the change to import the AndNot trait.
use idlset::{v1::IDLBitRange, AndNot};
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a.andnot(idl_b);
let idl_expect = IDLBitRange::from_iter(vec![1, 3]);
assert_eq!(idl_result, idl_expect);
// Note the change to import the AndNot trait.
use idlset::{v1::IDLBitRange, AndNot};
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
// Note how reversing a and b here will return an empty set.
let idl_result = idl_b.andnot(idl_a);
let idl_expect = IDLBitRange::new();
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The type of set implementation to return.
sourceimpl AndNot<IDLBitRange> for IDLBitRange
impl AndNot<IDLBitRange> for IDLBitRange
sourcefn andnot(self, rhs: Self) -> IDLBitRange
fn andnot(self, rhs: Self) -> IDLBitRange
Perform an AndNot (exclude) operation between two sets. This returns a new set containing the results. The set on the right is the candidate set to exclude from the set of the left.
Examples
// Note the change to import the AndNot trait.
use idlset::{v1::IDLBitRange, AndNot};
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a.andnot(idl_b);
let idl_expect = IDLBitRange::from_iter(vec![1, 3]);
assert_eq!(idl_result, idl_expect);
// Note the change to import the AndNot trait.
use idlset::{v1::IDLBitRange, AndNot};
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
// Note how reversing a and b here will return an empty set.
let idl_result = idl_b.andnot(idl_a);
let idl_expect = IDLBitRange::new();
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The type of set implementation to return.
sourceimpl BitAnd<&IDLBitRange> for &IDLBitRange
impl BitAnd<&IDLBitRange> for &IDLBitRange
sourcefn bitand(self, rhs: &IDLBitRange) -> IDLBitRange
fn bitand(self, rhs: &IDLBitRange) -> IDLBitRange
Perform an And (intersection) operation between two sets. This returns a new set containing the results.
Examples
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a & idl_b;
let idl_expect = IDLBitRange::from_iter(vec![2]);
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The resulting type after applying the &
operator.
sourceimpl BitAnd<IDLBitRange> for IDLBitRange
impl BitAnd<IDLBitRange> for IDLBitRange
sourcefn bitand(self, rhs: IDLBitRange) -> IDLBitRange
fn bitand(self, rhs: IDLBitRange) -> IDLBitRange
Perform an And (intersection) operation between two sets. This returns a new set containing the results.
Examples
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a & idl_b;
let idl_expect = IDLBitRange::from_iter(vec![2]);
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The resulting type after applying the &
operator.
sourceimpl BitOr<&IDLBitRange> for &IDLBitRange
impl BitOr<&IDLBitRange> for &IDLBitRange
sourcefn bitor(self, rhs: &IDLBitRange) -> IDLBitRange
fn bitor(self, rhs: &IDLBitRange) -> IDLBitRange
Perform an Or (union) operation between two sets. This returns a new set containing the results.
Examples
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a | idl_b;
let idl_expect = IDLBitRange::from_iter(vec![1, 2, 3]);
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The resulting type after applying the |
operator.
sourceimpl BitOr<IDLBitRange> for IDLBitRange
impl BitOr<IDLBitRange> for IDLBitRange
sourcefn bitor(self, rhs: Self) -> IDLBitRange
fn bitor(self, rhs: Self) -> IDLBitRange
Perform an Or (union) operation between two sets. This returns a new set containing the results.
Examples
let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);
let idl_result = idl_a | idl_b;
let idl_expect = IDLBitRange::from_iter(vec![1, 2, 3]);
assert_eq!(idl_result, idl_expect);
type Output = IDLBitRange
type Output = IDLBitRange
The resulting type after applying the |
operator.
sourceimpl Clone for IDLBitRange
impl Clone for IDLBitRange
sourcefn clone(&self) -> IDLBitRange
fn clone(&self) -> IDLBitRange
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl Debug for IDLBitRange
impl Debug for IDLBitRange
sourceimpl Default for IDLBitRange
impl Default for IDLBitRange
sourceimpl<'de> Deserialize<'de> for IDLBitRange
impl<'de> Deserialize<'de> for IDLBitRange
sourcefn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
sourceimpl Display for IDLBitRange
impl Display for IDLBitRange
sourceimpl FromIterator<u64> for IDLBitRange
impl FromIterator<u64> for IDLBitRange
sourcefn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self
fn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self
Build an IDLBitRange from at iterator. If you provide a sorted input, a fast append mode is used. Unsorted inputs use a slower insertion sort method instead.
sourceimpl<'a> IntoIterator for &'a IDLBitRange
impl<'a> IntoIterator for &'a IDLBitRange
type IntoIter = IDLBitRangeIter<'a>
type IntoIter = IDLBitRangeIter<'a>
Which kind of iterator are we turning this into?
sourcefn into_iter(self) -> IDLBitRangeIter<'a>ⓘNotable traits for IDLBitRangeIter<'a>impl<'a> Iterator for IDLBitRangeIter<'a> type Item = u64;
fn into_iter(self) -> IDLBitRangeIter<'a>ⓘNotable traits for IDLBitRangeIter<'a>impl<'a> Iterator for IDLBitRangeIter<'a> type Item = u64;
Creates an iterator from a value. Read more
sourceimpl PartialEq<IDLBitRange> for IDLBitRange
impl PartialEq<IDLBitRange> for IDLBitRange
sourcefn eq(&self, other: &IDLBitRange) -> bool
fn eq(&self, other: &IDLBitRange) -> bool
This method tests for self
and other
values to be equal, and is used
by ==
. Read more
sourcefn ne(&self, other: &IDLBitRange) -> bool
fn ne(&self, other: &IDLBitRange) -> bool
This method tests for !=
.
sourceimpl Serialize for IDLBitRange
impl Serialize for IDLBitRange
impl StructuralPartialEq for IDLBitRange
Auto Trait Implementations
impl RefUnwindSafe for IDLBitRange
impl Send for IDLBitRange
impl Sync for IDLBitRange
impl Unpin for IDLBitRange
impl UnwindSafe for IDLBitRange
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more