Last Comment Bug 753203 - (ExactRooting) [meta] GC: Exact Stack Rooting
(ExactRooting)
: [meta] GC: Exact Stack Rooting
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- normal with 13 votes (vote)
: mozilla28
Assigned To: Terrence Cole [:terrence]
:
Mentors:
: 902913 (view as bug list)
Depends on: 745742 750733 753542 753609 759895 761391 761712 762678 763096 763110 764440 772820 773686 777219 780309 780765 782802 786136 788904 790108 790836 791611 792218 793076 793086 793577 793588 793823 795743 796760 798638 800631 802319 807027 810102 811168 813244 816770 817091 826435 826879 828020 828244 828248 828293 828462 828494 828567 828690 828696 828753 828977 829087 829205 829230 829294 829372 829830 829898 829997 830783 830846 831370 831376 ExactRootingBrowser 831580 834909 838955 839376 841054 841558 845519 847728 848592 850074 850293 852602 858619 860050 864848 866112 866134 866775 866778 866789 867295 867426 868037 868302 869469 869479 870442 872185 872638 875939 879046 880392 883383 884065 884562 884617 884956 887009 895220 896280 898220 898606 915735 916338 926778 930378 930677 ExactRootingB2G 951743 959683 960028 960342 962256 963918 969989 973584 1009675 1061214
Blocks: GenerationalGC 795030 902913 933467
  Show dependency treegraph
 
Reported: 2012-05-08 17:22 PDT by Terrence Cole [:terrence]
Modified: 2015-08-08 01:10 PDT (History)
50 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
fixed
fixed


Attachments
Experiment: root everything and let C++ sort it out. (2.42 KB, patch)
2012-06-22 14:31 PDT, Terrence Cole [:terrence]
no flags Details | Diff | Splinter Review
enable_exr-v0.diff (1.25 KB, patch)
2013-11-22 12:55 PST, Terrence Cole [:terrence]
sphink: review-
jcoppeard: review-
Details | Diff | Splinter Review
enable_exr_on_linux-v0.diff (3.73 KB, patch)
2013-11-22 15:26 PST, Terrence Cole [:terrence]
no flags Details | Diff | Splinter Review
enable_exr_all_but_b2g_fennec-v3.diff (1.45 KB, patch)
2013-12-10 11:40 PST, Terrence Cole [:terrence]
sphink: feedback+
Details | Diff | Splinter Review
enable_exr_all_but_b2g_fennec-v4.diff (1.54 KB, patch)
2013-12-12 09:46 PST, Terrence Cole [:terrence]
ted: review+
terrence.d.cole: feedback+
Details | Diff | Splinter Review
enable_exr_all_but_b2g-v5.diff (296 bytes, patch)
2014-01-08 15:50 PST, Terrence Cole [:terrence]
no flags Details | Diff | Splinter Review
enable_exr_all_but_b2g-v5.diff (8.88 KB, patch)
2014-01-08 16:02 PST, Terrence Cole [:terrence]
ted: review+
Details | Diff | Splinter Review
enable_exr_on_desktop-v6.diff (10.27 KB, patch)
2014-01-17 09:15 PST, Terrence Cole [:terrence]
terrence.d.cole: review+
Details | Diff | Splinter Review
enable_exact_rooting_everywhere-v0.diff (1.26 KB, patch)
2014-07-17 15:36 PDT, Terrence Cole [:terrence]
sphink: review+
Details | Diff | Splinter Review

Description Terrence Cole [:terrence] 2012-05-08 17:22:26 PDT
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] 2012-06-22 14:31:03 PDT
Created attachment 635918 [details] [diff] [review]
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:] (PTO Sep23-28) 2012-06-22 15:12:45 PDT
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] 2012-06-22 15:33:20 PDT
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 [:njn] 2012-06-26 06:30:16 PDT
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 (:bhackett) 2012-06-26 08:13:39 PDT
(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] 2012-06-26 09:43:42 PDT
(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 [:njn] 2012-06-26 15:58:29 PDT
> 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] 2013-11-22 12:55:19 PST
Created attachment 8337011 [details] [diff] [review]
enable_exr-v0.diff
Comment 9 Steve Fink [:sfink] [:s:] (PTO Sep23-28) 2013-11-22 14:33:53 PST
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] 2013-11-22 15:26:08 PST
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
Comment 11 Terrence Cole [:terrence] 2013-11-22 15:28:19 PST
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 (:billm) 2013-11-22 15:29:28 PST
(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:] (PTO Sep23-28) 2013-11-22 15:31:38 PST
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] 2013-11-22 16:42:57 PST
Comment on attachment 8337104 [details] [diff] [review]
enable_exr_on_linux-v0.diff

We need to use configure.in.
Comment 15 Terrence Cole [:terrence] 2013-12-10 11:40:22 PST
Created attachment 8345436 [details] [diff] [review]
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:] (PTO Sep23-28) 2013-12-11 10:29:23 PST
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] 2013-12-12 09:46:45 PST
Created attachment 8346657 [details] [diff] [review]
enable_exr_all_but_b2g_fennec-v4.diff

Updated the patch with what Steve and I discussed.
Comment 18 Terrence Cole [:terrence] 2014-01-08 15:50:40 PST
Created attachment 8357461 [details] [diff] [review]
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 (:billm) 2014-01-08 15:53:19 PST
The patch is empty.
Comment 20 Terrence Cole [:terrence] 2014-01-08 16:02:26 PST
Created attachment 8357467 [details] [diff] [review]
enable_exr_all_but_b2g-v5.diff

Gah! Thanks, Bill!
Comment 21 Steve Fink [:sfink] [:s:] (PTO Sep23-28) 2014-01-08 23:11:52 PST
https://tbpl.mozilla.org/php/getParsedLog.php?id=32725838&tree=Try looks like it might be real.
Comment 22 Ted Mielczarek [:ted.mielczarek] 2014-01-10 12:47:15 PST
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] 2014-01-17 09:15:14 PST
Created attachment 8361795 [details] [diff] [review]
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] 2014-01-17 09:17:22 PST
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 26 Phil Ringnalda (:philor) 2014-01-18 15:22:32 PST
https://hg.mozilla.org/mozilla-central/rev/6f7227918e79
Comment 27 Boris Zbarsky [:bz] (still a bit busy) 2014-01-20 11:35:21 PST
This seems to have caused 3-4% dromaeo-css regressions across platforms...
Comment 28 Boris Zbarsky [:bz] (still a bit busy) 2014-01-20 11:37:07 PST
In particular 6% or more regressions on the mootools tests, and slightly smaller on the others....
Comment 29 Boris Zbarsky [:bz] (still a bit busy) 2014-01-20 11:37:36 PST
http://perf.snarkfest.net/compare-talos/index.html?oldRevs=b3c08e6fa790&newRev=61fd0f987cf2&submit=true has some links to data.
Comment 30 Terrence Cole [:terrence] 2014-01-21 13:35:52 PST
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 [:bz] (still a bit busy) 2014-01-21 13:40:48 PST
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] 2014-02-26 02:38:03 PST
(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 33 Terrence Cole [:terrence] 2014-05-08 15:07:39 PDT
*** Bug 902913 has been marked as a duplicate of this bug. ***
Comment 34 Terrence Cole [:terrence] 2014-07-17 15:36:45 PDT
Created attachment 8458317 [details] [diff] [review]
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:] (PTO Sep23-28) 2014-07-17 16:07:22 PDT
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] 2014-07-18 16:27:20 PDT
https://tbpl.mozilla.org/?tree=Try&rev=3252553ea95f
Comment 38 Chris Peterson [:cpeterson] 2014-07-21 13:36:39 PDT Comment hidden (obsolete)
Comment 39 Ryan VanderMeulen [:RyanVM] 2014-07-21 14:41:18 PDT
(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) 2014-07-21 18:02:08 PDT
https://hg.mozilla.org/mozilla-central/rev/af0d4e4d2779
Comment 41 Terrence Cole [:terrence] 2015-06-03 14:18:04 PDT
This is /so/ done.

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