Optimize inner-loop in JSON.stringify.

src/json-stringifier.h

 // Copyright 2012 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 41 matching lines @@
   template <bool is_ascii> void Extend();
 
   void ChangeEncoding();
 
   void ShrinkCurrentPart();
 
   template <bool is_ascii, typename Char>
   INLINE(void Append_(Char c));
 
   template <bool is_ascii, typename Char>
-  INLINE(void AppendUnchecked_(Char c));
-
-  template <bool is_ascii, typename Char>
   INLINE(void Append_(const Char* chars));
 
-  template <bool is_ascii, typename Char>
-  INLINE(void AppendUnchecked_(const Char* chars));
-
   INLINE(void Append(char c)) {
     if (is_ascii_) {
       Append_<true>(c);
     } else {
       Append_<false>(c);
     }
   }
 
   INLINE(void Append(const char* chars)) {
     if (is_ascii_) {
@@ skipping 36 matching lines @@
   INLINE(Result SerializeDouble(double number));
   INLINE(Result SerializeHeapNumber(Handle<HeapNumber> object)) {
     return SerializeDouble(object->value());
   }
 
   Result SerializeArray(Handle<JSArray> object);
   Result SerializeObject(Handle<JSObject> object);
 
   void SerializeString(Handle<String> object);
 
+  template <typename SrcChar, typename DestChar>
+  INLINE(void SerializeStringUnchecked_(const SrcChar* src,
+                                        DestChar* dest,
+                                        int length));
+
   template <bool is_ascii, typename Char>
   INLINE(void SerializeString_(Vector<const Char> vector,
                                Handle<String> string));
 
   template <typename Char>
+  INLINE(bool DoNotEscape(Char c));
+
+  template <typename Char>
   INLINE(Vector<const Char> GetCharVector(Handle<String> string));
 
   INLINE(Result StackPush(Handle<Object> object));
   INLINE(void StackPop());
 
   INLINE(Handle<String> accumulator()) {
     return Handle<String>(String::cast(accumulator_store_->value()));
   }
 
   INLINE(void set_accumulator(Handle<String> string)) {
     return accumulator_store_->set_value(*string);
   }
 
   Isolate* isolate_;
   // We use a value wrapper for the string accumulator to keep the
   // (indirect) handle to it in the outermost handle scope.
   Handle<JSValue> accumulator_store_;
   Handle<String> current_part_;
   Handle<String> tojson_symbol_;
   Handle<JSArray> stack_;
   int current_index_;
   int part_length_;
   bool is_ascii_;
 
-  static const int kJsonQuotesCharactersPerEntry = 8;
-  static const char* const JsonQuotes;
+  static const int kJsonEscapeTableEntrySize = 8;
+  static const char* const JsonEscapeTable;
 };
 
 
-const char* const BasicJsonStringifier::JsonQuotes =
+// Translation table to escape ASCII characters.
+// Table entries start at a multiple of 8 and are null-terminated.
+const char* const BasicJsonStringifier::JsonEscapeTable =
     "\\u0000\0 \\u0001\0 \\u0002\0 \\u0003\0 "
     "\\u0004\0 \\u0005\0 \\u0006\0 \\u0007\0 "
     "\\b\0     \\t\0     \\n\0     \\u000b\0 "
     "\\f\0     \\r\0     \\u000e\0 \\u000f\0 "
     "\\u0010\0 \\u0011\0 \\u0012\0 \\u0013\0 "
     "\\u0014\0 \\u0015\0 \\u0016\0 \\u0017\0 "
     "\\u0018\0 \\u0019\0 \\u001a\0 \\u001b\0 "
     "\\u001c\0 \\u001d\0 \\u001e\0 \\u001f\0 "
     " \0      !\0      \\\"\0     #\0      "
     "$\0      %\0      &\0      '\0      "
@@ skipping 58 matching lines @@
         current_index_++, c);
   } else {
     SeqTwoByteString::cast(*current_part_)->SeqTwoByteStringSet(
         current_index_++, c);
   }
   if (current_index_ == part_length_) Extend<is_ascii>();
 }
 
 
 template <bool is_ascii, typename Char>
-void BasicJsonStringifier::AppendUnchecked_(Char c) {
-  if (is_ascii) {
-    SeqAsciiString::cast(*current_part_)->SeqAsciiStringSet(
-        current_index_++, c);
-  } else {
-    SeqTwoByteString::cast(*current_part_)->SeqTwoByteStringSet(
-        current_index_++, c);
-  }
-  ASSERT(current_index_ < part_length_);
-}
-
-
-template <bool is_ascii, typename Char>
 void BasicJsonStringifier::Append_(const Char* chars) {
   for ( ; *chars != '\0'; chars++) Append_<is_ascii, Char>(*chars);
 }
 
 
-template <bool is_ascii, typename Char>
-void BasicJsonStringifier::AppendUnchecked_(const Char* chars) {
-  for ( ; *chars != '\0'; chars++) AppendUnchecked_<is_ascii, Char>(*chars);
-}
-
-
 Handle<Object> BasicJsonStringifier::GetProperty(Handle<JSObject> object,
                                                  Handle<String> key) {
   LookupResult lookup(isolate_);
   object->LocalLookupRealNamedProperty(*key, &lookup);
   if (!lookup.IsProperty()) return isolate_->factory()->undefined_value();
   switch (lookup.type()) {
     case NORMAL: {
       Object* value = lookup.holder()->GetNormalizedProperty(&lookup);
       ASSERT(!value->IsTheHole());
       return Handle<Object>(value);
@@ skipping 299 matching lines @@
   ShrinkCurrentPart();
   set_accumulator(
       isolate_->factory()->NewConsString(accumulator(), current_part_));
   current_part_ =
       isolate_->factory()->NewRawTwoByteString(part_length_);
   current_index_ = 0;
   is_ascii_ = false;
 }
 
 
+template <typename SrcChar, typename DestChar>
+void BasicJsonStringifier::SerializeStringUnchecked_(const SrcChar* src,
+                                                     DestChar* dest,
+                                                     int length) {
+  dest += current_index_;
+  DestChar* dest_start = dest;
+
+  *(dest++) = '"';
+  for (int i = 0; i < length; i++) {
+    SrcChar c = src[i];
+    if (DoNotEscape(c)) {
+      *(dest++) = c;
+    } else {
+      const char* chars = &JsonEscapeTable[c * kJsonEscapeTableEntrySize];
+      while (*chars != '\0') *(dest++) = *(chars++);
+    }
+  }
+
+  *(dest++) = '"';
+  current_index_ += dest - dest_start;
+}
+
+
 template <bool is_ascii, typename Char>
 void BasicJsonStringifier::SerializeString_(Vector<const Char> vector,
                                             Handle<String> string) {
   int length = vector.length();
-  if (current_index_ + (length << 3) < (part_length_ - 2)) {
-    AssertNoAllocation no_allocation_scope;
-    AppendUnchecked_<is_ascii, char>('"');
-    for (int i = 0; i < length; i++) {
-      Char c = vector[i];
-      if ((c >= '#' && c <= '~' && c != '\\') ||
-          (!is_ascii && ((c & 0xFF80) != 0))) {
-        AppendUnchecked_<is_ascii, Char>(c);
-      } else {
-        AppendUnchecked_<is_ascii, char>(
-            &JsonQuotes[c * kJsonQuotesCharactersPerEntry]);
-      }
+  // We do a rough estimate to find out if the current string can be
+  // serialized without allocating a new string part. The worst case length of
+  // an escaped character is 6.  Shifting left by 3 is a more pessimistic
+  // estimate than multiplying by 6, but faster to calculate.
+  static const int kEnclosingQuotesLength = 2;
+  if (current_index_ + (length << 3) + kEnclosingQuotesLength < part_length_) {
+    if (is_ascii) {
+      SerializeStringUnchecked_(
+          vector.start(),
+          SeqAsciiString::cast(*current_part_)->GetChars(),
+          length);
+    } else {
+      SerializeStringUnchecked_(
+          vector.start(),
+          SeqTwoByteString::cast(*current_part_)->GetChars(),
+          length);
     }
-    AppendUnchecked_<is_ascii, char>('"');
   } else {
     Append_<is_ascii, char>('"');
     String* string_location = *string;
     for (int i = 0; i < length; i++) {
       Char c = vector[i];
-      if ((c >= '#' && c <= '~' && c != '\\') ||
-          (!is_ascii && ((c & 0xFF80) != 0))) {
+      if (DoNotEscape(c)) {
         Append_<is_ascii, Char>(c);
       } else {
-        Append_<is_ascii, char>(&JsonQuotes[c * kJsonQuotesCharactersPerEntry]);
+        Append_<is_ascii, char>(
+            &JsonEscapeTable[c * kJsonEscapeTableEntrySize]);
       }
       // If GC moved the string, we need to refresh the vector.
       if (*string != string_location) {
         vector = GetCharVector<Char>(string);
         string_location = *string;
       }
     }
     Append_<is_ascii, char>('"');
   }
 }
 
 
 template <>
+bool BasicJsonStringifier::DoNotEscape(char c) {
+  return c >= '#' && c <= '~' && c != '\\';
+}
+
+
+template <>
+bool BasicJsonStringifier::DoNotEscape(uc16 c) {
+  return (c >= 0x80) || (c >= '#' && c <= '~' && c != '\\');
+}
+
+
+template <>
 Vector<const char> BasicJsonStringifier::GetCharVector(Handle<String> string) {
   String::FlatContent flat = string->GetFlatContent();
   ASSERT(flat.IsAscii());
   return flat.ToAsciiVector();
 }
 
 
 template <>
 Vector<const uc16> BasicJsonStringifier::GetCharVector(Handle<String> string) {
   String::FlatContent flat = string->GetFlatContent();
@@ skipping 17 matching lines @@
       SerializeString_<false, char>(flat.ToAsciiVector(), object);
     } else {
       SerializeString_<false, uc16>(flat.ToUC16Vector(), object);
     }
   }
 }
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSON_STRINGIFIER_H_