Add a fast case to Array.join when all the elements and the separator are fla...

Add a fast case to Array.join when all the elements and the separator are flat ascii strings.

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

[William Hesse, 2010-11-18 11:36:02]

The code in full-codegen and in codegen is identical, except for the start and
end.  Loop2 and Loop3 are also identical.
Should we factor out this identical stuff?

[Lasse Reichstein, 2010-11-18 13:26:54]

LGTM.
Definitly factor out identical loops. They do the same operation: Add a
sequential ASCII string to another sequential ASCII string that is at the tip of
NewSpace.

You could do new-space allocation manually instead of using the macros. I.e.,
don't allocate anything, just write after the end of newspace, and if you
succeed, move the newspace-top to after your data (or move it during processing,
and move it back if you fail).
It might be easier than remembering the padding during processing. You just need
to pad the result at the end.

This can bail out after any amount of work. Could it be worth checking the array
elements first, and only start copying if they are all sequential ASCII strings?
(Then you could know the total length too).

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6682: __ push(scratch);
You do four pushes of an unknown value. You might as well subtract 4 *
kPointerSize from esp. 
At least it'll be 5 bytes shorter.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6693: 1 << Map::kHasFastElements);
Should this be "testb" and should there be a jump if it's zero?

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6696: __ sar(scratch, 1);
You use sar here, but shr later, to convert from Smi to int.
Pick either one.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6703: __ mov(array_length, scratch);
It's impossible to distinguish named registers from named Operands. Could you
name the operands somehow to make it easier to see that this is a
mov(Operand,Register)?

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6713: // Check that the separator is a flat ascii
string.
ASCII is an acronym :)

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6769: __ jmp(&copy_loop_1_entry);
How about a conditional jump here, if zero: jump to line 6779?
It only happens when the first string of the array is empty.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6773: times_1, SeqAsciiString::kHeaderSize));
Indentation.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6795: __ mov(current_string_length,
You should definitly extract the "append seq-ASCII string to existing seq-ASCII
string at NewSpace-end" macro and use that for both separator and array
elements.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6803: __ neg(new_padding_chars);
You negate new_padding_chars, and then use them in a subtraction. If you stored
their negated value, and added it instead, you would save the negation.
Instead of "padding", you could call it something with "offset from end" :)

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6827: Operand(current_string, current_string_length,
times_1, 0));
Indentation.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6829: scratch);
Indentation.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6852: //   extend result by length(current)
Capitalize "E" in "extend". Comments are/should be sentences.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6894: __ bind(&bailout);
If you bail out to here after having allocated the first time, you leak the
allocated memory. You could undo the allocation by rolling the newspace-top back
to the allocation. 
E.g., have a bailout_and_free before the bailout label, and call that after the
first allocation.

[William Hesse, 2010-11-18 17:13:03]

Most changes made.  Works on all platforms now.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6682: __ push(scratch);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> You do four pushes of an unknown value. You might as well subtract 4 *
> kPointerSize from esp. 
> At least it'll be 5 bytes shorter.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6693: 1 << Map::kHasFastElements);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> Should this be "testb" and should there be a jump if it's zero?

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6696: __ sar(scratch, 1);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> You use sar here, but shr later, to convert from Smi to int.
> Pick either one.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6703: __ mov(array_length, scratch);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> It's impossible to distinguish named registers from named Operands. Could you
> name the operands somehow to make it easier to see that this is a
> mov(Operand,Register)?

If an assembly operation compiles, it means the same thing whether it is a
memory operand or a register.  So the type is not important.  And prefixes would
make the variable names more confusing.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6713: // Check that the separator is a flat ascii
string.
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> ASCII is an acronym :)

We use both ASCII and ascii in comments.  ascii is used more often.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6769: __ jmp(&copy_loop_1_entry);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> How about a conditional jump here, if zero: jump to line 6779?
> It only happens when the first string of the array is empty.

That would require another label.  The current behavior is correct, if not
optimal.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6773: times_1, SeqAsciiString::kHeaderSize));
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> Indentation.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6795: __ mov(current_string_length,
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> You should definitly extract the "append seq-ASCII string to existing
seq-ASCII
> string at NewSpace-end" macro and use that for both separator and array
> elements.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6803: __ neg(new_padding_chars);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> You negate new_padding_chars, and then use them in a subtraction. If you
stored
> their negated value, and added it instead, you would save the negation.
> Instead of "padding", you could call it something with "offset from end" :)

I would like to do this fix in a separate change.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6827: Operand(current_string, current_string_length,
times_1, 0));
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> Indentation.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6829: scratch);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> Indentation.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6852: //   extend result by length(current)
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> Capitalize "E" in "extend". Comments are/should be sentences.

Done.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6894: __ bind(&bailout);
On 2010/11/18 13:26:54, Lasse Reichstein wrote:
> If you bail out to here after having allocated the first time, you leak the
> allocated memory. You could undo the allocation by rolling the newspace-top
back
> to the allocation. 
> E.g., have a bailout_and_free before the bailout label, and call that after
the
> first allocation.

This would be a good fix for a later improved version.  I also think that
computing the length, and checking the types of all the strings first, would be
a good idea, and make the code simpler.

[Lasse Reichstein, 2010-11-18 17:49:09]

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6703: __ mov(array_length, scratch);
But they are not equivalent. I was about to suggest that you used array_length
in the calculations above, instead of using scratch and then moving scratch to
array_length ... until I realized that array_length was an Operand.

Reading what's written doesn't need distinguishing, but understanding why it's
written as it is, does.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6769: __ jmp(&copy_loop_1_entry);
You wouldn't need the entry label then, so the label count is the same.
Go for optimal! Great isn't good enough! :)

[William Hesse, 2010-11-19 08:53:43]

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc
File src/ia32/codegen-ia32.cc (right):

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6703: __ mov(array_length, scratch);
That is if you are reading it with a plan to change it or improve it, in which
case you should be aware of the register shortage, and the need to put specific
things in registers.

But this can be changed when it is rewritten with a separate checking and
counting loop, an allocation, and a copying loop.  Taking the allocation out of
the loops frees up a lot of variables.

On 2010/11/18 17:49:09, Lasse Reichstein wrote:
> But they are not equivalent. I was about to suggest that you used array_length
> in the calculations above, instead of using scratch and then moving scratch to
> array_length ... until I realized that array_length was an Operand.
> 
> Reading what's written doesn't need distinguishing, but understanding why it's
> written as it is, does.

http://codereview.chromium.org/5122005/diff/11001/src/ia32/codegen-ia32.cc#ne...
src/ia32/codegen-ia32.cc:6769: __ jmp(&copy_loop_1_entry);
On 2010/11/18 17:49:09, Lasse Reichstein wrote:
> You wouldn't need the entry label then, so the label count is the same.
> Go for optimal! Great isn't good enough! :)

Done.