Parallel marking.

Parallel marking.

Provide both Unsync/SyncMarkingVisitor, where the latter uses CAS to acquire the header bits, guaranteeing that each object is processed by exactly one task when parallel tasks are running.

UnsyncMarkingVisitor preserves the old behavior w.r.t. synchronization, and is used when num_tasks is 0.

Split root set into two parts, and give them to separate tasks when possible.

Add basic logging to help investigate how well work is distributed. (Marking stack block size is currently 64.)

BUG=
R=iposva@google.com

Committed: https://github.com/dart-lang/sdk/commit/32798855969e4ffda8f628bc85556732dae1d336

[koda, 2015-09-17 22:14:53]

koda@google.com changed reviewers:
+ iposva@google.com

[Ivan Posva, 2015-10-01 11:22:44]

First comments. I still need to understand the barrier use during marking a bit
better.

-Ivan

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:255: delay_set_->Insert(raw_weak);
There is a race here:
- This thread (A) observes the mark bit on the key unset, successfully sets the
watch bit. Alternatively this thread observes the watch bit set.
- Thread B marks the key object and observes the watch bit set.
- Thread B proceeds to grab (under lock) the registered weaks for the key and
visits them, removing them from the delay set in the process.
- Thread A succeeds in adding the weak to the delay set.
...

There are also couple of assertions missing at least in the DelaySet class, such
as ensuring that the cleared properties do indeed point to unmarked keys.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:276: // TODO(koda): Independent of sync; move out.
Please do this in this CL. The class can be local to this .cc file.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:365: // new/smi check.
Comment on wrong line. This is the IsMarked check.

Regarding the comment: In case of new you will need to do special handling which
you do not need for smi. I was wondering how you would like to combine them
without adding an extra branch in the smi case?

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:429: typedef MarkingVisitorBase<false>
UnsyncMarkingVisitor;
What is the performance impact of making the sync a property of the visitor
instead of duplicating the code?

[Ivan Posva, 2015-10-01 17:02:55]

Additional comments.

-Ivan

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:401: ASSERT(p != NULL);  // TODO(koda): Why?
Because the pointer to the address we are visiting allows us to get a distance
from the object start. At some point we might want to store exact addresses in
store buffers for locations far enough from the header, so that we do not need
to walk big objects only to find the single new reference in the last word
during scavenge. I don't think this is a problem though currently.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:660: // Phase 2: Drain marking stack from tasks.
Shouldn't phase 2 start after a barrier?

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:662: static_cast<uword>(num_tasks_));
This looks like you want to add a LoadRelaxed(intrptr_t*) as well.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:663: barrier_->Sync();
Is this barrier really necessary? The tasks that do not visit roots can start
draining the marking stacks.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:670: while (marking_stack_->IsEmpty() &&
How do you plan to fix the busy looping?

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:675: // I saw some work; get busy and compete for it.
Style comment: It is hard to read these blocks of contiguous comments and one
line statements. Maybe visually breaking them with new lines?

[koda, 2015-10-01 20:30:11]

Addressed comments; will now investigate performance impact of sync_ flag rather
than template.

Meanwhile, PTAL.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:255: delay_set_->Insert(raw_weak);
On 2015/10/01 11:22:44, Ivan Posva wrote:
> There is a race here:
> - This thread (A) observes the mark bit on the key unset, successfully sets
the
> watch bit. Alternatively this thread observes the watch bit set.
> - Thread B marks the key object and observes the watch bit set.
> - Thread B proceeds to grab (under lock) the registered weaks for the key and
> visits them, removing them from the delay set in the process.
> - Thread A succeeds in adding the weak to the delay set.
> ...
> 
> There are also couple of assertions missing at least in the DelaySet class,
such
> as ensuring that the cleared properties do indeed point to unmarked keys.

Good catch; fixed by re-checking mark bit after acquiring lock for insertion.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:276: // TODO(koda): Independent of sync; move out.
On 2015/10/01 11:22:44, Ivan Posva wrote:
> Please do this in this CL. The class can be local to this .cc file.

Done.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:365: // new/smi check.
On 2015/10/01 11:22:44, Ivan Posva wrote:
> Comment on wrong line. This is the IsMarked check.
> 
> Regarding the comment: In case of new you will need to do special handling
which
> you do not need for smi. I was wondering how you would like to combine them
> without adding an extra branch in the smi case?

Moved and expanded comment to clarify: The total number of branch instructions
generated would not change, but the code path taken to identify a marked old
object would involve fewer instructions.

It's not clear whether it's a win, but it might be worth investigating in the
future.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:401: ASSERT(p != NULL);  // TODO(koda): Why?
On 2015/10/01 17:02:54, Ivan Posva wrote:
> Because the pointer to the address we are visiting allows us to get a distance
> from the object start. At some point we might want to store exact addresses in
> store buffers for locations far enough from the header, so that we do not need
> to walk big objects only to find the single new reference in the last word
> during scavenge. I don't think this is a problem though currently.

Thanks for clarifying; added comment.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:429: typedef MarkingVisitorBase<false>
UnsyncMarkingVisitor;
On 2015/10/01 11:22:44, Ivan Posva wrote:
> What is the performance impact of making the sync a property of the visitor
> instead of duplicating the code?

I will investigate and update this thread.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:660: // Phase 2: Drain marking stack from tasks.
On 2015/10/01 17:02:54, Ivan Posva wrote:
> Shouldn't phase 2 start after a barrier?

Obsolete after combining the phases.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:662: static_cast<uword>(num_tasks_));
On 2015/10/01 17:02:54, Ivan Posva wrote:
> This looks like you want to add a LoadRelaxed(intrptr_t*) as well.

Obsolete after combining the phases.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:663: barrier_->Sync();
On 2015/10/01 17:02:54, Ivan Posva wrote:
> Is this barrier really necessary? The tasks that do not visit roots can start
> draining the marking stacks.

It was necessary to support the ASSERT in DrainMarkingStack that the classes
have already been marked. However, the added value of that assertion is very
limited.

Combined the phases and removed the ASSERT.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:670: while (marking_stack_->IsEmpty() &&
On 2015/10/01 17:02:55, Ivan Posva wrote:
> How do you plan to fix the busy looping?

We can replace the mutex inside marking_stack_ with a monitor that is notified
whenever more work is added.

https://codereview.chromium.org/1351453008/diff/140001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:675: // I saw some work; get busy and compete for it.
On 2015/10/01 17:02:55, Ivan Posva wrote:
> Style comment: It is hard to read these blocks of contiguous comments and one
> line statements. Maybe visually breaking them with new lines?

Done.

[koda, 2015-10-01 23:13:28]

Local performance tests suggest template version gives ~4% less total time spent
in GC (i.e., including scavenges) on SplayHarderIterations for ia32, both with
marker_tasks=0 and marker_tasks=2. Template does not seem to noticeably increase
stripped binary size (somewhat surprising).

[koda, 2015-10-02 20:46:23]

On 2015/10/01 23:13:28, koda wrote:
> Local performance tests suggest template version gives ~4% less total time
spent
> in GC (i.e., including scavenges) on SplayHarderIterations for ia32, both with
> marker_tasks=0 and marker_tasks=2. Template does not seem to noticeably
increase
> stripped binary size (somewhat surprising).

As agreed, added comment re. busy waiting; PTAL.

[Ivan Posva, 2015-10-08 19:56:12]

LGTM with comments.

-Ivan

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:43: // success, and false if the key is not white.
Please also note the precondition that this thread did successfully add the
watched bit atomically, which means the mark bit cannot be set without observing
the watched bit. This information is crucial to understanding how this algorithm
works.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:151: class WorkList : public ValueObject {
Thanks!

Maybe rename to MarkerWorkList?

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:335: void AbandonWork() {
Please document where this is used.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:511: if (slice_index == 0 || num_slices <= 1) {
()

[koda, 2015-10-08 21:32:08]

Submitting after final tests and sync.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:43: // success, and false if the key is not white.
On 2015/10/08 19:56:12, Ivan Posva wrote:
> Please also note the precondition that this thread did successfully add the
> watched bit atomically, which means the mark bit cannot be set without
observing
> the watched bit. This information is crucial to understanding how this
algorithm
> works.

Done.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:151: class WorkList : public ValueObject {
On 2015/10/08 19:56:12, Ivan Posva wrote:
> Thanks!
> 
> Maybe rename to MarkerWorkList?

Done.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:335: void AbandonWork() {
On 2015/10/08 19:56:12, Ivan Posva wrote:
> Please document where this is used.

Removed.

https://codereview.chromium.org/1351453008/diff/180001/runtime/vm/gc_marker.c...
runtime/vm/gc_marker.cc:511: if (slice_index == 0 || num_slices <= 1) {
On 2015/10/08 19:56:12, Ivan Posva wrote:
> ()

Done x2.

[koda, 2015-10-08 22:02:01]

Committed patchset #11 (id:200001) manually as
32798855969e4ffda8f628bc85556732dae1d336 (presubmit successful).