From 945673574e9eaf61635ef294265669c64526ae5e Mon Sep 17 00:00:00 2001
From: "vitalyr@chromium.org"
 <vitalyr@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 25 Feb 2010 12:49:23 +0000
Subject: [PATCH] Improve string runtime compare performance for flat strings.

Review URL: http://codereview.chromium.org/650058

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3949 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/objects.h  |  4 ----
 src/runtime.cc | 76 +++++++++++++++++++++++++++++++++++++++++++++++-----------
 src/utils.h    | 36 ++++++++++++++++++++++++----
 3 files changed, 94 insertions(+), 22 deletions(-)

diff --git a/src/objects.h b/src/objects.h
index 7533892..9d4cfd6 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -4051,10 +4051,6 @@ class SeqString: public String {
   // Casting.
   static inline SeqString* cast(Object* obj);
 
-  // Dispatched behaviour.
-  // For regexp code.
-  uint16_t* SeqStringGetTwoByteAddress();
-
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(SeqString);
 };
diff --git a/src/runtime.cc b/src/runtime.cc
index 6e85034..b589645 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -4593,6 +4593,66 @@ static Object* Runtime_SmiLexicographicCompare(Arguments args) {
 }
 
 
+static Object* StringInputBufferCompare(String* x, String* y) {
+  static StringInputBuffer bufx;
+  static StringInputBuffer bufy;
+  bufx.Reset(x);
+  bufy.Reset(y);
+  while (bufx.has_more() && bufy.has_more()) {
+    int d = bufx.GetNext() - bufy.GetNext();
+    if (d < 0) return Smi::FromInt(LESS);
+    else if (d > 0) return Smi::FromInt(GREATER);
+  }
+
+  // x is (non-trivial) prefix of y:
+  if (bufy.has_more()) return Smi::FromInt(LESS);
+  // y is prefix of x:
+  return Smi::FromInt(bufx.has_more() ? GREATER : EQUAL);
+}
+
+
+static Object* FlatStringCompare(String* x, String* y) {
+  ASSERT(x->IsFlat());
+  ASSERT(y->IsFlat());
+  Object* equal_prefix_result = Smi::FromInt(EQUAL);
+  int prefix_length = x->length();
+  if (y->length() < prefix_length) {
+    prefix_length = y->length();
+    equal_prefix_result = Smi::FromInt(GREATER);
+  } else if (y->length() > prefix_length) {
+    equal_prefix_result = Smi::FromInt(LESS);
+  }
+  int r;
+  if (x->IsAsciiRepresentation()) {
+    Vector<const char> x_chars = x->ToAsciiVector();
+    if (y->IsAsciiRepresentation()) {
+      Vector<const char> y_chars = y->ToAsciiVector();
+      r = memcmp(x_chars.start(), y_chars.start(), prefix_length);
+    } else {
+      Vector<const uc16> y_chars = y->ToUC16Vector();
+      r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
+    }
+  } else {
+    Vector<const uc16> x_chars = x->ToUC16Vector();
+    if (y->IsAsciiRepresentation()) {
+      Vector<const char> y_chars = y->ToAsciiVector();
+      r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
+    } else {
+      Vector<const uc16> y_chars = y->ToUC16Vector();
+      r = CompareChars(x_chars.start(), y_chars.start(), prefix_length);
+    }
+  }
+  Object* result;
+  if (r == 0) {
+    result = equal_prefix_result;
+  } else {
+    result = (r < 0) ? Smi::FromInt(LESS) : Smi::FromInt(GREATER);
+  }
+  ASSERT(result == StringInputBufferCompare(x, y));
+  return result;
+}
+
+
 static Object* Runtime_StringCompare(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 2);
@@ -4618,20 +4678,8 @@ static Object* Runtime_StringCompare(Arguments args) {
   x->TryFlattenIfNotFlat();
   y->TryFlattenIfNotFlat();
 
-  static StringInputBuffer bufx;
-  static StringInputBuffer bufy;
-  bufx.Reset(x);
-  bufy.Reset(y);
-  while (bufx.has_more() && bufy.has_more()) {
-    int d = bufx.GetNext() - bufy.GetNext();
-    if (d < 0) return Smi::FromInt(LESS);
-    else if (d > 0) return Smi::FromInt(GREATER);
-  }
-
-  // x is (non-trivial) prefix of y:
-  if (bufy.has_more()) return Smi::FromInt(LESS);
-  // y is prefix of x:
-  return Smi::FromInt(bufx.has_more() ? GREATER : EQUAL);
+  return (x->IsFlat() && y->IsFlat()) ? FlatStringCompare(x, y)
+                                      : StringInputBufferCompare(x, y);
 }
 
 
diff --git a/src/utils.h b/src/utils.h
index 2fcd241..2cad4c1 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -528,11 +528,11 @@ static inline void CopyChars(sinkchar* dest, const sourcechar* src, int chars) {
   sinkchar* limit = dest + chars;
 #ifdef V8_HOST_CAN_READ_UNALIGNED
   if (sizeof(*dest) == sizeof(*src)) {
-    // Number of characters in a uint32_t.
-    static const int kStepSize = sizeof(uint32_t) / sizeof(*dest);  // NOLINT
+    // Number of characters in a uintptr_t.
+    static const int kStepSize = sizeof(uintptr_t) / sizeof(*dest);  // NOLINT
     while (dest <= limit - kStepSize) {
-      *reinterpret_cast<uint32_t*>(dest) =
-          *reinterpret_cast<const uint32_t*>(src);
+      *reinterpret_cast<uintptr_t*>(dest) =
+          *reinterpret_cast<const uintptr_t*>(src);
       dest += kStepSize;
       src += kStepSize;
     }
@@ -544,6 +544,34 @@ static inline void CopyChars(sinkchar* dest, const sourcechar* src, int chars) {
 }
 
 
+// Compare ASCII/16bit chars to ASCII/16bit chars.
+template <typename lchar, typename rchar>
+static inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) {
+  const lchar* limit = lhs + chars;
+#ifdef V8_HOST_CAN_READ_UNALIGNED
+  if (sizeof(*lhs) == sizeof(*rhs)) {
+    // Number of characters in a uintptr_t.
+    static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs);  // NOLINT
+    while (lhs <= limit - kStepSize) {
+      if (*reinterpret_cast<const uintptr_t*>(lhs) !=
+          *reinterpret_cast<const uintptr_t*>(rhs)) {
+        break;
+      }
+      lhs += kStepSize;
+      rhs += kStepSize;
+    }
+  }
+#endif
+  while (lhs < limit) {
+    int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
+    if (r != 0) return r;
+    ++lhs;
+    ++rhs;
+  }
+  return 0;
+}
+
+
 // Calculate 10^exponent.
 int TenToThe(int exponent);
 
-- 
2.7.4