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

src/objects.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 510 matching lines @@
     case kConsStringTag: {
       ConsString* cs = ConsString::cast(this);
       if (String::cast(cs->second())->length() == 0) {
         return this;
       }
       // There's little point in putting the flat string in new space if the
       // cons string is in old space.  It can never get GCed until there is
       // 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;
     }
     default:
       return this;
   }
 }
 
 
@@ skipping 2315 matching lines @@
   TryFlatten();
   Access<StringInputBuffer> buffer(&string_input_buffer);
   buffer->Reset(0, this);
   int result = 0;
   while (buffer->has_more())
     result += unibrow::Utf8::Length(buffer->GetNext());
   return result;
 }
 
 
-Vector<const char> String::ToAsciiVector() {
+Vector<const byte> String::ToAsciiVector() {
   ASSERT(IsAsciiRepresentation());
   ASSERT(IsFlat());
 
   int offset = 0;
   int length = this->length();
   StringRepresentationTag string_tag = representation_tag();
   String* string = this;
   if (string_tag == kSlicedStringTag) {
       SlicedString* sliced = SlicedString::cast(string);
       offset += sliced->start();
       string = String::cast(sliced->buffer());
       string_tag = string->representation_tag();
   } else if (string_tag == kConsStringTag) {
       ConsString* cons = ConsString::cast(string);
       ASSERT(String::cast(cons->second())->length() == 0);
       string = String::cast(cons->first());
       string_tag = string->representation_tag();
   }
   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);
 }
 
 
 Vector<const uc16> String::ToUC16Vector() {
   ASSERT(IsTwoByteStringRepresentation());
   ASSERT(IsFlat());
 
   int offset = 0;
   int length = this->length();
   StringRepresentationTag string_tag = representation_tag();
@@ skipping 640 matching lines @@
   String* buf = String::cast(buffer());
   ASSERT(!buf->StringIsSlicedString());
   if (buf->StringIsConsString()) {
     Object* ok = buf->Flatten();
     if (ok->IsFailure()) return ok;
   }
   return this;
 }
 
 
-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;
           }
           to -= boundary;
           source = String::cast(cons_string->second());
         } else {
           // Left hand side is longer.  Recurse over right.  The hasher
           // needs us to visit the string from left to right so doing
           // 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;
     }
   }
 }
 
 
 void SlicedString::SlicedStringIterateBody(ObjectVisitor* v) {
   IteratePointer(v, kBufferOffset);
 }
 
 
@@ skipping 49 matching lines @@
 }
 
 
 static StringInputBuffer string_compare_buffer_b;
 
 
 template <typename IteratorA>
 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 {
     string_compare_buffer_b.Reset(0, b);
     return CompareStringContents(ia, &string_compare_buffer_b);
   }
 }
 
 
 static StringInputBuffer string_compare_buffer_a;
@@ skipping 13 matching lines @@
 
   if (this->IsSeqAsciiString() && other->IsSeqAsciiString()) {
     const char* str1 = SeqAsciiString::cast(this)->GetChars();
     const char* str2 = SeqAsciiString::cast(other)->GetChars();
     return CompareRawStringContents(Vector<const char>(str1, len),
                                     Vector<const char>(str2, len));
   }
 
   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);
       }
     } else {
       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);
       }
     }
   } else {
     string_compare_buffer_a.Reset(0, this);
     return CompareStringContentsPartial(&string_compare_buffer_a, other);
   }
 }
 
@@ skipping 2710 matching lines @@
   // No break point.
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 
 
 } }  // namespace v8::internal