UniqueIdLookup

UniqueIdLookup is a specialized data structure implementing an associative array specifically designed for integer keys.

This approach offers significant performance advantages over conventional hash maps, with benchmarks showing speed improvements in the range of 12x to 13x faster (use cases dependent).

UniqueIdLookup is implemented as a dynamic array with an offset, causing memory efficiency to decrease as the number of vacant entries increases. This makes it suitable for densely populated ID ranges.

Due to the offset IDs don't need to begin at zero for memory efficiency.

Simple Example

.get() is 12 times faster than equivalent HashMap

use unique_id_lookup::UniqueIdLookup;

let mut ascii_lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
ascii_lookup.insert(65, 'A');
ascii_lookup.insert(66, 'B');
ascii_lookup.insert(97, 'a');
ascii_lookup.insert(98, 'b');
// add all remaining upper and lower case letters

let c = ascii_lookup.get(97).unwrap();  
assert_eq!(c, 'a');    

Goal

This data structure is performance optimized specifically for two lookup methods:

• .get()
• .get_mut()

Other operations are not performance optimized. However, also .remove() and .insert() have constant time complexity (the latter provided the map is pre-allocated using .with_capacity_and_offset()).

The performance boost (over a Hash Map) is achieved by a couple of elements:

• elimination of hash functions
• no collision handling
• more compact and more contiguous memory layout (less cache misses)

Benchmark Details

All benchmarks invoke .get() / .get_mut() for every key in the map. The tests primarily differ in the memory size of the payload.

To prevent compiler optimization from eliminating these calls, aggregation logic has been incorporated. This creates some overhead which is reflected in the benchmark times.

Measurements are done with criterion.

The source code of the benchmarks is in unique_id_lookup/benches/benchmark_against_hash_map.rs

More Examples

Constructor

use unique_id_lookup::UniqueIdLookup;

// --- Adding each element via insert()
let mut ascii_lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
ascii_lookup.insert(65, 'A');

// --- Construct from HashMap
let hash_map: HashMap<u16, char> = HashMap::from([(5, 'c'), (6, 'd')]);
let lookup = UniqueIdLookup::from(hash_map);

// --- Construct from Array
let arr: [(u16, char); 2] = [(5, 'c'), (7, 'e')];
let lookup = UniqueIdLookup::from(arr);    

Lookup Functions

// --- First setup a simple ASCII lookup
let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
lookup.insert(65, 'A');
lookup.insert(67, 'C');

// --- .contains_id()
assert_eq!(lookup.contains_id(64), false);
assert_eq!(lookup.contains_id(65), true);
assert_eq!(lookup.contains_id(66), false);
assert_eq!(lookup.contains_id(67), true);
assert_eq!(lookup.contains_id(68), false);

// --- .get() - panics below 65 and above 67
assert_eq!(lookup.get(65).unwrap(), 'A');
assert_eq!(lookup.get(66).is_some(), false);
assert_eq!(lookup.get(67).unwrap(), 'C');        

// --- .get_or_none() - works for all IDs with a minor performance hit
assert_eq!(lookup.get_or_none(64).is_some(), false);
assert_eq!(lookup.get_or_none(65).unwrap(), 'A');
assert_eq!(lookup.get_or_none(68).is_some(), false);

// --- .get_mut() - to modify the payload
let payload = lookup.get_mut(65);
assert_eq!(**payload.as_ref().unwrap(), 'A');
*payload.unwrap() = 'a';
assert_eq!(*lookup.get(65).as_ref().unwrap(), 'a');

Iterator

// --- Iterates over all elements that have a value.
let arr: [(usize, char); 3] = [(5, 'c'), (6, 'd'), (8, 'f')];
let lookup = UniqueIdLookup::from(arr);

for (id, payload) in lookup.iter_occupied() {
    let tup = (id, *payload);
    assert!(arr.contains(&tup));
}

for id in lookup.iter_vacant_ids() {
    assert_eq!([7].contains(&id), true);
}

for payload in lookup.values() {
    assert!(['c', 'd', 'f'].contains(&payload));
}

Others

// --- into_occupied_vec() is similar to flatten() but more efficient
let arr: [(usize, char); 4] = [(5, 'c'), (6, 'd'), (8, 'f'), (10, 'h')];
let lookup = UniqueIdLookup::from(arr);
let occupied = lookup.into_occupied_vec();
assert_eq!(occupied, vec!['c', 'd', 'f', 'h']);