Bug 226872 – Add WeakHashMap

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Ryosuke Niwa]

Add the basic version of WeakHashMap which replies on lazy deletion of key & value.

[Ryosuke Niwa]

Created attachment 431061 [details]
Patch

[Geoffrey Garen]

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.

[Ryosuke Niwa]

(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.

[Ryosuke Niwa]

Created attachment 431100 [details]
Fixed the builds

[Geoffrey Garen]

> > 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.)

[Geoffrey Garen]

Note that I'm proposing an increment, a branch, and a function call. So, yes, a few bytes of code, but not a ton.

[Ryosuke Niwa]

Created attachment 431187 [details]
Added amortized deletion

[Geoffrey Garen]

Comment on attachment 431187 [details]
Added amortized deletion

r=me

[Ryosuke Niwa]

Comment on attachment 431187 [details]
Added amortized deletion

Clearing flags on attachment: 431187

Committed r278803 (238760@main): <https://commits.webkit.org/238760@main>

[Ryosuke Niwa]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/79227218>

[Fujii Hironori]

Filed: Bug 227102 – [Win] TestWTF.WTF_WeakPtr.WeakHashMapIterators is crashing