Implement Array::concat function in C++....

Implement Array::concat function in C++.

The performance of Array::concat is critical of jQuery benchmark from
http://www.dromaeo.com. Our current implementation in JavaScript is very
generic and is several times slower than JSC and SpiderMonkey.

Re-implement Array::concat in C++ to take advantage of underlying implementation
details. This cuts dom-travesal-jquery execution time by half.

We may want to move Array specific implementation into a separate source file,
say jsarray.cc.


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=625

[iposva, 2008-10-25 00:29:19]

An initial set of comments below. I will now look at the newly uploaded
revision.

-Ivan

http://codereview.chromium.org/7990/diff/1/6
File src/array.js (right):

http://codereview.chromium.org/7990/diff/1/6#newcode377
Line 377: var args = $Array(1 + arg_count);
After consulting the spec I see why this works, but it is very, very, very
confusing. Please use "new $Array" instead.

http://codereview.chromium.org/7990/diff/1/6#newcode378
Line 378: var result = $Array();
ditto

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

http://codereview.chromium.org/7990/diff/1/4#newcode3990
Line 3990: class ArrayConcatVisitor {
Comments please.

http://codereview.chromium.org/7990/diff/1/4#newcode4014
Line 4014: static uint32_t VisitElements(Handle<JSObject> receiver,
This function should probably be renamed IterateArrayElements() to avoid
confusion with a real Visitor.
Also please add more general comments about this function please.

http://codereview.chromium.org/7990/diff/1/4#newcode4058
Line 4058: static uint32_t VisitArrayElements(Handle<JSArray> array,
This function should probably be renamed IterateArrayElements.

http://codereview.chromium.org/7990/diff/1/4#newcode4065
Line 4065: List<Handle<JSObject> > objects(kEstimatedPrototypes);
Extra space in "List<Handle<JSObject> >"? Slightly confusing as it tends to read
as a "greater than" operator.

http://codereview.chromium.org/7990/diff/1/4#newcode4067
Line 4067: // Visit prototype first.
You should comment this whole recursion avoidance by adding to an array and
iterating it backwards a bit better.

http://codereview.chromium.org/7990/diff/1/4#newcode4084
Line 4084: static uint32_t VisitArrays(Handle<JSArray> arrays,
This should probably be renamed to IterateArguments, because you really iterate
over the arguments being passed to Array.Concat. Also please adjust the internal
variable names accordingly.

http://codereview.chromium.org/7990/diff/1/4#newcode4140
Line 4140: uint32_t estimate_nof_elements = VisitArrays(arrays, 0);
0 should probably be NULL

[Kasper Lund, 2008-10-27 11:02:19]

Drive by comment:

http://codereview.chromium.org/7990/diff/201/206
File src/array.js (right):

http://codereview.chromium.org/7990/diff/201/206#newcode376
Line 376: // TODO: can we just use arguments?
I think it would work fine with using 'arguments'. You probably have to pass in
the receiver (this) to the %ArrayConcat call as the first parameter, but it
should work and it should be a lot faster than the current code.

[Feng Qian, 2008-10-27 17:35:13]

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

http://codereview.chromium.org/7990/diff/1/4#newcode3990
Line 3990: class ArrayConcatVisitor {
On 2008/10/25 00:29:19, iposva wrote:
> Comments please.

Done.

http://codereview.chromium.org/7990/diff/1/4#newcode4014
Line 4014: static uint32_t VisitElements(Handle<JSObject> receiver,
Renamed to IterateElements.

On 2008/10/25 00:29:19, iposva wrote:
> This function should probably be renamed IterateArrayElements() to avoid
> confusion with a real Visitor.
> Also please add more general comments about this function please.

http://codereview.chromium.org/7990/diff/1/4#newcode4058
Line 4058: static uint32_t VisitArrayElements(Handle<JSArray> array,
On 2008/10/25 00:29:19, iposva wrote:
> This function should probably be renamed IterateArrayElements.

Done.

http://codereview.chromium.org/7990/diff/1/4#newcode4065
Line 4065: List<Handle<JSObject> > objects(kEstimatedPrototypes);
Ok, I saw we use List< Handle<JSObject> > in other places, I will put a space
between <<.
On 2008/10/25 00:29:19, iposva wrote:
> Extra space in "List<Handle<JSObject> >"? Slightly confusing as it tends to
read
> as a "greater than" operator.
>

http://codereview.chromium.org/7990/diff/1/4#newcode4084
Line 4084: static uint32_t VisitArrays(Handle<JSArray> arrays,
On 2008/10/25 00:29:19, iposva wrote:
> This should probably be renamed to IterateArguments, because you really
iterate
> over the arguments being passed to Array.Concat. Also please adjust the
internal
> variable names accordingly.

Done.

http://codereview.chromium.org/7990/diff/1/4#newcode4140
Line 4140: uint32_t estimate_nof_elements = VisitArrays(arrays, 0);
On 2008/10/25 00:29:19, iposva wrote:
> 0 should probably be NULL

Done.

[iposva, 2008-10-27 23:45:50]

More comments to follow in personal discussion. -ip

http://codereview.chromium.org/7990/diff/401/603
File src/runtime.cc (right):

http://codereview.chromium.org/7990/diff/401/603#newcode3996
Line 3996: * whether the storage is a fixed array or storage.
Should probably read:
The second parameter of the constructor, fast_elements, specifies
whether the storage is a FixedArray or a Dictionary.

http://codereview.chromium.org/7990/diff/401/603#newcode4018
Line 4018: bool fast_elements_;
Maybe if you would put the base offset into this visitor then you would not have
to keep passing it around in the iterators below?

http://codereview.chromium.org/7990/diff/401/603#newcode4034
Line 4034: uint32_t visitor_index_offset) {
See comment above about not passing the visitor_index_offset around all the
time...

http://codereview.chromium.org/7990/diff/401/603#newcode4122
Line 4122: * as it is an one-element array.
as it -> as if it

http://codereview.chromium.org/7990/diff/401/603#newcode4137
Line 4137: // Avoid obvious duplicated elements.
Please explain how one could get duplicated elements. My guess is that the
double counting for elements in the prototype chain could have accounted for
more elements than the length itself, correct?

http://codereview.chromium.org/7990/diff/401/603#newcode4184
Line 4184: bool fast_case = estimate_nof_elements * 2 >= result_length;
Please use parens around the arithmetic before the comparison. It makes it much
more readable in my opinion.

[Feng Qian, 2008-10-28 03:28:22]

http://codereview.chromium.org/7990/diff/401/603
File src/runtime.cc (right):

http://codereview.chromium.org/7990/diff/401/603#newcode3996
Line 3996: * whether the storage is a fixed array or storage.
On 2008/10/27 23:45:50, iposva wrote:
> Should probably read:
> The second parameter of the constructor, fast_elements, specifies
> whether the storage is a FixedArray or a Dictionary.

Done.

http://codereview.chromium.org/7990/diff/401/603#newcode4018
Line 4018: bool fast_elements_;
On 2008/10/27 23:45:50, iposva wrote:
> Maybe if you would put the base offset into this visitor then you would not
have
> to keep passing it around in the iterators below?

Done.

http://codereview.chromium.org/7990/diff/401/603#newcode4034
Line 4034: uint32_t visitor_index_offset) {
On 2008/10/27 23:45:50, iposva wrote:
> See comment above about not passing the visitor_index_offset around all the
> time...

Done.

http://codereview.chromium.org/7990/diff/401/603#newcode4122
Line 4122: * as it is an one-element array.
On 2008/10/27 23:45:50, iposva wrote:
> as it -> as if it

Done.

http://codereview.chromium.org/7990/diff/401/603#newcode4137
Line 4137: // Avoid obvious duplicated elements.
Updated. Please check it again.

On 2008/10/27 23:45:50, iposva wrote:
> Please explain how one could get duplicated elements. My guess is that the
> double counting for elements in the prototype chain could have accounted for
> more elements than the length itself, correct?

http://codereview.chromium.org/7990/diff/401/603#newcode4184
Line 4184: bool fast_case = estimate_nof_elements * 2 >= result_length;
On 2008/10/27 23:45:50, iposva wrote:
> Please use parens around the arithmetic before the comparison. It makes it
much
> more readable in my opinion.

Done.

[iposva, 2008-10-28 06:03:47]

LGTMN

-Ivan