[heap] Use HashMap as scratchpad backing store

[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and
temporary counts as values. During evacuation we collect a local hashmap of
visited allocation sites. Upon merging the local hashmap back into a global one
we update potential forward pointers of compacted allocation sites.  The
scavenger can directly enter its entries into the global hashmap. Note that the
actual memento found count is still kept on the AllocationSite as it needs to
survive scavenges and full GCs.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org

Committed: https://crrev.com/55422bdd501ff93e2eff737b5b3672dc92a147ff
Cr-Commit-Position: refs/heads/master@{#33233}

[Michael Lippautz, 2015-12-21 10:40:14]

Patchset #2 (id:20001) has been deleted

[Michael Lippautz, 2015-12-21 13:29:03]

Patchset #2 (id:40001) has been deleted

[Michael Lippautz, 2015-12-21 14:32:01]

Description was changed from

==========
[heap, prototype] Use HashMap as scratch pad backing store

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

to

==========
[heap, prototype] Use HashMap as scratch pad backing store

We use a scratchpad to remember visited allocation sites for
post processing. The previous implementation used a rooted FixedArray with
constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementations of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. During merging them back into a global hashmap we update potential
forward pointers of compacted allocation sites. The scavenger can directly enter
its entries into the global hashmap.

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

[Michael Lippautz, 2015-12-21 14:34:17]

Description was changed from

==========
[heap, prototype] Use HashMap as scratch pad backing store

We use a scratchpad to remember visited allocation sites for
post processing. The previous implementation used a rooted FixedArray with
constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementations of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. During merging them back into a global hashmap we update potential
forward pointers of compacted allocation sites. The scavenger can directly enter
its entries into the global hashmap.

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

to

==========
[heap, prototype] Use HashMap as scratch pad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

[Michael Lippautz, 2015-12-21 17:33:00]

Patchset #6 (id:140001) has been deleted

[Michael Lippautz, 2015-12-21 17:33:14]

Patchset #5 (id:120001) has been deleted

[Michael Lippautz, 2015-12-21 17:33:28]

Patchset #4 (id:100001) has been deleted

[Michael Lippautz, 2015-12-21 17:33:37]

Patchset #3 (id:80001) has been deleted

[Michael Lippautz, 2015-12-21 17:36:28]

Description was changed from

==========
[heap, prototype] Use HashMap as scratch pad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

[Michael Lippautz, 2015-12-21 18:58:50]

Patchset #2 (id:60001) has been deleted

[Michael Lippautz, 2015-12-21 19:05:36]

mlippautz@chromium.org changed reviewers:
+ hpayer@chromium.org

[Michael Lippautz, 2015-12-21 19:05:37]

PTAL. The change seems to be almost performance neutral on the bots (flaky
runs). It's not fully polished yet, but you can already see where we would be
going.

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

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap-inl.h#ne...
src/heap/heap-inl.h:511: bool insert) {
This is not really ideal, but for scavenging we need to update the memento count
on the fly as we don't have a merging step that updates it.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap-inl.h#ne...
src/heap/heap-inl.h:523: (*reinterpret_cast<intptr_t*>(&e->value))++;
We could change this code here to not keep a hash value if we insert on the fly.

The current implementation keeps the hashmap consistent without actually using
the values later on.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc
File src/heap/heap.cc (left):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#oldco...
src/heap/heap.cc:549: allocation_sites++;
I guess this is a minor bug. allocation_sites should be incremented outside of
this branch.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#newco...
src/heap/heap.cc:533: (*reinterpret_cast<intptr_t*>(&global_entry->value)) +=
value;
After incrementing the memento cound we don't need the actual value anymore. A
hashset would suffice.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/mark-compact....
src/heap/mark-compact.cc:3088: HashMap* MarkCompactCollector::EvacuateNewSpace()
{
We could also keep the hashmap on the stack and pass it in here.

[Hannes Payer (out of office), 2016-01-04 15:35:18]

First round.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc
File src/heap/heap.cc (left):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#oldco...
src/heap/heap.cc:549: allocation_sites++;
On 2015/12/21 19:05:37, Michael Lippautz wrote:
> I guess this is a minor bug. allocation_sites should be incremented outside of
> this branch.

Ack.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#newco...
src/heap/heap.cc:69: static bool ComparePointers(void* key1, void* key2) {
return key1 == key2; }
Remove this line and use HashMap::PointersMatch in the constructor.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#newco...
src/heap/heap.cc:533: (*reinterpret_cast<intptr_t*>(&global_entry->value)) +=
value;
On 2015/12/21 19:05:37, Michael Lippautz wrote:
> After incrementing the memento cound we don't need the actual value anymore. A
> hashset would suffice.

As discussed offline, let's remove the counter from the allocation site object.

[Michael Lippautz, 2016-01-05 09:07:39]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

Some performance numbers (feedback is heavily stressed in Octane):

BUG=524425
LOG=N
==========

[Michael Lippautz, 2016-01-05 11:03:18]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

Some performance numbers (feedback is heavily stressed in Octane):

BUG=524425
LOG=N
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

[Michael Lippautz, 2016-01-07 13:11:35]

Patchset #9 (id:300001) has been deleted

[Michael Lippautz, 2016-01-07 13:12:39]

PTAL

* I removed the counter field from AllocationSite
* Moving the memento created count there is possible but requires sub changes,
which I would do in a followup

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#newco...
src/heap/heap.cc:69: static bool ComparePointers(void* key1, void* key2) {
return key1 == key2; }
On 2016/01/04 15:35:18, Hannes Payer wrote:
> Remove this line and use HashMap::PointersMatch in the constructor.

Done.

https://codereview.chromium.org/1535723002/diff/220001/src/heap/heap.cc#newco...
src/heap/heap.cc:533: (*reinterpret_cast<intptr_t*>(&global_entry->value)) +=
value;
On 2016/01/04 15:35:18, Hannes Payer wrote:
> On 2015/12/21 19:05:37, Michael Lippautz wrote:
> > After incrementing the memento cound we don't need the actual value anymore.
A
> > hashset would suffice.
> 
> As discussed offline, let's remove the counter from the allocation site
object.

Done.

[Michael Lippautz, 2016-01-08 08:04:58]

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

[commit-bot: I haz the power, 2016-01-08 08:05:00]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1535723002/320001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1535723002/320001

[commit-bot: I haz the power, 2016-01-08 08:15:12]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-08 08:15:13]

Dry run: Try jobs failed on following builders:
  v8_linux_dbg on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg/builds/12739)

[Michael Lippautz, 2016-01-08 08:19:24]

Patchset #9 (id:320001) has been deleted

[Michael Lippautz, 2016-01-08 08:19:31]

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

[commit-bot: I haz the power, 2016-01-08 08:19:39]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1535723002/340001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1535723002/340001

[commit-bot: I haz the power, 2016-01-08 09:15:20]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-08 09:15:20]

Dry run: This issue passed the CQ dry run.

[Hannes Payer (out of office), 2016-01-08 09:55:07]

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.cc#newco...
src/heap/heap.cc:1286: InitPretenuring();
How about a pretenuring scope that takes care of the allocation/deletion of the
hash map?

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.h#newcod...
src/heap/heap.h:1543: void MergeLocalScratchPad(const HashMap&
local_scratchpad);
We should get rid of the name scratchpad, since we use now a proper hash map.
What about:
MergeAllocationSitePretenuringFeedback for that method.
local_scratchpad => local_pretenuring_feedback

Please also rename other methods, variables, and comments.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3085: HashMap* MarkCompactCollector::EvacuateNewSpace()
{
Why would this method return a HashMap?

The prologue of this performs the semi-space flip, this cannot happen multiple
times by multiple threads.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3109: HashMap* local_scratchpad = new
HashMap(HashMap::PointersMatch, 16);
16 should be defined as a k constant.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3605: heap_->MergeLocalScratchPad(*local_scratchpad);
You are already preparing for the parallel world. But it seems somehow half way.
Why don't we set it up as if there would be multiple threads.

https://codereview.chromium.org/1535723002/diff/340001/tools/v8heapconst.py
File tools/v8heapconst.py (left):

https://codereview.chromium.org/1535723002/diff/340001/tools/v8heapconst.py#o...
tools/v8heapconst.py:299: ("OLD_SPACE", 0x24fc5): "AllocationSitesScratchpad",
Please run 'make grokdump' and do not update this file manually.

[Michael Lippautz, 2016-01-08 10:45:56]

Patchset #10 (id:360001) has been deleted

[Michael Lippautz, 2016-01-08 10:47:15]

Patchset #10 (id:380001) has been deleted

[Michael Lippautz, 2016-01-08 10:50:38]

Patchset #10 (id:400001) has been deleted

[Michael Lippautz, 2016-01-08 10:52:32]

Patchset #10 (id:420001) has been deleted

[Michael Lippautz, 2016-01-08 10:56:24]

I could not go full way with structuring the code for parallization (yet) as
this would mean merging young and old generation phases. I will do this once the
scratchpad and counters are in place.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.cc#newco...
src/heap/heap.cc:1286: InitPretenuring();
On 2016/01/08 09:55:07, Hannes Payer wrote:
> How about a pretenuring scope that takes care of the allocation/deletion of
the
> hash map?

Good idea. Done (PretenuringScope).

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.h
File src/heap/heap.h (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/heap.h#newcod...
src/heap/heap.h:1543: void MergeLocalScratchPad(const HashMap&
local_scratchpad);
On 2016/01/08 09:55:07, Hannes Payer wrote:
> We should get rid of the name scratchpad, since we use now a proper hash map.
> What about:
> MergeAllocationSitePretenuringFeedback for that method.
> local_scratchpad => local_pretenuring_feedback
> 
> Please also rename other methods, variables, and comments.

Done.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3085: HashMap* MarkCompactCollector::EvacuateNewSpace()
{
On 2016/01/08 09:55:07, Hannes Payer wrote:
> Why would this method return a HashMap?
> 
> The prologue of this performs the semi-space flip, this cannot happen multiple
> times by multiple threads.

Split up the phases but still left out the part of merging newspace and oldspace
phases (see below).

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3109: HashMap* local_scratchpad = new
HashMap(HashMap::PointersMatch, 16);
On 2016/01/08 09:55:07, Hannes Payer wrote:
> 16 should be defined as a k constant.

Done.

https://codereview.chromium.org/1535723002/diff/340001/src/heap/mark-compact....
src/heap/mark-compact.cc:3605: heap_->MergeLocalScratchPad(*local_scratchpad);
On 2016/01/08 09:55:07, Hannes Payer wrote:
> You are already preparing for the parallel world. But it seems somehow half
way.
> Why don't we set it up as if there would be multiple threads.

I went a step further and split up the NewSpaceEvacuation in a Prologue and a
Parallel phase. I don't want to go full way, because that would mean merging
newspace and oldspace evacuation phases. I think this is out-of-scope of this CL
which should replace the scratchpad.

https://codereview.chromium.org/1535723002/diff/340001/tools/v8heapconst.py
File tools/v8heapconst.py (left):

https://codereview.chromium.org/1535723002/diff/340001/tools/v8heapconst.py#o...
tools/v8heapconst.py:299: ("OLD_SPACE", 0x24fc5): "AllocationSitesScratchpad",
On 2016/01/08 09:55:07, Hannes Payer wrote:
> Please run 'make grokdump' and do not update this file manually.

Done.

[Michael Lippautz, 2016-01-08 11:52:52]

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

[commit-bot: I haz the power, 2016-01-08 11:53:02]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1535723002/440001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1535723002/440001

[commit-bot: I haz the power, 2016-01-08 12:16:35]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-08 12:16:35]

Dry run: This issue passed the CQ dry run.

[Michael Lippautz, 2016-01-08 12:54:57]

FYI: The followup for moving the created memento counter in place of the found
memento counter:
  https://codereview.chromium.org/1571673002/

[Michael Lippautz, 2016-01-08 13:00:45]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
R=hpayer@chromium.org
==========

[Michael Lippautz, 2016-01-08 13:33:21]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=524425
LOG=N
R=hpayer@chromium.org
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org
==========

[Hannes Payer (out of office), 2016-01-08 14:40:10]

lgtm

[Michael Lippautz, 2016-01-11 18:30:57]

Patchset #14 (id:520001) has been deleted

[Michael Lippautz, 2016-01-11 18:32:47]

Patchset #14 (id:540001) has been deleted

[Michael Lippautz, 2016-01-11 21:41:38]

Patchset #14 (id:560001) has been deleted

[Michael Lippautz, 2016-01-12 07:41:17]

Patchset #14 (id:580001) has been deleted

[Michael Lippautz, 2016-01-12 07:48:39]

Patchset #14 (id:600001) has been deleted

[Michael Lippautz, 2016-01-12 07:50:17]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and counts
as values. During evacuation we collect a local hashmap of visited allocation
sites. Upon merging the local hashmap back into a global one we update potential
forward pointers of compacted allocation sites.  The scavenger can directly
enter its entries into the global hashmap.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and
temporary counts as values. During evacuation we collect a local hashmap of
visited allocation sites. Upon merging the local hashmap back into a global one
we update potential forward pointers of compacted allocation sites.  The
scavenger can directly enter its entries into the global hashmap. Note that the
actual memento found count is still kept on the AllocationSite as it needs to
survive scavenges and full GCs.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org
==========

[Michael Lippautz, 2016-01-12 11:02:24]

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

[commit-bot: I haz the power, 2016-01-12 11:02:30]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1535723002/620001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1535723002/620001

[commit-bot: I haz the power, 2016-01-12 11:32:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-12 11:32:50]

Dry run: This issue passed the CQ dry run.

[Michael Lippautz, 2016-01-12 11:44:17]

The CQ bit was checked by mlippautz@chromium.org

[Michael Lippautz, 2016-01-12 11:44:17]

The patchset sent to the CQ was uploaded after l-g-t-m from hpayer@chromium.org
Link to the patchset: https://codereview.chromium.org/1535723002/#ps620001
(title: "Revive the founder counter on the AllocationSite")

[commit-bot: I haz the power, 2016-01-12 11:44:23]

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

[commit-bot: I haz the power, 2016-01-12 11:45:52]

Committed patchset #14 (id:620001)

[commit-bot: I haz the power, 2016-01-12 11:46:47]

Description was changed from

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and
temporary counts as values. During evacuation we collect a local hashmap of
visited allocation sites. Upon merging the local hashmap back into a global one
we update potential forward pointers of compacted allocation sites.  The
scavenger can directly enter its entries into the global hashmap. Note that the
actual memento found count is still kept on the AllocationSite as it needs to
survive scavenges and full GCs.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org
==========

to

==========
[heap] Use HashMap as scratchpad backing store

We use a scratchpad to remember visited allocation sites for post processing
(making tenure decisions). The previous implementation used a rooted FixedArray
with constant length (256) to remember all sites. Updating the scratchpad is a
bottleneck in any parallel/concurrent implementation of newspace evacuation.

The new implementation uses a HashMap with allocation sites as keys and
temporary counts as values. During evacuation we collect a local hashmap of
visited allocation sites. Upon merging the local hashmap back into a global one
we update potential forward pointers of compacted allocation sites.  The
scavenger can directly enter its entries into the global hashmap. Note that the
actual memento found count is still kept on the AllocationSite as it needs to
survive scavenges and full GCs.

BUG=chromium:524425
LOG=N
R=hpayer@chromium.org

Committed: https://crrev.com/55422bdd501ff93e2eff737b5b3672dc92a147ff
Cr-Commit-Position: refs/heads/master@{#33233}
==========

[commit-bot: I haz the power, 2016-01-12 11:46:48]

Patchset 14 (id:??) landed as
https://crrev.com/55422bdd501ff93e2eff737b5b3672dc92a147ff
Cr-Commit-Position: refs/heads/master@{#33233}