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.

Sign up for GitHub

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

Jump to bottom

HashMap: Does not reserve in extend #36579

Closed
bluss opened this issue Sep 19, 2016 · 4 comments
Closed

HashMap: Does not reserve in extend #36579

bluss opened this issue Sep 19, 2016 · 4 comments
Labels
I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@bluss
Copy link
Member

bluss commented Sep 19, 2016 •
edited
Loading

HashMap: Does not reserve in extend. This exacerbates the performance pathology when extending one map with another, mentioned in #36481.

(I'm working on a fix)
This was referenced Sep 19, 2016
Closed
Closed
@bluss bluss added the I-slow Issue: Problems and improvements with respect to performance of generated code. label Sep 19, 2016
@bluss
Copy link
Member Author

bluss commented Sep 19, 2016

This should probably be closed ("WONTFIX") if we accept that hashmaps must be ready for being extended with iterators that are just duplicates of existing keys (i.e. no growth needed).

@sfackler sfackler added the T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. label Sep 19, 2016
@sfackler
Copy link
Member

Hmm, yeah, the overlap case is interesting. Probably worth discussing with @rust-lang/libs but I think I agree that the current no reserve behavior is the way to go.

@alexcrichton
Copy link
Member

Closing due to this comment but the libs team is very interested in exploring our options here!

@arthurprs
Copy link
Contributor

arthurprs commented Oct 31, 2016 •
edited
Loading

I think the decision here is a bit too conservative, we should discuss some sort of middle ground (even if arbitrary). The stdlib HM is optimized for reads, not writes, and this decision sort of goes against that.

From the top of my head I can think of two ways to move this forward

  1. Assume some factor of overlap but reserve a fraction of the items upfront.
  2. Consider a more write optimized load factor when doing batch inserts.

@arthurprs arthurprs mentioned this issue Nov 26, 2016
Merged
bors added a commit that referenced this issue Dec 6, 2016
@bors
Auto merge of #38017 - arthurprs:hm-extend, r=bluss
5f128ed 
Smarter HashMap/HashSet pre-allocation for extend/from_iter

HashMap/HashSet from_iter and extend are making totally different assumptions.

A more balanced decision may allocate half the lower hint (rounding up). For "well defined" iterators this effectively limits the worst case to two resizes (the initial reserve + one resize).

cc #36579
cc @bluss
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@alexcrichton @arthurprs @sfackler @bluss