Leverage Lasse's StringSearch object to speed up calculations of script ...

Leverage Lasse's StringSearch object to speed up calculations of script 
line ends. 

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

[sandholm, 2010-11-17 15:22:18]

Next step is to use the FixedArrayBuilder to only search through each script
once instead of twice. Let's first see if this change has any performance
impact, though.

[mnaganov (inactive), 2010-11-17 15:32:00]

LGTM with comments

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc#newcode509
src/handles.cc:509: Handle<FixedArray> CalculateLineEnds(Vector<const
SourceChar> src,
Please mark this private function 'static'.

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc#newcode554
src/handles.cc:554: if (seq_src->IsConsString()) seq_src =
ConsString::cast(seq_src)->first();
Should you assert anything about the second part of cons string? Must it be
empty or something?

[sandholm, 2010-11-17 15:45:23]

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc#newcode509
src/handles.cc:509: Handle<FixedArray> CalculateLineEnds(Vector<const
SourceChar> src,
On 2010/11/17 15:32:00, Michail Naganov wrote:
> Please mark this private function 'static'.

Done.

http://codereview.chromium.org/5100002/diff/3001/src/handles.cc#newcode554
src/handles.cc:554: if (seq_src->IsConsString()) seq_src =
ConsString::cast(seq_src)->first();
On 2010/11/17 15:32:00, Michail Naganov wrote:
> Should you assert anything about the second part of cons string? Must it be
> empty or something?

Yes. src is flat so if it is a cons string then the second part must be empty.

[Lasse Reichstein, 2010-11-18 08:11:47]

LGTM.

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode510
src/handles.cc:510: bool with_last_line) {
I wonder whether this function is performance critical or not.

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode518
src/handles.cc:518: position = search.Search(src, position);
Not calling Runtime::StringMatch is good (it's an "externally visible" function,
so it shouldn't be reused).

However, if the function is performance critical, this seems overkill for a
single-character string.
It will always do the "SingleCharSearch", which boils down to something like:
 int index;
 if (sizeof(SourceChar) == 1) { 
   char* pos = reinterpret_cast<char*>(
         memchr(src.start() + position, '\n', src.length()));
   index = pos ? static_cast<, n = , n = int>(pos - src.start()) : -1;
 } else { 
   ASSERT(sizeof(SourceChar) == 2);
   int n = src.length();
   for (index = position; index < n; index++) {
     if (src[i] == '\n') {
       break;
     }
   }
   if (index == n) index = -1;
 }

(not tested!)

I'd rather inline thee code, or extract it from SingleCharSearch to a static
function/template that can be called from outside the string-search object as
well.

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode528
src/handles.cc:528: // Pass 2: Fill in line ends positions
On the other hand, if the function isn't performance critical, then doing two
iterations to first find the count and then collect the values seems overly
complex, compared to just collecting the values in a List or Collector during
the first iteration.
Performance-wise it also seems like doing double the work in iteration instead
double the work copying the result afterwards.
It does save (C-heap) memory, though.

[sandholm, 2010-11-18 08:39:10]

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode510
src/handles.cc:510: bool with_last_line) {
On 2010/11/18 08:11:47, Lasse Reichstein wrote:
> I wonder whether this function is performance critical or not.

Me too. Let's see what happens.

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode518
src/handles.cc:518: position = search.Search(src, position);
On 2010/11/18 08:11:47, Lasse Reichstein wrote:
> Not calling Runtime::StringMatch is good (it's an "externally visible"
function,
> so it shouldn't be reused).
> 
> However, if the function is performance critical, this seems overkill for a
> single-character string.
> It will always do the "SingleCharSearch", which boils down to something like:
>  int index;
>  if (sizeof(SourceChar) == 1) { 
>    char* pos = reinterpret_cast<char*>(
>          memchr(src.start() + position, '\n', src.length()));
>    index = pos ? static_cast<, n = , n = int>(pos - src.start()) : -1;
>  } else { 
>    ASSERT(sizeof(SourceChar) == 2);
>    int n = src.length();
>    for (index = position; index < n; index++) {
>      if (src[i] == '\n') {
>        break;
>      }
>    }
>    if (index == n) index = -1;
>  }
> 
> (not tested!)
> 
> I'd rather inline thee code, or extract it from SingleCharSearch to a static
> function/template that can be called from outside the string-search object as
> well.

Makes sense. If there is any performance gain from this change, I'll inline in
another change.

http://codereview.chromium.org/5100002/diff/7001/src/handles.cc#newcode528
src/handles.cc:528: // Pass 2: Fill in line ends positions
On 2010/11/18 08:11:47, Lasse Reichstein wrote:
> On the other hand, if the function isn't performance critical, then doing two
> iterations to first find the count and then collect the values seems overly
> complex, compared to just collecting the values in a List or Collector during
> the first iteration.
> Performance-wise it also seems like doing double the work in iteration instead
> double the work copying the result afterwards.
> It does save (C-heap) memory, though.

Agree. That's why I suggested using Fixed ArrayBuilder as a next step. Sounds
like using a List or Collector would be even better.