Bug 199982 – Speed up HashTable decoding by reserving capacity and avoiding rehashing

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Chris Dumez]

Speed up HashTable decoding by reserving capacity and avoiding rehashing.

[Chris Dumez]

Created attachment 374560 [details]
Patch

[Radar WebKit Bug Importer]

<rdar://problem/53351433>

[EWS Watchlist]

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

[Saam Barati]

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

[Geoffrey Garen]

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.

[Chris Dumez]

Created attachment 374565 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 374565 [details]
Patch

Clearing flags on attachment: 374565

Committed r247673: <https://trac.webkit.org/changeset/247673>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.