Limit the number of transitions allowed per hidden class.

Limit the number of transitions allowed per hidden class.

Each time a transition is added to a hidden class, the whole
transitions array must be copied, which causes poor performance
in some circumstances.  This change limits the maximum size of
the transition array, avoiding this behavior in the pathological
case.  For example, this improves the performance of the EtchMark
benchmark by nearly 60%.

BUG=v8:3616
LOG=
R=verwaest@chromium.org, svenpanne@chromium.org

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

[mckev, 2014-10-07 20:16:08]

Hi Sven!

Please take a look at the proposed fix for v8:3616.  If other reviewers are
needed, please advise.  Let me know if you need anything else.

Thanks!
Kevin M. McCormick
mckev@amazon.com

[Sven Panne, 2014-10-08 06:47:24]

svenpanne@chromium.org changed reviewers:
+ verwaest@chromium.org

[Sven Panne, 2014-10-08 06:47:24]

Reassigning to Toon...

[Sven Panne, 2014-10-08 06:54:12]

svenpanne@chromium.org changed reviewers:
- svenpanne@chromium.org

[Toon Verwaest, 2014-10-14 08:58:44]

What about growing the transition array by X% each time, and using insertion
sort, just like we do for descriptor arrays? That would still be worse
complexity than not inserting anything; but may reduce overhead enough for such
silly benchmarks.

[mckev, 2014-10-20 16:00:17]

On 2014/10/14 08:58:44, Toon Verwaest wrote:
> What about growing the transition array by X% each time, and using insertion
> sort, just like we do for descriptor arrays? That would still be worse
> complexity than not inserting anything; but may reduce overhead enough for
such
> silly benchmarks.

Sounds fair.  Digging into the descriptor arrays, I noticed that they're limited
to a maximum length of 1022 (kMaxNumberOfDescriptors, defined in
property-details.h). If we used that as the maximum size of transition arrays,
that would be about about 36% slower in the pathological case than using a hard
limit of 200, but would still be 3-4x better than the current behavior.

My current plan is to rework the patch to have transition arrays work like
descriptor arrays in both manners: grow by a margin avoid some memory
allocations (although I haven't yet figured out how that happens for descriptor
arrays) and have a limited maximum size.  I'll have a patch up shortly for your
review.

[mckev, 2014-10-22 22:49:29]

Hey Toon,

Based on your feedback, I gave it a shot and added exponential growth to the
TransitionArrays and changed the limit to an existing value that wasn't being
used, instead of providing my own. Here's some performance data:

                                    10k iterations        20k        30k
Baseline (before patch):                   300ms         1100ms     3600ms
Original Patch:                             25ms           40ms       55ms
With Growth + New Limit (this patch):       31ms           45ms       60ms
With just Growth:                          127ms          442ms      964ms
(These are the median values from 5 runs.)

Based on the data, it still seems that the limit is the predominant contributor
to the performance improvement, but indeed as expected, just growth alone does
provide a benefit.  We've definitely confirmed that fewer allocations results in
fewer GC's across the board - in fact, this patch includes a fix for 2 tests
that assumed a GC would occur.

I'll defer to your judgement on this one - I'd be happy to provide a patch with
just the growth if you feel the limit is detrimental or has other side effects
I'm not considering.

Thanks in advance for your review!

[Toon Verwaest, 2014-10-23 09:44:34]

Reinstating the 1.5k limit sounds fine. The results of growth+new limit seem
close enough to the improvements of your original patch.

The patch overall is looking good, still some comments though.

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc
File src/transitions.cc (right):

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:113: array->NoIncrementalWriteBarrierSet(insertion_index,
*name, *target);
You can't omit the incremental write barrier if you didn't just allocate the
transition array.

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:125: insertion_index, key, array->GetTarget(insertion_index -
1));
Same here.

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:127: array->NoIncrementalWriteBarrierSet(insertion_index,
*name, *target);
Same here.

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:133: number_of_transitions < 4 ? 1 : number_of_transitions /
2);
Please add a helper function to calculate the actual number of slack that
doesn't overshoot the limit (kMaxNumberOfTransitions); and use it for allocating
the descriptor array as well.

[mckev, 2014-10-24 02:18:52]

Hi Toon,

Thanks for the review!  PTAL, I've added a new patchset to address your
comments.

Best,
Kevin

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc
File src/transitions.cc (right):

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:113: array->NoIncrementalWriteBarrierSet(insertion_index,
*name, *target);
On 2014/10/23 09:44:34, Toon Verwaest wrote:
> You can't omit the incremental write barrier if you didn't just allocate the
> transition array.

Ah.. SetTarget seems more appropriate then.

https://codereview.chromium.org/635883003/diff/20001/src/transitions.cc#newco...
src/transitions.cc:133: number_of_transitions < 4 ? 1 : number_of_transitions /
2);
On 2014/10/23 09:44:33, Toon Verwaest wrote:
> Please add a helper function to calculate the actual number of slack that
> doesn't overshoot the limit (kMaxNumberOfTransitions); and use it for
allocating
> the descriptor array as well.

Done.

[Toon Verwaest, 2014-10-24 05:20:57]

Thanks, that LGTM. I'll land the patch for you.

[Toon Verwaest, 2014-10-24 05:30:09]

Committed patchset #3 (id:40001) manually as 24857 (presubmit successful).