Bug 199982 - Speed up HashTable decoding by reserving capacity and avoiding rehashing
Summary: Speed up HashTable decoding by reserving capacity and avoiding rehashing
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Chris Dumez
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2019-07-20 12:20 PDT by Chris Dumez
Modified: 2019-07-20 20:53 PDT (History)
11 users (show)

See Also:

Attachments
Patch (7.87 KB, patch)
2019-07-20 12:27 PDT, Chris Dumez 		no flags Details | Formatted Diff | Diff
Patch (8.08 KB, patch)
2019-07-20 20:11 PDT, Chris Dumez 		no flags Details | Formatted Diff | Diff
Show Obsolete (1) View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Chris Dumez 2019-07-20 12:20:08 PDT 
Speed up HashTable decoding by reserving capacity and avoiding rehashing.
Comment 1 Chris Dumez 2019-07-20 12:27:31 PDT 
Created attachment 374560 [details]
Patch
Comment 2 Radar WebKit Bug Importer 2019-07-20 12:27:56 PDT 
<rdar://problem/53351433>
Comment 3 EWS Watchlist 2019-07-20 14:26:42 PDT 
Comment on attachment 374560 [details]
Patch

Attachment 374560 [details] did not pass jsc-ews (mac):
Output: https://webkit-queues.webkit.org/results/12780815

New failing tests:
mozilla-tests.yaml/js1_5/Array/regress-101964.js.mozilla-no-ftl
apiTests
Comment 4 Saam Barati 2019-07-20 16:28:33 PDT 
Comment on attachment 374560 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=374560&action=review

> Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:1041
> +TEST(WTF_HashMap, ReserveInitialCapacity)

Can you also add a test where you add more things past the initial capacity and ensure that the integrity of the table is maintained. Also, what happens when you reserve initial capacity then remove an entry from the table? Will we immediately rehash? (I’m not sure that’s terrible since that goes against the spirit of the API, but I’m just curious).

Might be worth adding a test where we do deletion after reserveInitialCapacity too just to ensure the integrity of the table
Comment 5 Geoffrey Garen 2019-07-20 17:39:02 PDT 
Comment on attachment 374560 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=374560&action=review

>> Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:1041
>> +TEST(WTF_HashMap, ReserveInitialCapacity)
> 
> Can you also add a test where you add more things past the initial capacity and ensure that the integrity of the table is maintained. Also, what happens when you reserve initial capacity then remove an entry from the table? Will we immediately rehash? (I’m not sure that’s terrible since that goes against the spirit of the API, but I’m just curious).
> 
> Might be worth adding a test where we do deletion after reserveInitialCapacity too just to ensure the integrity of the table

My reading is that remove() after reserveInitialCapacity() would indeed rehash in most cases (due to shouldShrink() and the minLoad constant). I think that's OK.

Subtly, it would rehash to half the reserved size, rather than the ideal size, due to the assumption that all calls to grow() happen after a limit is reached. I think that's also OK.
Comment 6 Chris Dumez 2019-07-20 20:11:11 PDT 
Created attachment 374565 [details]
Patch
Comment 7 WebKit Commit Bot 2019-07-20 20:53:37 PDT 
Comment on attachment 374565 [details]
Patch

Clearing flags on attachment: 374565

Committed r247673: <https://trac.webkit.org/changeset/247673>
Comment 8 WebKit Commit Bot 2019-07-20 20:53:39 PDT 
All reviewed patches have been landed.  Closing bug.