diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 98 |
1 files changed, 49 insertions, 49 deletions
@@ -4,7 +4,7 @@ hashbrown [](https://travis-ci.com/rust-lang/hashbrown) [](https://crates.io/crates/hashbrown) [](https://docs.rs/hashbrown) -[](https://github.com/rust-lang/hashbrown) +[](https://github.com/rust-lang/hashbrown) This crate is a Rust port of Google's high-performance [SwissTable] hash map, adapted to make it a drop-in replacement for Rust's standard `HashMap` @@ -26,7 +26,8 @@ in environments without `std`, such as embedded systems and kernels. ## Features - Drop-in replacement for the standard library `HashMap` and `HashSet` types. -- Uses `AHash` as the default hasher, which is much faster than SipHash. +- Uses [AHash](https://github.com/tkaitchuck/aHash) as the default hasher, which is much faster than SipHash. + However, AHash does *not provide the same level of HashDoS resistance* as SipHash, so if that is important to you, you might want to consider using a different hasher. - Around 2x faster than the previous standard library `HashMap`. - Lower memory usage: only 1 byte of overhead per entry instead of 8. - Compatible with `#[no_std]` (but requires a global allocator with the `alloc` crate). @@ -37,47 +38,46 @@ in environments without `std`, such as embedded systems and kernels. Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35). -With the hashbrown default AHash hasher (not HashDoS-resistant): - -```text - name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup - insert_ahash_highbits 20,846 7,397 -13,449 -64.52% x 2.82 - insert_ahash_random 20,515 7,796 -12,719 -62.00% x 2.63 - insert_ahash_serial 21,668 7,264 -14,404 -66.48% x 2.98 - insert_erase_ahash_highbits 29,570 17,498 -12,072 -40.83% x 1.69 - insert_erase_ahash_random 39,569 17,474 -22,095 -55.84% x 2.26 - insert_erase_ahash_serial 32,073 17,332 -14,741 -45.96% x 1.85 - iter_ahash_highbits 1,572 2,087 515 32.76% x 0.75 - iter_ahash_random 1,609 2,074 465 28.90% x 0.78 - iter_ahash_serial 2,293 2,120 -173 -7.54% x 1.08 - lookup_ahash_highbits 3,460 4,403 943 27.25% x 0.79 - lookup_ahash_random 6,377 3,911 -2,466 -38.67% x 1.63 - lookup_ahash_serial 3,629 3,586 -43 -1.18% x 1.01 - lookup_fail_ahash_highbits 5,286 3,411 -1,875 -35.47% x 1.55 - lookup_fail_ahash_random 12,365 4,171 -8,194 -66.27% x 2.96 - lookup_fail_ahash_serial 4,902 3,240 -1,662 -33.90% x 1.51 -``` - -With the libstd default SipHash hasher (HashDoS-resistant): - -```text - name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup - insert_std_highbits 32,598 20,199 -12,399 -38.04% x 1.61 - insert_std_random 29,824 20,760 -9,064 -30.39% x 1.44 - insert_std_serial 33,151 17,256 -15,895 -47.95% x 1.92 - insert_erase_std_highbits 74,731 48,735 -25,996 -34.79% x 1.53 - insert_erase_std_random 73,828 47,649 -26,179 -35.46% x 1.55 - insert_erase_std_serial 73,864 40,147 -33,717 -45.65% x 1.84 - iter_std_highbits 1,518 2,264 746 49.14% x 0.67 - iter_std_random 1,502 2,414 912 60.72% x 0.62 - iter_std_serial 6,361 2,118 -4,243 -66.70% x 3.00 - lookup_std_highbits 21,705 16,962 -4,743 -21.85% x 1.28 - lookup_std_random 21,654 17,158 -4,496 -20.76% x 1.26 - lookup_std_serial 18,726 14,509 -4,217 -22.52% x 1.29 - lookup_fail_std_highbits 25,852 17,323 -8,529 -32.99% x 1.49 - lookup_fail_std_random 25,913 17,760 -8,153 -31.46% x 1.46 - lookup_fail_std_serial 22,648 14,839 -7,809 -34.48% x 1.53 -``` +With the hashbrown default AHash hasher: + +| name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup | +|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------| +| insert_ahash_highbits | 18,865 | 8,020 | -10,845 | -57.49% | x 2.35 | +| insert_ahash_random | 19,711 | 8,019 | -11,692 | -59.32% | x 2.46 | +| insert_ahash_serial | 19,365 | 6,463 | -12,902 | -66.63% | x 3.00 | +| insert_erase_ahash_highbits | 51,136 | 17,916 | -33,220 | -64.96% | x 2.85 | +| insert_erase_ahash_random | 51,157 | 17,688 | -33,469 | -65.42% | x 2.89 | +| insert_erase_ahash_serial | 45,479 | 14,895 | -30,584 | -67.25% | x 3.05 | +| iter_ahash_highbits | 1,399 | 1,092 | -307 | -21.94% | x 1.28 | +| iter_ahash_random | 1,586 | 1,059 | -527 | -33.23% | x 1.50 | +| iter_ahash_serial | 3,168 | 1,079 | -2,089 | -65.94% | x 2.94 | +| lookup_ahash_highbits | 32,351 | 4,792 | -27,559 | -85.19% | x 6.75 | +| lookup_ahash_random | 17,419 | 4,817 | -12,602 | -72.35% | x 3.62 | +| lookup_ahash_serial | 15,254 | 3,606 | -11,648 | -76.36% | x 4.23 | +| lookup_fail_ahash_highbits | 21,187 | 4,369 | -16,818 | -79.38% | x 4.85 | +| lookup_fail_ahash_random | 21,550 | 4,395 | -17,155 | -79.61% | x 4.90 | +| lookup_fail_ahash_serial | 19,450 | 3,176 | -16,274 | -83.67% | x 6.12 | + + +With the libstd default SipHash hasher: + +|name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup | +|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------| +|insert_std_highbits |19,216 |16,885 | -2,331 | -12.13% | x 1.14 | +|insert_std_random |19,179 |17,034 | -2,145 | -11.18% | x 1.13 | +|insert_std_serial |19,462 |17,493 | -1,969 | -10.12% | x 1.11 | +|insert_erase_std_highbits |50,825 |35,847 | -14,978 | -29.47% | x 1.42 | +|insert_erase_std_random |51,448 |35,392 | -16,056 | -31.21% | x 1.45 | +|insert_erase_std_serial |87,711 |38,091 | -49,620 | -56.57% | x 2.30 | +|iter_std_highbits |1,378 |1,159 | -219 | -15.89% | x 1.19 | +|iter_std_random |1,395 |1,132 | -263 | -18.85% | x 1.23 | +|iter_std_serial |1,704 |1,105 | -599 | -35.15% | x 1.54 | +|lookup_std_highbits |17,195 |13,642 | -3,553 | -20.66% | x 1.26 | +|lookup_std_random |17,181 |13,773 | -3,408 | -19.84% | x 1.25 | +|lookup_std_serial |15,483 |13,651 | -1,832 | -11.83% | x 1.13 | +|lookup_fail_std_highbits |20,926 |13,474 | -7,452 | -35.61% | x 1.55 | +|lookup_fail_std_random |21,766 |13,505 | -8,261 | -37.95% | x 1.61 | +|lookup_fail_std_serial |19,336 |13,519 | -5,817 | -30.08% | x 1.43 | ## Usage @@ -85,7 +85,7 @@ Add this to your `Cargo.toml`: ```toml [dependencies] -hashbrown = "0.9" +hashbrown = "0.11" ``` Then: @@ -96,19 +96,19 @@ use hashbrown::HashMap; let mut map = HashMap::new(); map.insert(1, "one"); ``` - +## Flags This crate has the following Cargo features: -- `nightly`: Enables nightly-only features: `#[may_dangle]`. +- `nightly`: Enables nightly-only features including: `#[may_dangle]`. - `serde`: Enables serde serialization support. - `rayon`: Enables rayon parallel iterator support. - `raw`: Enables access to the experimental and unsafe `RawTable` API. - `inline-more`: Adds inline hints to most functions, improving run-time performance at the cost of compilation time. (enabled by default) +- `bumpalo`: Provides a `BumpWrapper` type which allows `bumpalo` to be used for memory allocation. - `ahash`: Compiles with ahash as default hasher. (enabled by default) -- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash, to increase the - DOS-resistance, but can result in issues for `no_std` builds. More details in - [issue#124](https://github.com/rust-lang/hashbrown/issues/124). (enabled by default) +- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash. For targets with no random number generator +this pre-generates seeds at compile time and embeds them as constants. See [aHash's documentation](https://github.com/tkaitchuck/aHash#flags) (disabled by default) ## License |