WeakMap: Bad performance when values are keys

RESOLVED DUPLICATE of bug 1164294

Status

()

RESOLVED DUPLICATE of bug 1164294
8 years ago
3 years ago

People

(Reporter: bruant.d, Unassigned)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

8 years ago
-----
var wm = WeakMap();
var key = {}, value = {};
var N = Math.pow(2, 20);
while(N--){
  wm.set(key, value);
  key = value;
  value = {};
}
----
On the latest nightly on my machine, run this code once is fast (~1sec), running it twice is very long (several minutes). This is likely to be a garbage-collection issue.
If running it twice is quick or very slow at the first time, play with the power value.
(Reporter)

Updated

8 years ago
Blocks: 547941

Comment 1

8 years ago
Yes, this exposes the quadratic behavior of weak map marking.

Comment 2

8 years ago
I don't think there is much we can do here short term. I can add a cutoff that stops the long GC time in favor of starting to leak memory (after a certain degree of cycles encountered). We are working on a linear-time algorithm, but that will take a little time.

Comment 3

8 years ago
In case it's useful, Felix's linear time algorithm is at https://mail.mozilla.org/pipermail/es-discuss/2011-March/013241.html
(Reporter)

Comment 4

8 years ago
(In reply to comment #2)
> I don't think there is much we can do here short term. I can add a cutoff
> that stops the long GC time in favor of starting to leak memory (after a
> certain degree of cycles encountered). We are working on a linear-time
> algorithm, but that will take a little time.
Can you set dependency with this bug so that people solving the linear-time garbage collector keep this bug in mind?
Thanks.
Assignee: general → nobody
Blocks: 1008333
Created attachment 8543442 [details]
WeakMaps.txt

I didn't know we already had a bug filed for this. I explored the possibilities here too in my own writeup a while back, and came to the same algorithm. I'm attaching the writeup, though it's kind of muddy and hard to follow. (Felix's algorithm is labeled algorithm 2 in my writeup.)

Only I really don't want to do the is-a-key check for every marked object during regular marking, even if it's just a flag bit check. But if we're ok with duplicating the marking paths (via templatizing on a bool InWeakMarking), then that's not such a big deal -- you do a first pass that only accumulates the guarded_by table but never consults it, then if the table is nonempty at the end you construct a new gray set by scanning the table for black keys and then running Felix's algorithm as written.

This is almost algorithm 4 in the attached writeup, though I was kind of fixated on using mark bits when I wrote it.

I have other optimizations in mind to make it more likely to hit early exits in common cases, but they're minor. The memory management for the extra data is a little sticky for this stuff, and I'm still thinking about using TI for weakmap keys and whether some sort of inverted or separate representation might be better at least for some WeakMap use cases.

Comment 6

4 years ago
Notice that the transposed representation only needs the is-a-key check for the WeakMap identity objects. This is on addition to all the other reasons for using the transposed representation.

Comment 7

3 years ago
This got fixed by bug 1164294, no?
Flags: needinfo?(sphink)
Dang it, why can I never remember to reuse bugs? Yes, I implemented this in bug 1164294. Thanks for pointing that out. Forward-duping since that bug has the patches and landing state.

Looks like we may reuse some of this for weak refs as well. Still haven't made much headway towards implementing the transposed representation.
Status: NEW → RESOLVED
Last Resolved: 3 years ago
Flags: needinfo?(sphink)
Resolution: --- → DUPLICATE
Duplicate of bug: 1164294
You need to log in before you can comment on or make changes to this bug.