Copy-on-write arrays.

Copy-on-write arrays.

Object model changes
----------------------------------------
New fixed_cow_array_map is used for the elements array of a JSObject
to mark it as COW. The JSObject's map and other fields are not
affected. The JSObject's map still has the "fast elements" bit set. It
means we can do only the receiver map check in keyed loads and the
receiver and the elements map checks in keyed stores. So introducing
COW arrays doesn't hurt performance of these operations. But note that
the elements map check is necessary in all mutating operations because
the "has fast elements" bit now means "has fast elements for reading".
EnsureWritableFastElements can be used in runtime functions to perform
the necessary lazy copying.

Generated code changes
----------------------------------------
Generic keyed load is updated to only do the receiver map check (this
could have been done earlier). FastCloneShallowArrayStub now has two
modes: clone elements and use COW elements. AssertFastElements macro
is added to check the elements when necessary. The custom call IC
generators for Array.prototype.{push,pop} are updated to avoid going
to the slow case (and patching the IC) when calling the builtin should
work.

COW enablement
----------------------------------------
Currently we only put shallow and simple literal arrays in the COW
mode. This is done by the parser.

Committed: http://code.google.com/p/v8/source/detail?r=5275

[Mads Ager (chromium), 2010-08-11 10:42:31]

LGTM!

http://codereview.chromium.org/3144002/diff/1/8
File src/ia32/ic-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/8#newcode454
src/ia32/ic-ia32.cc:454: // Loads an indexed element from a fast case array.
Maybe update the comment (either here or in the header file) with information
about the use of the not_fast_array label?

http://codereview.chromium.org/3144002/diff/1/8#newcode568
src/ia32/ic-ia32.cc:568: 1 << Map::kHasFastElements);
Should we update the name of the bit to HasFastElementsForReading to reflect the
new meaning?

Maybe that is not needed with the new explanation to the general HasFastElements
method, but it might clearify the code generators to be explicit about it in the
name of the bit.

http://codereview.chromium.org/3144002/diff/1/13
File src/objects-inl.h (right):

http://codereview.chromium.org/3144002/diff/1/13#newcode1401
src/objects-inl.h:1401: ASSERT(map_word().ToMap() !=
Heap::raw_unchecked_fixed_cow_array_map());
Just use 'map()' in all of these asserts?

Are these used during GC so that you need to use
raw_unchecked_fixed_cow_array_map or could you just use fixed_cow_array_map()?

[antonm, 2010-08-11 11:28:22]

LGTM.

Do we believe current test coverage is enough?  Maybe throw in some more tests?

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

http://codereview.chromium.org/3144002/diff/1/2#newcode355
src/builtins.cc:355: if (elms->map() == Heap::fixed_array_map()) return
FixedArray::cast(elms);
I don't think you need FixedArray::cast anymore.

http://codereview.chromium.org/3144002/diff/1/2#newcode363
src/builtins.cc:363: static bool IsJSArrayElementMovingAllowed(JSArray*
receiver) {
you might want to keep Fast in the name---this check allows to use
memmove/memcopy to move elements around.

http://codereview.chromium.org/3144002/diff/1/4
File src/heap.cc (right):

http://codereview.chromium.org/3144002/diff/1/4#newcode1533
src/heap.cc:1533: obj = AllocateMap(FIXED_ARRAY_TYPE, FixedArray::kHeaderSize);
maybe move to allocation of fixed_array_map?

http://codereview.chromium.org/3144002/diff/1/6
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/6#newcode9484
src/ia32/codegen-ia32.cc:9484: // dictionary.
this comment probably needs an update.  Overall, is there a way to check other
places?

http://codereview.chromium.org/3144002/diff/1/8
File src/ia32/ic-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/8#newcode980
src/ia32/ic-ia32.cc:980: // Check that the object is in fast mode (not
dictionary).
again fast writable mode?

http://codereview.chromium.org/3144002/diff/1/8#newcode1036
src/ia32/ic-ia32.cc:1036: // array. Check that the array is in fast mode; if it
is the
again fast writable mode?  or we should just make COW an exception?

http://codereview.chromium.org/3144002/diff/1/8#newcode1886
src/ia32/ic-ia32.cc:1886: __ CmpObjectType(scratch, FIXED_ARRAY_TYPE, scratch);
just to double check: that should be fine as StoreIC would take care of COWs,
correct?

http://codereview.chromium.org/3144002/diff/1/11
File src/ia32/stub-cache-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/11#newcode1398
src/ia32/stub-cache-ia32.cc:1398: // Check that the elements are in fast mode
(not dictionary).
you may want to update the comment to mention fast writable mode.

http://codereview.chromium.org/3144002/diff/1/11#newcode1540
src/ia32/stub-cache-ia32.cc:1540: // Check that the elements are in fast mode
(not dictionary).
Ditto for comment

http://codereview.chromium.org/3144002/diff/1/14
File src/objects.cc (right):

http://codereview.chromium.org/3144002/diff/1/14#newcode5670
src/objects.cc:5670: Object* obj =
SetFastElementsCapacityAndLength(new_capacity, value);
that would apparently keep COWness of original array, was it intended?

[antonm, 2010-08-11 12:39:38]

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

http://codereview.chromium.org/3144002/diff/1/2#newcode357
src/builtins.cc:357: return array->EnsureWritableFastElements();
just as an idea for speed up: maybe we could add utility function to turn
elements into writables with api like: JSArray::TurnToWritables(FixedArray*
elements) which bypasses map check and elements lookup.  But I don't know how
much will it buy us.

Overall, do you know how many COW arrays come into builtins in Dromaeo array
benchmark?

[Vitaly Repeshko, 2010-08-13 14:14:00]

All issues addressed. Ported to x64 and arm. Also fixed a bug in generic keyed
load (broke the internal "elements in ecx" assumption).

Please take another look.

Thanks,
Vitaly

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

http://codereview.chromium.org/3144002/diff/1/2#newcode355
src/builtins.cc:355: if (elms->map() == Heap::fixed_array_map()) return
FixedArray::cast(elms);
On 2010/08/11 11:28:22, antonm wrote:
> I don't think you need FixedArray::cast anymore.

Done.

http://codereview.chromium.org/3144002/diff/1/2#newcode357
src/builtins.cc:357: return array->EnsureWritableFastElements();
On 2010/08/11 12:39:38, antonm wrote:
> just as an idea for speed up: maybe we could add utility function to turn
> elements into writables with api like: JSArray::TurnToWritables(FixedArray*
> elements) which bypasses map check and elements lookup.  But I don't know how
> much will it buy us.

Given the conversion cost I think the benefit is negligible.

> Overall, do you know how many COW arrays come into builtins in Dromaeo array
> benchmark?

Very very few.

http://codereview.chromium.org/3144002/diff/1/2#newcode363
src/builtins.cc:363: static bool IsJSArrayElementMovingAllowed(JSArray*
receiver) {
On 2010/08/11 11:28:22, antonm wrote:
> you might want to keep Fast in the name---this check allows to use
> memmove/memcopy to move elements around.

Done.

http://codereview.chromium.org/3144002/diff/1/4
File src/heap.cc (right):

http://codereview.chromium.org/3144002/diff/1/4#newcode1533
src/heap.cc:1533: obj = AllocateMap(FIXED_ARRAY_TYPE, FixedArray::kHeaderSize);
On 2010/08/11 11:28:22, antonm wrote:
> maybe move to allocation of fixed_array_map?

fixed_array_map is allocated early in a special way. COW map wont' fit there.

http://codereview.chromium.org/3144002/diff/1/6
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/6#newcode9484
src/ia32/codegen-ia32.cc:9484: // dictionary.
On 2010/08/11 11:28:22, antonm wrote:
> this comment probably needs an update.  Overall, is there a way to check other
> places?

Done.

http://codereview.chromium.org/3144002/diff/1/8
File src/ia32/ic-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/8#newcode454
src/ia32/ic-ia32.cc:454: // Loads an indexed element from a fast case array.
On 2010/08/11 10:42:31, Mads Ager wrote:
> Maybe update the comment (either here or in the header file) with information
> about the use of the not_fast_array label?

Done.

http://codereview.chromium.org/3144002/diff/1/8#newcode568
src/ia32/ic-ia32.cc:568: 1 << Map::kHasFastElements);
On 2010/08/11 10:42:31, Mads Ager wrote:
> Should we update the name of the bit to HasFastElementsForReading to reflect
the
> new meaning?
> 
> Maybe that is not needed with the new explanation to the general
HasFastElements
> method, but it might clearify the code generators to be explicit about it in
the
> name of the bit.

Yeah, I'd like to avoid renaming the bit. The bit is new, very little code
relied on it, so I think it's okay to give it a new meaning in the new
explanation.

http://codereview.chromium.org/3144002/diff/1/8#newcode980
src/ia32/ic-ia32.cc:980: // Check that the object is in fast mode (not
dictionary).
On 2010/08/11 11:28:22, antonm wrote:
> again fast writable mode?

Done.

http://codereview.chromium.org/3144002/diff/1/8#newcode1036
src/ia32/ic-ia32.cc:1036: // array. Check that the array is in fast mode; if it
is the
On 2010/08/11 11:28:22, antonm wrote:
> again fast writable mode?  or we should just make COW an exception?

Done.

http://codereview.chromium.org/3144002/diff/1/8#newcode1886
src/ia32/ic-ia32.cc:1886: __ CmpObjectType(scratch, FIXED_ARRAY_TYPE, scratch);
On 2010/08/11 11:28:22, antonm wrote:
> just to double check: that should be fine as StoreIC would take care of COWs,
> correct?

Good question. StoreIC takes care of COWs, but this is subtle and needs a
comment.

http://codereview.chromium.org/3144002/diff/1/11
File src/ia32/stub-cache-ia32.cc (right):

http://codereview.chromium.org/3144002/diff/1/11#newcode1398
src/ia32/stub-cache-ia32.cc:1398: // Check that the elements are in fast mode
(not dictionary).
On 2010/08/11 11:28:22, antonm wrote:
> you may want to update the comment to mention fast writable mode.

Done.

http://codereview.chromium.org/3144002/diff/1/13
File src/objects-inl.h (right):

http://codereview.chromium.org/3144002/diff/1/13#newcode1401
src/objects-inl.h:1401: ASSERT(map_word().ToMap() !=
Heap::raw_unchecked_fixed_cow_array_map());
On 2010/08/11 10:42:31, Mads Ager wrote:
> Just use 'map()' in all of these asserts?
> 
> Are these used during GC so that you need to use
> raw_unchecked_fixed_cow_array_map or could you just use fixed_cow_array_map()?

Changed map_word().ToMap() to map(). Some of these are used during GC (our
descriptor dance) so I used "unchecked" in all of them for consistency.

http://codereview.chromium.org/3144002/diff/1/14
File src/objects.cc (right):

http://codereview.chromium.org/3144002/diff/1/14#newcode5670
src/objects.cc:5670: Object* obj =
SetFastElementsCapacityAndLength(new_capacity, value);
On 2010/08/11 11:28:22, antonm wrote:
> that would apparently keep COWness of original array, was it intended?

As discussed offline this is not an issue. We don't attempt mutation of COW
arrays here.

[Vyacheslav Egorov (Chromium), 2010-08-13 16:15:08]

I was driving by on my fancy markbits-mobile :-)

http://codereview.chromium.org/3144002/diff/1/13
File src/objects-inl.h (right):

http://codereview.chromium.org/3144002/diff/1/13#newcode1401
src/objects-inl.h:1401: ASSERT(map_word().ToMap() !=
Heap::raw_unchecked_fixed_cow_array_map());
On 2010/08/13 14:14:01, Vitaly wrote:
> On 2010/08/11 10:42:31, Mads Ager wrote:
> > Just use 'map()' in all of these asserts?
> > 
> > Are these used during GC so that you need to use
> > raw_unchecked_fixed_cow_array_map or could you just use
fixed_cow_array_map()?
> 
> Changed map_word().ToMap() to map(). Some of these are used during GC (our
> descriptor dance) so I used "unchecked" in all of them for consistency.
> 

If some of them are used during GC then they should take into account that
object can be marked. For marked object assertion 

ASSERT(map() != Heap::raw_unchecked_fixed_cow_array_map()); 

will never fail even if object actually have COW array map. 

During GC you have to clear mark and overflow bits from map word to get a real
map pointer.

[antonm, 2010-08-13 16:50:47]

http://codereview.chromium.org/3144002/diff/4002/13004
File src/arm/ic-arm.cc (right):

http://codereview.chromium.org/3144002/diff/4002/13004#newcode1143
src/arm/ic-arm.cc:1143: __ ldr(r4, FieldMemOperand(r1,
JSObject::kElementsOffset));
Do we need to load elements, shouldn't they be in r2 already (otherwise comment
for GenerateFastArrayLoad should be corrected).

http://codereview.chromium.org/3144002/diff/4002/13029
File src/x64/ic-x64.cc (right):

http://codereview.chromium.org/3144002/diff/4002/13029#newcode640
src/x64/ic-x64.cc:640: __ movq(rcx, FieldOperand(rdx,
JSObject::kElementsOffset));
again looks like rcx should already hold elements.

[Vitaly Repeshko, 2010-08-16 12:35:02]

All done. Please take yet another look.


Thanks,
Vitaly

http://codereview.chromium.org/3144002/diff/1/13
File src/objects-inl.h (right):

http://codereview.chromium.org/3144002/diff/1/13#newcode1401
src/objects-inl.h:1401: ASSERT(map_word().ToMap() !=
Heap::raw_unchecked_fixed_cow_array_map());
On 2010/08/13 16:15:08, Vyacheslav Egorov wrote:
> On 2010/08/13 14:14:01, Vitaly wrote:
> > On 2010/08/11 10:42:31, Mads Ager wrote:
> > > Just use 'map()' in all of these asserts?
> > > 
> > > Are these used during GC so that you need to use
> > > raw_unchecked_fixed_cow_array_map or could you just use
> fixed_cow_array_map()?
> > 
> > Changed map_word().ToMap() to map(). Some of these are used during GC (our
> > descriptor dance) so I used "unchecked" in all of them for consistency.
> > 
> 
> If some of them are used during GC then they should take into account that
> object can be marked. For marked object assertion 
> 
> ASSERT(map() != Heap::raw_unchecked_fixed_cow_array_map()); 
> 
> will never fail even if object actually have COW array map. 
> 
> During GC you have to clear mark and overflow bits from map word to get a real
> map pointer.

Right, but given that during GC the value of the map word can be almost
anything, we can't write a reliable map check here. I simply was trying to make
it not crash during GC. We discussed the issue with Slava. He had an idea to
have a generic safe way to get the map during GC (using a global function
pointer updated by various GC phases). We agreed that this is an overkill here
and decided to add unchecked setters for the GC to use.

http://codereview.chromium.org/3144002/diff/4002/13004
File src/arm/ic-arm.cc (right):

http://codereview.chromium.org/3144002/diff/4002/13004#newcode1143
src/arm/ic-arm.cc:1143: __ ldr(r4, FieldMemOperand(r1,
JSObject::kElementsOffset));
On 2010/08/13 16:50:47, antonm wrote:
> Do we need to load elements, shouldn't they be in r2 already (otherwise
comment
> for GenerateFastArrayLoad should be corrected).

Because of the "has fast elements" bit check we now can get to this code before
even trying to load the elements.

http://codereview.chromium.org/3144002/diff/4002/13029
File src/x64/ic-x64.cc (right):

http://codereview.chromium.org/3144002/diff/4002/13029#newcode640
src/x64/ic-x64.cc:640: __ movq(rcx, FieldOperand(rdx,
JSObject::kElementsOffset));
On 2010/08/13 16:50:47, antonm wrote:
> again looks like rcx should already hold elements.

See above.

[Mads Ager (chromium), 2010-08-16 13:38:04]

LGTM