657264 - WeakMap: Bad performance when values are keys

Status: RESOLVED DUPLICATE of bug 1164294

(Core :: JavaScript Engine, defect)

Description

[David Bruant]

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

Comment 1

[Andreas Gal :gal]

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

Comment 2

[Andreas Gal :gal]

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

[Mark S. Miller]

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

Comment 4

[David Bruant]

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

Comment 5

[Steve Fink [:sfink] [:s:]]

Attachment: 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

[Mark S. Miller]

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

[Guilherme Lima]

This got fixed by bug 1164294, no?

Comment 8

[Steve Fink [:sfink] [:s:]]

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.