[Not for commit] Make Array.splice change receiver's FixedArray when significant part is cut.

[Not for commit] Make Array.splice change receiver's FixedArray when significant part is cut.

When Array.splice removes significant part of original array, it could be a
good idea to allocate memory for the part left in receiver and not the one
removed from it.

[iegorov, 2010-04-02 16:17:24]

Anton,

Could you please have a look?

Thank you in advance.

http://codereview.chromium.org/1549016/diff/1/2
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/1/2#newcode332
src/builtins.cc:332: former_start[0] = Heap::raw_unchecked_byte_array_map();
Don't know how to do this.

[antonm, 2010-04-02 16:39:29]

+ Erik as that was originally his idea.

First pass comments.

http://codereview.chromium.org/1549016/diff/1/2
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/1/2#newcode303
src/builtins.cc:303: static FixedArray* LeftTrimFixedArray(FixedArray* elms, int
by) {
is not it the second variant of LeftTrimFixedArray (see ln. 344 in modified
file)?

http://codereview.chromium.org/1549016/diff/1/2#newcode332
src/builtins.cc:332: former_start[0] = Heap::raw_unchecked_byte_array_map();
On 2010/04/02 16:17:26, iegorov wrote:
> Don't know how to do this.

see above

http://codereview.chromium.org/1549016/diff/1/2#newcode775
src/builtins.cc:775: result = Heap::AllocateUninitializedFixedArray(new_length);
new_length might be too much for receiver.

http://codereview.chromium.org/1549016/diff/1/2#newcode781
src/builtins.cc:781: if (Heap::new_space()->Contains(receiver_elms)) {
why this condition?  CopyElements should do the trick for you, don't they?

http://codereview.chromium.org/1549016/diff/1/2#newcode805
src/builtins.cc:805: result_array->set_elements(LeftTrimFixedArray(elms,
actual_start), SKIP_WRITE_BARRIER);
am I missing something or you didn't see a proper length in elms FixedArray? 
Looks like you keep the reminder after actual_start + actual_delete_count.  And
if it's true, those probably should be filled with holes.

http://codereview.chromium.org/1549016/diff/1/2#newcode807
src/builtins.cc:807: return result_array;
ideally I would prefer to keep control flow and let the rest of the code to fill
newly inserted elements.

[iegorov, 2010-04-02 18:29:06]

Anton,

Thank you for comments. When have some time, please take a look at new variant.

http://codereview.chromium.org/1549016/diff/1/2
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/1/2#newcode303
src/builtins.cc:303: static FixedArray* LeftTrimFixedArray(FixedArray* elms, int
by) {
I'm so-so blind! Fixed.
On 2010/04/02 16:39:38, antonm wrote:
> is not it the second variant of LeftTrimFixedArray (see ln. 344 in modified
> file)?

http://codereview.chromium.org/1549016/diff/1/2#newcode775
src/builtins.cc:775: result = Heap::AllocateUninitializedFixedArray(new_length);
It's correct here as discussed offline.
On 2010/04/02 16:39:38, antonm wrote:
> new_length might be too much for receiver.

http://codereview.chromium.org/1549016/diff/1/2#newcode781
src/builtins.cc:781: if (Heap::new_space()->Contains(receiver_elms)) {
Removed branch. Left CopyElements.
On 2010/04/02 16:39:38, antonm wrote:
> why this condition?  CopyElements should do the trick for you, don't they?

http://codereview.chromium.org/1549016/diff/1/2#newcode805
src/builtins.cc:805: result_array->set_elements(LeftTrimFixedArray(elms,
actual_start), SKIP_WRITE_BARRIER);
On 2010/04/02 16:39:38, antonm wrote:
> am I missing something or you didn't see a proper length in elms FixedArray? 
> Looks like you keep the reminder after actual_start + actual_delete_count. 
And
> if it's true, those probably should be filled with holes.

Done.

http://codereview.chromium.org/1549016/diff/1/2#newcode807
src/builtins.cc:807: return result_array;
On 2010/04/02 16:39:38, antonm wrote:
> ideally I would prefer to keep control flow and let the rest of the code to
fill
> newly inserted elements.

Done.

[antonm, 2010-04-02 18:41:18]

mostly lgtm, but I very agree with Erik that before submitting it, we need some
proof that the complication is worth it.

http://codereview.chromium.org/1549016/diff/1/2
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/1/2#newcode807
src/builtins.cc:807: return result_array;
On 2010/04/02 18:29:08, iegorov wrote:
> On 2010/04/02 16:39:38, antonm wrote:
> > ideally I would prefer to keep control flow and let the rest of the code to
> fill
> > newly inserted elements.
> 
> Done.

Sorry for taking my own words back, but diff seems to be ways less readable now.
 May you either revert to the previous variant or invent some better way to
layout flow control.  Yes, the diff is too stupid to see indentation added, but
alas.

http://codereview.chromium.org/1549016/diff/5001/6001#newcode773
src/builtins.cc:773: result_array = JSArray::cast(result);
nit: v8's style requires . at the end of the line comment.

http://codereview.chromium.org/1549016/diff/5001/6001#newcode785
src/builtins.cc:785: memcopy(dst + actual_start + item_count,
too long the line.  try ./tools/presubmit.py

[antonm, 2010-04-05 12:21:13]

http://codereview.chromium.org/1549016/diff/12001/8002
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/12001/8002#newcode728
src/builtins.cc:728: (2 * actual_delete_count >= len + item_count)) {
looks like you're trying to keep the number of writes minimal.  In this case for
inplace result number of writes is actual_start + tail_length (+ tail_length to
fill with the holes) while out of place result requires item_count + tail_length
moves.

Thus condition might be actual_start + tail_length >= item_count.

http://codereview.chromium.org/1549016/diff/12001/8002#newcode759
src/builtins.cc:759: elms = LeftTrimFixedArray(elms, actual_start);
good you noticed that---was going to bring your attention to it :)

[iegorov, 2010-04-05 13:01:48]

Anton,

Thank you once again for comments. First of all, I have doubts about boundary,
see comments below. Secondly, I've ran simple benchmark on my desktop, which
shown (well, as expected), that this optimization does really work in its cases
and doesn't have significant impact on other cases (the impact is lower than
noise). I also added some tests for this particular branch of code to mjsunit.
Unfortunately for us, it doesn't seem that the changes have significant
performance on relevant existing benchmarks.

http://codereview.chromium.org/1549016/diff/12001/8002
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/12001/8002#newcode728
src/builtins.cc:728: (2 * actual_delete_count >= len + item_count)) {
My counts differ:
- when making inplace (terminology: that's what I do, right?): we need
actual_start + items_count + tail_length to create result, and tail_length
writes to make holes in receiver;
- unfortunately when doing out of place, the result differs on items_count
compared to actual_delete_count. When equal: it is only items_count, when
items_count is less than actual_delete_count it is items_count + tail_length
moves, otherwise it results in creation of a new array, which is items_count +
tail_length + actual_start.

The question is what is the boundary? Should I count it precisely? 
On 2010/04/05 12:21:13, antonm wrote:
> looks like you're trying to keep the number of writes minimal.  In this case
for
> inplace result number of writes is actual_start + tail_length (+ tail_length
to
> fill with the holes) while out of place result requires item_count +
tail_length
> moves.
> 
> Thus condition might be actual_start + tail_length >= item_count.

http://codereview.chromium.org/1549016/diff/12001/8002#newcode759
src/builtins.cc:759: elms = LeftTrimFixedArray(elms, actual_start);
Yeah, testing rocks :)
On 2010/04/05 12:21:13, antonm wrote:
> good you noticed that---was going to bring your attention to it :)

[antonm, 2010-04-05 14:34:29]

Regarding if we should commit it at all.  I don't know :)  The code seems to be
notably more complicated (and ArrayShift is not the simplest piece of code
already).  It's obvious we could make a benchmark which shows the benefit of new
approach, but as there is no 'real' benchmark, I'd suggest to attempt to gather
real world stats.

For example, you could write a patch that will gather starts about all the
array.splice operations in, say, GMail, Wave and see if those apps would benefit
from this patch.

More radical approach would be to embed this stat gathering into Chrome itself
to see if it's common operations on some other sites.

http://codereview.chromium.org/1549016/diff/12001/8002
File src/builtins.cc (right):

http://codereview.chromium.org/1549016/diff/12001/8002#newcode728
src/builtins.cc:728: (2 * actual_delete_count >= len + item_count)) {
Sorry, I should have been explicit but I didn't account for item_writes as there
is no way to escape them (unless we'd like to allocate result's elements in the
stack, kidding :).

So estimate for new approach for result allocation appears to be the same for
you and me: actual_start + 2*tail_length + item_count.

Now to estimates for the present approach.  My mistake was I only thought about
one case when length of fixed element array is enough.  Now to your more
detailed analysis.

item_count == actual_delete_count:

It's not just item_count---it's 2*item_count if you account for new elements
writes---item_count to copy old items + item_count to write new ones.  So we do
less writes with new approach given actual_start + 2*tail_length < item_count.

item_count < actual_delete_count:

I think we need item_count (new elements writes) + tail_length (to move former
elements) + (actual_delete_count - item_count) (to fill with the holes) (if we
cannot apply new space trick which could save additional moves)

item_count > actual_delete_count:

even more complicated as we need to fill with the holes the rest of newly
allocated array.

Overall numbers seems quite different and I suspect (but I didn't think
properly) when simple heuristics could lead to worse behaviour.

So could you experiment (if you please, of course) if it's possible to refactor
the code in the following fashion:

for all three cases (item_count <>= actual_delete_count) we decide how exactly
we should go?

On 2010/04/05 13:01:49, iegorov wrote:
> My counts differ:
> - when making inplace (terminology: that's what I do, right?): we need
> actual_start + items_count + tail_length to create result, and tail_length
> writes to make holes in receiver;
> - unfortunately when doing out of place, the result differs on items_count
> compared to actual_delete_count. When equal: it is only items_count, when
> items_count is less than actual_delete_count it is items_count + tail_length
> moves, otherwise it results in creation of a new array, which is items_count +
> tail_length + actual_start.
> 
> The question is what is the boundary? Should I count it precisely? 
> On 2010/04/05 12:21:13, antonm wrote:
> > looks like you're trying to keep the number of writes minimal.  In this case
> for
> > inplace result number of writes is actual_start + tail_length (+ tail_length
> to
> > fill with the holes) while out of place result requires item_count +
> tail_length
> > moves.
> > 
> > Thus condition might be actual_start + tail_length >= item_count. 
> 
>