Improve string runtime compare performance for flat strings.

src/runtime.cc

 // Copyright 2006-2009 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 4575 matching lines @@
     if (diff != 0) return Smi::FromInt(diff);
   }
 
   // If one array is a suffix of the other array, the longest array is
   // the representation of the largest of the Smis in the
   // lexicographic ordering.
   return Smi::FromInt(x_index - y_index);
 }
 
 
+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* Runtime_StringCompare(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 2);
 
   CONVERT_CHECKED(String, x, args[0]);
   CONVERT_CHECKED(String, y, args[1]);
 
   Counters::string_compare_runtime.Increment();
 
   // A few fast case tests before we flatten.
   if (x == y) return Smi::FromInt(EQUAL);
   if (y->length() == 0) {
     if (x->length() == 0) return Smi::FromInt(EQUAL);
     return Smi::FromInt(GREATER);
   } else if (x->length() == 0) {
     return Smi::FromInt(LESS);
   }
 
   int d = x->Get(0) - y->Get(0);
   if (d < 0) return Smi::FromInt(LESS);
   else if (d > 0) return Smi::FromInt(GREATER);
 
   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);
+  if (x->IsFlat() && y->IsFlat()) {

[Søren Thygesen Gjesse, 2010/02/22 10:14:00]

How about moving the body of this if into a function, e.g. FlatStringCompare?

And make it into an if/else.

[Vitaly Repeshko, 2010/02/25 12:50:10]

Done.

+    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);

[Søren Thygesen Gjesse, 2010/02/22 10:14:00]

There is a wmemcmp in wchar.h - don't know if it makes sense to use it here.

[Vitaly Repeshko, 2010/02/25 12:50:10]

I'm worried about variations in wchar_t definitions.

+      }
+    }
+    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;
   }
 
-  // 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 StringInputBufferCompare(x, y);
 }
 
 
 static Object* Runtime_Math_abs(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 1);
 
   CONVERT_DOUBLE_CHECKED(x, args[0]);
   return Heap::AllocateHeapNumber(fabs(x));
 }
@@ skipping 3619 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     Counters::gc_last_resort_from_js.Increment();
     Heap::CollectAllGarbage(false);
   }
 }
 
 
 } }  // namespace v8::internal