I'm working on switching our iterate-to-fixed-point algorithm over to a linear-time ephemeron marking algorithm. The basic idea: when marking a WeakMap, throw all unmarked keys' values into a big table mapping from key => list of values (from any WeakMap). Then whenever you mark an object, look it up in the table to see if you need to mark some values too. Then apply optimizations to make that not as horrible perf-wise as it sounds. It's still an experiment; we'll see if it's worth it.

It turns out that an OrderedHashMap would be extremely useful here. Our table is append-only, we want to be able to iterate over a snapshot of the keys from a point in time while allowing new keys to be inserted, and iteration speed matters. OHM is perfect for this. But to use it, I'll need to free it from the bonds of MapObject.cpp.

Some notes after working on this a bit and then sitting in a dentist's chair for a while: There's no problem with just doing WeakMaps first and extending it to other types later. I can just pull the weakmap marking out of the iterative marking loop. Any further weakmaps discovered during the iterative marking of the rest (eg watchpoint maps, debugger, etc) will be automatically handled properly because we're in the "full-lookup" mode of marking. That said, I thought about the watchpoint maps. They are really weak maps from <object,property id> pairs to function objects (and from there to the world). Well, with an extra 'hold' boolean for when they're live. So if an object dies, then all of its entries should be cleared out. If a property name dies (which necessarily means it is not used as a key for any live object), then the function object should also not be kept alive. I believe this is doable with some minor modifications: when marking a watchpoint map, mark everything for which both the object and property name are already marked. If the object is unmarked, insert the object into the weak key table, mapping to the full <object,property id,function> entry. If the property is unmarked, insert the property id into the weak key table, mapping to the same full tuple. If both are unmarked, insert them both. Then, when you mark an object and therefore look it up in the weak key table, check whether the property id is also marked. If so, mark through to the function. If not, skip it. Same for the property name. Oh, and if the entry is held, then it's a strong reference from the watchpoint map directly to the function value, so just mark through and don't populate any tables at all. In terms of code complexity, this is great -- you handle even a complex system of references with very little modification to the WeakMap scheme. For time, it's a mixed bag. You visit the entries multiple times before you can mark through them, but I think that's really minor and probably about as good as you can do. More seriously, you now have to check the weak key table every time you mark a string that could be used as a property key. That may not be worth it for this goofy purpose, and you'd be better off leaving this part iterative. I suspect that's the right answer for now, but after I look at the other cases (Debugger stuff and jit code stuff) it may be that we have to check property names anyway. Also, with jonco's suggestion of flagging arenas if they contain any weak keys, the check may not be as slow as I've been thinking.

I think this is reviewable, though I really need to do a try push. I'm not very confident that this works with compacting GC yet.

Preparing for wreckage: https://treeherder.mozilla.org/#/jobs?repo=try&revision=86e635979793

Comment on attachment 8609090 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Review of attachment 8609090 [details] [diff] [review]: ----------------------------------------------------------------- This is a gorgeous piece of work! ::: js/src/gc/Marking.cpp @@ +732,5 @@ > } > namespace js { > +template <> void GCMarker::traverse(JSObject* thing) { > + if (mark(thing)) { > + pushTaggedPtr(ObjectTag, thing); The ephemeron value marking here /really/ needs to get named, split out, and shared with the identical "root" marking block in markWeakReferences. The knock on effect is that we can make markAndPush return bool and then phrase this as. if (markAndPush(ObjectTag, thing)) maybeMarkEphemeronValues(thing); ::: js/src/jsgc.cpp @@ +1174,5 @@ > allocTask(rt, emptyChunks_), > helperState(rt) > { > setGCMode(JSGC_MODE_GLOBAL); > + if (marker.weakMapAction() == ExpandWeakMaps) { I guess this allows us to disable the new weak algorithm on a runtime? I'd guess we should probably just init this unconditionally. @@ +4044,5 @@ > + entry.value[i]->maybeMarkEntry(&marker, entry.key.toObject()); > + MOZ_ASSERT(entry.value.length() == initialLen); > + bool found; > + (void) marker.weakKeys.remove(entry.key, &found); > + MOZ_ASSERT(found); marker.maybeMarkEphemeronValues(entry.key())

Comment on attachment 8609090 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Review of attachment 8609090 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/gc/Marking.cpp @@ +1537,5 @@ > /*** GCMarker *************************************************************************************/ > > /* > * DoNotTraceWeakMaps: the GC is recomputing the liveness of WeakMap entries, > * so we delay visting entries. Does this comment need to be updated, given the change below?

Comment on attachment 8609092 [details] [diff] [review] Allow removing an OHT entry without looking it up again The core patch here has mutated heavily, and this follow-on patch is no longer relevant. For one, the removal triggers a correctness problem, no matter how you do it. But there's a good chance I'll need something like Ptr before all this is done, just to assert safety if nothing else.

Comment on attachment 8604965 [details] [diff] [review] Move OrderedHashTable to ds/ Review of attachment 8604965 [details] [diff] [review]: ----------------------------------------------------------------- No need to wait on a jorendorff review for this; it's just code motion. (I un-did all of my other changes to OHM.)

I've cleaned this up some since my last successful try push, so no guarantees that it's not horribly broken in some stupid way, but this should be close enough to review. Er, re-review; the previous patch was overly optimistic.

Comment on attachment 8604965 [details] [diff] [review] Move OrderedHashTable to ds/ Review of attachment 8604965 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ds/OrderedHashTable.h @@ +2,5 @@ > + * vim: set ts=8 sts=4 et sw=4 tw=99: > + * This Source Code Form is subject to the terms of the Mozilla Public > + * License, v. 2.0. If a copy of the MPL was not distributed with this > + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ > + This needs #ifndef/#define include guards still. Otherwise looks fine.

Comment on attachment 8638236 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm This patch could use some fuzzing. I don't know if there's a way to tune it to emphasize certain tests, but if so the gc/weak-marking-01.js and especially the last test in gc/weak-marking-02.js would be good to focus on. (That last test was an attempt to replicate a failure that I could only see running the in-browser devtools suite, but I failed to get the exact right pattern of behavior.) Thanks!

Rebased. Applies to e6bee0b58b9e.

Comment on attachment 8638810 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Didn't find anything interesting over the weekend.

This is an automated crash issue comment: Summary: Assertion failure: tag_ == TracerKindTag::WeakMarking, at js/src/gc/Marking.h:214 Build version: mozilla-central-patch Build flags: --enable-optimize --enable-posix-nspr-emulation --enable-valgrind --enable-gczeal --disable-tests --enable-debug Runtime options: --fuzzing-safe --no-threads --baseline-eager --ion-check-range-analysis Testcase: try { enableTrackAllocations(); evaluate("throw Error();", {fileName: (null )}); } catch(exc0) {} oomAfterAllocations(("")) Backtrace: Program terminated with signal SIGSEGV, Segmentation fault. #0 0x00000000006f7319 in js::GCMarker::leaveWeakMarkingMode (this=0x7fbd1b23d110) at js/src/gc/Marking.h:214 #1 0x0000000000baf234 in js::gc::GCRuntime::markWeakReferences<js::CompartmentsIterT<js::gc::GCZoneGroupIter> > (this=this@entry=0x7fbd1b237348, phase=phase@entry=js::gcstats::PHASE_SWEEP_MARK_WEAK) at js/src/jsgc.cpp:4027 #2 0x0000000000b506dc in markWeakReferencesInCurrentGroup (phase=js::gcstats::PHASE_SWEEP_MARK_WEAK, this=0x7fbd1b237348) at js/src/jsgc.cpp:4033 #3 js::gc::GCRuntime::endMarkingZoneGroup (this=this@entry=0x7fbd1b237348) at js/src/jsgc.cpp:4758 #4 0x0000000000b7ece1 in js::gc::GCRuntime::beginSweepPhase (this=this@entry=0x7fbd1b237348, destroyingRuntime=destroyingRuntime@entry=false) at js/src/jsgc.cpp:5147 #5 0x0000000000b8384b in js::gc::GCRuntime::incrementalCollectSlice (this=this@entry=0x7fbd1b237348, budget=..., reason=reason@entry=JS::gcreason::DESTROY_CONTEXT) at js/src/jsgc.cpp:5890 #6 0x0000000000b84812 in js::gc::GCRuntime::gcCycle (this=this@entry=0x7fbd1b237348, incremental=incremental@entry=false, budget=..., reason=reason@entry=JS::gcreason::DESTROY_CONTEXT) at js/src/jsgc.cpp:6087 #7 0x0000000000b84c22 in js::gc::GCRuntime::collect (this=this@entry=0x7fbd1b237348, incremental=incremental@entry=false, budget=..., reason=reason@entry=JS::gcreason::DESTROY_CONTEXT) at js/src/jsgc.cpp:6201 #8 0x0000000000b84fa0 in js::gc::GCRuntime::gc (this=this@entry=0x7fbd1b237348, gckind=gckind@entry=GC_NORMAL, reason=reason@entry=JS::gcreason::DESTROY_CONTEXT) at js/src/jsgc.cpp:6262 #9 0x0000000000ad32b0 in js::DestroyContext (cx=0x7fbd1b206800, mode=js::DCM_FORCE_GC) at js/src/jscntxt.cpp:186 #10 0x0000000000ad362e in JS_DestroyContext (cx=<optimized out>) at js/src/jsapi.cpp:756 #11 0x0000000000477714 in DestroyContext (withGC=true, cx=0x7fbd1b206800) at js/src/shell/js.cpp:5596 #12 main (argc=<optimized out>, argv=<optimized out>, envp=<optimized out>) at js/src/shell/js.cpp:6393 rax 0x0 0 rbx 0x7fbd1b23d110 140450180878608 rcx 0x7fbd1b5ea870 140450184734832 rdx 0x0 0 rsi 0x7fbd1b8bf9d0 140450187704784 rdi 0x7fbd1b8be1c0 140450187698624 rbp 0x7fffeb67f080 140737142845568 rsp 0x7fffeb67f050 140737142845520 r8 0x7fbd1c92f780 140450204940160 r9 0x6568637461702d6c 7307199746910727532 r10 0x7fbd1b8bbbe0 140450187688928 r11 0x246 582 r12 0x7fbd1b23d110 140450180878608 r13 0x7fffeb67f0e0 140737142845664 r14 0x7fbd1b237348 140450180854600 r15 0x0 0 rip 0x6f7319 <js::GCMarker::leaveWeakMarkingMode()+601> => 0x6f7319 <js::GCMarker::leaveWeakMarkingMode()+601>: movl $0xd6,0x0 0x6f7324 <js::GCMarker::leaveWeakMarkingMode()+612>: callq 0x4993c0 <abort()> I keep seeing this OOM assertion only with your patch. This might be coincidence but it triggers fairly often.

Comment on attachment 8638810 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Adding Jon for a second set of eyes.

Comment on attachment 8638810 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Review of attachment 8638810 [details] [diff] [review]: ----------------------------------------------------------------- This is brilliant! Now that I've had a chance to sit down with it for a couple hours, I think it's considerably clearer than the iterative algorithm. Also, great tests! We really should have had those for as long as we've had weakmaps. ::: js/src/ds/OrderedHashTable.h @@ +672,5 @@ > > public: > Entry() : key(), value() {} > Entry(const Key& k, const Value& v) : key(k), value(v) {} > + Entry(const Key& k, Value&& v) : key(k), value(Move(v)) {} |v| is already a move-ref, so I think this should be Forward<Value>(v) instead of Move(v). @@ +708,5 @@ > Range all() { return impl.all(); } > const Entry* get(const Key& key) const { return impl.get(key); } > Entry* get(const Key& key) { return impl.get(key); } > bool put(const Key& key, const Value& value) { return impl.put(Entry(key, value)); } > + bool put(const Key& key, Value&& value) { return impl.put(Entry(key, Move(value))); } |value| is already a move-ref, so I think this should be Forward<Value>(value) instead of Move(value). ::: js/src/jit-test/tests/gc/weak-marking-02.js @@ +1,4 @@ > +// These tests will be using object literals as keys, and we want some of them > +// to be dead after being inserted into a WeakMap. That means we must wrap > +// everything in functions because it seems like the toplevel script hangs onto > +// its object literals. IIRC, they get built during parsing and attached right to the script. ::: js/src/jsgc.cpp @@ +1312,5 @@ > if (!marker.init(mode)) > return false; > > + if (marker.weakMapAction() == ExpandWeakMaps) { > + if (!marker.weakKeys.init()) This seems like an exceptionally weird way to control construction of of the weakKeys table. It's on the runtime, so I'd prefer to see us just create this unconditionally, or at the least toggled by something less implicit. At the moment it looks like weakMapAction's value is implicit from creation of the GCMarker and I don't see anything that can control that. Just seems weird. @@ +4171,5 @@ > + if (!savedWeakKeys.init()) > + return; > + > + for (gc::WeakKeyTable::Range r = gc->marker.weakKeys.all(); !r.empty(); r.popFront()) > + savedWeakKeys.put(Move(r.front().key), Move(r.front().value)); If we're moving the keys then I guess this kills the weakKeys table? It seems like we should have some infra to move tables around with less looping and more copying the fields directly. Coule the move constructor work for this? @@ +4248,5 @@ > + > + gc->marker.weakKeys.clear(); > + for (gc::WeakKeyTable::Range r = savedWeakKeys.all(); !r.empty(); r.popFront()) { > + if (!gc->marker.weakKeys.put(Move(r.front().key), Move(r.front().value))) > + CrashAtUnhandlableOOM("restoring weak keys table for validator"); We're checking for OOM on this table copy, but not above? It seems like the result is going to be the same if we fail at either copy. ::: js/src/jsweakmap.h @@ +183,5 @@ > + TraceEdge(trc, &p->value(), "WeakMap ephemeron value"); > + TraceEdge(trc, &key, "proxy-preserved WeakMap ephemeron key"); > + MOZ_ASSERT(key == p->key()); // No moving > + } > + key.unsafeSet(nullptr); Some explanation of this line would be nice. I know I found at some point, but I have no idea right now. @@ +230,5 @@ > + addWeakEntry(trc, weakKey, markable); > + if (JSObject* delegate = getDelegate(key)) > + addWeakEntry(trc, JS::GCCellPtr(delegate), markable); > + } > + key.unsafeSet(nullptr); ditto @@ +267,5 @@ > + } > + > + JSObject* getDelegate(gc::Cell* cell) const { > + return nullptr; > + } I don't think this override is ever called because of the Cell* specialization of keyNeedsMark?

Comment on attachment 8638810 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Review of attachment 8638810 [details] [diff] [review]: ----------------------------------------------------------------- This is really nice. I like the comments and the new tests. ::: js/public/TracingAPI.h @@ +41,5 @@ > + > + // Do true ephemeron marking with a weak key lookup marking phase. This is > + // expected to be constant for the lifetime of a JSTracer; it does not > + // change when switching from "plain" marking to weak marking. > + ExpandWeakMaps, I think doesn't really belong in the public API as it's only useful for the marking tracer. I can't think of a better way of doing this right now though. ::: js/src/ds/OrderedHashTable.h @@ +672,5 @@ > > public: > Entry() : key(), value() {} > Entry(const Key& k, const Value& v) : key(k), value(v) {} > + Entry(const Key& k, Value&& v) : key(k), value(Move(v)) {} I think we can use a universal reference and replace both key/value constructors, like this: template <typename V> Entry(const Key& k, V&& v) : key(k), value(Forward(v)) {} Ditto below. ::: js/src/gc/Marking.cpp @@ +619,5 @@ > + > +template <> > +struct LinearlyMarkedEphemeronKeyType<JSScript*> { > + typedef JSScript* Type; > +}; There might be another way of doing this (e.g. function overloading maybe?) that doesn't require slightly-confusing DoNothingMarkingType. @@ +641,5 @@ > +{ > + if (!isWeakMarkingTracer()) > + return; > + > + MOZ_ASSERT(!gc::TenuredCell::fromPointer(markedThing)->zone()->isGCSweeping()); Can we assert isGCMarking() here? @@ +1391,5 @@ > > scan_obj: > { > AssertZoneIsMarking(obj); > + markPotentialEphemeronKey(obj); We should probably do this after checking the budget. ::: js/src/gc/Marking.h @@ +151,5 @@ > +struct WeakMarkable { > + WeakMapBase* weakmap; > + JS::GCCellPtr key; > + > + WeakMarkable(WeakMapBase* weakmapArg, JS::GCCellPtr&& keyArg) I'm pretty sure this constructor isn't required. @@ +221,5 @@ > + } > + > + void abortLinearWeakMarking() { > + leaveWeakMarkingMode(); > + linearWeakMarkingDisabled_ = true; Is there a test that exercises this path? ::: js/src/jit-test/tests/gc/weak-marking-01.js @@ +11,5 @@ > + wm1.set(hold, {'name': 'val2'}); > + wm1.set({'name': 'obj3'}, {'name': 'val3'}); > + > + startgc(100000, 'shrinking'); > + gcslice(); Do we need to be doing an incremental GC for some reason? It seems like we could just call gc() here. @@ +52,5 @@ > + var obj1 = makeFinalizeObserver(); > + var obj2 = {'name': 'obj2'}; > + var obj3 = {'name': 'obj3'}; > + var obj4 = {'name': 'obj4'}; > + var clear = {'name': ''}; // Make the interpreter forget about the last obj created Heh, that's terrible. @@ +131,5 @@ > + > +// The weakKeys table is populated during regular marking. When a key is later > +// deleted, both it and its delegate should be removed from weakKeys. > +// Otherwise, it will hold its value live if it gets marked, and our table > +// traversals will include non-keys, etc. Can you add tests for adding keys after the start of marking too? I'm wondering if we should have a zeal mode that yields between regular marking and weakmap marking as well. @@ +139,5 @@ > + > + for (var i = 0; i < 1000; i++) > + wm.set(g.Object.create(null), i); > + > + startgc(100, 'shrinking'); We should probably assert that gcstate() is still "mark" here. ::: js/src/jsgc.cpp @@ +4172,5 @@ > + return; > + > + for (gc::WeakKeyTable::Range r = gc->marker.weakKeys.all(); !r.empty(); r.popFront()) > + savedWeakKeys.put(Move(r.front().key), Move(r.front().value)); > + Also, I think you can Move the whole table in one go. @@ +4920,5 @@ > + auto key(r.front().key); > + r.popFront(); > + if (gc::TenuredCell::fromPointer(key.asCell())->zone()->isGCSweeping()) { > + bool found; > + marker.weakKeys.remove(key, &found); Can we use WeakKeyTable::Enum and removeFront() rather than re-looking up the key? ::: js/src/jsweakmap.h @@ +84,5 @@ > // Remove a weakmap from its compartment's weakmaps list. > static void removeWeakMapFromList(WeakMapBase* weakmap); > > + // Any weakmap key types that want to participate in the non-iterative > + // ephemeron marking must overriding this method. "override" @@ +198,5 @@ > + if (!weakEntries.append(Move(markable))) > + marker.abortLinearWeakMarking(); > + } else { > + gc::WeakEntryVector weakEntries; > + JS_ALWAYS_TRUE(weakEntries.append(Move(markable))); MOZ_ALWAYS_TRUE.

(In reply to Terrence Cole [:terrence] from comment #19) > ::: js/src/jsgc.cpp > @@ +1312,5 @@ > > if (!marker.init(mode)) > > return false; > > > > + if (marker.weakMapAction() == ExpandWeakMaps) { > > + if (!marker.weakKeys.init()) > > This seems like an exceptionally weird way to control construction of of the > weakKeys table. It's on the runtime, so I'd prefer to see us just create > this unconditionally, or at the least toggled by something less implicit. At > the moment it looks like weakMapAction's value is implicit from creation of > the GCMarker and I don't see anything that can control that. Just seems > weird. I made it unconditionally called by marker.init(). > @@ +4171,5 @@ > > + if (!savedWeakKeys.init()) > > + return; > > + > > + for (gc::WeakKeyTable::Range r = gc->marker.weakKeys.all(); !r.empty(); r.popFront()) > > + savedWeakKeys.put(Move(r.front().key), Move(r.front().value)); > > If we're moving the keys then I guess this kills the weakKeys table? It > seems like we should have some infra to move tables around with less looping > and more copying the fields directly. Coule the move constructor work for > this? This is probably a matter of OHM immaturity. I suppose I should add it. Or figure out why I'm even still using OHM at this point. (See below.) > @@ +4248,5 @@ > > + > > + gc->marker.weakKeys.clear(); > > + for (gc::WeakKeyTable::Range r = savedWeakKeys.all(); !r.empty(); r.popFront()) { > > + if (!gc->marker.weakKeys.put(Move(r.front().key), Move(r.front().value))) > > + CrashAtUnhandlableOOM("restoring weak keys table for validator"); > > We're checking for OOM on this table copy, but not above? It seems like the > result is going to be the same if we fail at either copy. Err... I thought I had a good reason for this, but I can't fathom what it might be. Fixed. > ::: js/src/jsweakmap.h > @@ +183,5 @@ > > + TraceEdge(trc, &p->value(), "WeakMap ephemeron value"); > > + TraceEdge(trc, &key, "proxy-preserved WeakMap ephemeron key"); > > + MOZ_ASSERT(key == p->key()); // No moving > > + } > > + key.unsafeSet(nullptr); > > Some explanation of this line would be nice. I know I found at some point, > but I have no idea right now. How does "cargo culting" sound? I said // Prevent destructor from running barriers. Is that even correct? > @@ +267,5 @@ > > + } > > + > > + JSObject* getDelegate(gc::Cell* cell) const { > > + return nullptr; > > + } > > I don't think this override is ever called because of the Cell* > specialization of keyNeedsMark? This is also called from markEphemeronEntries. (In reply to Jon Coppeard (:jonco) from comment #20) > ::: js/public/TracingAPI.h > @@ +41,5 @@ > > + > > + // Do true ephemeron marking with a weak key lookup marking phase. This is > > + // expected to be constant for the lifetime of a JSTracer; it does not > > + // change when switching from "plain" marking to weak marking. > > + ExpandWeakMaps, > > I think doesn't really belong in the public API as it's only useful for the > marking tracer. I can't think of a better way of doing this right now > though. Yeah. I'm not very happy about this part. It's sort of part of the type of marker. > ::: js/src/gc/Marking.cpp > @@ +619,5 @@ > > + > > +template <> > > +struct LinearlyMarkedEphemeronKeyType<JSScript*> { > > + typedef JSScript* Type; > > +}; > > There might be another way of doing this (e.g. function overloading maybe?) > that doesn't require slightly-confusing DoNothingMarkingType. I tried to come up with something simpler for a while before ending up with this. It would be nice if I could unify this with other traits stuff we have. > @@ +641,5 @@ > > +{ > > + if (!isWeakMarkingTracer()) > > + return; > > + > > + MOZ_ASSERT(!gc::TenuredCell::fromPointer(markedThing)->zone()->isGCSweeping()); > > Can we assert isGCMarking() here? Good idea! > @@ +1391,5 @@ > > > > scan_obj: > > { > > AssertZoneIsMarking(obj); > > + markPotentialEphemeronKey(obj); > > We should probably do this after checking the budget. Very good idea. > ::: js/src/gc/Marking.h > @@ +151,5 @@ > > +struct WeakMarkable { > > + WeakMapBase* weakmap; > > + JS::GCCellPtr key; > > + > > + WeakMarkable(WeakMapBase* weakmapArg, JS::GCCellPtr&& keyArg) > > I'm pretty sure this constructor isn't required. You're right, whatever wanted it is dead now. > @@ +221,5 @@ > > + } > > + > > + void abortLinearWeakMarking() { > > + leaveWeakMarkingMode(); > > + linearWeakMarkingDisabled_ = true; > > Is there a test that exercises this path? No. >>TODO Well, decoder might have one. But it crashed. :-P > ::: js/src/jit-test/tests/gc/weak-marking-01.js > @@ +11,5 @@ > > + wm1.set(hold, {'name': 'val2'}); > > + wm1.set({'name': 'obj3'}, {'name': 'val3'}); > > + > > + startgc(100000, 'shrinking'); > > + gcslice(); > > Do we need to be doing an incremental GC for some reason? It seems like we > could just call gc() here. We don't *need* it, since it currently works either way. But I previously had a bug that was only triggered by splitting things across incremental slices. And since I hope to be switching back to that eventually, when I make this incremental, I'd rather keep the test like this. > @@ +52,5 @@ > > + var obj1 = makeFinalizeObserver(); > > + var obj2 = {'name': 'obj2'}; > > + var obj3 = {'name': 'obj3'}; > > + var obj4 = {'name': 'obj4'}; > > + var clear = {'name': ''}; // Make the interpreter forget about the last obj created > > Heh, that's terrible. I'm not sure if it's still needed now that I switched the interpreter to ReservedRooted. > @@ +131,5 @@ > > + > > +// The weakKeys table is populated during regular marking. When a key is later > > +// deleted, both it and its delegate should be removed from weakKeys. > > +// Otherwise, it will hold its value live if it gets marked, and our table > > +// traversals will include non-keys, etc. > > Can you add tests for adding keys after the start of marking too? Great idea! > I'm wondering if we should have a zeal mode that yields between regular > marking and weakmap marking as well. > > @@ +139,5 @@ > > + > > + for (var i = 0; i < 1000; i++) > > + wm.set(g.Object.create(null), i); > > + > > + startgc(100, 'shrinking'); > > We should probably assert that gcstate() is still "mark" here. I don't think that's guaranteed. If you were in some zeal mode that GCs every N allocations, and there happens to be an allocation between the startgc() call and the check, then it would be correct for it to finish a complete GC and have gcstate() return 'none' here. > ::: js/src/jsgc.cpp > @@ +4172,5 @@ > > + return; > > + > > + for (gc::WeakKeyTable::Range r = gc->marker.weakKeys.all(); !r.empty(); r.popFront()) > > + savedWeakKeys.put(Move(r.front().key), Move(r.front().value)); > > + > > Also, I think you can Move the whole table in one go. Not with an OHM (OrderedHashMap). Not implemented. > @@ +4920,5 @@ > > + auto key(r.front().key); > > + r.popFront(); > > + if (gc::TenuredCell::fromPointer(key.asCell())->zone()->isGCSweeping()) { > > + bool found; > > + marker.weakKeys.remove(key, &found); > > Can we use WeakKeyTable::Enum and removeFront() rather than re-looking up > the key? Nope, there's no such thing as OHM::Enum. Ok, so that begs the question: why use OHM? Originally, it seemed perfect: I thought I'd do a bunch of insertions while traversing the mark graph, then switch to weak marking mode and iterate over the whole table, then start mixing lookups in with the insertions, and finally nuke the whole table in one go. That's like the best-case usage scenario for OHM -- completely dense table so no worries about fragmentation and iteration is *fast*. (Way faster than the branch prediction nightmare that is our normal hashtable's iteration.) But the current reality is very different. I no longer insert during regular marking, because regular marking has the mutator mixed into it so the entries added to the table may get removed from their weakmaps and thus need to be removed from the table too. I'll need to do that to make this incremental, but for now it's simpler to skip it and just scan through all marked weakmaps in existence when entering weak marking mode. I do have to iterate over the table for every zone group, though as you notice I'm looking up the key so I'm not really getting much benefit. (The Range iteration is blazingly fast but it's not walking the real table. So this isn't an "extra" lookup, it's just a lookup for each key that needs to be removed. It could be a win or a lose vs a regular hashtable, depending on the distribution of keys per zone group.) And I'm making holes in the key space with these zone group removals. In short, my intended access patterns perfectly matched OHM initially, but no longer do at all. And yet, it's not clear that switching to a HashMap would be any better (other than for debug-only validation), and it's working as written, so... :-|

Terrence -- this is just the incremental patch updating for review comments. The only thing I'd like you to look at is the extractUnbarriered thing. I'm not sure why this suddenly started failing, but it won't compile without this now because it can't figure out how to get from GCCellPtr(PreBarriered<JSObject*>) to the GCCellPtr(JSObject*) constructor. Maybe there's a better way? I hate putting this in a header.

Comment on attachment 8647239 [details] [diff] [review] Handle review comments Review of attachment 8647239 [details] [diff] [review]: ----------------------------------------------------------------- It's gross, but it's not like it's the first awful hack in of this sort in weakmap. We really need to sit down and come up with enough generic tooling to handle weakmap in a nice way; I'm sure it would come in handy elsewhere too. For now, this is fine -- I've had to do my own share of hacking around C++ constructor selection this week, so I totally empathize.

Comment on attachment 8638810 [details] [diff] [review] Implement a linear-time ephemeron marking algorithm Thanks, decoder, I fixed the bug you found here, landed it, then fixed the followup bug you filed separately. So there's no need to fuzz this specific patch anymore. But if you have any ideas about a better way to fuzz the OOM path in this stuff, I'm all ears -- your fuzzer gets at it a little with OOMAfterAllocations, but that's kind of indirect. I could have a separate AbortWeakMarkingAfter() thing, I suppose, though it seems kind of specific.

Oops, I should have removed the leave-open keyword. Looks like this landed in 43.