753203 - (ExactRooting) [meta] GC: Exact Stack Rooting

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Terrence Cole [:terrence]]

This is a meta bug that links to all of the on-going rooting work that is blocking further work on the GC.

Comment 1

[Terrence Cole [:terrence]]

Attachment: Experiment: root everything and let C++ sort it out.

We have wondered for awhile how much difference it will make to just Root everything on the stack always.  The worry here is that this will be slow compared to rooting a minimalish set of what we need, but much, much easier to use and maintain.

Dave had an excellent idea yesterday for how to test this: fake "link" everything coming out of (Try)NewGCThing into a list.  This will give us the performance equivalent to putting every new thing into a Rooted immediately.  Caveat: this misses the cost of re-rooting returned values and doesn't address the double indirection through handles.

Both were builds were with:  --target=i686-pc-linux --enable-tests --enable-valgrind --disable-debug --enable-optimize

Inbound tip (97329:bfa21a56f646) before the patch:
       crypto: 0.04 sys 1.81 user 0:02.02 wall 213728 kb
    deltablue: 0.06 sys 1.96 user 0:02.01 wall 446336 kb
 earley-boyer: 0.06 sys 7.46 user 0:07.54 wall 409408 kb
     raytrace: 0.01 sys 4.17 user 0:04.17 wall 407872 kb
       regexp: 0.05 sys 2.01 user 0:02.05 wall 199248 kb
     richards: 0.01 sys 1.51 user 0:01.54 wall 54880 kb
        splay: 0.05 sys 0.58 user 0:00.63 wall 1008160 kb

With the attached patch:
       crypto: 0.03 sys 1.81 user 0:01.84 wall 213664 kb
    deltablue: 0.02 sys 2.00 user 0:02.01 wall 446320 kb
 earley-boyer: 0.04 sys 7.50 user 0:07.54 wall 409536 kb
     raytrace: 0.03 sys 4.08 user 0:04.10 wall 407760 kb
       regexp: 0.02 sys 2.05 user 0:02.06 wall 199264 kb
     richards: 0.00 sys 1.52 user 0:01.51 wall 54848 kb
        splay: 0.07 sys 0.57 user 0:00.63 wall 1008144 kb

The cost is not zero, but it's pretty close.

Comment 2

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

Seems promising! Are you unlinking as well?

Thinking about how this compares to hypothetical reality, this will root some things we wouldn't root (and so is pessimistic), but only roots things once (and so is optimistic.)

We could get an estimate for the cost of the narrowest possible rooting, by doing a stack scan at every NewGCThing and gathering together the set of gcthings on the stack into a vector. Then on the next stack scan, you find the longest common prefix and assume that you wouldn't have to re-root those. The sum of all the suffix lengths is the total number of things you would root. But to estimate the cost, you'd probably want to just store a vector of the suffix lengths, and "fake-root" that many objects on each call (assuming a deterministic replay). The overhead of that is a fairer baseline to compare your naive "root 'em all and let God sort 'em out" strategy, though I wish there were a simple way of coming up with a more accurate estimate of a maximal rooting strategy. Or rather, a sufficiently pessimistic one. Anybody?

I wonder how much the "root everything" resolves? It certainly removes the guesswork about what can potentially trigger GC. But there are still quite a few messy cases where you have arrays and structures of rootables, especially ones that are sometimes stored on the heap.

Comment 3

[Terrence Cole [:terrence]]

Thanks for pushing me to get some real stats.  This is mean + (stdev) for 6 runs from before and after.

Before:
      crypto 11.667ms (11.690) sys 1828.333ms (11.690) user 1830.000ms (0.000) wall
   deltablue 55.000ms (23.452) sys 1965.000ms (23.452) user 2010.000ms (0.000) wall
earley-boyer 43.333ms (13.663) sys 7476.667ms (13.663) user 7510.000ms (0.000) wall
    raytrace 45.000ms (17.607) sys 4115.000ms (17.607) user 4150.000ms (0.000) wall
      regexp 30.000ms (15.492) sys 2036.667ms (18.619) user 2060.000ms (6.325) wall
    richards 5.000ms (8.367) sys 1505.000ms (13.784) user 1500.000ms (6.325) wall
       splay 73.333ms (8.165) sys 556.667ms (8.165) user 623.333ms (5.164) wall

After:
      crypto 15.000ms (13.784) sys 1825.000ms (13.784) user 1840.000ms (0.000) wall
   deltablue 41.667ms (11.690) sys 1978.333ms (11.690) user 2010.000ms (0.000) wall
earley-boyer 33.333ms (10.328) sys 7506.667ms (10.328) user 7538.333ms (4.082) wall
    raytrace 33.333ms (20.656) sys 4066.667ms (20.656) user 4090.000ms (0.000) wall
      regexp 30.000ms (8.944) sys 2048.333ms (13.292) user 2068.333ms (7.528) wall
    richards 11.667ms (9.832) sys 1508.333ms (9.832) user 1510.000ms (0.000) wall
       splay 85.000ms (5.477) sys 555.000ms (5.477) user 630.000ms (0.000) wall

Comment 4

[Nicholas Nethercote [inactive]]

In my experience, V8 is quite non-deterministic, even at the instruction level (e.g. measuring instruction counts with Cachegrind).

With that in mind, to me these results say "the cost is zero, as closely as we can tell".

Comment 5

[Brian Hackett [Laid off!]]

(In reply to Terrence Cole [:terrence] from comment #1)
> Dave had an excellent idea yesterday for how to test this: fake "link"
> everything coming out of (Try)NewGCThing into a list.  This will give us the
> performance equivalent to putting every new thing into a Rooted immediately.
> Caveat: this misses the cost of re-rooting returned values and doesn't
> address the double indirection through handles.

I don't think this experiment is a good approximation of rooting costs.  The number of times a value is explicitly rooted (zero to many) is independent from the number of times it is allocated (once).  Moreover, most GC things in these benchmarks are being allocated in JIT code and won't hit NewGCThing or TryNewGCThing.

Comment 6

[Terrence Cole [:terrence]]

(In reply to Brian Hackett (:bhackett) from comment #5)
> I don't think this experiment is a good approximation of rooting costs.  The
> number of times a value is explicitly rooted (zero to many) is independent
> from the number of times it is allocated (once).  Moreover, most GC things
> in these benchmarks are being allocated in JIT code and won't hit NewGCThing
> or TryNewGCThing.

You're right, I totally forgot about that.  Given that this is a gross underestimate of the cost and that there is a visible impact even so, it looks like we are going to have to do things the hard way.  Oh well.

Comment 7

[Nicholas Nethercote [inactive]]

> Given that this is a gross
> underestimate of the cost and that there is a visible impact even so

I can believe the "gross underestimate", but like I said in comment 4, I disagree about the "visible impact".  In other words, I wouldn't abandon this approach yet.

Comment 8

[Terrence Cole [:terrence]]

Attachment: enable_exr-v0.diff

Comment 9

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

Comment on attachment 8337011 [details] [diff] [review]
enable_exr-v0.diff

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

Lunch discussion - we want to enable this a platform at a time.

Comment 10

[Terrence Cole [:terrence]]

Attachment: enable_exr_on_linux-v0.diff

Enable exact rooting on linux64. This is a bit challenging because there is no common configuration for only linux64.

https://tbpl.mozilla.org/?tree=Try&rev=09f9ddd79b16

Comment 11

[Terrence Cole [:terrence]]

Comment on attachment 8337104 [details] [diff] [review]
enable_exr_on_linux-v0.diff

Steve is still insisting that he isn't a build peer, so adding one.

Comment 12

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

(In reply to Terrence Cole [:terrence] from comment #10)
> Created attachment 8337104 [details] [diff] [review]
> enable_exr_on_linux-v0.diff
> 
> Enable exact rooting on linux64. This is a bit challenging because there is
> no common configuration for only linux64.
> 
> https://tbpl.mozilla.org/?tree=Try&rev=09f9ddd79b16

This is not a good way to do it. People's local builds won't pick up the change, which will cause a lot of confusion. If you want to make the change be platform-specific, I think you're going to have to modify configure.in :-(.

Comment 13

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

Comment on attachment 8337104 [details] [diff] [review]
enable_exr_on_linux-v0.diff

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

lgtm

Comment 14

[Terrence Cole [:terrence]]

Comment on attachment 8337104 [details] [diff] [review]
enable_exr_on_linux-v0.diff

We need to use configure.in.

Comment 15

[Terrence Cole [:terrence]]

Attachment: enable_exr_all_but_b2g_fennec-v3.diff

I'm not sure I like this approach as it seems like it would make it harder to test and enable exact rooting on mobile and b2g. What do you think Steve?

Comment 16

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

Comment on attachment 8345436 [details] [diff] [review]
enable_exr_all_but_b2g_fennec-v3.diff

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

We discussed over irc, and decided to (1) default the setting based on app name, and (2) whitelist apps instead of blacklisting b2g.

Comment 17

[Terrence Cole [:terrence]]

Attachment: enable_exr_all_but_b2g_fennec-v4.diff

Updated the patch with what Steve and I discussed.

Comment 18

[Terrence Cole [:terrence]]

Attachment: enable_exr_all_but_b2g-v5.diff

I did not know that we need to manually dup everything we want in configure.in manually over from js/src/configure.in, so this patch adds that. Additionally, we need the new option to come after the default app-name computation, so I moved that up. I also noticed that JSGC_INCREMENTAL is set twice so I removed one of them. And the JS options were spread out in two spots in the file, so I moved them all to one location.

https://tbpl.mozilla.org/?tree=Try&rev=9e6c71cf58f5

Comment 19

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

The patch is empty.

Comment 20

[Terrence Cole [:terrence]]

Attachment: enable_exr_all_but_b2g-v5.diff

Gah! Thanks, Bill!

Comment 21

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

https://tbpl.mozilla.org/php/getParsedLog.php?id=32725838&tree=Try looks like it might be real.

Comment 22

[(not currently active) Ted Mielczarek]

Comment on attachment 8357467 [details] [diff] [review]
enable_exr_all_but_b2g-v5.diff

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

r=me with one change.

::: configure.in
@@ +7061,5 @@
> +dnl = Use exact stack rooting for GC
> +dnl ========================================================
> +dnl Only enable exact rooting specifically on platforms with analysis coverage.
> +JSGC_USE_EXACT_ROOTING=
> +if test "$MOZ_APP_NAME" = firefox -o "$MOZ_APP_NAME" = mobile/android ; then

These want to go in confvars.sh:
http://mxr.mozilla.org/mozilla-central/source/browser/confvars.sh
http://mxr.mozilla.org/mozilla-central/source/mobile/android/confvars.sh

::: js/src/configure.in
@@ +3372,5 @@
>  dnl = Use exact stack rooting for GC
>  dnl ========================================================
> +dnl Only enable exact rooting specifically on platforms with analysis coverage.
> +JSGC_USE_EXACT_ROOTING=
> +if test "$MOZ_APP_NAME" = firefox -o "$MOZ_APP_NAME" = mobile/android ; then

Same as the other one.

Comment 23

[Terrence Cole [:terrence]]

Attachment: enable_exr_on_desktop-v6.diff

I changed the patch a bit so that instead of relying on APP_NAME to propagate to SM's configury, we just set --enable-exact-rooting directly from the toplevel configure. This will keep it from referring to undefined variables in shell builds and make the mechanism of how the flag gets sent to our build during browser builds clearer.

Comment 24

[Terrence Cole [:terrence]]

Note: a try run ensuring this all works as expected is here: https://tbpl.mozilla.org/?tree=Try&rev=c69f8a9e520a

I inserted a #error #ifdef JSGC_USE_EXACT_ROOTING, so the red builds are the ones with it enabled and the green builds are not impacted behaviorally by the change. This looks like the right set.

Comment 25

[Terrence Cole [:terrence]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6f7227918e79

green try run:
https://tbpl.mozilla.org/?tree=Try&rev=eb22234a8b36

Comment 26

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/6f7227918e79

Comment 27

[Boris Zbarsky [:bzbarsky]]

This seems to have caused 3-4% dromaeo-css regressions across platforms...

Comment 28

[Boris Zbarsky [:bzbarsky]]

In particular 6% or more regressions on the mootools tests, and slightly smaller on the others....

Comment 29

[Boris Zbarsky [:bzbarsky]]

http://perf.snarkfest.net/compare-talos/index.html?oldRevs=b3c08e6fa790&newRev=61fd0f987cf2&submit=true has some links to data.

Comment 30

[Terrence Cole [:terrence]]

And a 5% increase on v8, which I did not expect. V8 is going to stay mostly in ion, so there should be few roots either way; I expect not traversing the stack is strictly less work there. On the other hand, DOM <-> Layout <-> XPCOM <-> JSAPI layer probably involves a lot of re-rooting. In particular the Define* API's are still re-rooting. I'd like to get to those today and see if it helps.

Comment 31

[Boris Zbarsky [:bzbarsky]]

It's also worth just profiling some of those tests.  10+% regressions (possibly more on some of the subtests?) should be pretty easy to pick up.

Comment 32

[Hannes Verschore [:h4writer]]

(In reply to Phil Ringnalda (:philor) from comment #26)
> https://hg.mozilla.org/mozilla-central/rev/6f7227918e79

Setting flag so it is easy to see exact rooting was enabled in FF28.

Comment 34

[Terrence Cole [:terrence]]

Attachment: enable_exact_rooting_everywhere-v0.diff

We still don't have a hazard analysis on mobile, but we don't have any implicated code there either, it seems. I think we should go ahead and land this and get ready to remove the conservative scanner with the next ESR.

Comment 35

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

Comment on attachment 8458317 [details] [diff] [review]
enable_exact_rooting_everywhere-v0.diff

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

I agree.

Comment 36

[Terrence Cole [:terrence]]

https://tbpl.mozilla.org/?tree=Try&rev=3252553ea95f

Comment 37

[Terrence Cole [:terrence]]

https://tbpl.mozilla.org/?tree=Try&rev=3252553ea95f
https://hg.mozilla.org/integration/mozilla-inbound/rev/af0d4e4d2779

Comment 38

[Chris Peterson [:cpeterson]]

Firefox OS 2.1 is based on Gecko 34, so it be the first version of Firefox OS with exact rooting.

Comment 39

[Ryan VanderMeulen [:RyanVM]]

(In reply to Chris Peterson (:cpeterson) from comment #38)
> Firefox OS 2.1 is based on Gecko 34, so it be the first version of Firefox
> OS with exact rooting.

Exact rooting for B2G was enabled in bug 941796 during the Gecko 32 cycle, i.e. v2.0.

Comment 40

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

https://hg.mozilla.org/mozilla-central/rev/af0d4e4d2779

Comment 41

[Terrence Cole [:terrence]]

This is /so/ done.