Bug 223895

Summary: [WTF] Introduce RobinHoodHashTable
Product: WebKit Reporter: Yusuke Suzuki <ysuzuki>
Component: New BugsAssignee: Yusuke Suzuki <ysuzuki>
Status: RESOLVED FIXED    
Severity: Normal CC: aboxhall, annulen, apinheiro, benjamin, cdumez, cfleizach, changseok, cmarcelo, dino, dmazzoni, eric.carlson, esprehn+autocc, ews-watchlist, fmalita, fpizlo, glenn, gyuyoung.kim, jcraig, jdiggs, jer.noble, kangil.han, keith_miller, kondapallykalyan, mark.lam, mifenton, mmaxfield, msaboff, pdr, philipj, ryuan.choi, saam, sabouhallawa, samuel_white, sam, schenney, sergio, tzagallo, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
ews-feeder: commit-queue-
Patch
none
Patch
ews-feeder: commit-queue-
Patch
ews-feeder: commit-queue-
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
none
Patch
ews-feeder: commit-queue-
Patch
none
Patch
none
Patch
fpizlo: review+
Patch
none
Patch
none
Patch none

Description Yusuke Suzuki 2021-03-29 13:02:51 PDT 
[WTF] Introduce RobinHoodHashTable
Comment 1 Yusuke Suzuki 2021-03-29 13:03:24 PDT 
Created attachment 424567 [details]
Patch
Comment 2 Yusuke Suzuki 2021-03-29 13:07:38 PDT 
Created attachment 424568 [details]
Patch
Comment 3 Yusuke Suzuki 2021-03-29 14:44:13 PDT 
Created attachment 424583 [details]
Patch
Comment 4 Yusuke Suzuki 2021-03-29 14:47:05 PDT 
Created attachment 424584 [details]
Patch
Comment 5 Yusuke Suzuki 2021-03-29 14:58:36 PDT 
Created attachment 424586 [details]
Patch
Comment 6 Yusuke Suzuki 2021-03-29 16:04:21 PDT 
Created attachment 424599 [details]
Patch
Comment 7 Yusuke Suzuki 2021-03-29 22:41:43 PDT 
Created attachment 424617 [details]
Patch
Comment 8 Yusuke Suzuki 2021-03-30 01:17:36 PDT 
Created attachment 424621 [details]
Patch
Comment 9 Yusuke Suzuki 2021-03-30 01:36:51 PDT 
Created attachment 424623 [details]
Patch
Comment 10 Yusuke Suzuki 2021-03-30 13:31:02 PDT 
Created attachment 424682 [details]
Patch
Comment 11 Yusuke Suzuki 2021-03-30 16:26:47 PDT 
Created attachment 424712 [details]
Patch
Comment 12 Yusuke Suzuki 2021-03-31 03:07:17 PDT 
Created attachment 424750 [details]
Patch
Comment 13 Yusuke Suzuki 2021-03-31 03:43:23 PDT 
Created attachment 424752 [details]
Patch
Comment 14 Radar WebKit Bug Importer 2021-03-31 11:23:42 PDT 
<rdar://problem/76061870>
Comment 15 Yusuke Suzuki 2021-03-31 13:12:59 PDT 
Created attachment 424810 [details]
Patch
Comment 16 Yusuke Suzuki 2021-03-31 23:55:06 PDT 
Created attachment 424874 [details]
Patch
Comment 17 Yusuke Suzuki 2021-03-31 23:59:03 PDT 
Created attachment 424875 [details]
Patch
Comment 18 Yusuke Suzuki 2021-04-01 00:23:01 PDT 
Created attachment 424877 [details]
Patch
Comment 19 Yusuke Suzuki 2021-04-01 01:56:49 PDT 
Created attachment 424882 [details]
Patch
Comment 20 Yusuke Suzuki 2021-04-01 05:41:44 PDT 
Created attachment 424888 [details]
Patch
Comment 21 Filip Pizlo 2021-04-01 07:48:12 PDT 
Comment on attachment 424888 [details]
Patch

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

> Source/WTF/wtf/RobinHoodHashTable.h:312
> +    while (1) {

Maybe while (true) here and elsewhere?
Comment 22 Yusuke Suzuki 2021-04-01 10:01:00 PDT 
Comment on attachment 424888 [details]
Patch

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

>> Source/WTF/wtf/RobinHoodHashTable.h:312
>> +    while (1) {
> 
> Maybe while (true) here and elsewhere?

Yeah, fixed :)
Comment 23 Yusuke Suzuki 2021-04-01 14:52:36 PDT 
Created attachment 424950 [details]
Patch
Comment 24 Yusuke Suzuki 2021-04-01 16:46:49 PDT 
Created attachment 424961 [details]
Patch
Comment 25 Yusuke Suzuki 2021-04-01 23:40:24 PDT 
Created attachment 424992 [details]
Patch
Comment 26 Yusuke Suzuki 2021-04-02 01:33:45 PDT 
Committed r275410 (236073@main): <https://commits.webkit.org/236073@main>
Comment 27 Yusuke Suzuki 2021-04-02 01:50:32 PDT 
Committed r275411 (236074@main): <https://commits.webkit.org/236074@main>
Comment 28 Sam Weinig 2021-04-02 12:47:23 PDT 
Comment on attachment 424888 [details]
Patch

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

Very cool. I think as a follow up we should consider renaming WTF::HashTable to something more evocative of its implementation, since it is now just one of multiple table implementations one can choose.

> Source/WTF/ChangeLog:23
> +        1. MemoryCompactLookupOnlyRobinHoodHashSet / HashMap

Could we gain even more here by making these perfect hash tables (ala gperf)?

> Source/JavaScriptCore/runtime/Identifier.h:297
> +    static constexpr bool hasHashInValue = true;

I'm not a huge fan of this name, as it reads to me as "has hashInValue" and the use of "value" makes me think that means it is not in the key.  Perhaps something like "hashValueStoredInKey"? It would also be good to document this somewhere in HashFunctions.h.
Comment 29 Sam Weinig 2021-04-02 12:49:48 PDT 
https://blog.quarkslab.com/frozen-an-header-only-constexpr-alternative-to-gperf-for-c14-users.html as example of a perfect hash in c++.
Comment 30 Sam Weinig 2021-04-02 12:51:55 PDT 
or https://github.com/Kronuz/constexpr-phf