223895 – [WTF] Introduce RobinHoodHashTable

RESOLVED FIXED223895

[WTF] Introduce RobinHoodHashTable

https://bugs.webkit.org/show_bug.cgi?id=223895

Summary [WTF] Introduce RobinHoodHashTable

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-	Details Formatted Diff Diff
Patch (65.31 KB, patch) 2021-03-29 13:07 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (100.45 KB, patch) 2021-03-29 14:44 PDT, Yusuke Suzuki	ews-feeder: commit-queue-	Details Formatted Diff Diff
Patch (100.50 KB, patch) 2021-03-29 14:47 PDT, Yusuke Suzuki	ews-feeder: commit-queue-	Details Formatted Diff Diff
Patch (99.51 KB, patch) 2021-03-29 14:58 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (105.16 KB, patch) 2021-03-29 16:04 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (107.95 KB, patch) 2021-03-29 22:41 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (109.11 KB, patch) 2021-03-30 01:17 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (109.14 KB, patch) 2021-03-30 01:36 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (108.64 KB, patch) 2021-03-30 13:31 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (143.79 KB, patch) 2021-03-30 16:26 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (216.18 KB, patch) 2021-03-31 03:07 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (216.88 KB, patch) 2021-03-31 03:43 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (219.19 KB, patch) 2021-03-31 13:12 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (289.69 KB, patch) 2021-03-31 23:55 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (289.68 KB, patch) 2021-03-31 23:59 PDT, Yusuke Suzuki	ews-feeder: commit-queue-	Details Formatted Diff Diff
Patch (289.73 KB, patch) 2021-04-01 00:23 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (289.99 KB, patch) 2021-04-01 01:56 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (290.42 KB, patch) 2021-04-01 05:41 PDT, Yusuke Suzuki	fpizlo: review+	Details Formatted Diff Diff
Patch (292.48 KB, patch) 2021-04-01 14:52 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (294.13 KB, patch) 2021-04-01 16:46 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
Patch (295.20 KB, patch) 2021-04-01 23:40 PDT, Yusuke Suzuki	no flags	Details Formatted Diff Diff
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.

Status RESOLVED

Resolution FIXED

Priority P2

Severity Normal

Classification Unclassified

Version WebKit Nightly Build

Hardware Unspecified

OS Unspecified

Product WebKit

Component New Bugs

Assignee

Yusuke Suzuki

Reported

2021-03-29 13:02 PDT

Modified

2021-04-02 12:51 PDT History

CC List

38 users Show

URL

Keywords InRadar

Depends on

Blocks

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