| Summary: | HashTable should have inline capacity | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Alex Christensen <achristensen> | ||||||||||||||
| Component: | Web Template Framework | Assignee: | Alex Christensen <achristensen> | ||||||||||||||
| Status: | NEW --- | ||||||||||||||||
| Severity: | Normal | CC: | barraclough, benjamin, buildbot, cmarcelo, commit-queue, ggaren, kling, rniwa | ||||||||||||||
| Priority: | P2 | ||||||||||||||||
| Version: | 528+ (Nightly build) | ||||||||||||||||
| Hardware: | Unspecified | ||||||||||||||||
| OS: | Unspecified | ||||||||||||||||
| Attachments: |
|
||||||||||||||||
|
Description
Alex Christensen
2015-03-27 15:36:07 PDT
Created attachment 249614 [details]
Patch
Created attachment 249622 [details]
Patch
Created attachment 249626 [details]
Patch
Comment on attachment 249626 [details] Patch Attachment 249626 [details] did not pass mac-wk2-ews (mac-wk2): Output: http://webkit-queues.appspot.com/results/5911759877570560 Number of test failures exceeded the failure limit. Created attachment 249629 [details]
Archive of layout-test-results from ews105 for mac-mavericks-wk2
The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews105 Port: mac-mavericks-wk2 Platform: Mac OS X 10.9.5
Created attachment 249630 [details]
Patch
Created attachment 249635 [details]
Patch
Feel free to review, but I'm going to gather some data about HashTable sizes before landing this to have some speculative evidence that this is a good direction to go. In the destructor of HashTable I printed out the largest m_keyCount a HashTable had seen, and I found this histogram data from opening Gmail and Facebook in MiniBrowser:
Max Size Hash Table Count
0 1187217
1 113932
2 64251
3 36962
4 23451
5 14731
6 12945
7 8240
8 6282
>8 39911
Most HashTables never get an entry. We already optimized for this case.
>30% of HashTables that get entries only get 1 entry before being destroyed.
>80% of HashTables that get entries never grow beyond a size of 8.
Based on this data, I think it is worth looking into optimizing small HashTables and this is a step in the right direction.
(In reply to comment #9) It seems like it would be especially valuable to optimize for the zero case. I don't think we quite do that right now, since an empty has table has a pretty large constant overhead. Perhaps a good first step is to make a table just a pointer, and use the null pointer to indicate an empty table. That would make the empty table 3X smaller. Side note: if we want to specialize for, say, the <= 3 case, the best specialization is probably to use a vector rather than a hash table. Comment on attachment 249635 [details]
Patch
I'm going to look into making a HashTable just a pointer. Inline capacity is too specific to my one use case, and it probably shouldn't go in WTF.
|