Improvement to SmiLexicalCompare

src/runtime.cc

 // Copyright 2011 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 27 matching lines @@
 #include "cpu.h"
 #include "dateparser-inl.h"
 #include "debug.h"
 #include "deoptimizer.h"
 #include "execution.h"
 #include "global-handles.h"
 #include "jsregexp.h"
 #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"
 #include "runtime.h"
 #include "scopeinfo.h"
 #include "smart-pointer.h"
 #include "string-search.h"
 #include "stub-cache.h"
 #include "v8threads.h"
 #include "vm-state-inl.h"
@@ skipping 6582 matching lines @@
 
   // Extract the integer values from the Smis.
   CONVERT_CHECKED(Smi, x, args[0]);
   CONVERT_CHECKED(Smi, y, args[1]);
   int x_value = x->value();
   int y_value = y->value();
 
   // 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);
+  if (x_value == 0 || y_value == 0)
+    return Smi::FromInt(x_value < y_value ? LESS : GREATER);
 
   // If only one of the integers is negative the negative number is
   // smallest because the char code of '-' is less than the char code
   // of any digit.  Otherwise, we make both values positive.
+
+  // Use unsigned values otherwise the logic is incorrect for -MIN_INT on
+  // architectures using 32-bit Smis.
+  uint32_t x_scaled = x_value;
+  uint32_t y_scaled = y_value;
   if (x_value < 0 || y_value < 0) {
     if (y_value >= 0) return Smi::FromInt(LESS);
     if (x_value >= 0) return Smi::FromInt(GREATER);
-    x_value = -x_value;
-    y_value = -y_value;
+    x_scaled = -x_value;
+    y_scaled = -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 uint32_t kPowersOf10[] = {
+    1, 10, 100, 1000, 10*1000, 100*1000,
+    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;
-    x_value /= 10;
-  }
-  while (y_value > 0) {
-    y_elms[y_index++] = y_value % 10;
-    y_value /= 10;
+  // From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
+  int x_log2 = IntegerLog2(x_scaled);
+  int x_log10 = ((x_log2 + 1) * 1233) >> 12;
+  x_log10 -= x_scaled < kPowersOf10[x_log10];
+
+  int y_log2 = IntegerLog2(y_scaled);
+  int y_log10 = ((y_log2 + 1) * 1233) >> 12;
+  y_log10 -= y_scaled < kPowersOf10[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_scaled *= kPowersOf10[y_log10 - x_log10 - 1];
+    y_scaled /= 10;
+    tie = LESS;
+  } else if (y_log10 < x_log10) {
+    y_scaled *= kPowersOf10[x_log10 - y_log10 - 1];
+    x_scaled /= 10;
+    tie = GREATER;
   }
 
-  // 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_scaled < y_scaled) return Smi::FromInt(LESS);
+  if (x_scaled > y_scaled) return Smi::FromInt(GREATER);
+  return Smi::FromInt(tie);
 }
 
 
 static Object* StringInputBufferCompare(RuntimeState* state,
                                         String* x,
                                         String* y) {
   StringInputBuffer& bufx = *state->string_input_buffer_compare_bufx();
   StringInputBuffer& bufy = *state->string_input_buffer_compare_bufy();
   bufx.Reset(x);
   bufy.Reset(y);
@@ skipping 5779 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     isolate->counters()->gc_last_resort_from_js()->Increment();
     isolate->heap()->CollectAllGarbage(false);
   }
 }
 
 
 } }  // namespace v8::internal