# 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:

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

and

```rust
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:

```bash
$ 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:

```rust
#[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](LICENSE-APACHE), Version 2.0 or [MIT license](LICENSE-MIT)
at your option.

## Code of conduct

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

[![Contributor Covenant](contributor-covenant-v2.0-adopted-ff69b4.svg)](code_of_conduct.md)