rust-lang/rust — pull request #15720 by pczarn (2014-07-16 15:08:34+00:00)
Title: Optimized HashMap. RawTable exposes a safe interface.

First, a benchmark of the original hashmap implementation on Intel i3.
```
find_existing ... 54450 ns/iter (+/- 5524)
find_nonexisting ... 52472 ns/iter (+/- 1672)
find_pop_insert ... 262 ns/iter (+/- 3)
hashmap_as_queue ... 148 ns/iter (+/- 0)
insert ... 183 ns/iter (+/- 6)
new_drop ... 200 ns/iter (+/- 52)
new_insert_drop ... 317 ns/iter (+/- 104)
```

## `bucket_distance` and `pop_internal`

A branchless implementation of probe count calculation. A branch was necessary to avoid unsigned underflow. Since the `capacity` is a power of 2, we can ignore underflow and simply return the difference modulo capacity. We can use the fact that indexes >= capacity are acceptable later on.

`pop_internal` returns `V` instead of `Option`.

No more low hanging fruits...

## iteration over buckets

Let's use external iterators for their greatest advantage in Rust: to efficiently avoid bounds checks. Thus `{Empty,Full}Index` becomes `{Empty,Full}Bucket`.

The growing is done an optimized reinsertion algorithm based on `insert_hashed_ordered`. `HashMap::new()` returns a table with the capacity set to 0. Hashmaps that never had an element inserted won't allocate, as measured by `bench::new_drop`.

Removed two pointers from `RawTable` as they can be recalculated once per iteration rather than every indexing operation. `RawTable` struct is as small as `Vec` with 24 bytes.

Reduced code duplication between `swap` and `insert_hashed_nocheck`. Created a new method `insert_or_replace_with` that accepts a simple closure for this. Moreover, `robin_hood` will most likely get inlined.

```
find_existing ... 45556 ns/iter (+/- 1510)
find_nonexisting ... 43812 ns/iter (+/- 1212)
find_pop_insert ... 224 ns/iter (+/- 9)
hashmap_as_queue ... 134 ns/iter (+/- 0)
insert ... 183 ns/iter (+/- 14)
new_drop ... 118 ns/iter (+/- 2)
new_insert_drop ... 241 ns/iter (+/- 29)
```

## safe interface

This is possible thanks to a lot of prior work by @nikomatsakis!

To eliminate the double-take issue, we must tie a bucket pointer to a reference to the table within a private structure. Only a bucket that holds a unique reference can be updated. `GapThenFull` uses a similar strategy to encapsulate two consecutive buckets and a single reference. Some of HashMap's methods became functions parameterized over mutability.

We could use an uninit reference or drop trickery to replace one zeroing of a bucket's hash per `shift` of `GapThenFull` with a single memory access. The former language feature is not planned and the latter seems inefficient.

```
find_existing ... 48131 ns/iter (+/- 3469)
find_nonexisting ... 48518 ns/iter (+/- 1785)
find_pop_insert ... 238 ns/iter (+/- 5)
hashmap_as_queue ... 131 ns/iter (+/- 2)
insert ... 217 ns/iter (+/- 6)
new_drop ... 120 ns/iter (+/- 11)
new_insert_drop ... 238 ns/iter (+/- 25)
```

## split hashmap.rs into separate files

Total number of lines approaches 3000.

## final refactoring

Standalone `robin_hood`.

I realized that `insert_or_update_with` can call `insert_or_replace_with` directly.

Inlining now started happening in microbenchmarks for some reason. Looks like `search_hashed_generic` is quite small:
```
find_existing ... 51137 ns/iter (+/- 8663)
find_nonexisting ... 17286 ns/iter (+/- 2961)
find_pop_insert ... 198 ns/iter (+/- 4)
hashmap_as_queue ... 134 ns/iter (+/- 1)
insert ... 220 ns/iter (+/- 5)
new_drop ... 121 ns/iter (+/- 11)
new_insert_drop ... 234 ns/iter (+/- 6)
```

## conclusion
Further optimizations are increasingly difficult, usually they would require new language features or make the code unreadable.

It's possible to build cache aware HashMap on top of a vector of SoAs, such as `Vec<([u64, ..N], [K, ..N], [V, ..N])>`. Possibility of in-place growing is the only performance advantage of this approach. Unfortunately, (an increase in iteration complexity)[https://github.com/pczarn/code/blob/master/rust/vectrivec/mod.rs] surpasses benefits of storage reuse.

Documentation is not finished. Most methods need more comments and tests.

Robin hood hashing scheme was introduced in #12081.

cc @cgaebel