shardize

Experiments in whether we can create sharded forms of existing containers using a macro.

If it works, this will allow us to reduce contention in multi-threaded scenarios, by ensuring locks (or contests over lock-free resources) only apply to a single shard rather than the whole container.

Performance

In a very naive test, we compare these two structures:

let m1 = Mutex::new(HashMap::<usize, String>::new());

and

let m2 = ShardedMutexHashmap::<Mutex<HashMap<usize, String>>, 10>::new(&my_shard_key);

m2 is a container with get and set methods like m1, but its underlying implementation uses 10 different HashMaps, each inside its own Mutex.

When we spawn 10 threads and read/write 1000 values into m1 and m2, we can see that m2 performs much faster:

$ cargo bench
...
test read_from_mutex_hashmap         ... bench:   1,032,460 ns/iter (+/- 835,085)
test read_from_sharded_mutex_hashmap ... bench:     302,203 ns/iter (+/- 22,340)
test write_to_mutex_hashmap          ... bench:   1,221,228 ns/iter (+/- 1,394,711)
test write_to_sharded_mutex_hashmap  ... bench:     378,115 ns/iter (+/- 21,017)

How to use

In order to be able to use ShardedMutexHashmap as shown above, we need to provide the following code:

#[shardize(ShardedMutexHashmap)]
trait MyTrait: Default {
    fn get(&self, key: usize) -> String;
    fn set(&self, key: usize, value: String);
}

impl MyTrait for Mutex<HashMap<usize, String>> {
    fn get(&self, key: usize) -> String {
        self.lock().unwrap().get(&key).unwrap().clone()
    }

    fn set(&self, key: usize, value: String) {
        self.lock().unwrap().insert(key, value);
    }
}

fn my_shard_key(key: usize) -> usize {
    key
}

ShardedMutexHashmap was generated by the shardize macro based on MyTrait and an implementation of MyTrait. The generated code creates one copy of the underlying container (here, a Mutex<HashMap<...>>) for each shard, and stores/retrieves values from the approprate shard, which it finds by calling my_shard_key on the key passed in to get or set.

License

Copyright 2022 John Bell and Andy Balaam, licensed under either of Apache License, Version 2.0 or MIT license at your option.

Code of conduct

Please note that this project is released with a Contributor Code of Conduct. By participating in this project you agree to abide by its terms.