Skip to content

Use hashbrown's new single-lookup insertion#263

Merged
cuviper merged 1 commit intoindexmap-rs:masterfrom
cuviper:insert_in_slot
Jun 6, 2023
Merged

Use hashbrown's new single-lookup insertion#263
cuviper merged 1 commit intoindexmap-rs:masterfrom
cuviper:insert_in_slot

Conversation

@cuviper
Copy link
Member

@cuviper cuviper commented Jun 6, 2023

With find_or_find_insert_slot and insert_in_slot, we can avoid an
extra insertion lookup after checking for existence. However, that also
reserves space for a new entry before checking existence, so it's a
little biased towards new items. For that reason, we're not using this
for map entry or set replace, as both imply a little more weight on
the expectation that it may already exist.

@cuviper
Use hashbrown's new single-lookup insertion
c37dae6 
With `find_or_find_insert_slot` and `insert_in_slot`, we can avoid an
extra insertion lookup after checking for existence. However, that also
reserves space for a new entry *before* checking existence, so it's a
little biased towards new items. For that reason, we're not using this
for map `entry` or set `replace`, as both imply a little more weight on
the expectation that it may already exist.
@cuviper
Copy link
Member Author

cuviper commented Jun 6, 2023

Benchmarks with rustc 1.72.0-nightly (e6d4725c7 2023-06-05) on Fedora 38, AMD Ryzen 7 5800X:

$ cargo benchcmp --threshold=5 master insert_in_slot
 name                           master ns/iter  insert_in_slot ns/iter  diff ns/iter   diff %  speedup
 entry_indexmap_150             2,110           2,265                            155    7.35%   x 0.93
 grow_fnv_indexmap_100_000      2,509,579       2,297,042                   -212,537   -8.47%   x 1.09
 indexmap_clone_for_sort_u32    13,637          12,636                        -1,001   -7.34%   x 1.08
 indexmap_merge_simple          237,821         225,027                      -12,794   -5.38%   x 1.06
 insert_indexmap_100_000        1,915,473       1,623,913                   -291,560  -15.22%   x 1.18
 insert_indexmap_10_000         144,566         126,376                      -18,190  -12.58%   x 1.14
 insert_indexmap_150            2,153           1,897                           -256  -11.89%   x 1.13
 iter_black_box_hashmap_10_000  6,049           4,800                         -1,249  -20.65%   x 1.26
 lookup_hashmap_100_000_single  13              12                                -1   -7.69%   x 1.08
 with_capacity_10e5_hashmap     161             152                               -9   -5.59%   x 1.06

Those are some good wins on insert*. The others are more confusing, some which have nothing to do with these changes at all. The loss on entry_indexmap_150 looks like just different inlining decisions, since I changed push, but it's close enough that I expect real-world scenarios could vary a lot more.

@cuviper cuviper merged commit bb48357 into indexmap-rs:master Jun 6, 2023
@cuviper cuviper mentioned this pull request Jul 8, 2023
Merged
@cuviper cuviper deleted the insert_in_slot branch July 18, 2023 02:41
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@cuviper