[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188
Committed: https://crrev.com/4f161eac0b1f1b76ef9cd36de5a6dce3c9002a71
Cr-Commit-Position: refs/heads/master@{#440074}

[Michael Lippautz, 2016-12-20 14:08:26]

Description was changed from

==========
[wrapper-tracing] Optimize marking

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in marking deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

BUG=
==========

[Michael Lippautz, 2016-12-20 14:11:48]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in marking deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in marking deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Some performance measurements for some known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

[Michael Lippautz, 2016-12-20 14:54:35]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in marking deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Some performance measurements for some known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Some performance measurements for some known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

[Michael Lippautz, 2016-12-20 14:56:40]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference is
that we don't make grey exlicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Some performance measurements for some known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

[Michael Lippautz, 2016-12-20 15:03:26]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
that ~50% of all marking deque pushes were duplicates.

BUG=
==========

[Michael Lippautz, 2016-12-20 15:03:27]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: 

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
that ~50% of all marking deque pushes were duplicates.

BUG=
==========

[Michael Lippautz, 2016-12-20 15:05:42]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

There's currently no need to query for grey as we don't need a path to recover
from e.g. a marking deque overflow. 

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
+17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
that ~50% of all marking deque pushes were duplicates.

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=
==========

[Michael Lippautz, 2016-12-20 15:06:10]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

[Michael Lippautz, 2016-12-20 15:10:05]

mlippautz@chromium.org changed reviewers:
+ haraken@chromium.org, hpayer@chromium.org, ulan@chromium.org

[Michael Lippautz, 2016-12-20 15:10:31]

PTAL

Also added Ulan/Hannes for further GC expertise.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/GarbageCollected.h (right):

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/GarbageCollected.h:116: void
adjustAndFullyMarkAndTraceWrapper(const WrapperVisitor* visitor)        \
Ideally we could use covariant return types here. E.g. have something like
  TYPE* castToBase() override;
which would be the only method needed here.

Since we don't have a common supertype though (GarbageCollected<A> !=
GarbageCollected<B>) I do not (yet) see how to do it.

[Michael Lippautz, 2016-12-20 15:11:08]

Forgot to mention: This is to be landed after the flag switch, to properly track
improvements.

[Hannes Payer (out of office), 2016-12-20 15:30:34]

lgtm

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h
(right):

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:144: // be
in a non-construction state.
Also leave a comment that this code path may still result in duplicates on the
marking deque.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:146:
->pushToMarkingDeque(TraceTrait<T>::fullyMarkAndTraceWrapper,
I would propose to rename to:
- MarkAndTraceWrapper
- TraceMarkedWrapper or TraceWrapper (since it should imply that it is already
marked. Otherwise we would not trace.)

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/TraceTraits.h (right):

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:51: const T* t) {
DCHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:57: static void
markWrapperHeaderOnly(const WrapperVisitor* visitor, const T* t) {
DCHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:62:
CHECK(heapObjectHeader(t)->isWrapperHeaderMarked());
s/CHECK/DCHECK/

[ulan, 2016-12-20 15:35:43]

lgtm, maybe also add a check to pushMarkingDeque that the object header is
marked.

[Michael Lippautz, 2016-12-20 15:57:23]

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h
(right):

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:144: // be
in a non-construction state.
On 2016/12/20 15:30:33, Hannes Payer wrote:
> Also leave a comment that this code path may still result in duplicates on the
> marking deque.

Done.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:146:
->pushToMarkingDeque(TraceTrait<T>::fullyMarkAndTraceWrapper,
On 2016/12/20 15:30:33, Hannes Payer wrote:
> I would propose to rename to:
> - MarkAndTraceWrapper
> - TraceMarkedWrapper or TraceWrapper (since it should imply that it is already
> marked. Otherwise we would not trace.)

Tried to address the naming and also added another comments where it breaks for
historical reasons.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/TraceTraits.h (right):

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:51: const T* t) {
On 2016/12/20 15:30:33, Hannes Payer wrote:
> DCHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());

This one cannot be done, as it is used when we cannot eagerly process an object
in mixin construction. It has to stay conditional.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:57: static void
markWrapperHeaderOnly(const WrapperVisitor* visitor, const T* t) {
On 2016/12/20 15:30:33, Hannes Payer wrote:
> DCHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());

Done.

https://codereview.chromium.org/2585433003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:62:
CHECK(heapObjectHeader(t)->isWrapperHeaderMarked());
On 2016/12/20 15:30:34, Hannes Payer wrote:
> s/CHECK/DCHECK/

Most of the assertions will be CHECKs until this is stabilized a bit more.

[Michael Lippautz, 2016-12-20 15:58:10]

On 2016/12/20 15:35:43, ulan wrote:
> lgtm, maybe also add a check to pushMarkingDeque that the object header is
> marked.

We still have the mixin path for pushing white objects on the marking deque
(bottom of ScriptWrappableVisitor::writeBarrier).

[Michael Lippautz, 2016-12-20 16:47:24]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking. The difference to
regular GC literature is that we don't make grey explicit.

The colors are represented by the tuple (color, in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

to

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

[haraken, 2016-12-21 01:38:37]

LGTM

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h
(right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:145:
->pushToMarkingDeque(TraceTrait<T>::markAndTraceWrapper,

I don't have any strong opinion about the naming, but if you want to be
consistent with oilpan:

  markAndTraceWrapper => markWrapper
  markWrapperHeaderOnly => markNoTracing (Oilpan already have the notion)

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/TraceTraits.h (right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:57:
CHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());

Should this be a DCHECK? This code is on a performance-sensitive path.

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:61:
CHECK(heapObjectHeader(t)->isWrapperHeaderMarked());

Ditto.

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/WrapperVisitor.h (right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/WrapperVisitor.h:109:
pushToMarkingDeque(TraceTrait<T>::traceMarkedWrapper,

Why can't we simply use markAndTraceWrapper?

[Michael Lippautz, 2016-12-21 09:31:08]

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h
(right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:145:
->pushToMarkingDeque(TraceTrait<T>::markAndTraceWrapper,
On 2016/12/21 01:38:37, haraken wrote:
> 
> I don't have any strong opinion about the naming, but if you want to be
> consistent with oilpan:
> 
>   markAndTraceWrapper => markWrapper
>   markWrapperHeaderOnly => markNoTracing (Oilpan already have the notion)

I realize I am diverging a bit with oilpan, but I'd like to name them:
- markAndTraceWrapper
- markWrapperNoTracing 
- traceMarkedWrapper

These names describe exactly what is happening :)

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/TraceTraits.h (right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:57:
CHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());
On 2016/12/21 01:38:37, haraken wrote:
> 
> Should this be a DCHECK? This code is on a performance-sensitive path.

Initially wanted to have them for the first couple Canaries but are right as
this seems to heavy. => DCHECK.

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/TraceTraits.h:61:
CHECK(heapObjectHeader(t)->isWrapperHeaderMarked());
On 2016/12/21 01:38:37, haraken wrote:
> 
> Ditto.

Done.

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/WrapperVisitor.h (right):

https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/WrapperVisitor.h:109:
pushToMarkingDeque(TraceTrait<T>::traceMarkedWrapper,
On 2016/12/21 01:38:37, haraken wrote:
> 
> Why can't we simply use markAndTraceWrapper?

We could but it would add duplicates to the marking deque. 

(1) Assume we have to objects on the deque: |A|B|
(2) Both have references to an object C, i.e, A->C, B->C.
(3) Now, when we process A, we leave the deque in a state |B|C|.
(4) After processing B, we have |C|C|.

With the eager marking we end up with |C| as we bail out the 2nd time we would
append it.

[Michael Lippautz, 2016-12-21 09:31:43]

The CQ bit was checked by mlippautz@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-12-21 09:31:55]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Michael Lippautz, 2016-12-21 09:40:47]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

[Michael Lippautz, 2016-12-21 09:40:47]

Description was changed from

==========
[wrapper-tracing] Optimize marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

[haraken, 2016-12-21 09:51:52]

On 2016/12/21 09:31:08, Michael Lippautz wrote:
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h
> (right):
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> third_party/WebKit/Source/bindings/core/v8/ScriptWrappableVisitor.h:145:
> ->pushToMarkingDeque(TraceTrait<T>::markAndTraceWrapper,
> On 2016/12/21 01:38:37, haraken wrote:
> > 
> > I don't have any strong opinion about the naming, but if you want to be
> > consistent with oilpan:
> > 
> >   markAndTraceWrapper => markWrapper
> >   markWrapperHeaderOnly => markNoTracing (Oilpan already have the notion)
> 
> I realize I am diverging a bit with oilpan, but I'd like to name them:
> - markAndTraceWrapper
> - markWrapperNoTracing 
> - traceMarkedWrapper
> 
> These names describe exactly what is happening :)
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/platform/heap/TraceTraits.h (right):
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> third_party/WebKit/Source/platform/heap/TraceTraits.h:57:
> CHECK(!heapObjectHeader(t)->isWrapperHeaderMarked());
> On 2016/12/21 01:38:37, haraken wrote:
> > 
> > Should this be a DCHECK? This code is on a performance-sensitive path.
> 
> Initially wanted to have them for the first couple Canaries but are right as
> this seems to heavy. => DCHECK.
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> third_party/WebKit/Source/platform/heap/TraceTraits.h:61:
> CHECK(heapObjectHeader(t)->isWrapperHeaderMarked());
> On 2016/12/21 01:38:37, haraken wrote:
> > 
> > Ditto.
> 
> Done.
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> File third_party/WebKit/Source/platform/heap/WrapperVisitor.h (right):
> 
>
https://codereview.chromium.org/2585433003/diff/40001/third_party/WebKit/Sour...
> third_party/WebKit/Source/platform/heap/WrapperVisitor.h:109:
> pushToMarkingDeque(TraceTrait<T>::traceMarkedWrapper,
> On 2016/12/21 01:38:37, haraken wrote:
> > 
> > Why can't we simply use markAndTraceWrapper?
> 
> We could but it would add duplicates to the marking deque. 
> 
> (1) Assume we have to objects on the deque: |A|B|
> (2) Both have references to an object C, i.e, A->C, B->C.
> (3) Now, when we process A, we leave the deque in a state |B|C|.
> (4) After processing B, we have |C|C|.
> 
> With the eager marking we end up with |C| as we bail out the 2nd time we would
> append it.

LGTM

[Michael Lippautz, 2016-12-21 10:54:50]

The CQ bit was checked by mlippautz@chromium.org

[Michael Lippautz, 2016-12-21 10:54:50]

The patchset sent to the CQ was uploaded after l-g-t-m from hpayer@chromium.org,
ulan@chromium.org, haraken@chromium.org
Link to the patchset: https://codereview.chromium.org/2585433003/#ps80001
(title: "Fix test case")

[commit-bot: I haz the power, 2016-12-21 10:55:07]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Michael Lippautz, 2016-12-21 11:39:48]

Description was changed from

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811
==========

[Michael Lippautz, 2016-12-21 11:42:47]

Description was changed from

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188
==========

[commit-bot: I haz the power, 2016-12-21 12:29:58]

CQ is committing da patch.

Bot data: {"patchset_id": 80001, "attempt_start_ts": 1482317690345610,
"parent_rev": "8ee72a3ca28823ca7f1e2b8f8fd7bf862720644a", "commit_rev":
"749e30ebaae4919871afbc02eb46d2754ad01c19"}

[commit-bot: I haz the power, 2016-12-21 12:30:29]

Description was changed from

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188

Review-Url: https://codereview.chromium.org/2585433003
==========

[commit-bot: I haz the power, 2016-12-21 12:30:31]

Committed patchset #5 (id:80001)

[commit-bot: I haz the power, 2016-12-21 12:32:46]

Description was changed from

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188

Review-Url: https://codereview.chromium.org/2585433003
==========

to

==========
[wrapper-tracing] Reduce marking overhead: Tri-color marking without 3 colors

This CL implements marking very similar to tri-color marking, with the
difference to standard GC literature being that the grey state is being made
explicit. The colors are logically represented by the tuple (color,
in_marking_deque):
- white: (0, false)
- grey: (1, true)
- black: (1, false)

This works because there is currently no need to query whether an object is grey
as we don't need a path to recover from e.g. a marking deque overflow.

Performance for known regressions:
- blink.perf_bindings structured-clone-long-string-serialize: -17% instead of
  +17%
- speedometer: Reducing marking deque pushes from 3.3M to 1.7M. This is means
  that ~50% of all marking deque pushes were duplicates.

BUG=chromium:468240, chromium:667811, chromium:669188

Committed: https://crrev.com/4f161eac0b1f1b76ef9cd36de5a6dce3c9002a71
Cr-Commit-Position: refs/heads/master@{#440074}
==========

[commit-bot: I haz the power, 2016-12-21 12:32:47]

Patchset 5 (id:??) landed as
https://crrev.com/4f161eac0b1f1b76ef9cd36de5a6dce3c9002a71
Cr-Commit-Position: refs/heads/master@{#440074}

[agrieve, 2016-12-21 19:59:51]

On 2016/12/21 12:32:47, commit-bot: I haz the power wrote:
> Patchset 5 (id:??) landed as
> https://crrev.com/4f161eac0b1f1b76ef9cd36de5a6dce3c9002a71
> Cr-Commit-Position: refs/heads/master@{#440074}

FYI - this added 20kb to libchrome.so on Android. No action required, just
wanted to annotate the commit with this fact (unless you can think of an obvious
way to reduce the overhead).
https://chromeperf.appspot.com/report?sid=a1a758ce61ac3a6d21c8ca8f5ea0a043a2a...

[Michael Lippautz, 2016-12-22 08:24:07]

On 2016/12/21 19:59:51, agrieve wrote:
> On 2016/12/21 12:32:47, commit-bot: I haz the power wrote:
> > Patchset 5 (id:??) landed as
> > https://crrev.com/4f161eac0b1f1b76ef9cd36de5a6dce3c9002a71
> > Cr-Commit-Position: refs/heads/master@{#440074}
> 
> FYI - this added 20kb to libchrome.so on Android. No action required, just
> wanted to annotate the commit with this fact (unless you can think of an
obvious
> way to reduce the overhead).
>
https://chromeperf.appspot.com/report?sid=a1a758ce61ac3a6d21c8ca8f5ea0a043a2a...

Thanks! https://codereview.chromium.org/2595053002/ should recover and even
reduce the overhead. Turns out we don't need those paths anymore. Cannot promise
for the long run though.