1367795 - Incrementalise table sweeping

Status: RESOLVED FIXED

(Core :: JavaScript: GC, enhancement)

Description

[Jon Coppeard (:jonco)]

At the start of sweeping a sweep group there currently are a whole bunch of tables that need to be swept before we yield to the mutator.  We should come up with an abstraction for a table that can be swept incrementally and allow this work to happen incrementally.

Comment 1

[Jon Coppeard (:jonco)]

Attachment: 1-specialise-weak-set

Specialise WeakCache for GCHashSet so that we can add barriers to it later.

Comment 2

[Jon Coppeard (:jonco)]

Attachment: 2-specialise-weak-map

Same for maps.

Comment 3

[Jon Coppeard (:jonco)]

Attachment: 3-barrier-weak-set

Add barriers to GCHashSet.  

Note that this barrier allows us to return to the mutator between sweeping sets but not part way through sweep of a particular set.  I have patches to do the later but I'm going to try and land the simpler version first and see what effect that has.

Comment 4

[Jon Coppeard (:jonco)]

Attachment: 4-barrier-weak-map

Add barriers to GCHashMap.

Comment 5

[Jon Coppeard (:jonco)]

Attachment: 5-refactor-movable-cell-hashing

Refactor movable cell hashing.  Methods to get the unique ID / hashcode for a class are moved to MovableCellHash<> for that class, which is in turn implemented in terms of MovableCellHasher<> for the constituent fields.  Also Zone::getUniqueId is renamed to getOrCreateUniqueId.

Comment 6

[Jon Coppeard (:jonco)]

Attachment: 6-fix-movable-cell-match

When adding an entry to a weak cache table that hasn't been swept yet, we can attempt to match the new entry against an existing dead entry.  If the table is keyed on unique IDs, the ID will have been removed from the unique ID table by this point.  We need to allow this to happen and fail the match.  Test code for this is present in a later patch.

Comment 7

[Jon Coppeard (:jonco)]

Attachment: 7-defer-weak-cache-sweep

Add an incremental sweep phase to sweep weak caches.  This gives us incremental sweeping of these tables but only sweeps one at a time on the main thread.

Comment 8

[Jon Coppeard (:jonco)]

Attachment: 8-add-tests

Add a bunch of jsapi tests for set and map barriers and the unique ID issue mentioned previously.

Comment 9

[Jon Coppeard (:jonco)]

Attachment: 9-use-single-parallel-task

Use a single parallel task for sweeping weak caches.

Comment 10

[Jon Coppeard (:jonco)]

Attachment: 10-use-multiple-parallel-tasks

Use multiple parallel tasks for table sweeping.

Comment 11

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

Comment on attachment 8883329 [details] [diff] [review]
3-barrier-weak-set

Review of attachment 8883329 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/public/GCHashTable.h
@@ +587,5 @@
> +
> +    size_t capacity() const {
> +        // Barriering is not implemented for this method.
> +        MOZ_ASSERT(!needsBarrier);
> +        return set.capacity();

I don't understand the choice of APIs to restrict.

capacity() it seems like could pass through, although I guess it depends on whether the caller is using capacity for "if I insert something will it need to resize?" vs "once the table is swept, how many things can the table hold?"

count() on the other hand seems like it really ought to only include live entries. Except when it's being used as a work estimate.

Comment 12

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] from comment #11)
> I don't understand the choice of APIs to restrict.

This was just being pragmatic: I added barriers where it was necessary and easy, and disallowed the rest.

capacity() is ambiguous about what it should return so I left it out.  count() would require iterating the set and is only rarely used, so I disallowed that as well.

I guess I should change the comments to say "currently not implemented" and explain why.

Comment 13

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

(In reply to Jon Coppeard (:jonco) from comment #12)
> (In reply to Steve Fink [:sfink] [:s:] from comment #11)
> > I don't understand the choice of APIs to restrict.
> 
> This was just being pragmatic: I added barriers where it was necessary and
> easy, and disallowed the rest.
> 
> capacity() is ambiguous about what it should return so I left it out. 
> count() would require iterating the set and is only rarely used, so I
> disallowed that as well.

Well, no, that was the confusion. You *allow* count() in this patch, just returning set.count(), so it's giving the count of both live and dead entries. I suspect it's because you're using it as the return value for sweep(). Except you don't, you directly call set.count() instead. If they were all disallowed, it would make more sense. And I think that's what you did in a following patch for another one.

But this is totally minor, and I haven't made it through all the remaining patches yet to see if things change later on. I guess I would lean towards disallowing count() here for consistency, unless you really need it for something.

Comment 14

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

Comment on attachment 8883342 [details] [diff] [review]
6-fix-movable-cell-match

Review of attachment 8883342 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/gc/Barrier.cpp
@@ +193,5 @@
> +#endif
> +
> +    uint64_t keyId;
> +    if (!zone->maybeGetUniqueId(k, &keyId))
> +        return false;

Add some sort of comment, eg // live cell cannot match dead cell

Comment 15

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

Comment on attachment 8883343 [details] [diff] [review]
7-defer-weak-cache-sweep

Review of attachment 8883343 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsgc.cpp
@@ +5227,5 @@
>  IterateWeakCaches(JSRuntime* rt, Functor f)
>  {
>      for (GCSweepGroupIter zone(rt); !zone.done(); zone.next()) {
>          for (JS::detail::WeakCacheBase* cache : zone->weakCaches()) {
> +            if (!f(cache, true))

Sorry, the true/false is pretty cryptic. Can this use a file-local enum { ForSweepGroup, ForZone }?

@@ +5244,5 @@
> +static bool
> +PrepareWeakCacheTasks(JSRuntime* rt, WeakCacheTaskVector* immediateTasks)
> +{
> +    // Start incremental sweeping for caches which support it or add to a vector
> +    // of sweep tasks to run on a helper thread.

s/which/that/ (sorry, pet peeve, and accepted usage says nobody cares anymore. But I still like to use 'that' for restrictive clauses, 'which' for unrestrictive ones.)

Comment 16

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

Comment on attachment 8883344 [details] [diff] [review]
8-add-tests

Review of attachment 8883344 [details] [diff] [review]:
-----------------------------------------------------------------

Wow, really nice!

Comment 17

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

Comment on attachment 8883345 [details] [diff] [review]
9-use-single-parallel-task

Review of attachment 8883345 [details] [diff] [review]:
-----------------------------------------------------------------

I think I'll mostly depend on try results for this patch. It all looks ok to me.

::: js/src/jsgc.cpp
@@ +5732,5 @@
> +        runtime()->gc.joinTask(*this, gcstats::PhaseKind::SWEEP_WEAK_CACHES, lock_);
> +    }
> +
> +  private:
> +    void  run() override {

s/void  run/void run/

Comment 18

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

Comment on attachment 8883330 [details] [diff] [review]
4-barrier-weak-map

Review of attachment 8883330 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/public/GCHashTable.h
@@ +363,5 @@
> +// Template for a hashtable Ptr or AddPtr that records which table it points
> +// into. This is complicated by the fact that MainSet and NewSet may or may not
> +// be the same type.
> +template <typename MainSetPtr, typename NewSetPtr, typename Entry>
> +class VariantHashTablePtr

Ok, I delayed r+'ing this one because I wanted to see its users. I had an alternative approach to some of this. But I didn't see this get used anywhere. Is this dead code from a previous approach, or did I miss it? (Totally possible.)

Comment 19

[Jon Coppeard (:jonco)]

Attachment: 0-refactor-weak-cache-use

I forgot to attach this patch.  This refactors a couple of palaces in wasm to move the WeakCache into the defined table type.  This is necessary because we sometimes use the table type and the new specialised versions of WeakCache don't convert to the inner table type any more.

Comment 20

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] from comment #13)
> Well, no, that was the confusion. You *allow* count() in this patch

Oh, that was unintentional!  It's meant to be the same as the following patch.  I'll disallow and re-test.

Comment 21

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] from comment #18)
VariantHashTablePtr was dead code from a previous approach.  I've removed it.

Comment 22

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/8209dbf3584f
Refactor some use of WeakCache r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/c726ece401b9
Specialise JS::WeakCache for GCHashSet so we can add barriers r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/e432f2a10f2a
Specialise JS::WeakCache for GCHashMap so we can add barriers r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/3290d214503d
Add barriers to JS::WeakCache for GCHashSet r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/03e4fa4f4cde
Add barriers to JS::WeakCache for GCHashMap r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/e84fcf7957db
Refactor movable cell hashing methods to move them to MovableCellHasher<T> r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/ce64262091ba
Allow movable cell hashing to handle matching against a dead table entry r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/5c5ed1bd3eb1
Move weak cache sweeping out of the initial slice for the sweep group r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/29dbcc6cf468
Add tests for incremental weak cache sweeping r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/af886a4299f3
Use a single parallel task for weak cache sweeping r=sfink
https://hg.mozilla.org/integration/mozilla-inbound/rev/8116597d45f9
Use multiple parallel tasks for weak cache sweeping r=sfink

Comment 23

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/8209dbf3584f
https://hg.mozilla.org/mozilla-central/rev/c726ece401b9
https://hg.mozilla.org/mozilla-central/rev/e432f2a10f2a
https://hg.mozilla.org/mozilla-central/rev/3290d214503d
https://hg.mozilla.org/mozilla-central/rev/03e4fa4f4cde
https://hg.mozilla.org/mozilla-central/rev/e84fcf7957db
https://hg.mozilla.org/mozilla-central/rev/ce64262091ba
https://hg.mozilla.org/mozilla-central/rev/5c5ed1bd3eb1
https://hg.mozilla.org/mozilla-central/rev/29dbcc6cf468
https://hg.mozilla.org/mozilla-central/rev/af886a4299f3
https://hg.mozilla.org/mozilla-central/rev/8116597d45f9