Struct idlset::IDLBitRange

pub struct IDLBitRange { /* private fields */ }

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

pub fn new() -> Self

Construct a new, empty set.

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.

pub fn contains(&self, id: u64) -> bool

Returns true if the id u64 value exists within the set.

Trait Implementations

impl AndNot<IDLBitRange> for IDLBitRange

fn andnot(self, rhs: Self) -> Self

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);

type Output = IDLBitRange

The type of set implementation to return.

impl BitAnd<IDLBitRange> for IDLBitRange

fn bitand(self, rhs: Self) -> Self

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

The resulting type after applying the & operator.

impl BitOr<IDLBitRange> for IDLBitRange

fn bitor(self, rhs: Self) -> Self

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

The resulting type after applying the | operator.

impl Debug for IDLBitRange

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

Formats the value using the given formatter.

impl FromIterator<u64> for IDLBitRange

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.

impl<'a> IntoIterator for &'a IDLBitRange

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>

Creates an iterator from a value.

impl PartialEq<IDLBitRange> for IDLBitRange

fn eq(&self, other: &IDLBitRange) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for IDLBitRange