[−][src]Struct idlset::IDLBitRange
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::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
impl IDLBitRange
[src]
pub fn new() -> Self
[src]
Construct a new, empty set.
pub fn from_u64(id: u64) -> Self
[src]
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.
pub fn contains(&self, id: u64) -> bool
[src]
Returns true
if the id u64
value exists within the set.
pub fn insert_id(&mut self, value: u64)
[src]
Insert an id into the set, correctly sorted.
pub fn remove_id(&mut self, value: u64)
[src]
Remove an id from the set, leaving it correctly sorted. Note this doesn't purge unused IdlRange tuples, so this may still occupy memory even if empty.
If the value is not present, no action is taken.
pub unsafe fn push_id(&mut self, value: u64)
[src]
Push an id into the set. The value is inserted onto the tail of the set
which may cause you to break the structure if your input isn't sorted.
You probably want insert_id
instead.
pub fn len(&self) -> usize
[src]
Returns the number of ids in the set.
Trait Implementations
impl AndNot<IDLBitRange> for IDLBitRange
[src]
type Output = Self
The type of set implementation to return.
fn andnot(self, rhs: Self) -> Self
[src]
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::{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::{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);
impl BitAnd<IDLBitRange> for IDLBitRange
[src]
type Output = Self
The resulting type after applying the &
operator.
fn bitand(self, rhs: Self) -> Self
[src]
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);
impl BitOr<IDLBitRange> for IDLBitRange
[src]
type Output = Self
The resulting type after applying the |
operator.
fn bitor(self, rhs: Self) -> Self
[src]
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);
impl Clone for IDLBitRange
[src]
fn clone(&self) -> IDLBitRange
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl Debug for IDLBitRange
[src]
impl<'de> Deserialize<'de> for IDLBitRange
[src]
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
__D: Deserializer<'de>,
[src]
__D: Deserializer<'de>,
impl FromIterator<u64> for IDLBitRange
[src]
fn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self
[src]
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.
impl<'a> IntoIterator for &'a IDLBitRange
[src]
type Item = u64
The type of the elements being iterated over.
type IntoIter = IDLBitRangeIter<'a>
Which kind of iterator are we turning this into?
fn into_iter(self) -> IDLBitRangeIter<'a>
[src]
impl PartialEq<IDLBitRange> for IDLBitRange
[src]
fn eq(&self, other: &IDLBitRange) -> bool
[src]
fn ne(&self, other: &IDLBitRange) -> bool
[src]
impl Serialize for IDLBitRange
[src]
fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
__S: Serializer,
[src]
__S: Serializer,
impl StructuralPartialEq for IDLBitRange
[src]
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
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> DeserializeOwned for T where
T: for<'de> Deserialize<'de>,
[src]
T: for<'de> Deserialize<'de>,
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,