Small HashSets have terrible performance compared to an array. Why not use an array with small sets? This is a step towards getting that working.
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.