Bookkeeping for allocation site pretenuring

The goal is to discover the appropriate heap space for objects created in full
code. By the time we optimize the code, we'll be able to decide on new or old
space based on the number of surviving objects after one or more gcs.

The mechanism is a "memento" placed behind objects in the heap. It's currently
done for array and object literals, with plans to use mementos for constructed
objects as well (in a later CL).

The feature is behind the flag allocation_site_pretenuring, currently off.

R=hpayer@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=18104

[mvstanton, 2013-10-24 12:34:55]

Hi Hannes, Michael,
There are a few failing tests to investigate, but this is basically it.
Thx,
--Michael

[mvstanton, 2013-10-25 08:31:54]

Chopping this CL up into smaller ones, thx.

[mvstanton, 2013-11-20 15:39:29]

Hi Hannes,
PTAL, I've rebased the CL as dependent on another CL that adds the calculation
fields.
Thx,
--Michael

[Hannes Payer (out of office), 2013-11-21 20:52:24]

First round of comments, cool stuff!

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/flag-definiti...
File src/flag-definitions.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/flag-definiti...
src/flag-definitions.h:213: DEFINE_bool(allocation_site_pretenuring, true,
Should be set to false.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h
File src/heap-inl.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h#ne...
src/heap-inl.h:495: // Update state
Remove this comment.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h#ne...
src/heap-inl.h:502: object->GetIsolate()->heap()->allocation_mementos_found_++;
Do we still need this variable? We could just ask the allocation sites.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc
File src/heap.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:1557: if (!(casted->DecisionMade())) {
See the other comment about not enough allocation mementos created - here I
would stay in undecided mode.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:1566: }
Right now we do not support switching state which is OK. But let's add a TODO
here.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:4403: allocation_site->IncrementMementoCreateCount();
I am wondering if this counter is not only interesting for pretenuring but also
for other clients of allocation mementos.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h
File src/heap.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h#newcod...
src/heap.h:1460: // some extra work.
Ambiguous comment, can we be more precise here.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h#newcod...
src/heap.h:1464: void EnsureFromSpaceIsCommitted();
I did not find the reason why this method has to be public.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc#n...
src/hydrogen.cc:2256: // Increment create count
Beautify comment.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc#n...
src/hydrogen.cc:2268: store->SkipWriteBarrier();  // I am writing a smi
Move comment in extra line and make it nice.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h
File src/objects-inl.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h...
src/objects-inl.h:1400: double ratio = create_count > 0
We have to guard against the case where we just started emitting mementos before
a gc happend. In that state we cannot make a sane pretenuring decision.
Moreover, we do not want to pretenure non-interesting sites, i.e. sites that
just allocated one object. 

Let us add a constant. If the create count is smaller than this constant we
return false. A good value for that constant is hard to find, we have to look
into benchmarks for that but let us start with something reasonable like e.g.
kPretenureMinimumCreated = 100

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h...
src/objects-inl.h:1406: return ratio >= 0.60;
This should be a constant in allocation site called e.g. kPretenureRatio.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h#new...
src/objects.h:8110: static const int kZombie = 3;
Right now the state diagram (should) looks like that:
0 -> 1
0 -> 2
1 -> 3
2 -> 3
The 0 ->  3 transition is missing see my comments.
A follow up CL should add the 1 -> 2 and 2 -> 1 transitions.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h#new...
src/objects.h:8131: 
Can we have newlines between the methods?

[mvstanton, 2013-11-22 11:18:50]

Here you go Hannes, thx for the comments, they prompted a few bigger changes.
--Michael

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/flag-definiti...
File src/flag-definitions.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/flag-definiti...
src/flag-definitions.h:213: DEFINE_bool(allocation_site_pretenuring, true,
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Should be set to false.

Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h
File src/heap-inl.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h#ne...
src/heap-inl.h:495: // Update state
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Remove this comment.

Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap-inl.h#ne...
src/heap-inl.h:502: object->GetIsolate()->heap()->allocation_mementos_found_++;
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Do we still need this variable? We could just ask the allocation sites.

Done. Facilitated by moving the allocation site feedback digestion to the gc
epilogue.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc
File src/heap.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:1557: if (!(casted->DecisionMade())) {
On 2013/11/21 20:52:24, Hannes Payer wrote:
> See the other comment about not enough allocation mementos created - here I
> would stay in undecided mode.

I've simplified and encapsulated this code in a way that also respects a minimum
number of mementos found.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:1566: }
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Right now we do not support switching state which is OK. But let's add a TODO
> here.

Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.cc#newco...
src/heap.cc:4403: allocation_site->IncrementMementoCreateCount();
On 2013/11/21 20:52:24, Hannes Payer wrote:
> I am wondering if this counter is not only interesting for pretenuring but
also
> for other clients of allocation mementos.

Maybe so, but not yet. I like the idea of keeping all this infrastructure behind
the pretenuring flag for now, at least until there is another client or we can
get rid of the flag.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h
File src/heap.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h#newcod...
src/heap.h:1460: // some extra work.
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Ambiguous comment, can we be more precise here.

Thx, I renamed the method to UpdateAllocationSiteFeedback to clarify meaning.
I'll keep the comment there because it's the style of heap.h, but modify it a
bit.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/heap.h#newcod...
src/heap.h:1464: void EnsureFromSpaceIsCommitted();
On 2013/11/21 20:52:24, Hannes Payer wrote:
> I did not find the reason why this method has to be public.

Me neither! fixed.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc#n...
src/hydrogen.cc:2256: // Increment create count
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Beautify comment.

Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/hydrogen.cc#n...
src/hydrogen.cc:2268: store->SkipWriteBarrier();  // I am writing a smi
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Move comment in extra line and make it nice.

Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h
File src/objects-inl.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h...
src/objects-inl.h:1400: double ratio = create_count > 0
On 2013/11/21 20:52:24, Hannes Payer wrote:
> We have to guard against the case where we just started emitting mementos
before
> a gc happend. In that state we cannot make a sane pretenuring decision.
> Moreover, we do not want to pretenure non-interesting sites, i.e. sites that
> just allocated one object. 
> 
> Let us add a constant. If the create count is smaller than this constant we
> return false. A good value for that constant is hard to find, we have to look
> into benchmarks for that but let us start with something reasonable like e.g.
> kPretenureMinimumCreated = 100

Good advice. Done.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects-inl.h...
src/objects-inl.h:1406: return ratio >= 0.60;
On 2013/11/21 20:52:24, Hannes Payer wrote:
> This should be a constant in allocation site called e.g. kPretenureRatio.

Done. Awkwardly, it must be initialized in objects.cc because of the rules
around floating point constants.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h#new...
src/objects.h:8110: static const int kZombie = 3;
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Right now the state diagram (should) looks like that:
> 0 -> 1
> 0 -> 2
> 1 -> 3
> 2 -> 3
> The 0 ->  3 transition is missing see my comments.
> A follow up CL should add the 1 -> 2 and 2 -> 1 transitions.

Thx. I made these 4 state values into an enum to indicate grouping and because
of a compiler issue.

The new TODO in heap.cc talks about revisiting the decision for the 1->2 and
2->1 cases.

Finally, I think the zombie state is okay. But it's a strange concept so I added
a long comment right before IsZombie(), lets chat about that.

https://chromiumcodereview.appspot.com/40063002/diff/350001/src/objects.h#new...
src/objects.h:8131: 
On 2013/11/21 20:52:24, Hannes Payer wrote:
> Can we have newlines between the methods?

Done.

[Hannes Payer (out of office), 2013-11-25 11:45:51]

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/allocation-si...
File src/allocation-site-scopes.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/allocation-si...
src/allocation-site-scopes.cc:100: ASSERT(FLAG_allocation_site_pretenuring);
This assert has to hold in that case, please remove it.
I think it would make sense to assert that the type of the object is JSObject or
JSArray.

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/allocation-si...
src/allocation-site-scopes.cc:102: PrintF("*** Creating Memento for
JSObject/JSArray %p\n",
Can we determine JSObject/JSArray dynamically?

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/heap.cc
File src/heap.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/heap.cc#newco...
src/heap.cc:514: if (cur->IsAllocationSite()) {
I guess the if is not needed.

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/heap.cc#newco...
src/heap.cc:4403: reinterpret_cast<Address>(result) + map->instance_size());
Is there a way to increase the memento count at memento creation time? Right now
it seems to be a bit fragile to manually increase the counter after creating the
memento.

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/hydrogen.cc#n...
src/hydrogen.cc:2249: BuildCreateAllocationMemento(array,
I guess it would make sense to make the code block below part of
BuildCreateAllocationMemento. WDYT?

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/hydrogen.cc#n...
src/hydrogen.cc:2264: // no write barrier needed to store a smi.
"No"

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/mark-compact.h
File src/mark-compact.h (right):

https://chromiumcodereview.appspot.com/40063002/diff/550001/src/mark-compact....
src/mark-compact.h:742: // Special case for processing weak references in a
compacting collection.
"compacting" -> "full"

[mvstanton, 2013-11-25 13:49:17]

Thx, Hannes, here you go.
--Michael

https://codereview.chromium.org/40063002/diff/550001/src/allocation-site-scop...
File src/allocation-site-scopes.cc (right):

https://codereview.chromium.org/40063002/diff/550001/src/allocation-site-scop...
src/allocation-site-scopes.cc:100: ASSERT(FLAG_allocation_site_pretenuring);
On 2013/11/25 11:45:52, Hannes Payer wrote:
> This assert has to hold in that case, please remove it.
> I think it would make sense to assert that the type of the object is JSObject
or
> JSArray.

Done.

https://codereview.chromium.org/40063002/diff/550001/src/allocation-site-scop...
src/allocation-site-scopes.cc:102: PrintF("*** Creating Memento for
JSObject/JSArray %p\n",
On 2013/11/25 11:45:52, Hannes Payer wrote:
> Can we determine JSObject/JSArray dynamically?

Indeed. In fact, I ordered this code in a better way, we only need one print
statement and nesting can be reduced.

https://codereview.chromium.org/40063002/diff/550001/src/heap.cc
File src/heap.cc (right):

https://codereview.chromium.org/40063002/diff/550001/src/heap.cc#newcode514
src/heap.cc:514: if (cur->IsAllocationSite()) {
On 2013/11/25 11:45:52, Hannes Payer wrote:
> I guess the if is not needed.

Done.

https://codereview.chromium.org/40063002/diff/550001/src/heap.cc#newcode4403
src/heap.cc:4403: reinterpret_cast<Address>(result) + map->instance_size());
On 2013/11/25 11:45:52, Hannes Payer wrote:
> Is there a way to increase the memento count at memento creation time? Right
now
> it seems to be a bit fragile to manually increase the counter after creating
the
> memento.

I consolidated the two heap.cc memento construction sites in
InitializeAllocationMemento, so there is some encapsulation. The remaining site
that creates a memento is in HGraphBuilder::BuildJSArrayHeader(). Obviously the
method is different (hydrogen nodes).

BTW, you prompted me to go look at BuildJSArrayHeader() and I found that I
wasn't skipping an overflow check that I should, so I fixed that. I definitely
don't want a HeapNumber in the memento count field!

https://codereview.chromium.org/40063002/diff/550001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/40063002/diff/550001/src/hydrogen.cc#newcode2249
src/hydrogen.cc:2249: BuildCreateAllocationMemento(array,
On 2013/11/25 11:45:52, Hannes Payer wrote:
> I guess it would make sense to make the code block below part of
> BuildCreateAllocationMemento. WDYT?

The reason I left it out of there was that constructed arrays don't need this
code until they are participating in the alloc-site-based-pretenuring regime,
and I don't want that code to pay the performance penalty until it's getting the
reward too. The alternative is to add a boolean parameter to
BuildCreateAllocationMemento, like increment_create_count, but it would only be
necessary for a short time in the code base, until constructed arrays are part
of pretenuring.

https://codereview.chromium.org/40063002/diff/550001/src/hydrogen.cc#newcode2264
src/hydrogen.cc:2264: // no write barrier needed to store a smi.
On 2013/11/25 11:45:52, Hannes Payer wrote:
> "No"

Done.

https://codereview.chromium.org/40063002/diff/550001/src/mark-compact.h
File src/mark-compact.h (right):

https://codereview.chromium.org/40063002/diff/550001/src/mark-compact.h#newco...
src/mark-compact.h:742: // Special case for processing weak references in a
compacting collection.
On 2013/11/25 11:45:52, Hannes Payer wrote:
> "compacting" -> "full"

Done.

[Hannes Payer (out of office), 2013-11-27 10:51:37]

LGTM, just minor nits. The next step should be a set of tests. BTW. can you
rename this CL to "Bookkeeping for allocation site pretenuring"

https://codereview.chromium.org/40063002/diff/660001/src/allocation-site-scop...
File src/allocation-site-scopes.cc (right):

https://codereview.chromium.org/40063002/diff/660001/src/allocation-site-scop...
src/allocation-site-scopes.cc:89: if (FLAG_allocation_site_pretenuring) {
This method looks too complicated.
What about:

if (activated_ && AllocationSite::CanTrack(object->map()->instance_type())) {
  if (FLAG_allocation_site_pretenuring ||
      AllocationSite::GetMode(object->GetElementsKind()) ==
          TRACK_ALLOCATION_SITE) {
    if (FLAG_trace_creation_allocation_sites) {
      PrintF("*** Creating Memento for %s %p\n",
               object->IsJSArray() ? "JSArray" : "JSObject",
               static_cast<void*>(*object));
    }
    return true;
  }
}
return false;

https://codereview.chromium.org/40063002/diff/660001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/40063002/diff/660001/src/objects.cc#newcode9213
src/objects.cc:9213: // Currently, AllocationMemento objects are only allocated
immediately
Please update this comment.

[mvstanton, 2013-11-27 13:27:58]

Right on thanks much,
--Michael

https://codereview.chromium.org/40063002/diff/660001/src/allocation-site-scop...
File src/allocation-site-scopes.cc (right):

https://codereview.chromium.org/40063002/diff/660001/src/allocation-site-scop...
src/allocation-site-scopes.cc:89: if (FLAG_allocation_site_pretenuring) {
On 2013/11/27 10:51:37, Hannes Payer wrote:
> This method looks too complicated.
> What about:
> 
> if (activated_ && AllocationSite::CanTrack(object->map()->instance_type())) {
>   if (FLAG_allocation_site_pretenuring ||
>       AllocationSite::GetMode(object->GetElementsKind()) ==
>           TRACK_ALLOCATION_SITE) {
>     if (FLAG_trace_creation_allocation_sites) {
>       PrintF("*** Creating Memento for %s %p\n",
>                object->IsJSArray() ? "JSArray" : "JSObject",
>                static_cast<void*>(*object));
>     }
>     return true;
>   }
> }
> return false;


great idea, thx.

https://codereview.chromium.org/40063002/diff/660001/src/objects.cc
File src/objects.cc (right):

https://codereview.chromium.org/40063002/diff/660001/src/objects.cc#newcode9213
src/objects.cc:9213: // Currently, AllocationMemento objects are only allocated
immediately
On 2013/11/27 10:51:37, Hannes Payer wrote:
> Please update this comment.

Done.

[mvstanton, 2013-11-27 14:03:55]

Committed patchset #12 manually as r18104 (presubmit successful).