Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Frequent rehashes when size is close to capacity #85

Closed
edre opened this issue Jun 3, 2019 · 1 comment · Fixed by #86
Closed

Frequent rehashes when size is close to capacity #85

edre opened this issue Jun 3, 2019 · 1 comment · Fixed by #86

Comments

@edre
Copy link
Contributor

edre commented Jun 3, 2019

In the new benchmark suite, for table sizes just under the capacity, inserting and erasing elements leads to frequent resizes and complete table rehashes.

For SIZE=895:
test insert_erase_std_highbits ... bench:  16,548,714 ns/iter (+/- 1,936,585)
test insert_erase_std_random   ... bench:  16,376,567 ns/iter (+/- 1,338,857)
test insert_erase_std_serial   ... bench:  14,408,640 ns/iter (+/- 2,043,451)

For SIZE=896:
test insert_erase_std_highbits ... bench:      61,495 ns/iter (+/- 6,014)
test insert_erase_std_random   ... bench:      63,244 ns/iter (+/- 3,980)
test insert_erase_std_serial   ... bench:      60,410 ns/iter (+/- 13,798)

The benchmark is inserting and removing items in a loop keeping it at the given size, and once we generate one DELETED control byte we get pushed over the growth_left limit. We're then forced into a resize for a table of the same size as the one we started with. Ideally the amortized cost of insert/remove should be constant.

@edre
Copy link
Contributor Author

edre commented Jun 4, 2019

For comparison, the absl hash table always doubles the size if it doesn't rehash in place from an insertion [1], but has different logic for reserve calls. [2]

[1] https://github.com/abseil/abseil-cpp/blob/aa468ad/absl/container/internal/raw_hash_set.h#L1579
[2] https://github.com/abseil/abseil-cpp/blob/aa468ad/absl/container/internal/raw_hash_set.h#L1219

edre added a commit to edre/hashbrown that referenced this issue Jun 4, 2019
…deletions.

Otherwise we can force a rehash for each insert and removal if we're right under the size limit.

Benchmark with SIZE=895, just under a rehash limit.
    name                     oops ns/iter  okthen ns/iter  diff ns/iter   diff %   speedup
    insert_erase_std_serial  9,875,585     60,696            -9,814,889  -99.39%  x 162.71

Fixes rust-lang#85
edre added a commit to edre/hashbrown that referenced this issue Jun 5, 2019
…deletions.

Otherwise we can force a rehash for each insert and removal if we're right under the size limit.

Benchmark with SIZE=895, just under a rehash limit.
    name                     oops ns/iter  okthen ns/iter  diff ns/iter   diff %   speedup
    insert_erase_std_serial  9,875,585     60,696            -9,814,889  -99.39%  x 162.71

Fixes rust-lang#85
edre added a commit to edre/hashbrown that referenced this issue Jun 5, 2019
…deletions.

Otherwise we can force a rehash for each insert and removal if we're right under the size limit.

Benchmark with SIZE=895, just under a rehash limit.
    name                     oops ns/iter  okthen ns/iter  diff ns/iter   diff %   speedup
    insert_erase_std_serial  9,875,585     60,696            -9,814,889  -99.39%  x 162.71

Fixes rust-lang#85
bors added a commit that referenced this issue Jun 6, 2019
Resize with a more conservative amount of space after deletions

Otherwise we can force a rehash for each insert and removal if we're right under the size limit.

Benchmark with SIZE=895, just under a rehash limit.
    name                     oops ns/iter  okthen ns/iter  diff ns/iter   diff %   speedup
    insert_erase_std_serial  9,875,585     60,696            -9,814,889  -99.39%  x 162.71

Fixes #85
@bors bors closed this as completed in #86 Jun 6, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant