1564136 - Investigate performing sweep phase marking in parallel with sweeping

Status: RESOLVED FIXED

(Core :: JavaScript: GC, enhancement, P3)

Description

[Jon Coppeard (:jonco)]

When we start a slice in the sweep phase, the first thing we do is to do any new marking caused by barriers being triggered. After that is finished we start sweeping.

The marking and sweeping cannot occur in the same zones so it should be possible to perform these concurrently. The marking only happens in zones that are still in the marking state and the sweeping only happens in zones that are in the sweeping state.

We would need to wait for any concurrent marking to finsish in GCRuntime::endMarkingSweepGroup.

(Note that this bug is not about full concurrent marking).

Comment 1

[Jon Coppeard (:jonco)]

Before doing this it would be a good idea to gather some data about what the potential improvement is here.

Comment 2

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Hi Jonco
I'd like to measure the time we can save, but from your comment
https://mozilla.logbot.info/jsapi/20190717#c16471332-c16471360
<quote>
jonco:it would be good to know what the absolute time that we could save is too
jonco:I think it will be min ( marking time, time until gray marking ) if that makes sense
</quote>

there are some cases that I am not sure how to measure,

1. markUntilBudgetExhausted uses up the budget, it returns NotFinished
   https://searchfox.org/mozilla-central/rev/4fbcfe6fecf75d7b828fbebda79a31385f7eab5f/js/src/gc/GC.cpp#6715

2. when markUntilBudgetExhausted finishes, the gc slice doesn't have too much time left, so the slice ends before it reaches markGrayReferenceInCurrentGroup
   Should I take these two cases into account?

Also you mentioned to measure time until gray marking? The start of measuring is when markUntilBudgetExhausted finishes, right?
But then it will go to sweepActions, the question I have is from the log, sometimes markGrayReferencesInCurrentGroup is not the first action to run, (for example, sometimes GCRuntime::sweepTypeInformation runs after markUntilBudgetExhausted), and even sometimes gc slice finishes,
markGrayReferenceInCurrentGroup will run in the next gc slice, how to define 'time until gray marking' in this case?

Thanks

Comment 3

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: minor_gc happening during sweep_mark

So far I have a rough analysis, I use https://browserbench.org/JetStream/ as my test page,  (as octane is short-running)
and I measure the time spent in markUntilBudgetExhausted in performSweepActions
https://searchfox.org/mozilla-central/rev/40e889be8ff926e32f7567957f4c316f14f6fbef/js/src/gc/GC.cpp#6714

I didn't measure the time until gray marking (markGrayReferencesInCurrentGroup), as sometimes it won't be reached in the same slice.

When the JetStream2 finishes, the sweep-marking will run roughly 150 times, and I compare the time spent in markUntilBudgetExhausted with the SliceBudget passed in performSweepActions  (https://searchfox.org/mozilla-central/rev/40e889be8ff926e32f7567957f4c316f14f6fbef/js/src/gc/GC.cpp#6698)

total: 152 times (markUntilBudgetExhausted is called)
time spent in markUntilBudgetExhausted / slice budget
0%~9% : 87 
10%~80%: 21
90%: 31
100%: 13

for the most cases, the slice budget are 5~15ms

Also there's one case that minor_gc is happening during sweep_mark, and causes sweep_mark to spend more time.

Comment 4

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

dummy

Comment 5

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

This is continue on comment 3.
markUntilBudgetExhausted is called : 270 times
time spent in markUntilBudgetExhausted compared to the slice budget
<10%: 117 times => 43% of calls spend very few time in sweep-marking. Mostly <0.1 ms
70~100%: 71 times => 26% of the calls will spend more than 70% of the slice budget

Here I compare the time to the slice duration and the slice budget, because sometimes the slice duration runs longer than the budget.

A: total time spent in markUntilBudgetExhausted (in performSweepActions): 554 ms
B: total time duration (accumulated slice duration if markUntilBudgetExhausted runs in the slice): 2029 ms
C: total budget (accumulated budget if markUntilBudgetExhausted runs in the slice): 1649

A/B =>27%
A/C =>33%

And I also measured the time from the end of markUntilBudgetExhausted
https://searchfox.org/mozilla-central/rev/29cce9a2684ef64c4f1f996087da8b7545d31f65/js/src/gc/GC.cpp#6787
to the begin of markGrayReferencesInCurrentGroup
https://searchfox.org/mozilla-central/rev/29cce9a2684ef64c4f1f996087da8b7545d31f65/js/src/gc/GC.cpp#5572

the time until markGrayReferencesInCurrentGroup is reached, is always greater than the time spent in markUntilBudgetExhausted,
possibly for reaons:
(1): It's pretty rare than after markUntilBudgetExhausted the code will reach in markGrayReferencesInCurrentGroup above
because in many cases performSweepActions is called when the initialState is Mark and then reaches to markGrayReferencesInCurrentGroup to set hasMarkedGrayRoots to true, so next time performSweepActions is called when initialState is Sweep, the code to markGrayReferencesInCurrentGroup will bail out early.
https://searchfox.org/mozilla-central/rev/29cce9a2684ef64c4f1f996087da8b7545d31f65/js/src/gc/GC.cpp#5570

(2): the time spent in markUnitilBudgetExhausted is either very short or uses up the budget.
So the possible saved time is almost the time we spent in markUnitilBudgetExhausted

---

And here is another sample that will possibly have more improvements

markUntilBudgetExhausted is called : 242 times
time spent in markUntilBudgetExhausted compared to the slice budget
<10%: 105 times => 43% of calls spend very few time in sweep-marking. Mostly <0.1 ms
70~100%: 114 times => 47% of the calls will spend more than 70% of the slice budget

Here I compare the time to the slice duration and the slice budget, because sometimes the slice duration runs longer than the budget.

A: total time spent in markUntilBudgetExhausted (in performSweepActions): 1016 ms
B: total time duration (accumulated slice duration if markUntilBudgetExhausted runs in the slice): 3066 ms
C: total budget (accumulated budget if markUntilBudgetExhausted runs in the slice): 1967

A/B =>33%
A/C =>51%

And I found in this sample B is much larger than C is because in some slices, endSweepingSweepGroup uses more duration than budget,
sometimes it only has 5ms budget but ran 128ms.

endSweepingSweepGroup
120209751.319: begin: sweep.finalize_end
120209759.289: end: sweep.finalize_end duration=0.007970
120211508.344: begin: sweep
120211515.017: begin: sweep.destroy
120211707.174: end: sweep.destroy duration=0.192045
120211716.339: begin: sweep.finalize_end
120211750.045: end: sweep.finalize_end duration=0.033690
120211759.054: end: sweep duration=0.250515
120211765.813: begin: wait_background_thread
120291450.570: end: wait_background_thread duration=79.684458
120291469.723: begin: sweep
120291474.054: begin: sweep.destroy
120291479.683: end: sweep.destroy duration=0.005607
120291484.757: end: sweep duration=0.014501
120291489.013: begin: decommit
120291543.940: end: decommit duration=0.054879
120291548.838: begin: wait_background_thread
120322441.842: end: wait_background_thread duration=30.892579

Comment 6

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 1: SweepMarkTask.

Comment 7

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 7: disable AutoPhase when running on GCParallelTask.

Comment 8

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 2: data structures sharing.

Comment 9

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 4: check CanUseExtraThreads() if we can launch a thread.

For some tests multi-threading is disable.

Comment 10

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 6: join task when abortSweepAfterCurrentGroup is true.

abortSweepAfterCurrentGroup will reset the zone GCState to NoGC,
meanwhile the SweepMarkingTask is still marking, and will trigger
assertion in AssertShouldMarkInZone.

Comment 11

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 6: end current GC slice once GCMarker returns Yield.

Comment 12

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Comment on attachment 9090745 [details]
Bug 1564136 - Part 7: disable AutoPhase when running on GCParallelTask.

I forgot to explain this in the commit message.
I disable it because the currentPhase() in Statistics cannot handle phase stacks for multi-threads.
https://searchfox.org/mozilla-central/rev/e5327b05c822cdac24e233afa37d72c0552dbbaf/js/src/gc/Statistics.cpp#156

Comment 13

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Currently there are still some assertions in QuantumRender, I'll trying to fix those. Otherwise it's all green on Linux64.
And I haven't done the assert-only-1-thread-is-marking as Jonco suggested me before, will finish this in next round.

Comment 14

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 4: AutoSetThreadIsMarking

Comment 15

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 5: use TlsContext.get() in UnmarkGrayGCThing.

Comment 16

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 3: update assertions.

Comment 17

[BugBot [:suhaib / :marco/ :calixte]]

There are some r+ patches which didn't land and no activity in this bug for 2 weeks.
:allstars.chh, could you have a look please?
For more information, please visit auto_nag documentation.

Comment 18

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

there are still some patches coming soon
(In reply to Release mgmt bot [:sylvestre / :calixte / :marco for bugbug] from comment #17)

There are some r+ patches which didn't land and no activity in this bug for 2 weeks.
:allstars.chh, could you have a look please?
For more information, please visit auto_nag documentation.

Comment 19

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 8: call joinTask for recordParallelTimes.

Comment 20

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

Attachment: Bug 1564136 - Part 9: relax assertion with gcMarking in CheckIsMarkedThing.

Comment 21

[Yoshi Cheng-Hao Huang [:allstars.chh][:allstarschh][:yoshi]]

full try:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=539f773bf6f9d79907f7fdbba558514830b04ded

perfherder
https://treeherder.mozilla.org/perf.html#/compare?originalProject=try&newProject=try&newRevision=f8cb668be11f9f17a0cdbbd0c323a9ede6f7b11b&originalRevision=4be533cd9e6187157a3fe3544b68bd289c63a3fd

This week is soft freeze, so I will land this next week.

Comment 22

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/e9b1077e6b4a
Part 1: SweepMarkTask. r=jonco
https://hg.mozilla.org/integration/autoland/rev/4f90ac7e07e2
Part 2: data structures sharing. r=jonco
https://hg.mozilla.org/integration/autoland/rev/0346261fa958
Part 3: update assertions. r=jonco
https://hg.mozilla.org/integration/autoland/rev/f7e13423fb51
Part 4: AutoSetThreadIsMarking r=jonco
https://hg.mozilla.org/integration/autoland/rev/3c1e56d2db4d
Part 5: use TlsContext.get() in UnmarkGrayGCThing. r=jonco
https://hg.mozilla.org/integration/autoland/rev/22228e730a79
Part 6: join task when abortSweepAfterCurrentGroup is true. r=jonco
https://hg.mozilla.org/integration/autoland/rev/1fe5050eb279
Part 7: disable AutoPhase when running on GCParallelTask. r=jonco
https://hg.mozilla.org/integration/autoland/rev/a15e0a7fb30b
Part 8: call joinTask for recordParallelTimes. r=jonco
https://hg.mozilla.org/integration/autoland/rev/fa1d78394a96
Part 9: relax assertion with gcMarking in CheckIsMarkedThing. r=jonco

Comment 23

[Natalia Csoregi [:nataliaCs]]

https://hg.mozilla.org/mozilla-central/rev/e9b1077e6b4a
https://hg.mozilla.org/mozilla-central/rev/4f90ac7e07e2
https://hg.mozilla.org/mozilla-central/rev/0346261fa958
https://hg.mozilla.org/mozilla-central/rev/f7e13423fb51
https://hg.mozilla.org/mozilla-central/rev/3c1e56d2db4d
https://hg.mozilla.org/mozilla-central/rev/22228e730a79
https://hg.mozilla.org/mozilla-central/rev/1fe5050eb279
https://hg.mozilla.org/mozilla-central/rev/a15e0a7fb30b
https://hg.mozilla.org/mozilla-central/rev/fa1d78394a96