Converted String.prototype.split with string to C++.

Converted String.prototype.split with string to C++.

[Lasse Reichstein, 2010-03-11 11:41:31]

Fairly simple review.

[Vitaly Repeshko, 2010-03-11 14:02:36]

LGTM.

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

http://codereview.chromium.org/875001/diff/1/2#newcode2087
src/runtime.cc:2087: struct StringMatchState {
Consider making this a class and moving BoyerMoore variants initialization here
to methods like SwitchToBoyerMoore*(pattern, start).

http://codereview.chromium.org/875001/diff/1/2#newcode2089
src/runtime.cc:2089: StringMatchState(int pattern_length)
explicit

http://codereview.chromium.org/875001/diff/1/2#newcode2199
src/runtime.cc:2199: int badness;
It might be less fragile to use state->badness directly below.

http://codereview.chromium.org/875001/diff/1/2#newcode4256
src/runtime.cc:4256: 
Too many empty lines.

http://codereview.chromium.org/875001/diff/1/2#newcode4264
src/runtime.cc:4264: unsigned int max_split) {
unsigned int is dangerous. Can we just use int here?

http://codereview.chromium.org/875001/diff/1/2#newcode4280
src/runtime.cc:4280: void inline FindStringIndices(Vector<const schar> subject,
FindCharIndices?

http://codereview.chromium.org/875001/diff/1/2#newcode4283
src/runtime.cc:4283: unsigned int max_split) {
See above.

http://codereview.chromium.org/875001/diff/1/2#newcode4302
src/runtime.cc:4302: CONVERT_NUMBER_CHECKED(uint32_t, max_split, Uint32,
args[2]);
Why not use the name from spec and from string.js ("limit")?

http://codereview.chromium.org/875001/diff/1/2#newcode4314
src/runtime.cc:4314: int initial_capacity =
Can this be simplified to Min<uint32_t>(kMaxInitialListCapacity, max_split)?

http://codereview.chromium.org/875001/diff/1/2#newcode4375
src/runtime.cc:4375: HandleScope localLoopHandle;
noCamelCasePlease.

http://codereview.chromium.org/875001/diff/1/2#newcode4379
src/runtime.cc:4379: elements->set(i, *substring, UPDATE_WRITE_BARRIER);
UPDATE_WRITE_BARRIER is the default.

[Erik Corry, 2010-03-12 10:08:03]

LGTM

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

http://codereview.chromium.org/875001/diff/1/2#newcode2088
src/runtime.cc:2088: enum State { SIMPLE, BOYER_MOORE_HORSEPOOL, BOYER_MOORE };
Poor Mr. Horspool :-(

http://codereview.chromium.org/875001/diff/1/2#newcode2120
src/runtime.cc:2120: static void BoyerMoorePopulateGoodSuffixTable(
What is the purpose of this change?

http://codereview.chromium.org/875001/diff/1/2#newcode2306
src/runtime.cc:2306: schar pattern_char,
Indentation.

http://codereview.chromium.org/875001/diff/1/2#newcode4259
src/runtime.cc:4259: 
Too many blank lines.

http://codereview.chromium.org/875001/diff/1/2#newcode4266
src/runtime.cc:4266: // Stop after finding at most max_split values.
If max_split == 0 has a special meaning then a comment should reflect that.

http://codereview.chromium.org/875001/diff/1/2#newcode4302
src/runtime.cc:4302: CONVERT_NUMBER_CHECKED(uint32_t, max_split, Uint32,
args[2]);
Does this have a fast case for Smis to avoid the double-conversion round trip.

http://codereview.chromium.org/875001/diff/1/2#newcode4336
src/runtime.cc:4336: FindStringIndices(subject_vector, pattern->ToAsciiVector(),
Per discussion yesterday we prefer 1 argument per line in the case where they
don't all fit on one line.

[Lasse Reichstein, 2010-03-12 11:08:27]

Addressed comments.
I couldn't find an easy way to restore performance of the critical inner loops
of the BM and BMH algorithms, so I reverted them to the original.
That means that badness isn't cumulative over consecutive runs.
I also refactored the search functions to allow consecutive calls to avoid
repeating an initial overhead.

We should try to see if we can introduce a cumulative badness in a later patch,
but for now, this should be no worse, at worst, than what we did from
JavaScript.

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

http://codereview.chromium.org/875001/diff/1/2#newcode2087
src/runtime.cc:2087: struct StringMatchState {
I was actually considering dropping the struct entirely and just having the
badness and algorithm as static variables.
It's used completely single threaded, so there should be no problem in that.

This change has caused a 20% regression in a single benchmark that relies almost
entirely on indexOf with longer strings, so it seems I have thrown the carefully
balanced timing of the search algorithms out of whack.
I'll try a few alternatives to see if I can restore the timing in that case as
well.

http://codereview.chromium.org/875001/diff/1/2#newcode2088
src/runtime.cc:2088: enum State { SIMPLE, BOYER_MOORE_HORSEPOOL, BOYER_MOORE };
Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode2089
src/runtime.cc:2089: StringMatchState(int pattern_length)
Well spotted.

http://codereview.chromium.org/875001/diff/1/2#newcode2120
src/runtime.cc:2120: static void BoyerMoorePopulateGoodSuffixTable(
There was at some point an extra parameter that couldn't fit on the line. I.e.,
nothing. Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode2199
src/runtime.cc:2199: int badness;
I'll try it, but I seem to remember that the badness variable was critical to
performance when the algorithm was created.

http://codereview.chromium.org/875001/diff/1/2#newcode2306
src/runtime.cc:2306: schar pattern_char,
Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode4256
src/runtime.cc:4256: 
Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode4264
src/runtime.cc:4264: unsigned int max_split) {
Sadly not (not in a simple way at least).
The limit is passed from JavaScript, where it is created using TO_UINT32, and
defaulting to 0xffffffffu.

In practice, we can probably make the limit lower, since we don't allow strings
that are this long, but I'd prefer to keep it to make it easier to argue for
correctness.

http://codereview.chromium.org/875001/diff/1/2#newcode4266
src/runtime.cc:4266: // Stop after finding at most max_split values.
No special meaning. It's just a counter, a limit on the number of parts we need
to find.
In fact, the value will never be zero initially when we get here. ASSERT added.

http://codereview.chromium.org/875001/diff/1/2#newcode4280
src/runtime.cc:4280: void inline FindStringIndices(Vector<const schar> subject,
Done.

http://codereview.chromium.org/875001/diff/1/2#newcode4302
src/runtime.cc:4302: CONVERT_NUMBER_CHECKED(uint32_t, max_split, Uint32,
args[2]);
Good point. Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode4302
src/runtime.cc:4302: CONVERT_NUMBER_CHECKED(uint32_t, max_split, Uint32,
args[2]);
It does.

http://codereview.chromium.org/875001/diff/1/2#newcode4314
src/runtime.cc:4314: int initial_capacity =
It could. With no extra casts, even. Amazing.

http://codereview.chromium.org/875001/diff/1/2#newcode4336
src/runtime.cc:4336: FindStringIndices(subject_vector, pattern->ToAsciiVector(),
Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode4375
src/runtime.cc:4375: HandleScope localLoopHandle;
Fixed.

http://codereview.chromium.org/875001/diff/1/2#newcode4379
src/runtime.cc:4379: elements->set(i, *substring, UPDATE_WRITE_BARRIER);
Removed.

[Erik Corry, 2010-03-15 12:57:48]

LGTM

Presumably we have a test for the case where the pattern is "".

http://codereview.chromium.org/875001/diff/9001/10001
File src/runtime.cc (right):

http://codereview.chromium.org/875001/diff/9001/10001#newcode2270
src/runtime.cc:2270: // If we could just break out of the for loop here.
What would then happen?

http://codereview.chromium.org/875001/diff/9001/10001#newcode2476
src/runtime.cc:2476: // FALLTHROUGH.
Does the linter insist on this annoying capitalization?

http://codereview.chromium.org/875001/diff/9001/10003
File src/string.js (right):

http://codereview.chromium.org/875001/diff/9001/10003#newcode560
src/string.js:560: // and KJS have this behavior only when no separator is
given.  If
!@*%$