Add a fast case for one-element arrays in ArrayJoin

Add a fast case for one-element arrays in ArrayJoin

This case handles all one-element arrays that were not handled by _FastOneByteArrayJoin

BUG=
R=yangguo@chromium.org

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

[fmeawad, 2014-09-26 00:52:12]

fmeawad@chromium.org changed reviewers:
+ yangguo@chromium.org

[fmeawad, 2014-09-26 00:52:12]

PTAL.

[fmeawad, 2014-09-26 18:18:43]

On 2014/09/26 00:52:34, fmeawad-cr wrote:

A micro-benchmark that motivates adding the fast path is 

for (var j = 0; j < 100000; j++){
  for(var i = 0; i < 100; i++) {
    new Array('Do Something ' + i).join('');
  }
}

where a consistent 30% speedup is observed.

Without the fast path, It attempts FastOneByteArrayJoin and fails since the
string is a CONS_ONE_BYTE_STRING_TYPE, then it goes in Join, where it fails the
Sparse Array check, then hits the one element fast case in Join.

[arv (Not doing code reviews), 2014-09-29 18:42:13]

On 2014/09/26 18:18:43, fmeawad-cr wrote:
> On 2014/09/26 00:52:34, fmeawad-cr wrote:
> 
> A micro-benchmark that motivates adding the fast path is 
> 
> for (var j = 0; j < 100000; j++){
>   for(var i = 0; i < 100; i++) {
>     new Array('Do Something ' + i).join('');
>   }
> }
> 
> where a consistent 30% speedup is observed.
> 
> Without the fast path, It attempts FastOneByteArrayJoin and fails since the
> string is a CONS_ONE_BYTE_STRING_TYPE, then it goes in Join, where it fails
the
> Sparse Array check, then hits the one element fast case in Join.

How much slower is this case?

for (var j = 0; j < 100000; j++){
  for(var i = 0; i < 100; i++) {
    [42].join('');
  }
}

and what about this one?

for (var j = 0; j < 100000; j++){
  for(var i = 0; i < 100; i++) {
    ['a', 'b'].join('');
  }
}

[fmeawad, 2014-09-29 21:27:09]

Thanks arv@ for the extra test cases.

I moved the added fast path below the FastOneByteArrayJoin
Once we make the Join call, we incur a high overhead, so any branch check
overhead added by this patch is undetectable from noise.

As follow are the numbers without then with the patch
['Do Something ' + i].join('');	4.424	0.444	(-98.47%)
[42].join('');			4.6	0.377	(-92.02%)
['a', 'b'].join('');		0.368	0.359	(-0.28%)

Average of 10 runs, stddev is very small except for the last case where the real
change is theoretically and practically 0%.

(Changed the tests to [].join('') instead of new Array().join(''), apparently
"new Array()" can use some optimizations as well)

[fmeawad, 2014-09-29 21:35:04]

Minor calculations error

['Do Something ' + i].join('');	4.424	0.444	(-89.91%)
[42].join('');			4.6	0.377	(-91.81%)
['a', 'b'].join('');		0.368	0.359	(-1.03%)

[arv (Not doing code reviews), 2014-09-29 22:09:41]

arv@chromium.org changed reviewers:
+ arv@chromium.org

[arv (Not doing code reviews), 2014-09-29 22:09:42]

-1% for the common case but ~10x improvement for the edge case. I think that is
reasonable.

If we really want to make this fast (like SpiderMonkey) we should generate code
for it. I'm actually surprised that we are not doing this already since
Array.prototype.join is such common pattern for string builders.

https://codereview.chromium.org/607503004/diff/60001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/607503004/diff/60001/src/array.js#newcode383
src/array.js:383: var e = array[0];
Maybe:

if (length === 1) return TO_STRING_INLINE(array[0]);

[fmeawad, 2014-09-29 23:37:47]

PTAL.

https://codereview.chromium.org/607503004/diff/60001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/607503004/diff/60001/src/array.js#newcode383
src/array.js:383: var e = array[0];
On 2014/09/29 22:09:42, arv wrote:
> Maybe:
> 
> if (length === 1) return TO_STRING_INLINE(array[0]);

That will not work, we need to check for null and undefined, as they have a
different behavior under join (they return '' instead of 'null' and 'undefined'
respectively,
it is also 2X slower for strings, 20% slower for numbers and boolean.

But I took your advice, now all length === 1 are handled here.

[Yang, 2014-09-30 08:41:40]

I was able to observe the 30% improvement, but not the 10x improvement you wrote
about later. Is there something I'm missing?

https://codereview.chromium.org/607503004/diff/80001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode386
src/array.js:386: if (IS_NUMBER(e)) return %_NumberToString(e);
Aside from the null or undefined case, this part shares a lot of the code in
NonStringToString (src/runtime.js). Can we omit the number and boolean case and
leave it to NonStringToString? Or is it somehow desirable to inline those two
cases?

https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode388
src/array.js:388: return NonStringToString(array[0]);
e instead of array[0].

GVN will be able to recognize that it's the same, but in unoptimized code this
will make a slight difference. Also, with accessors, loading the element a
second time would be observable.

[fmeawad, 2014-09-30 14:49:53]

> I  was able to observe the 30% improvement, but not the 10x improvement you
wrote
> about later. Is there something I'm missing?

Have you switched the "new Array(...).join('')"  to "[...].join('')"

PTAL.

https://codereview.chromium.org/607503004/diff/80001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode386
src/array.js:386: if (IS_NUMBER(e)) return %_NumberToString(e);
On 2014/09/30 08:41:40, Yang wrote:
> Aside from the null or undefined case, this part shares a lot of the code in
> NonStringToString (src/runtime.js). Can we omit the number and boolean case
and
> leave it to NonStringToString? Or is it somehow desirable to inline those two
> cases?

I tried what you said, for a String, a NonStringToString probably does not know
that it is a string, and it takes 2x as much.
For Numbers and booleans NonStringToString is 20% slower than inlining it here.
I guess we can afford the 20% for cleanness and then Optimize NonStringToString
later. WDYT?

https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode388
src/array.js:388: return NonStringToString(array[0]);
On 2014/09/30 08:41:40, Yang wrote:
> e instead of array[0].
> 
> GVN will be able to recognize that it's the same, but in unoptimized code this
> will make a slight difference. Also, with accessors, loading the element a
> second time would be observable.

Was a typo, fixed.

[Yang, 2014-09-30 14:59:16]

On 2014/09/30 14:49:53, fmeawad-cr wrote:
> > I  was able to observe the 30% improvement, but not the 10x improvement you
> wrote
> > about later. Is there something I'm missing?
> 
> Have you switched the "new Array(...).join('')"  to "[...].join('')"
> 
> PTAL.
> 
> https://codereview.chromium.org/607503004/diff/80001/src/array.js
> File src/array.js (right):
> 
> https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode386
> src/array.js:386: if (IS_NUMBER(e)) return %_NumberToString(e);
> On 2014/09/30 08:41:40, Yang wrote:
> > Aside from the null or undefined case, this part shares a lot of the code in
> > NonStringToString (src/runtime.js). Can we omit the number and boolean case
> and
> > leave it to NonStringToString? Or is it somehow desirable to inline those
two
> > cases?
> 
> I tried what you said, for a String, a NonStringToString probably does not
know
> that it is a string, and it takes 2x as much.
> For Numbers and booleans NonStringToString is 20% slower than inlining it
here.
> I guess we can afford the 20% for cleanness and then Optimize
NonStringToString
> later. WDYT?
> 
> https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode388
> src/array.js:388: return NonStringToString(array[0]);
> On 2014/09/30 08:41:40, Yang wrote:
> > e instead of array[0].
> > 
> > GVN will be able to recognize that it's the same, but in unoptimized code
this
> > will make a slight difference. Also, with accessors, loading the element a
> > second time would be observable.
> 
> Was a typo, fixed.

lgtm.

[fmeawad, 2014-09-30 14:59:41]

PTAL.

https://codereview.chromium.org/607503004/diff/80001/src/array.js
File src/array.js (right):

https://codereview.chromium.org/607503004/diff/80001/src/array.js#newcode386
src/array.js:386: if (IS_NUMBER(e)) return %_NumberToString(e);
On 2014/09/30 14:49:52, fmeawad-cr wrote:
> On 2014/09/30 08:41:40, Yang wrote:
> > Aside from the null or undefined case, this part shares a lot of the code in
> > NonStringToString (src/runtime.js). Can we omit the number and boolean case
> and
> > leave it to NonStringToString? Or is it somehow desirable to inline those
two
> > cases?
> 
> I tried what you said, for a String, a NonStringToString probably does not
know
> that it is a string, and it takes 2x as much.
> For Numbers and booleans NonStringToString is 20% slower than inlining it
here.
> I guess we can afford the 20% for cleanness and then Optimize
NonStringToString
> later. WDYT?

Based on our offline discussion, we will remove handling numbers and Booleans
not to duplicate NonStringToString functionality

[Yang, 2014-09-30 15:07:30]

Committed patchset #7 (id:120001) manually as 24334 (presubmit successful).

[arv (Not doing code reviews), 2014-09-30 15:38:39]

LGTM