755604 - Incrementalize JSCompartment::markTypes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Right now, when running animations, we spend between 20ms and 70ms in the markTypes phase of GC. It would be great if we could incrementalize this step.

The only thing markTypes does is to mark all types and scripts in a compartment, and all JS objects with singleton types. Marking the singleton objects takes virtually all the time. The other steps we should probably leave alone, if only for simplicity.

We use a CellIterUnderGC to iterate over all JSObjects. The implementation of this class is in jsgcinlines.h; most of it comes from its parent class, CellIterImpl. It basically iterates over all ArenaHeaders, and all Cells in the ArenaHeader. For each Cell (which in this case is always an object), markTypes checks hasSingletonType() and then pushes it onto the mark stack via MarkObjectRoot. If you step through MarkObjectRoot in a debugger, it calls MarkRoot, which calls MarkInternal, which calls PushMarkStack, which calls GCMarker::pushObject. All these functions are defined in js/src/gc/Marking.cpp.

The mark stack is defined in jsgc.h in the GCMarker and MarkStack classes. Besides objects, we can push a variety of other things onto the mark stack. The lower bits of each mark stack entry tells you what kind they are.

To incrementalize this, I think we should have a new kind of mark stack item for an entire ArenaList. So the markTypes code for objects would look something like this instead:

for (size_t thingKind = FINALIZE_OBJECT0;
     thingKind < FINALIZE_OBJECT_LIMIT;
     thingKind++)
{
    rt->gcMarker.pushArenaList(arenas.getFirstArena(thingKind));
}

Then we would need to have a way to process this mark stack entry. This would happen in the GCMarker::processMarkStackOther function, in gc/Marking.cpp. In this function, we would start at the arena pushed onto the mark stack, iterate through more arenas via their next pointers, and over the cells in the arenas, just like in CellIterImpl. We would check the hasSingletonType flag and push the object on to the mark stack in that case.

Occasionally, we would have to check if budget.isOverBudget(). This tells us whether it's time for the current mark slice to end; see the checks in GCMarker::processMarkStackTop. If so, we would push the current arena back onto the mark stack and return.

I realize that there is a lot of complexity here. However, I don't think that the final patch would be too big. Please ask lots of questions, Till. Also, please let me know if you think it's too big a problem. There are lots of other things to work on.

Comment 1

[Till Schneidereit [:till]]

Thanks for the thorough description, Bill. That looks doable to me, so I'll see how far I get and ping you on IRC with any questions I might have in the process.

For reference, Google's Spinning Balls benchmark is a good test-case for this, as it currently causes GCs whose first slice takes about 70ms.

Comment 2

[Till Schneidereit [:till]]

Attachment: incrementalize JSCompartment::MarkTypes

Two notes on this:

- I wonder whether it'd make sense to have a cell iterator that only iterates over the cells of one arena as a simple abstraction. Both ForEachArenaAndCell and CellIterImpl::next contain code that's very similar to what I have now added to GCMarker::processMarkStackOther and it seems to me like much of that should be combinable into an iterator.

- I'm not sure if budget.step() is placed correctly. Should that only happen if object->hasSingletonType()?

Comment 3

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 624462 [details] [diff] [review]
incrementalize JSCompartment::MarkTypes

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

This looks exactly right to me, Till. Thanks! I only asked for some minor syntactic changes. Could you post an updated patch?

I like the idea of abstracting out the code to iterate over cells in an arena. Could you file a bug for that?

If you're interested, the SpiderMonkey coding style is here. We try to stick to a single uniform style.
  https://wiki.mozilla.org/JavaScript:SpiderMonkey:C++_Coding_Style

Also, you might want to look into getting level 1 committer access if you don't already have it. This page gives more information:
  http://www.mozilla.org/hacking/committer/
Basically, you have to fill out a form and fax it to Mozilla. Then you can push patches to our tryserver, which runs a bunch of automated tests. This is the first step toward being able to commit code to the repository yourself.

::: js/src/gc/Marking.cpp
@@ +997,5 @@
>              pushObject(obj);
> +    } else if (tag == ArenaTag) {
> +        for (ArenaHeader *aheader = reinterpret_cast<ArenaHeader *>(addr);
> +             aheader;
> +             aheader = aheader->next) {

Please put the brace on its own line. We do this if the part before the brace spans multiple lines. It makes it easier to see when the loop body starts.

@@ +999,5 @@
> +        for (ArenaHeader *aheader = reinterpret_cast<ArenaHeader *>(addr);
> +             aheader;
> +             aheader = aheader->next) {
> +            AllocKind thingKind = aheader->getAllocKind();
> +            size_t thingSize = Arena::thingSize(thingKind);

You can move these two statements outside of the loop, since this stuff will be the same for all the arenas you're iterating over.

@@ +1013,5 @@
> +                    thing = span->last;
> +                    span = span->nextSpan();
> +                } else {
> +                    JSObject *object = reinterpret_cast<JSObject *>(thing);
> +                    if (object->hasSingletonType()) {

We don't put braces around single-line statements.

::: js/src/jscompartment.cpp
@@ +413,2 @@
>           thingKind < FINALIZE_OBJECT_LIMIT;
>           thingKind++) {

Could you move the brace to its own line? We only started using this style a little while ago, so not all the code uses it.

Also, although the pushArenaList statement is only one line, I think we should still use braces here because the for (...) loop takes multiple lines.

Comment 4

[Till Schneidereit [:till]]

Attachment: incrementalize JSCompartment::MarkTypes, v2, carrying billm's r+

(In reply to Bill McCloskey (:billm) from comment #3)
> Comment on attachment 624462 [details] [diff] [review]
> incrementalize JSCompartment::MarkTypes

Thanks for the review, links, and suggestions, Bill!

I have applied for level 1 commit access, with jorendorff and gwagner vouching, so that should happen soon.

> I like the idea of abstracting out the code to iterate over cells in an
> arena. Could you file a bug for that?

Done: bug 756130

> ::: js/src/jscompartment.cpp
> @@ +413,2 @@
> >           thingKind < FINALIZE_OBJECT_LIMIT;
> >           thingKind++) {
> 
> Could you move the brace to its own line? We only started using this style a
> little while ago, so not all the code uses it.

In the end I decided not to break the for() loop header into multiple lines as it fits into 99 columns.

Comment 5

[Ryan VanderMeulen [:RyanVM]]

patching file js/src/gc/Marking.cpp
Hunk #1 FAILED at 977
1 out of 2 hunks FAILED -- saving rejects to file js/src/gc/Marking.cpp.rej
patching file js/src/jsgc.h
Hunk #2 FAILED at 915
1 out of 3 hunks FAILED -- saving rejects to file js/src/jsgc.h.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir

Comment 6

[Till Schneidereit [:till]]

Damn, bitten by e4x - in an hg patch of all places ;)

New patch coming up, waiting for my build to finish.

Comment 7

[Till Schneidereit [:till]]

Attachment: incrementalize JSCompartment::MarkTypes, v3, un-bitrotted, carrying billm's r+

Un-bitrotted patch, applies cleanly to central as of now

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a97741bbd972

Comment 9

[Ed Morley [:emorley]]

Unfortunately had to back out for compilation errors:
https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=a97741bbd972

eg:
https://tbpl.mozilla.org/php/getParsedLog.php?id=11837479&tree=Mozilla-Inbound

{
../../../js/src/jscompartment.cpp: In member function 'void JSCompartment::markTypes(JSTracer*)':
../../../js/src/jscompartment.cpp:412: warning: comparison between signed and unsigned integer expressions
../../../js/src/jscompartment.cpp:412: error: no 'operator++(int)' declared for postfix '++', trying prefix operator instead
../../../js/src/jscompartment.cpp:412: error: no match for 'operator++' in '++thingKind'
make[5]: *** [jscompartment.o] Error 1
}

https://hg.mozilla.org/integration/mozilla-inbound/rev/f2a65c6a01f6

Comment 10

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Pushed this to try with the compiler error fixed:
https://tbpl.mozilla.org/?tree=Try&rev=13692ba66a13

Comment 11

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

It looks like a few jit-tests are failing. Luckily, these are usually the easiest ones to fix. The failing tests are:
bug713226.js, bug732087.js, bug738841.js, bug738846.js, bug754150.js (and a few others)

If you build a JS shell, you can run these tests from the command line like so:
    ./jit-test/jit_test.py $PATH_TO_JS_SHELL/js --jitflags=mna bug713226.js
It should report a failure. You can see the output by passing the -so command line option. Or you can start the test in the debugger by passing -g.

Let me know if you get stuck.

Comment 12

[Ryan VanderMeulen [:RyanVM]]

Original landing and backout:
https://hg.mozilla.org/mozilla-central/rev/a97741bbd972
https://hg.mozilla.org/mozilla-central/rev/f2a65c6a01f6

Comment 13

[Till Schneidereit [:till]]

Attachment: incrementalize JSCompartment::MarkTypes, v4, with bustage fixed, carrying billm's r+

This version looks pretty green on try: https://tbpl.mozilla.org/?tree=Try&rev=f7ac05a7f596

The problem with the previous one was that markTypes was pushing arena headers onto the mark stack without checking if they even existed, causing NPEs in GCMarker::processMarkStackOther

Comment 14

[Till Schneidereit [:till]]

green on try, finally.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5232403e7b8f

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5232403e7b8f