Improvement to SmiLexicalCompare

src/runtime.cc

Index: src/runtime.cc
===================================================================
--- src/runtime.cc	(revision 8424)
+++ src/runtime.cc	(working copy)
@@ -45,6 +45,7 @@
 #include "json-parser.h"
 #include "liveedit.h"
 #include "liveobjectlist-inl.h"
+#include "misc-intrinsics.h"
 #include "parser.h"
 #include "platform.h"
 #include "runtime-profiler.h"
@@ -6647,7 +6648,7 @@
   // If the integers are equal so are the string representations.
   if (x_value == y_value) return Smi::FromInt(EQUAL);
 
-  // If one of the integers are zero the normal integer order is the
+  // If one of the integers is zero the normal integer order is the
   // same as the lexicographic order of the string representations.
   if (x_value == 0 || y_value == 0) return Smi::FromInt(x_value - y_value);
 
@@ -6661,36 +6662,47 @@
     y_value = -y_value;
   }
 
-  // Arrays for the individual characters of the two Smis.  Smis are
-  // 31 bit integers and 10 decimal digits are therefore enough.
-  // TODO(isolates): maybe we should simply allocate 20 bytes on the stack.
-  int* x_elms = isolate->runtime_state()->smi_lexicographic_compare_x_elms();
-  int* y_elms = isolate->runtime_state()->smi_lexicographic_compare_y_elms();
+  static const int powersOf10[] = { 1, 10, 100, 1000, 10*1000, 100*1000,

[Erik Corry, 2011/06/25 11:12:03]

This is a constant so it should be named as a constant:  kPowersOf10.
Also, the indentation is wrong.  Newline-after { is the norm in the rest of the
code base and } gets its own line.

[sra1, 2011/06/25 19:31:33]

Done.

+                                    1000*1000, 10*1000*1000, 100*1000*1000,
+                                    1000*1000*1000 };
 
+  // If the integers have the same number of decimal digits they can be
+  // compared directly as the numeric order is the same as the
+  // lexicographic order.  If one integer has fewer digits, it is scaled
+  // by some power of 10 to have the same number of digits as the longer
+  // integer.  If the scaled integers are equal it means the shorter
+  // integer comes first in the lexicographic order.
 
-  // Convert the integers to arrays of their decimal digits.
-  int x_index = 0;
-  int y_index = 0;
-  while (x_value > 0) {
-    x_elms[x_index++] = x_value % 10;
+  // From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+  int x_log2 = IntegerLog2(x_value);
+  int x_log10 = ((x_log2 + 1) * 1233) >> 12;
+  x_log10 -= x_value < powersOf10[x_log10];
+
+  int y_log2 = IntegerLog2(y_value);
+  int y_log10 = ((y_log2 + 1) * 1233) >> 12;
+  y_log10 -= y_value < powersOf10[y_log10];
+
+  int tie = EQUAL;
+
+  if (x_log10 < y_log10) {
+    // X has fewer digits.  We would like to simply scale up X but that
+    // might overflow, e.g when comparing 9 with 1_000_000_000, 9 would
+    // be scaled up to 9_000_000_000. So we scale up by the next
+    // smallest power and scale down Y to drop one digit. It is OK to
+    // drop one digit from the longer integer since the final digit is
+    // past the length of the shorter integer.
+    x_value *= powersOf10[y_log10 - x_log10 - 1];
+    y_value /= 10;
+    tie = LESS;
+  } else if (y_log10 < x_log10) {
+    y_value *= powersOf10[x_log10 - y_log10 - 1];
     x_value /= 10;
+    tie = GREATER;
   }
-  while (y_value > 0) {
-    y_elms[y_index++] = y_value % 10;
-    y_value /= 10;
-  }
 
-  // Loop through the arrays of decimal digits finding the first place
-  // where they differ.
-  while (--x_index >= 0 && --y_index >= 0) {
-    int diff = x_elms[x_index] - y_elms[y_index];
-    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);
+  if (x_value < y_value) return Smi::FromInt(LESS);
+  if (x_value > y_value) return Smi::FromInt(GREATER);
+  return Smi::FromInt(tie);
 }