Crate utote

The Utote crate provides statically allocated multisets of unsigned integers. A nightly only simd feature can also be used to greatly improve performance.

A multiset, also known as a “bag”, is an extension to the concept of set where elements can occur multiple times. Utote calls the number of times an element occurs its count, though the term multiplicity is more often used in mathematical descriptions of multisets. All the common operations on sets have implementations on multisets, so you can intersect and union multisets, along with everything else you would expect to be able to do.

If you have a known number of things that you want to count and do set-like operations on, then this crate will likely be useful to you.

Recipes

Multiset can only keep track of uint counters, but if you have a fixed number of non-uint items then pairing a HashMap with a Multiset can provide significant performance benefits.

use std::collections::HashMap;
use utote::Multiset;

let mut item_map: HashMap<&str, usize> = HashMap::new();
item_map.insert("foo", 0);
item_map.insert("bar", 1);

let multiset: Multiset<u16, 2> = Multiset::empty();

// do a whole load of stuff to the multiset...

let bar_count: &u16 = multiset.get(*item_map.get("bar").unwrap()).unwrap();

SIMD and Generics

Due to remaining rough edges in the const generic feature there is an extra constraint required when using Multiset generically. The const values for the number of lanes for the simd types of a counter type need to be constrained. The constraint:

where [(); T::L128 * T::L256 * T::LF]: Sized

is the most simple to add.

Cargo Features

• simd: Requires nightly rust toolchain. Enables simd implementations using the packed_simd crate crate and unsatble features: const_generics and const_evaluatable_checked.
• rand: Enables choose_random methods for multiset structs using the rand crate.

Performance

The largest factor in multiset performance is the size of the multiset, the larger the slower it is. The simplest way to improve performance is to keep them as small as possible.

Using SIMD

The most simple way to improve performance is to use the simd implementations by turning on the simd feature of Utote. If you can use the nightly toolchain then this should be utilised.

Structs

• Multiset
  A stack allocated multiset of unsigned integers.

Traits

• Counter
  The Counter trait simplifies the use of Multiset with generics. This trait is sealed and not implementable outside of this crate.