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

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 such as .insert() or .from_hash_map() (for construction), as well as iterators, are not performance optimized.

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 mut hash_map = HashMap::new();
hash_map.insert(65, 'A');
let lookup = UniqueIdLookup::from_hash_map(hash_map);

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 mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
let all_ids = vec![65, 67];
let all_chars = vec!['A', 'C'];
lookup.insert(65, 'A');
lookup.insert(67, 'C');        
for (id, payload) in lookup.iter() {
    assert!(all_ids.contains(&id));
    assert!(all_chars.contains(&payload.unwrap()));
}