Bug 239576

Summary: Adopt RobinHoodHashMap / RobinHoodHashSet more broadly in WebCore
Product: WebKit Reporter: Chris Dumez <cdumez>
Component: WebCore Misc.Assignee: Chris Dumez <cdumez>
Status: RESOLVED FIXED    
Severity: Normal CC: alecflett, beidson, benjamin, calvaris, changseok, cmarcelo, dino, eric.carlson, esprehn+autocc, ews-watchlist, fmalita, ggaren, glenn, gyuyoung.kim, hi, hta, japhet, jer.noble, joepeck, jsbell, kangil.han, kondapallykalyan, mifenton, mkwst, mmaxfield, pangle, pdr, philipj, sabouhallawa, schenney, sergio, tommyw, webkit-bug-importer, ysuzuki
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
none
Patch
none
Patch
none
Patch none

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.