about summary refs log tree commit diff
path: root/compiler/rustc_trait_selection/src
diff options
context:
space:
mode:
authorAngelicosPhosphoros <xuzin.timur@gmail.com>2022-05-20 15:38:04 +0300
committerAngelicosPhosphoros <xuzin.timur@gmail.com>2022-05-20 18:46:24 +0300
commitde97d7393fd20215cdc1a2cacfa84290df4ae460 (patch)
tree05078be60065b3bc6c52efcc47a31b9ab4883b73 /compiler/rustc_trait_selection/src
parentcd73afadae5b0163f9285f1b5edbbd1c84fde410 (diff)
downloadrust-de97d7393fd20215cdc1a2cacfa84290df4ae460.tar.gz
rust-de97d7393fd20215cdc1a2cacfa84290df4ae460.zip
Add complexity estimation of iterating over HashSet and HashMap
It is not obvious (at least for me) that complexity of iteration over hash tables depends on capacity and not length. Especially comparing with other containers like Vec or String. I think, this behaviour is worth mentioning.

I run benchmark which tests iteration time for maps with length 50 and different capacities and get this results:
```
capacity - time
64       - 203.87 ns
256      - 351.78 ns
1024     - 607.87 ns
4096     - 965.82 ns
16384    - 3.1188 us
```

If you want to dig why it behaves such way, you can look current implementation in [hashbrown code](https://github.com/rust-lang/hashbrown/blob/f3a9f211d06f78c5beb81ac22ea08fdc269e068f/src/raw/mod.rs#L1933).

Benchmarks code would be presented in PR related to this commit.
Diffstat (limited to 'compiler/rustc_trait_selection/src')
0 files changed, 0 insertions, 0 deletions