Bug 239576 - Adopt RobinHoodHashMap / RobinHoodHashSet more broadly in WebCore
Summary: Adopt RobinHoodHashMap / RobinHoodHashSet more broadly in WebCore
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebCore Misc. (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Chris Dumez
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2022-04-20 16:34 PDT by Chris Dumez
Modified: 2022-04-21 16:34 PDT (History)
34 users (show)

See Also:


Attachments
Patch (107.70 KB, patch)
2022-04-20 16:41 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (112.21 KB, patch)
2022-04-20 21:19 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (107.72 KB, patch)
2022-04-21 08:43 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (107.80 KB, patch)
2022-04-21 08:44 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (107.88 KB, patch)
2022-04-21 12:21 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Chris Dumez 2022-04-20 16:34:02 PDT
Adopt RobinHoodHashMap / RobinHoodHashSet more broadly in WebCore to avoid wasting memory in hash tables. RobinHoodHashMap / RobinHoodHashSet have more restrictions on what key types they work with and may result in slower performance but they have a much higher load factor that the regular HashMap / HashSet, thus reducing memory usage. This patch adopts RobinHoodHashMap / RobinHoodHashSet on non performance sensitive maps / sets in WebCore that have compatible keys (String / AtomString / URL because they cache their hash).
Comment 1 Chris Dumez 2022-04-20 16:41:12 PDT
Created attachment 458021 [details]
Patch
Comment 2 Yusuke Suzuki 2022-04-20 20:31:53 PDT
Interesting. Some of audio tests are failing because of (probably) hashtable ordering. Either or both of,

1. Our implementation is relying on HashTable ordering, which is undefined.
2. The test result is relying on HashTable ordering, which is undefined.
Comment 3 Chris Dumez 2022-04-20 20:33:36 PDT
(In reply to Yusuke Suzuki from comment #2)
> Interesting. Some of audio tests are failing because of (probably) hashtable
> ordering. Either or both of,
> 
> 1. Our implementation is relying on HashTable ordering, which is undefined.
> 2. The test result is relying on HashTable ordering, which is undefined.

I'll fix it tomorrow, shouldn't be difficult. I am waiting on perf A/B results anyway.
Comment 4 Yusuke Suzuki 2022-04-20 20:33:54 PDT
(In reply to Chris Dumez from comment #3)
> (In reply to Yusuke Suzuki from comment #2)
> > Interesting. Some of audio tests are failing because of (probably) hashtable
> > ordering. Either or both of,
> > 
> > 1. Our implementation is relying on HashTable ordering, which is undefined.
> > 2. The test result is relying on HashTable ordering, which is undefined.
> 
> I'll fix it tomorrow, shouldn't be difficult. I am waiting on perf A/B
> results anyway.

Nice
Comment 5 Chris Dumez 2022-04-20 21:19:23 PDT
Created attachment 458037 [details]
Patch
Comment 6 Chris Dumez 2022-04-21 08:43:03 PDT
Created attachment 458066 [details]
Patch
Comment 7 Chris Dumez 2022-04-21 08:44:22 PDT
Created attachment 458067 [details]
Patch
Comment 8 Chris Dumez 2022-04-21 12:21:06 PDT
Created attachment 458081 [details]
Patch
Comment 9 Yusuke Suzuki 2022-04-21 14:28:17 PDT
Comment on attachment 458081 [details]
Patch

r=me
Comment 10 Geoffrey Garen 2022-04-21 16:21:46 PDT
Comment on attachment 458081 [details]
Patch

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

> Source/WebCore/ChangeLog:15
> +        This is perf-neutral on all our benchmarks according to A/B testing.

Does memory use go down?
Comment 11 EWS 2022-04-21 16:28:50 PDT
Committed r293195 (249870@main): <https://commits.webkit.org/249870@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 458081 [details].
Comment 12 Radar WebKit Bug Importer 2022-04-21 16:29:15 PDT
<rdar://problem/92128851>
Comment 13 Chris Dumez 2022-04-21 16:34:42 PDT
(In reply to Geoffrey Garen from comment #10)
> Comment on attachment 458081 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=458081&action=review
> 
> > Source/WebCore/ChangeLog:15
> > +        This is perf-neutral on all our benchmarks according to A/B testing.
> 
> Does memory use go down?

I didn't check PLUM on iOS (I can look at the bot now that it landed). Sadly it didn't move the needle on Membuster on macOS according to A/B testing, I was hoping it would.