Bug 207182 - [WTF] Implement RobinHoodHashTable
Summary: [WTF] Implement RobinHoodHashTable
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2020-02-03 20:38 PST by Yusuke Suzuki
Modified: 2020-02-29 00:14 PST (History)
0 users

See Also:

Attachments
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 Yusuke Suzuki 2020-02-03 20:38:44 PST 
...
Comment 1 Yusuke Suzuki 2020-02-03 21:43:34 PST 
Maybe, we cannot use 90% load factor in Robin-hood hashing :(
https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
Comment 2 Yusuke Suzuki 2020-02-28 23:21:09 PST 
We know that there are many super-large HashMaps exist, which are typically used as a singleton => do not need to copy.
Let's just implement RobinHoodHashTable and use it for particularly large singleton-like HashMap.
Comment 3 Yusuke Suzuki 2020-02-28 23:32:46 PST 
(In reply to Yusuke Suzuki from comment #2)
> We know that there are many super-large HashMaps exist, which are typically
> used as a singleton => do not need to copy.
> Let's just implement RobinHoodHashTable and use it for particularly large
> singleton-like HashMap.

e.g. AtomStringTable, ShareableElementData's Table, etc.
Comment 4 Yusuke Suzuki 2020-02-29 00:14:08 PST 
(In reply to Yusuke Suzuki from comment #3)
> (In reply to Yusuke Suzuki from comment #2)
> > We know that there are many super-large HashMaps exist, which are typically
> > used as a singleton => do not need to copy.
> > Let's just implement RobinHoodHashTable and use it for particularly large
> > singleton-like HashMap.
> 
> e.g. AtomStringTable, ShareableElementData's Table, etc.

EventTargetDataMap,