leapfrog 0.1.1

A fast, lock-free concurrent hash map
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# Leapfrog

The leapfrog crate contains two HashMap implementations, `HashMap`, which is
a single-threaded HashMap, which can be used as an alternative to rusts built
in HashMap (without somewhat limited functionality but better performance), and 
`LeapMap`, which is fast, lock-free concurrent version of the `HashMap`, where
all operations can be used concurrently from any number of threads. The
performance for most real-world use cases is around 2x the next fastest Rust
hashmap, and around 13.6x `std::collections::HashMap` wrapped with RwLock for 16
cores. It also scales better than other hash map implementations. Benchmark results 
can be found at [rust hashmap benchmarks](https://github.com/robclu/conc-map-bench).

# Performance

A snapshot of the results for the LeapMap on a read heavy workload using a 16 core 
AMD 3950x CPU are the following (with throughput in Mops/second, cores in brackets, 
and  performance realtive to `std::collections::HashMap` with RwLock):

| Map              | Throughput (1) | Relative (1) | Throughput (16) | Relative (16) |
|------------------|----------------|--------------|-----------------|---------------|
| RwLock + HashMap | 17.6           | 1.0          | 12.3            | 0.69          |
| Flurry           | 10.2           | 0.58         | 76.3            | 4.34          |
| DashMap          | 14.1           | 0.80         | 84.5            | 4.8           |
| LeapMap          | 16.8           | 0.95         | 167.8           | 9.53          |

For the single threaded leapfrog HashMap, a benchmark of random inserts and deletes (a port of
[this](https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-03-03-result-RandomInsertErase/)
benchmark of C++ hashmaps) has the rust std HashMap at around 57Mops/s and
the leapfrog HashMap at around 80Mops/s, with Murmur as the hash function. The
leapfrog HashMap has performance which is at least comparable to, if not better
than, the fastest C++ hash maps from the linked benchmark.

# Probing

Both maps use the same leapfrog probing strategy, for which you can find more
information on Jeff Preshing's [leapfrog probing blog post](https://preshing.com/20160314/leapfrog-probing/),
A c++ implementation of the map can be found at his [Junction library](https://github.com/preshing/junction),
which was the starting point for this implementation.

# Additional Notes

For a more detailed description of the limitations and behaviour of the maps,
see the crate documentation: 

# License

This crate is licensed under either the Apache License, Version 2.0, see 
[here](LICENSE-APACHE) or [here](http://www.apache.org/licenses/LICENSE-2.0) or
the MIT license see [here](LICENSE-MIT) or [here](http://opensource.org/licenses/MIT),
at your chosing. It can be used freely for both commercial and non-commercial 
applications, so long as you publish the contents of your chosen license file
somewhere in your documentation.