Bug 226872 - Add WeakHashMap
Summary: Add WeakHashMap
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2021-06-10 04:05 PDT by Ryosuke Niwa
Modified: 2021-06-16 17:07 PDT (History)
15 users (show)

See Also:


Attachments
Patch (53.71 KB, patch)
2021-06-10 04:18 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Fixed the builds (53.71 KB, patch)
2021-06-10 11:43 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Added amortized deletion (60.72 KB, patch)
2021-06-11 04:20 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2021-06-10 04:05:02 PDT
Add the basic version of WeakHashMap which replies on lazy deletion of key & value.
Comment 1 Ryosuke Niwa 2021-06-10 04:18:01 PDT
Created attachment 431061 [details]
Patch
Comment 2 Geoffrey Garen 2021-06-10 09:44:15 PDT
Pending ews, this approach looks good to me. 

But I also think we should add a counter, so that after N operations on a weak map, we iterate and clear all nulls. Such a counter maintains the average case amortized O(1) guarantee. And that way, when we talk about the need for a more intrusive way to clear nulls, we’ll compare against the best possible baseline and avoid premature optimization.
Comment 3 Ryosuke Niwa 2021-06-10 11:43:44 PDT
(In reply to Geoffrey Garen from comment #2)
> Pending ews, this approach looks good to me. 
> 
> But I also think we should add a counter, so that after N operations on a
> weak map, we iterate and clear all nulls. Such a counter maintains the
> average case amortized O(1) guarantee. And that way, when we talk about the
> need for a more intrusive way to clear nulls, we’ll compare against the best
> possible baseline and avoid premature optimization.

Which operations though? If done natively, that seems like it's gonna bloat the code size everywhere.
Comment 4 Ryosuke Niwa 2021-06-10 11:43:57 PDT
Created attachment 431100 [details]
Fixed the builds
Comment 5 Geoffrey Garen 2021-06-10 13:04:26 PDT
> > But I also think we should add a counter, so that after N operations on a
> > weak map, we iterate and clear all nulls. Such a counter maintains the
> > average case amortized O(1) guarantee. And that way, when we talk about the
> > need for a more intrusive way to clear nulls, we’ll compare against the best
> > possible baseline and avoid premature optimization.
> 
> Which operations though? If done natively, that seems like it's gonna bloat
> the code size everywhere.

My straw man proposal would be all insertion, removal, and lookup operations.

If that has a significant impact on code size, my second straw man proposal would be not to mark those functions inline. (I seriously doubt their value as inline functions on modern processors, since the cost is always going to be in the out of line lookup function.)
Comment 6 Geoffrey Garen 2021-06-10 13:05:08 PDT
Note that I'm proposing an increment, a branch, and a function call. So, yes, a few bytes of code, but not a ton.
Comment 7 Ryosuke Niwa 2021-06-11 04:20:20 PDT
Created attachment 431187 [details]
Added amortized deletion
Comment 8 Geoffrey Garen 2021-06-11 09:27:05 PDT
Comment on attachment 431187 [details]
Added amortized deletion

r=me
Comment 9 Ryosuke Niwa 2021-06-11 18:42:13 PDT
Comment on attachment 431187 [details]
Added amortized deletion

Clearing flags on attachment: 431187

Committed r278803 (238760@main): <https://commits.webkit.org/238760@main>
Comment 10 Ryosuke Niwa 2021-06-11 18:42:16 PDT
All reviewed patches have been landed.  Closing bug.
Comment 11 Radar WebKit Bug Importer 2021-06-11 18:43:37 PDT
<rdar://problem/79227218>
Comment 12 Fujii Hironori 2021-06-16 17:07:55 PDT
Filed: Bug 227102 – [Win] TestWTF.WTF_WeakPtr.WeakHashMapIterators is crashing