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

Yusuke Suzuki
Reported 2021-03-29 13:02:51 PDT
[WTF] Introduce RobinHoodHashTable
Attachments
Patch (65.28 KB, patch)
2021-03-29 13:03 PDT, Yusuke Suzuki 		ews-feeder: commit-queue-
DetailsFormatted DiffDiff
Patch (65.31 KB, patch)
2021-03-29 13:07 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (100.45 KB, patch)
2021-03-29 14:44 PDT, Yusuke Suzuki 		ews-feeder: commit-queue-
DetailsFormatted DiffDiff
Patch (100.50 KB, patch)
2021-03-29 14:47 PDT, Yusuke Suzuki 		ews-feeder: commit-queue-
DetailsFormatted DiffDiff
Patch (99.51 KB, patch)
2021-03-29 14:58 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (105.16 KB, patch)
2021-03-29 16:04 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (107.95 KB, patch)
2021-03-29 22:41 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (109.11 KB, patch)
2021-03-30 01:17 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (109.14 KB, patch)
2021-03-30 01:36 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (108.64 KB, patch)
2021-03-30 13:31 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (143.79 KB, patch)
2021-03-30 16:26 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (216.18 KB, patch)
2021-03-31 03:07 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (216.88 KB, patch)
2021-03-31 03:43 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (219.19 KB, patch)
2021-03-31 13:12 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (289.69 KB, patch)
2021-03-31 23:55 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (289.68 KB, patch)
2021-03-31 23:59 PDT, Yusuke Suzuki 		ews-feeder: commit-queue-
DetailsFormatted DiffDiff
Patch (289.73 KB, patch)
2021-04-01 00:23 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (289.99 KB, patch)
2021-04-01 01:56 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (290.42 KB, patch)
2021-04-01 05:41 PDT, Yusuke Suzuki 		fpizlo: review+
DetailsFormatted DiffDiff
Patch (292.48 KB, patch)
2021-04-01 14:52 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (294.13 KB, patch)
2021-04-01 16:46 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Patch (295.20 KB, patch)
2021-04-01 23:40 PDT, Yusuke Suzuki 		no flags
DetailsFormatted DiffDiff
Show Obsolete (20) View All Add attachment proposed patch, testcase, etc.
Yusuke Suzuki
Comment 1 2021-03-29 13:03:24 PDT
Created attachment 424567 [details] Patch
Yusuke Suzuki
Comment 2 2021-03-29 13:07:38 PDT
Created attachment 424568 [details] Patch
Yusuke Suzuki
Comment 3 2021-03-29 14:44:13 PDT
Created attachment 424583 [details] Patch
Yusuke Suzuki
Comment 4 2021-03-29 14:47:05 PDT
Created attachment 424584 [details] Patch
Yusuke Suzuki
Comment 5 2021-03-29 14:58:36 PDT
Created attachment 424586 [details] Patch
Yusuke Suzuki
Comment 6 2021-03-29 16:04:21 PDT
Created attachment 424599 [details] Patch
Yusuke Suzuki
Comment 7 2021-03-29 22:41:43 PDT
Created attachment 424617 [details] Patch
Yusuke Suzuki
Comment 8 2021-03-30 01:17:36 PDT
Created attachment 424621 [details] Patch
Yusuke Suzuki
Comment 9 2021-03-30 01:36:51 PDT
Created attachment 424623 [details] Patch
Yusuke Suzuki
Comment 10 2021-03-30 13:31:02 PDT
Created attachment 424682 [details] Patch
Yusuke Suzuki
Comment 11 2021-03-30 16:26:47 PDT
Created attachment 424712 [details] Patch
Yusuke Suzuki
Comment 12 2021-03-31 03:07:17 PDT
Created attachment 424750 [details] Patch
Yusuke Suzuki
Comment 13 2021-03-31 03:43:23 PDT
Created attachment 424752 [details] Patch
Radar WebKit Bug Importer
Comment 14 2021-03-31 11:23:42 PDT
<rdar://problem/76061870>
Yusuke Suzuki
Comment 15 2021-03-31 13:12:59 PDT
Created attachment 424810 [details] Patch
Yusuke Suzuki
Comment 16 2021-03-31 23:55:06 PDT
Created attachment 424874 [details] Patch
Yusuke Suzuki
Comment 17 2021-03-31 23:59:03 PDT
Created attachment 424875 [details] Patch
Yusuke Suzuki
Comment 18 2021-04-01 00:23:01 PDT
Created attachment 424877 [details] Patch
Yusuke Suzuki
Comment 19 2021-04-01 01:56:49 PDT
Created attachment 424882 [details] Patch
Yusuke Suzuki
Comment 20 2021-04-01 05:41:44 PDT
Created attachment 424888 [details] Patch
Filip Pizlo
Comment 21 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?
Yusuke Suzuki
Comment 22 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 :)
Yusuke Suzuki
Comment 23 2021-04-01 14:52:36 PDT
Created attachment 424950 [details] Patch
Yusuke Suzuki
Comment 24 2021-04-01 16:46:49 PDT
Created attachment 424961 [details] Patch
Yusuke Suzuki
Comment 25 2021-04-01 23:40:24 PDT
Created attachment 424992 [details] Patch
Yusuke Suzuki
Comment 26 2021-04-02 01:33:45 PDT
Committed r275410 (236073@main): <https://commits.webkit.org/236073@main>
Yusuke Suzuki
Comment 27 2021-04-02 01:50:32 PDT
Committed r275411 (236074@main): <https://commits.webkit.org/236074@main>
Sam Weinig
Comment 28 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.
Sam Weinig
Comment 29 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++.
Sam Weinig
Comment 30 2021-04-02 12:51:55 PDT
or https://github.com/Kronuz/constexpr-phf
Note You need to log in before you can comment on or make changes to this bug.