The leapfrog crate contains two HashMap implementations, HashMap, which is
a single-threaded HashMap, which can be used as an alternative to rust's 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.
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 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.
Both maps use the same leapfrog probing strategy, for which you can find more information on Jeff Preshing's leapfrog probing blog post, A c++ implementation of the map can be found at his Junction library, which was the starting point for this implementation.
For a more detailed description of the limitations and behaviour of the maps, see the crate documentation:
This crate is licensed under either the Apache License, Version 2.0, see here or here or the MIT license see here or here, 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.