Last Comment Bug 755604 - Incrementalize JSCompartment::markTypes
: Incrementalize JSCompartment::markTypes
Status: RESOLVED FIXED
[Snappy]
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: mozilla15
Assigned To: Till Schneidereit [till] (pto until Dec 5)
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on: 756796 756851
Blocks: 756130
  Show dependency treegraph
 
Reported: 2012-05-15 18:57 PDT by [PTO to Dec5] Bill McCloskey (:billm)
Modified: 2012-05-21 01:02 PDT (History)
7 users (show)
ryanvm: in‑testsuite-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
incrementalize JSCompartment::MarkTypes (5.88 KB, patch)
2012-05-16 11:26 PDT, Till Schneidereit [till] (pto until Dec 5)
wmccloskey: review+
Details | Diff | Splinter Review
incrementalize JSCompartment::MarkTypes, v2, carrying billm's r+ (5.88 KB, patch)
2012-05-17 09:49 PDT, Till Schneidereit [till] (pto until Dec 5)
till: review+
Details | Diff | Splinter Review
incrementalize JSCompartment::MarkTypes, v3, un-bitrotted, carrying billm's r+ (5.88 KB, patch)
2012-05-17 11:06 PDT, Till Schneidereit [till] (pto until Dec 5)
till: review+
Details | Diff | Splinter Review
incrementalize JSCompartment::MarkTypes, v4, with bustage fixed, carrying billm's r+ (5.97 KB, patch)
2012-05-18 08:57 PDT, Till Schneidereit [till] (pto until Dec 5)
till: review+
Details | Diff | Splinter Review

Description [PTO to Dec5] Bill McCloskey (:billm) 2012-05-15 18:57:48 PDT
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] (pto until Dec 5) 2012-05-16 01:42:53 PDT
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] (pto until Dec 5) 2012-05-16 11:26:23 PDT
Created attachment 624462 [details] [diff] [review]
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 [PTO to Dec5] Bill McCloskey (:billm) 2012-05-16 17:11:19 PDT
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] (pto until Dec 5) 2012-05-17 09:49:05 PDT
Created attachment 624784 [details] [diff] [review]
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] 2012-05-17 09:52:42 PDT
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] (pto until Dec 5) 2012-05-17 10:06:20 PDT
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] (pto until Dec 5) 2012-05-17 11:06:35 PDT
Created attachment 624801 [details] [diff] [review]
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] 2012-05-17 11:26:22 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/a97741bbd972
Comment 9 Ed Morley [:emorley] 2012-05-17 11:38:30 PDT
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 [PTO to Dec5] Bill McCloskey (:billm) 2012-05-17 11:55:22 PDT
Pushed this to try with the compiler error fixed:
https://tbpl.mozilla.org/?tree=Try&rev=13692ba66a13
Comment 11 [PTO to Dec5] Bill McCloskey (:billm) 2012-05-17 16:12:15 PDT
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] 2012-05-17 20:39:42 PDT
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] (pto until Dec 5) 2012-05-18 08:57:43 PDT
Created attachment 625132 [details] [diff] [review]
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] (pto until Dec 5) 2012-05-18 09:08:01 PDT
green on try, finally.
Comment 15 Ryan VanderMeulen [:RyanVM] 2012-05-18 10:43:35 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/5232403e7b8f
Comment 16 Ryan VanderMeulen [:RyanVM] 2012-05-18 18:23:56 PDT
https://hg.mozilla.org/mozilla-central/rev/5232403e7b8f

Note You need to log in before you can comment on or make changes to this bug.