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§
source§impl 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§
source§impl AndNot for &IDLBitRange
impl AndNot for &IDLBitRange
source§fn 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
source§impl AndNot for IDLBitRange
impl AndNot for IDLBitRange
source§fn 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
source§impl BitAnd for &IDLBitRange
impl BitAnd for &IDLBitRange
source§fn 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
&
operator.source§impl BitAnd for IDLBitRange
impl BitAnd for IDLBitRange
source§fn 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
&
operator.source§impl BitOr for &IDLBitRange
impl BitOr for &IDLBitRange
source§fn 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
|
operator.source§impl BitOr for IDLBitRange
impl BitOr for IDLBitRange
source§fn 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
|
operator.source§impl Clone for IDLBitRange
impl Clone for IDLBitRange
source§fn clone(&self) -> IDLBitRange
fn clone(&self) -> IDLBitRange
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl Debug for IDLBitRange
impl Debug for IDLBitRange
source§impl<'de> Deserialize<'de> for IDLBitRange
impl<'de> Deserialize<'de> for IDLBitRange
source§fn 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>,
source§impl Display for IDLBitRange
impl Display for IDLBitRange
source§impl FromIterator<u64> for IDLBitRange
impl FromIterator<u64> for IDLBitRange
source§fn 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.
source§impl<'a> IntoIterator for &'a IDLBitRange
impl<'a> IntoIterator for &'a IDLBitRange
source§impl PartialEq for IDLBitRange
impl PartialEq for IDLBitRange
source§fn eq(&self, other: &IDLBitRange) -> bool
fn eq(&self, other: &IDLBitRange) -> bool
self
and other
values to be equal, and is used
by ==
.