Immediatelly promote marked objects

Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger does not care about MarkCompact's mark bits. When an object is alive and marked, and at least one scavenge happens during incremental marking, the object will be copied once to the other semispace in the new_space, and then once to the old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure marked objects are scavenged, all marked objects will survive therefore there will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress, and the object is marked, we promote it unconditionally.

BUG=
LOG=no

Committed: https://crrev.com/dc78e0d4d7f8e67d99165ee4fc5cc118e1be2a9f
Cr-Commit-Position: refs/heads/master@{#36643}

[Marcel Hlopko, 2016-05-24 10:46:48]

Description was changed from

==========
Immediatelly promote marked objects

BUG=
LOG=no
==========

to

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion.txt:
    samples:    25
    average: 18276.68  -1.40
    median:  18244.00  -1.71
    stddev:    231.35  +0.20
    minimum: 17789     -1.09
    maximum: 18723     -1.15
    CI 95%:  18181.18 to 18372.18

BUG=
LOG=no
==========

[Marcel Hlopko, 2016-05-24 10:46:48]

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

[Marcel Hlopko, 2016-05-24 10:54:06]

Description was changed from

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion.txt:
    samples:    25
    average: 18276.68  -1.40
    median:  18244.00  -1.71
    stddev:    231.35  +0.20
    minimum: 17789     -1.09
    maximum: 18723     -1.15
    CI 95%:  18181.18 to 18372.18

BUG=
LOG=no
==========

to

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion_real.txt:
    samples:    25
    average: 18318.60  -1.17
    median:  18322.00  -1.29
    stddev:    235.24  +1.88
    minimum: 17826     -0.88
    maximum: 18826     -0.61
    CI 95%:  18221.50 to 18415.70

BUG=
LOG=no
==========

[Marcel Hlopko, 2016-05-24 10:54:26]

Description was changed from

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion_real.txt:
    samples:    25
    average: 18318.60  -1.17
    median:  18322.00  -1.29
    stddev:    235.24  +1.88
    minimum: 17826     -0.88
    maximum: 18826     -0.61
    CI 95%:  18221.50 to 18415.70

BUG=
LOG=no
==========

to

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion.txt:
    samples:    25
    average: 18318.60  -1.17
    median:  18322.00  -1.29
    stddev:    235.24  +1.88
    minimum: 17826     -0.88
    maximum: 18826     -0.61
    CI 95%:  18221.50 to 18415.70

BUG=
LOG=no
==========

[Marcel Hlopko, 2016-05-24 10:55:04]

Ptal.

[Michael Lippautz, 2016-05-24 11:54:51]

Can we get a cctest for this one?

https://codereview.chromium.org/2005173003/diff/20001/src/heap/heap-inl.h
File src/heap/heap-inl.h (right):

https://codereview.chromium.org/2005173003/diff/20001/src/heap/heap-inl.h#new...
src/heap/heap-inl.h:401: if (marks_handling == TRANSFER_MARKS) {
TRANSFER_MARKS is a confusing name for this one as we don't actually transfer
the marks but rather consider them when deciding whether to promote or not.

Maybe have a separate enum and call this one PROMOTE_MARKED?

[Marcel Hlopko, 2016-05-24 12:47:42]

As discussed offline, I've rewritten the code to use PromotionMode and runtime
arguments. The performance impact is noticeable:

Splay-octane2.1(Score)
  baseline:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  template_version:
    samples:    25
    average: 18318.60  -1.17
    median:  18322.00  -1.29
    stddev:    235.24  +1.88
    minimum: 17826     -0.88
    maximum: 18826     -0.61
    CI 95%:  18221.50 to 18415.70
  promotion_mode_version:
    samples:    25
    average: 18483.48  -0.28
    median:  18421.00  -0.75
    stddev:    288.98 +25.16
    minimum: 17826     -0.88
    maximum: 18910     -0.16
    CI 95%:  18364.19 to 18602.77

[Marcel Hlopko, 2016-05-24 16:04:03]

Description was changed from

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally. With this cl, we
observe 1% improvement on the splay benchmark:

Splay-octane2.1(Score)
  baseline.txt:
    samples:    25
    average: 18535.92 base
    median:  18561.00 base
    stddev:    230.89 base
    minimum: 17985    base
    maximum: 18941    base
    CI 95%:  18440.61 to 18631.23
  force_promotion.txt:
    samples:    25
    average: 18318.60  -1.17
    median:  18322.00  -1.29
    stddev:    235.24  +1.88
    minimum: 17826     -0.88
    maximum: 18826     -0.61
    CI 95%:  18221.50 to 18415.70

BUG=
LOG=no
==========

to

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally.

BUG=
LOG=no
==========

[ulan, 2016-05-24 16:41:59]

Looking good.

https://codereview.chromium.org/2005173003/diff/40001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/40001/src/heap/scavenger-inl....
src/heap/scavenger-inl.h:42: Heap* heap, Address slot_address, PromotionMode
promotion_mode) {
Callers of this function should be changed too.

Instead of DEFAULT_PROMOTION we need to pass PROMOTE_MARKED or DEFAULT_PROMOTION
depending on incremental marking state.

[Marcel Hlopko, 2016-05-24 17:16:13]

I addressed the comments. Ptaal :)

[Hannes Payer (out of office), 2016-05-25 05:35:46]

I like it. Just one nit.

Moreover, could you run the try perf jobs? tools/try_perf.py sunspider jetstream
octane kraken_orig

https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h
File src/heap/heap-inl.h (right):

https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h#new...
src/heap/heap-inl.h:404: bool Heap::ShouldBePromoted(Address old_address, int
object_size,
How about templatizing this function based on mode?

[ulan, 2016-05-25 08:24:09]

https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h
File src/heap/heap-inl.h (right):

https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h#new...
src/heap/heap-inl.h:404: bool Heap::ShouldBePromoted(Address old_address, int
object_size,
On 2016/05/25 05:35:46, Hannes Payer wrote:
> How about templatizing this function based on mode?

The callers would have to check the mode at runtime and dispatch to correct
version of ShouldBePromoted. IMO we will not win much performance.

An alternative would be to templatize all the way up.

[Marcel Hlopko, 2016-05-25 08:30:47]

On 2016/05/25 at 08:24:09, ulan wrote:
> https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h
> File src/heap/heap-inl.h (right):
> 
>
https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h#new...
> src/heap/heap-inl.h:404: bool Heap::ShouldBePromoted(Address old_address, int
object_size,
> On 2016/05/25 05:35:46, Hannes Payer wrote:
> > How about templatizing this function based on mode?
> 
> The callers would have to check the mode at runtime and dispatch to correct
version of ShouldBePromoted. IMO we will not win much performance.
> 
> An alternative would be to templatize all the way up.

The result will be that ScavengingVisitor will have to have 3rd template
parameter, then Scavenger::ScavengeObject, Scavenger::CheckAndScavengeObject,
and Scavenger::ScavengeObjectSlow will have to be templatized, and RememberedSet
iteration during scavenging in heap.cc will have to dispatch at runtime. Wdyt
Hannes?

[Hannes Payer (out of office), 2016-05-25 19:19:17]

On 2016/05/25 08:30:47, Marcel Hlopko wrote:
> On 2016/05/25 at 08:24:09, ulan wrote:
> > https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h
> > File src/heap/heap-inl.h (right):
> > 
> >
>
https://codereview.chromium.org/2005173003/diff/80001/src/heap/heap-inl.h#new...
> > src/heap/heap-inl.h:404: bool Heap::ShouldBePromoted(Address old_address,
int
> object_size,
> > On 2016/05/25 05:35:46, Hannes Payer wrote:
> > > How about templatizing this function based on mode?
> > 
> > The callers would have to check the mode at runtime and dispatch to correct
> version of ShouldBePromoted. IMO we will not win much performance.
> > 
> > An alternative would be to templatize all the way up.
> 
> The result will be that ScavengingVisitor will have to have 3rd template
> parameter, then Scavenger::ScavengeObject, Scavenger::CheckAndScavengeObject,
> and Scavenger::ScavengeObjectSlow will have to be templatized, and
RememberedSet
> iteration during scavenging in heap.cc will have to dispatch at runtime. Wdyt
> Hannes?

Let's try.

Performance on Splay seems to regress. We should have a look.

[Marcel Hlopko, 2016-05-30 13:54:12]

I now use PromotionMode as template parameter. Wdyt?

[ulan, 2016-05-30 14:07:28]

https://codereview.chromium.org/2005173003/diff/120001/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/2005173003/diff/120001/src/heap/heap.h#newcod...
src/heap/heap.h:779: inline PromotionMode CurrentPromotionMode();
Not used anymore?

https://codereview.chromium.org/2005173003/diff/120001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/120001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:49:
scavenger->scavenging_visitors_table_.GetVisitor(map)(map, p, object);
I think here we are losing the FORCE_PROMOTION mode. 

The scavenging visitors table is either DEFAULT_PROMOTION or PROMOTE_MARKED.

[Marcel Hlopko, 2016-05-30 14:41:29]

Uploaded cl with FORCE_PROMOTION removed. Still, I'm worried about the duplicity
Ulan found:

Scavenger::SelectScavengingVisitorsTable tests whether we are marking and picks
correct visitor (with promotion_mode built in)
-and-
Heap::Scavenge tests whether we are marking and then passes promotion_mode down.


The calls go like this:

Scavenge() -> RememberedSet:Iterate -> CheckAndScavengeObject -> ScavengeObject
-> ScavengeObjectSlow -> scavenger.scavenging_visitors_table_.GetVisitor

It is possible to introduce a bug where we start with one promotion mode (set in
Heap::Scavenge) and end up with different (set in
SelectScavengingVisitorsTable).

Does this worry you too? :)

I could templatize SelectScavengingVisitorsTable to get promotion_mode as
parameter, but then I have to move it to scavenger-inl.h, together with
ScavenginVisitors.

Wdyt?

[ulan, 2016-05-30 16:09:06]

A test that checks promotion during incremental marking would catch the
discrepancy between the visitor table and object visitor.

Few suggestions about detemplatizing big functions, where I think template
doesn't buy much.

https://codereview.chromium.org/2005173003/diff/140001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/2005173003/diff/140001/src/heap/heap.cc#newco...
src/heap/heap.cc:1611: void Heap::Scavenge() {
Wdyt about detemplatizing this functoin and making the promotion_mode a local
variable?

https://codereview.chromium.org/2005173003/diff/140001/src/heap/heap.cc#newco...
src/heap/heap.cc:1664: ScavengeVisitor<promotion_mode> scavenge_visitor(this);
If we make the promotion mode a field of ScavengeVisitor, then we can
detemplatize this function.

https://codereview.chromium.org/2005173003/diff/140001/src/heap/heap.cc#newco...
src/heap/heap.cc:1928: Address new_space_front) {
How about making promotion_mode a parameter of the function?

https://codereview.chromium.org/2005173003/diff/140001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/140001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:42: template <PromotionMode promotion_mode>
Since the promotion_mode is not used, I would drop it here and in all callers.

[Marcel Hlopko, 2016-05-31 05:45:04]

Added tests, addressed comments. Ptal :)

[ulan, 2016-06-01 09:09:40]

https://codereview.chromium.org/2005173003/diff/160001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/160001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:42: template <PromotionMode promotion_mode>
promotion_mode is not used in this function, so you could remove it and also
remove the mode from callers.

[Marcel Hlopko, 2016-06-01 09:19:50]

Addresssed comments.

https://codereview.chromium.org/2005173003/diff/160001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/160001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:42: template <PromotionMode promotion_mode>
Aah sorry for not noticing this. Done.

[Marcel Hlopko, 2016-06-01 09:42:48]

Another attempt on cleaning up my mess :) Ptal :)

[ulan, 2016-06-01 11:53:35]

LGTM with two comments.

https://codereview.chromium.org/2005173003/diff/240001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/2005173003/diff/240001/src/heap/heap.cc#newco...
src/heap/heap.cc:1674: this, [this, promotion_mode](Address addr) {
promotion mode is not needed here and below in IterateTyped.

https://codereview.chromium.org/2005173003/diff/240001/src/heap/scavenger-inl.h
File src/heap/scavenger-inl.h (right):

https://codereview.chromium.org/2005173003/diff/240001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:41: Heap* heap, Address slot_address, PromotionMode
promotion_mode) {
We can remove the mode now

https://codereview.chromium.org/2005173003/diff/240001/src/heap/scavenger-inl...
src/heap/scavenger-inl.h:48: if (promotion_mode == PROMOTE_MARKED) {
No need for this case distinction :)

[Marcel Hlopko, 2016-06-01 12:03:54]

The CQ bit was checked by hlopko@chromium.org

[Marcel Hlopko, 2016-06-01 12:03:55]

The patchset sent to the CQ was uploaded after l-g-t-m from ulan@chromium.org
Link to the patchset: https://codereview.chromium.org/2005173003/#ps280001
(title: "Really should concentrate more")

[commit-bot: I haz the power, 2016-06-01 12:04:01]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2005173003/280001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2005173003/280001

[commit-bot: I haz the power, 2016-06-01 12:32:13]

Committed patchset #15 (id:280001)

[commit-bot: I haz the power, 2016-06-01 12:32:27]

Description was changed from

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally.

BUG=
LOG=no
==========

to

==========
Immediately promote marked objects during scavenge

It happens that a scavenger runs during incremental marking. Currently scavenger
does not care about MarkCompact's mark bits. When an object is alive and marked,
and at least one scavenge happens during incremental marking, the object will be
copied once to the other semispace in the new_space, and then once to the
old_space. For surviving objects this is useless extra work.

In our current attempts (https://codereview.chromium.org/1988623002) to ensure
marked objects are scavenged, all marked objects will survive therefore there
will be many objects which will be uselessly copied.

This cl modifies our promotion logic so when incremental marking is in progress,
and the object is marked, we promote it unconditionally.

BUG=
LOG=no

Committed: https://crrev.com/dc78e0d4d7f8e67d99165ee4fc5cc118e1be2a9f
Cr-Commit-Position: refs/heads/master@{#36643}
==========

[commit-bot: I haz the power, 2016-06-01 12:32:28]

Patchset 15 (id:??) landed as
https://crrev.com/dc78e0d4d7f8e67d99165ee4fc5cc118e1be2a9f
Cr-Commit-Position: refs/heads/master@{#36643}