Specialized string equality based on representation

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 504 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 = IsAscii() ?
+      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);
       cs->set_first(result);
       cs->set_second(Heap::empty_string());
       return this;
     }
     default:
@@ skipping 212 matching lines @@
 
 
 int HeapObject::SlowSizeFromMap(Map* map) {
   // Avoid calling functions such as FixedArray::cast during GC, which
   // read map pointer of this object again.
   InstanceType instance_type = map->instance_type();
 
   if (instance_type < FIRST_NONSTRING_TYPE
       && (reinterpret_cast<String*>(this)->map_representation_tag(map)
           == kSeqStringTag)) {
-    if (reinterpret_cast<String*>(this)->is_ascii_map(map)) {
-      return reinterpret_cast<AsciiString*>(this)->AsciiStringSize(map);
+    if (reinterpret_cast<String*>(this)->is_ascii_representation_map(map)) {
+      return reinterpret_cast<SeqAsciiString*>(this)->AsciiStringSize(map);
     } else {
-      return reinterpret_cast<TwoByteString*>(this)->TwoByteStringSize(map);
+      return reinterpret_cast<SeqTwoByteString*>(this)->TwoByteStringSize(map);
     }
   }
 
   switch (instance_type) {
     case FIXED_ARRAY_TYPE:
       return reinterpret_cast<FixedArray*>(this)->FixedArraySize();
     case BYTE_ARRAY_TYPE:
       return reinterpret_cast<ByteArray*>(this)->ByteArraySize();
     case CODE_TYPE:
       return reinterpret_cast<Code*>(this)->CodeSize();
@@ skipping 2191 matching lines @@
     case kSlicedStringTag:
     case kExternalStringTag:
       return true;
     default:
       return false;
   }
 }
 
 
 int String::Utf8Length() {
-  if (is_ascii()) return length();
+  if (is_ascii_representation()) return length();
   // Attempt to flatten before accessing the string.  It probably
   // doesn't make Utf8Length faster, but it is very likely that
   // the string will be accessed later (for example by WriteUtf8)
   // so it's still a good idea.
   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() {
+  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);
+  }
+  ASSERT(string_tag == kExternalStringTag);
+  ExternalAsciiString* ext = ExternalAsciiString::cast(string);
+  const char* start = ext->resource()->data();
+  return Vector<const char>(start + offset, length);
+}
+
+
+Vector<const uc16> String::ToUC16Vector() {
+  ASSERT(IsTwoByteStringRepresentation());
+  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) {
+    SeqTwoByteString* seq = SeqTwoByteString::cast(string);
+    uc16* start = reinterpret_cast<uc16*>(seq->GetCharsAddress());
+    return Vector<const uc16>(start + offset, length);
+  }
+  ASSERT(string_tag == kExternalStringTag);
+  ExternalTwoByteString* ext = ExternalTwoByteString::cast(string);
+  const uc16* start =
+      reinterpret_cast<const uc16*>(ext->resource()->data());
+  return Vector<const uc16>(start + offset, length);
+}
+
+
 SmartPointer<char> String::ToCString(AllowNullsFlag allow_nulls,
                                      RobustnessFlag robust_flag,
                                      int offset,
                                      int length,
                                      int* length_return) {
   ASSERT(NativeAllocationChecker::allocation_allowed());
   if (robust_flag == ROBUST_STRING_TRAVERSAL && !LooksValid()) {
     return SmartPointer<char>(NULL);
   }
 
@@ skipping 46 matching lines @@
   return ToCString(allow_nulls, robust_flag, 0, -1, length_return);
 }
 
 
 const uc16* String::GetTwoByteData() {
   return GetTwoByteData(0);
 }
 
 
 const uc16* String::GetTwoByteData(unsigned start) {
-  ASSERT(!IsAscii());
+  ASSERT(!IsAsciiRepresentation());
   switch (representation_tag()) {
     case kSeqStringTag:
-      return TwoByteString::cast(this)->TwoByteStringGetData(start);
+      return SeqTwoByteString::cast(this)->TwoByteStringGetData(start);
     case kExternalStringTag:
       return ExternalTwoByteString::cast(this)->
         ExternalTwoByteStringGetData(start);
     case kSlicedStringTag: {
       SlicedString* sliced_string = SlicedString::cast(this);
       String* buffer = String::cast(sliced_string->buffer());
       if (buffer->StringIsConsString()) {
         ConsString* cons_string = ConsString::cast(buffer);
         // Flattened string.
         ASSERT(String::cast(cons_string->second())->length() == 0);
@@ skipping 25 matching lines @@
   int i = 0;
   while (buffer->has_more()) {
     uint16_t character = buffer->GetNext();
     result[i++] = character;
   }
   result[i] = 0;
   return SmartPointer<uc16>(result);
 }
 
 
-const uc16* TwoByteString::TwoByteStringGetData(unsigned start) {
+const uc16* SeqTwoByteString::TwoByteStringGetData(unsigned start) {
   return reinterpret_cast<uc16*>(
       reinterpret_cast<char*>(this) - kHeapObjectTag + kHeaderSize) + start;
 }
 
 
-void TwoByteString::TwoByteStringReadBlockIntoBuffer(ReadBlockBuffer* rbb,
+void SeqTwoByteString::TwoByteStringReadBlockIntoBuffer(ReadBlockBuffer* rbb,
                                                      unsigned* offset_ptr,
                                                      unsigned max_chars) {
   unsigned chars_read = 0;
   unsigned offset = *offset_ptr;
   while (chars_read < max_chars) {
     uint16_t c = *reinterpret_cast<uint16_t*>(
         reinterpret_cast<char*>(this) -
             kHeapObjectTag + kHeaderSize + offset * kShortSize);
     if (c <= kMaxAsciiCharCode) {
       // Fast case for ASCII characters.   Cursor is an input output argument.
@@ skipping 12 matching lines @@
       }
     }
     offset++;
     chars_read++;
   }
   *offset_ptr = offset;
   rbb->remaining += chars_read;
 }
 
 
-const unibrow::byte* AsciiString::AsciiStringReadBlock(unsigned* remaining,
+const unibrow::byte* SeqAsciiString::AsciiStringReadBlock(unsigned* remaining,
                                                        unsigned* offset_ptr,
                                                        unsigned max_chars) {
   // Cast const char* to unibrow::byte* (signedness difference).
   const unibrow::byte* b = reinterpret_cast<unibrow::byte*>(this) -
       kHeapObjectTag + kHeaderSize + *offset_ptr * kCharSize;
   *remaining = max_chars;
   *offset_ptr += max_chars;
   return b;
 }
 
@@ skipping 141 matching lines @@
         break;
     }
     offset++;
     chars_read++;
   }
   *offset_ptr = offset;
   rbb->remaining += chars_read;
 }
 
 
-void AsciiString::AsciiStringReadBlockIntoBuffer(ReadBlockBuffer* rbb,
+void SeqAsciiString::AsciiStringReadBlockIntoBuffer(ReadBlockBuffer* rbb,
                                                  unsigned* offset_ptr,
                                                  unsigned max_chars) {
   unsigned capacity = rbb->capacity - rbb->cursor;
   if (max_chars > capacity) max_chars = capacity;
   memcpy(rbb->util_buffer + rbb->cursor,
          reinterpret_cast<char*>(this) - kHeapObjectTag + kHeaderSize +
              *offset_ptr * kCharSize,
          max_chars);
   rbb->remaining += max_chars;
   *offset_ptr += max_chars;
@@ skipping 24 matching lines @@
                                        ReadBlockBuffer* rbb,
                                        unsigned* offset_ptr,
                                        unsigned max_chars) {
   ASSERT(*offset_ptr <= static_cast<unsigned>(input->length()));
   if (max_chars == 0) {
     rbb->remaining = 0;
     return NULL;
   }
   switch (input->representation_tag()) {
     case kSeqStringTag:
-      if (input->is_ascii()) {
-        return AsciiString::cast(input)->AsciiStringReadBlock(&rbb->remaining,
+      if (input->is_ascii_representation()) {
+        return SeqAsciiString::cast(input)->AsciiStringReadBlock(&rbb->remaining,
                                                               offset_ptr,
                                                               max_chars);
       } else {
-        TwoByteString::cast(input)->TwoByteStringReadBlockIntoBuffer(rbb,
+        SeqTwoByteString::cast(input)->TwoByteStringReadBlockIntoBuffer(rbb,
                                                                      offset_ptr,
                                                                      max_chars);
         return rbb->util_buffer;
       }
     case kConsStringTag:
       return ConsString::cast(input)->ConsStringReadBlock(rbb,
                                                           offset_ptr,
                                                           max_chars);
     case kSlicedStringTag:
       return SlicedString::cast(input)->SlicedStringReadBlock(rbb,
                                                               offset_ptr,
                                                               max_chars);
     case kExternalStringTag:
-      if (input->is_ascii()) {
+      if (input->is_ascii_representation()) {
         return ExternalAsciiString::cast(input)->ExternalAsciiStringReadBlock(
             &rbb->remaining,
             offset_ptr,
             max_chars);
       } else {
         ExternalTwoByteString::cast(input)->
             ExternalTwoByteStringReadBlockIntoBuffer(rbb,
                                                      offset_ptr,
                                                      max_chars);
         return rbb->util_buffer;
@@ skipping 23 matching lines @@
 // to fill up a buffer.
 void String::ReadBlockIntoBuffer(String* input,
                                  ReadBlockBuffer* rbb,
                                  unsigned* offset_ptr,
                                  unsigned max_chars) {
   ASSERT(*offset_ptr <= (unsigned)input->length());
   if (max_chars == 0) return;
 
   switch (input->representation_tag()) {
     case kSeqStringTag:
-      if (input->is_ascii()) {
-        AsciiString::cast(input)->AsciiStringReadBlockIntoBuffer(rbb,
+      if (input->is_ascii_representation()) {
+        SeqAsciiString::cast(input)->AsciiStringReadBlockIntoBuffer(rbb,
                                                                  offset_ptr,
                                                                  max_chars);
         return;
       } else {
-        TwoByteString::cast(input)->TwoByteStringReadBlockIntoBuffer(rbb,
+        SeqTwoByteString::cast(input)->TwoByteStringReadBlockIntoBuffer(rbb,
                                                                      offset_ptr,
                                                                      max_chars);
         return;
       }
     case kConsStringTag:
       ConsString::cast(input)->ConsStringReadBlockIntoBuffer(rbb,
                                                              offset_ptr,
                                                              max_chars);
       return;
     case kSlicedStringTag:
       SlicedString::cast(input)->SlicedStringReadBlockIntoBuffer(rbb,
                                                                  offset_ptr,
                                                                  max_chars);
       return;
     case kExternalStringTag:
-      if (input->is_ascii()) {
+      if (input->is_ascii_representation()) {
          ExternalAsciiString::cast(input)->
              ExternalAsciiStringReadBlockIntoBuffer(rbb, offset_ptr, max_chars);
        } else {
          ExternalTwoByteString::cast(input)->
              ExternalTwoByteStringReadBlockIntoBuffer(rbb,
                                                       offset_ptr,
                                                       max_chars);
        }
        return;
     default:
@@ skipping 236 matching lines @@
 }
 
 
 uint16_t SlicedString::SlicedStringGet(int index) {
   ASSERT(index >= 0 && index < this->length());
   // Delegate to the buffer string.
   return String::cast(buffer())->Get(start() + index);
 }
 
 
+template <typename IteratorA, typename IteratorB>
+static inline bool CompareStringContents(IteratorA* ia, IteratorB* ib) {
+  // General slow case check.  We know that the ia and ib iterators
+  // have the same length.
+  while (ia->has_more()) {
+    uc32 ca = ia->GetNext();
+    uc32 cb = ib->GetNext();
+    if (ca != cb)
+      return false;
+  }
+  return true;
+}
+
+
+static StringInputBuffer string_compare_buffer_b;
+
+
+template <typename IteratorA>
+static inline bool CompareStringContentsPartial(IteratorA* ia, String* b) {
+  if (b->IsFlat()) {
+    if (b->IsAsciiRepresentation()) {
+      VectorIterator<const char> ib(b->ToAsciiVector());
+      return CompareStringContents(ia, &ib);
+    } else {
+      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;
+
+
 bool String::SlowEquals(String* other) {
   // Fast check: negative check with lengths.
   int len = length();
   if (len != other->length()) return false;
   if (len == 0) return true;
 
   // Fast check: if hash code is computed for both strings
   // a fast negative check can be performed.
   if (HasHashCode() && other->HasHashCode()) {
     if (Hash() != other->Hash()) return false;
   }
 
-  // Fast case: avoid input buffers for small strings.
-  const int kMaxLenthForFastCaseCheck = 5;
-  for (int i = 0; i < kMaxLenthForFastCaseCheck; i++) {
-    if (Get(i) != other->Get(i)) return false;
-    if (i + 1 == len) return true;
+  if (this->IsFlat()) {
+    if (this->IsAsciiRepresentation()) {
+      VectorIterator<const char> buf1(this->ToAsciiVector());
+      return CompareStringContentsPartial(&buf1, other);
+    } else {
+      VectorIterator<const uc16> buf1(this->ToUC16Vector());
+      return CompareStringContentsPartial(&buf1, other);
+    }
+  } else {
+    string_compare_buffer_a.Reset(0, this);
+    return CompareStringContentsPartial(&string_compare_buffer_a, other);
   }
-
-  // General slow case check.
-  static StringInputBuffer buf1;
-  static StringInputBuffer buf2;
-  buf1.Reset(kMaxLenthForFastCaseCheck, this);
-  buf2.Reset(kMaxLenthForFastCaseCheck, other);
-  while (buf1.has_more()) {
-    if (buf1.GetNext() != buf2.GetNext()) {
-      return false;
-    }
-  }
-  return true;
 }
 
 
 bool String::MarkAsUndetectable() {
   if (this->IsSymbol()) return false;
 
   Map* map = this->map();
   if (map == Heap::short_string_map()) {
     this->set_map(Heap::undetectable_short_string_map());
     return true;
@@ skipping 2713 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