Use direct copy and templates to speed up flattening of strings.

src/objects.cc

Index: src/objects.cc
===================================================================
--- src/objects.cc	(revision 535)
+++ src/objects.cc	(working copy)
@@ -528,12 +528,28 @@
       // an old space GC.
       PretenureFlag tenure = Heap::InNewSpace(this) ? NOT_TENURED : TENURED;
       int len = length();
-      Object* object = IsAsciiRepresentation() ?
-          Heap::AllocateRawAsciiString(len, tenure) :
-          Heap::AllocateRawTwoByteString(len, tenure);
-      if (object->IsFailure()) return object;
-      String* result = String::cast(object);
-      Flatten(this, result, 0, len, 0);
+      Object* object;
+      String* result;
+      if (IsAsciiRepresentation()) {
+        object = Heap::AllocateRawAsciiString(len, tenure);
+        if (object->IsFailure()) return object;
+        result = String::cast(object);
+        String* first = String::cast(cs->first());
+        int first_length = first->length();
+        byte* dest = SeqAsciiString::cast(result)->GetCharsAddress();
+        WriteToFlat(first, dest, 0, first_length);
+        WriteToFlat(String::cast(cs->second()), dest + first_length, 0, len - first_length);
+      } else {
+        object = Heap::AllocateRawTwoByteString(len, tenure);
+        if (object->IsFailure()) return object;
+        result = String::cast(object);
+        uc16* dest = reinterpret_cast<uc16*>(
+            SeqTwoByteString::cast(result)->GetCharsAddress());

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Maybe add an accessor on seq two byte string that returns its chars viewed under
the right type.  I expect we could use that in other places too.

[Erik Corry, 2008/10/22 11:59:48]

Good idea.

+        String* first = String::cast(cs->first());
+        int first_length = first->length();
+        WriteToFlat(first, dest, 0, first_length);
+        WriteToFlat(String::cast(cs->second()), dest + first_length, 0, len - first_length);
+      }
       cs->set_first(result);
       cs->set_second(Heap::empty_string());
       return this;
@@ -2869,7 +2885,7 @@
 }
 
 
-Vector<const char> String::ToAsciiVector() {
+Vector<const byte> String::ToAsciiVector() {
   ASSERT(IsAsciiRepresentation());
   ASSERT(IsFlat());
 
@@ -2890,13 +2906,13 @@
   }
   if (string_tag == kSeqStringTag) {
     SeqAsciiString* seq = SeqAsciiString::cast(string);
-    char* start = reinterpret_cast<char*>(seq->GetCharsAddress());
-    return Vector<const char>(start + offset, length);
+    byte* start = seq->GetCharsAddress();
+    return Vector<const byte>(start + offset, length);
   }
   ASSERT(string_tag == kExternalStringTag);
   ExternalAsciiString* ext = ExternalAsciiString::cast(string);
-  const char* start = ext->resource()->data();
-  return Vector<const char>(start + offset, length);
+  const byte* start = reinterpret_cast<const byte*>(ext->resource()->data());

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Bleh.  Why not stick with char?

[Erik Corry, 2008/10/22 11:59:48]

Done

+  return Vector<const byte>(start + offset, length);
 }
 
 
@@ -3557,47 +3573,87 @@
 }
 
 
-void String::Flatten(String* src,
-                     String* sink,
-                     int f,
-                     int t,
-                     int so) {
+// Assumes that if the sink is ASCII then the src will also be ASCII
+// representation (not just ASCII in a 16 bit string).
+template <typename sinkchar>
+void String::WriteToFlat(String* src,
+                         sinkchar* sink,
+                         int f,
+                         int t) {
   String* source = src;
   int from = f;
   int to = t;
-  int sink_offset = so;
   while (true) {
     ASSERT(0 <= from && from <= to && to <= source->length());
-    ASSERT(0 <= sink_offset && sink_offset < sink->length());
-    switch (source->representation_tag()) {
-      case kSeqStringTag:
-      case kExternalStringTag: {
-        Access<StringInputBuffer> buffer(&string_input_buffer);
-        buffer->Reset(from, source);
-        int j = sink_offset;
-        for (int i = from; i < to; i++) {
-          uc32 c = buffer->GetNext();
-          sink->Set(j++, c);
+    switch (source->full_representation_tag()) {
+      case kAsciiStringTag + kExternalStringTag: {
+        if (sizeof(sinkchar) == 1) {
+          memcpy(

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Could this be simplified by using a template-ified memcpy with a specialization
for each character type?

[Erik Corry, 2008/10/22 11:59:48]

Done.

+              sink,
+              ExternalAsciiString::cast(source)->resource()->data() + from,
+              to - from);
+        } else {
+          Cpy168(
+              sink,
+              // Sign cast.
+              reinterpret_cast<const byte*>(
+                  ExternalAsciiString::cast(source)->resource()->data()) +
+                from,
+              to - from);
         }
         return;
       }
-      case kSlicedStringTag: {
+      case kTwoByteStringTag + kExternalStringTag: {

[Christian Plesner Hansen, 2008/10/21 14:16:22]

If | gives the same result as + we should use that instead -- but maybe it
doesn't?

[Erik Corry, 2008/10/22 11:59:48]

Done

+        ASSERT(sizeof(sinkchar) == 2);
+        memcpy(
+            sink,
+            ExternalTwoByteString::cast(source)->resource()->data() + (from << 1),
+            (to - from) << 1);
+        return;
+      }
+      case kAsciiStringTag + kSeqStringTag: {
+        if (sizeof(sinkchar) == 1) {
+          const byte* src =

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Isn't this the branch where we can memcpy?  Source is a sequential ascii string
and sizeof(sinkchar) is 1.

[Erik Corry, 2008/10/22 11:59:48]

The non-memcpy may be marginally faster, but this is removed in the new version.

+              SeqAsciiString::cast(source)->GetCharsAddress() + from;
+          const byte* end = src - from + to;
+          while (src < end) {
+            *sink++ = *src++;
+          }
+        } else {
+          Cpy168(

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Conversely, this looks to me like we're memcpying from a seq ascii string into
an uc16 array.

[Erik Corry, 2008/10/22 11:59:48]

Gone in new version.

+              sink,
+              SeqAsciiString::cast(source)->GetCharsAddress() + from,
+              to - from);
+        }
+        return;
+      }
+      case kTwoByteStringTag + kSeqStringTag: {
+        ASSERT(sizeof(sinkchar) == 2);
+        memcpy(
+            sink,
+            SeqTwoByteString::cast(source)->GetCharsAddress() + (from << 1),
+            (to - from) << 1);
+        return;
+      }
+      case kAsciiStringTag + kSlicedStringTag:
+      case kTwoByteStringTag + kSlicedStringTag: {
         SlicedString* sliced_string = SlicedString::cast(source);
         int start = sliced_string->start();
         from += start;
         to += start;
         source = String::cast(sliced_string->buffer());
+        break;
       }
-      break;
-      case kConsStringTag: {
+      case kAsciiStringTag + kConsStringTag:
+      case kTwoByteStringTag + kConsStringTag: {
         ConsString* cons_string = ConsString::cast(source);
         String* first = String::cast(cons_string->first());
         int boundary = first->length();
-        if (to - boundary >= boundary - from) {
+        if (boundary < 64 || to - boundary >= boundary - from) {

[Christian Plesner Hansen, 2008/10/21 14:16:22]

Magic number.  Please define a constant.

[Erik Corry, 2008/10/22 11:59:48]

I got rid of this optimization because I found a test failure and the fix would
probably deoptimize the optimization.

           // Right hand side is longer.  Recurse over left.
           if (from < boundary) {
-            Flatten(first, sink, from, boundary, sink_offset);
-            sink_offset += boundary - from;
+            WriteToFlat(first, sink, from, boundary);
+            sink += boundary - from;
             from = 0;
           } else {
             from -= boundary;
@@ -3610,17 +3666,16 @@
           // this invalidates that hash.
           if (to > boundary) {
             String* second = String::cast(cons_string->second());
-            Flatten(second,
-                    sink,
-                    0,
-                    to - boundary,
-                    sink_offset + boundary - from);
+            WriteToFlat(second,
+                        sink + boundary - from,
+                        0,
+                        to - boundary);
             to = boundary;
           }
           source = first;
         }
+        break;
       }
-      break;
     }
   }
 }
@@ -3690,10 +3745,10 @@
 static inline bool CompareStringContentsPartial(IteratorA* ia, String* b) {
   if (b->IsFlat()) {
     if (b->IsAsciiRepresentation()) {
-      VectorIterator<char> ib(b->ToAsciiVector());
+      VectorIterator<const byte> ib(b->ToAsciiVector());

[Christian Plesner Hansen, 2008/10/21 14:16:22]

There's no need to explicitly add 'const' to a Vector iterator.  A
VectorIterator<T> holds a Vector<const T>.

[Erik Corry, 2008/10/22 11:59:48]

OK

       return CompareStringContents(ia, &ib);
     } else {
-      VectorIterator<uc16> ib(b->ToUC16Vector());
+      VectorIterator<const uc16> ib(b->ToUC16Vector());
       return CompareStringContents(ia, &ib);
     }
   } else {
@@ -3727,18 +3782,18 @@
 
   if (this->IsFlat()) {
     if (this->IsAsciiRepresentation()) {
-      Vector<const char> vec1 = this->ToAsciiVector();
+      Vector<const byte> vec1 = this->ToAsciiVector();
       if (other->IsFlat()) {
         if (other->IsAsciiRepresentation()) {
-          Vector<const char> vec2 = other->ToAsciiVector();
+          Vector<const byte> vec2 = other->ToAsciiVector();
           return CompareRawStringContents(vec1, vec2);
         } else {
-          VectorIterator<char> buf1(vec1);
-          VectorIterator<uc16> ib(other->ToUC16Vector());
+          VectorIterator<const byte> buf1(vec1);
+          VectorIterator<const uc16> ib(other->ToUC16Vector());
           return CompareStringContents(&buf1, &ib);
         }
       } else {
-        VectorIterator<char> buf1(vec1);
+        VectorIterator<const byte> buf1(vec1);
         string_compare_buffer_b.Reset(0, other);
         return CompareStringContents(&buf1, &string_compare_buffer_b);
       }
@@ -3746,15 +3801,15 @@
       Vector<const uc16> vec1 = this->ToUC16Vector();
       if (other->IsFlat()) {
         if (other->IsAsciiRepresentation()) {
-          VectorIterator<uc16> buf1(vec1);
-          VectorIterator<char> ib(other->ToAsciiVector());
+          VectorIterator<const uc16> buf1(vec1);
+          VectorIterator<const byte> ib(other->ToAsciiVector());
           return CompareStringContents(&buf1, &ib);
         } else {
           Vector<const uc16> vec2(other->ToUC16Vector());
           return CompareRawStringContents(vec1, vec2);
         }
       } else {
-        VectorIterator<uc16> buf1(vec1);
+        VectorIterator<const uc16> buf1(vec1);
         string_compare_buffer_b.Reset(0, other);
         return CompareStringContents(&buf1, &string_compare_buffer_b);
       }