diff options
Diffstat (limited to 'vendor/indexmap/README.md')
| -rw-r--r-- | vendor/indexmap/README.md | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/vendor/indexmap/README.md b/vendor/indexmap/README.md new file mode 100644 index 000000000..d80b7099c --- /dev/null +++ b/vendor/indexmap/README.md @@ -0,0 +1,55 @@ +# indexmap + +[](https://github.com/bluss/indexmap/actions) +[](https://crates.io/crates/indexmap) +[](https://docs.rs/indexmap) +[](https://img.shields.io/badge/rust-1.56%2B-orange.svg) + +A pure-Rust hash table which preserves (in a limited sense) insertion order. + +This crate implements compact map and set data-structures, +where the iteration order of the keys is independent from their hash or +value. It preserves insertion order (except after removals), and it +allows lookup of entries by either hash table key or numerical index. + +Note: this crate was originally released under the name `ordermap`, +but it was renamed to `indexmap` to better reflect its features. + +# Background + +This was inspired by Python 3.6's new dict implementation (which remembers +the insertion order and is fast to iterate, and is compact in memory). + +Some of those features were translated to Rust, and some were not. The result +was indexmap, a hash table that has following properties: + +- Order is **independent of hash function** and hash values of keys. +- Fast to iterate. +- Indexed in compact space. +- Preserves insertion order **as long** as you don't call `.remove()`. +- Uses hashbrown for the inner table, just like Rust's libstd `HashMap` does. + +## Performance + +`IndexMap` derives a couple of performance facts directly from how it is constructed, +which is roughly: + +> A raw hash table of key-value indices, and a vector of key-value pairs. + +- Iteration is very fast since it is on the dense key-values. +- Removal is fast since it moves memory areas only in the table, + and uses a single swap in the vector. +- Lookup is fast-ish because the initial 7-bit hash lookup uses SIMD, and indices are + densely stored. Lookup also is slow-ish since the actual key-value pairs are stored + separately. (Visible when cpu caches size is limiting.) + +- In practice, `IndexMap` has been tested out as the hashmap in rustc in [PR45282] and + the performance was roughly on par across the whole workload. +- If you want the properties of `IndexMap`, or its strongest performance points + fits your workload, it might be the best hash table implementation. + +[PR45282]: https://github.com/rust-lang/rust/pull/45282 + +# Recent Changes + +See [RELEASES.md](https://github.com/bluss/indexmap/blob/master/RELEASES.md). |