Skip to content

Reduce size overhead of adaptative hashmap#40237

Merged
bors merged 1 commit intorust-lang:masterfrom
arthurprs:hm-adapt2
Mar 9, 2017
Merged

Reduce size overhead of adaptative hashmap#40237
bors merged 1 commit intorust-lang:masterfrom
arthurprs:hm-adapt2

Conversation

@arthurprs
Copy link
Contributor

@arthurprs arthurprs commented Mar 3, 2017 •
edited
Loading

Exposes a boolean flag in RawTable and use it instead of a bool field in HashMap.

Taking a bit from capacity or length would make overflow handling tricky.

Fixes: #40042

@rust-highfive
Copy link
Contributor

rust-highfive commented Mar 3, 2017

r? @BurntSushi

(rust_highfive has picked a reviewer for you, use r? to override)

nagisa
nagisa reviewed Mar 3, 2017
View reviewed changes
src/libstd/collections/hash/table.rs Outdated
Copy link
Member

@nagisa nagisa Mar 3, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

1 is the smallest alignment possible, so this assertion is always triggered, no?

Copy link
Contributor Author

@arthurprs arthurprs Mar 3, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I was under the impression that hashes in raw table is always aligned to at least four. I'll double check.

Copy link
Member

@nagisa nagisa Mar 3, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh wait, never mind me.

Copy link
Member

@nagisa nagisa Mar 3, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So, a few comments here.

While I don’t think that happens in practice, it is certainly possible for HashUint get an alignment of 1 in theory. For example a custom data-layout could be used to achieve that. This is one minor portability concern.

I’m somewhat doubting the need to have this as a generic pointer, rather than just a TaggedHashUintPtr type. This is so unusual a thing to do, that having a generic version is unlikely to ever have any benefit.

Copy link
Contributor Author

@arthurprs arthurprs Mar 3, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good point, I'll get rid of the generic.

@arthurprs
Copy link
Contributor Author

arthurprs commented Mar 3, 2017

I screwed the diff, will fix shortly.

@nagisa
Copy link
Member

nagisa commented Mar 3, 2017

@arthurprs I remember you having some nice benchmarks for previous PR. Could you rerun those and make a comparison between having separate bool, embedding bool into tagged pointer and the state before adaptive hashing was implemented?

@arthurprs arthurprs force-pushed the hm-adapt2 branch 2 times, most recently from 3010727 to 347180f Compare March 3, 2017 22:36
@arthurprs
Copy link
Contributor Author

arthurprs commented Mar 3, 2017 •
edited
Loading

I did some benchmarks and discovered some weird inline failures

There's things like

   5eb50:	55                   	push   %rbp
   5eb51:	48 89 e5             	mov    %rsp,%rbp
   5eb54:	5d                   	pop    %rbp
   5eb55:	c3                   	retq   
   5eb56:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
   5eb5d:	00 00 00

really... same for the small functions of the tagged ptr.

I added some inline annotations and it was enough to bring the performance diff down to noise.

 name                          pre ns/iter  adp ns/iter  diff ns/iter   diff % 
 ::_warmup                     9,879,877    9,717,641        -162,236   -1.64% 
 ::grow_100_000                9,791,163    9,780,559         -10,604   -0.11% 
 ::grow_10_000                 817,340      857,893            40,553    4.96% 
 ::grow_big_value_100_000      18,160,315   18,247,759         87,444    0.48% 
 ::grow_big_value_10_000       1,773,579    1,773,119            -460   -0.03% 
 ::insert_1000                 24,019       23,320               -699   -2.91% 
 ::insert_100_000              4,109,099    3,941,102        -167,997   -4.09% 
 ::insert_10_000               302,664      289,692           -12,972   -4.29% 
 ::insert_1_000_000            102,924,155  103,442,875       518,720    0.50% 
 ::insert_int_bigvalue_10_000  728,218      735,648             7,430    1.02% 
 ::insert_str_10_000           284,537      281,461            -3,076   -1.08% 
 ::insert_string_10_000        735,035      735,932               897    0.12% 
 ::lookup_100_000              212,963      213,979             1,016    0.48% 
 ::lookup_100_000_unif         209,842      209,719              -123   -0.06% 
 ::lookup_1_000_000_unif       705,827      714,638             8,811    1.25% 
 ::lru_sim                     61,649,969   60,346,446     -1,303,523   -2.11% 
 ::merge_dos                   47,713,779   578,203       -47,135,576  -98.79% 
 ::merge_shuffle               1,158,273    1,153,456          -4,817   -0.42%

@arthurprs
Reduce size overhead of adaptative hashmap
3273003 
Exposes a boolean flag in RawTable and use it
instead of a bool field in HashMap.

Fixes: rust-lang#40042
@nagisa
Copy link
Member

nagisa commented Mar 4, 2017

I did some benchmarks and discovered some weird inline failures

These happened because Tagged*Ptr thing became non-generic and got instantiated directly into libcollections crate, and thus couldn’t be considered for inlining. Adding #[inline] is the right solution to that.

All in all implementation of this looks very good to me, but since I’m not a T-libs person, I cannot take the liberty to r+ this.

@alexcrichton
Copy link
Member

alexcrichton commented Mar 6, 2017

@bors: r+

Thanks @arthurprs!

@bors
Copy link
Collaborator

bors commented Mar 6, 2017

📌 Commit 3273003 has been approved by alexcrichton

arielb1 pushed a commit to arielb1/rust that referenced this pull request Mar 8, 2017
Rollup merge of rust-lang#40237 - arthurprs:hm-adapt2, r=alexcrichton
2c252ff 
Reduce size overhead of adaptative hashmap

Exposes a boolean flag in RawTable and use it instead of a bool field in HashMap.

Taking a bit from capacity or length would make overflow handling tricky.

Fixes: rust-lang#40042
@arielb1 arielb1 mentioned this pull request Mar 8, 2017
Merged
bors added a commit that referenced this pull request Mar 9, 2017
@bors
Auto merge of #40368 - arielb1:rollup, r=arielb1
3087a1f 
Rollup of 20 pull requests

- Successful merges: #40154, #40222, #40226, #40237, #40254, #40258, #40265, #40268, #40279, #40283, #40292, #40293, #40296, #40316, #40321, #40325, #40326, #40327, #40333, #40335
- Failed merges:
@bors bors merged commit 3273003 into rust-lang:master Mar 9, 2017
@bors
Copy link
Collaborator

bors commented Mar 9, 2017

⌛ Testing commit 3273003 with merge 3087a1f...

@arthurprs arthurprs deleted the hm-adapt2 branch March 9, 2017 10:58
@arthurprs arthurprs restored the hm-adapt2 branch March 9, 2017 10:58
@arthurprs arthurprs deleted the hm-adapt2 branch March 10, 2017 08:49
@arthurprs arthurprs restored the hm-adapt2 branch March 10, 2017 08:49
@arthurprs arthurprs deleted the hm-adapt2 branch March 10, 2017 08:50
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@nagisa nagisa nagisa left review comments

Assignees

@BurntSushi BurntSushi

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@arthurprs @rust-highfive @nagisa @alexcrichton @bors @BurntSushi