Speed up quoting of JSON strings by allocating a string that is big enough...

src/runtime.cc

 // Copyright 2010 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 4528 matching lines @@
     int step;
     destination->Set(dest_position, Unescape(source, i, length, &step));
     i += step;
   }
   return destination;
 }
 
 
 static const unsigned int kQuoteTableLength = 128u;
 
-static const char* const JsonQuotes[kQuoteTableLength] = {
-    "\\u0000", "\\u0001", "\\u0002", "\\u0003",
-    "\\u0004", "\\u0005", "\\u0006", "\\u0007",
-    "\\b", "\\t", "\\n", "\\u000b",
-    "\\f", "\\r", "\\u000e", "\\u000f",
-    "\\u0010", "\\u0011", "\\u0012", "\\u0013",
-    "\\u0014", "\\u0015", "\\u0016", "\\u0017",
-    "\\u0018", "\\u0019", "\\u001a", "\\u001b",
-    "\\u001c", "\\u001d", "\\u001e", "\\u001f",
-    NULL, NULL, "\\\"", NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    "\\\\", NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-    NULL, NULL, NULL, NULL,
-};
+static const int kJsonQuotesCharactersPerEntry = 8;
+static const char* const JsonQuotes =
+    "\\u0000  \\u0001  \\u0002  \\u0003  "
+    "\\u0004  \\u0005  \\u0006  \\u0007  "
+    "\\b      \\t      \\n      \\u000b  "
+    "\\f      \\r      \\u000e  \\u000f  "
+    "\\u0010  \\u0011  \\u0012  \\u0013  "
+    "\\u0014  \\u0015  \\u0016  \\u0017  "
+    "\\u0018  \\u0019  \\u001a  \\u001b  "
+    "\\u001c  \\u001d  \\u001e  \\u001f  "
+    "        !       \\\"      #       "
+    "$       %       &       '       "
+    "(       )       *       +       "
+    ",       -       .       /       "
+    "0       1       2       3       "
+    "4       5       6       7       "
+    "8       9       :       ;       "
+    "<       =       >       ?       "
+    "@       A       B       C       "
+    "D       E       F       G       "
+    "H       I       J       K       "
+    "L       M       N       O       "
+    "P       Q       R       S       "
+    "T       U       V       W       "
+    "X       Y       Z       [       "
+    "\\\\      ]       ^       _       "
+    "`       a       b       c       "
+    "d       e       f       g       "
+    "h       i       j       k       "
+    "l       m       n       o       "
+    "p       q       r       s       "
+    "t       u       v       w       "
+    "x       y       z       {       "
+    "|       }       ~       \177       ";
 
 
+// For a string that is less than 32k characters it should always be
+// possible to allocate it in new space.
+static const int kMaxGuaranteedNewSpaceString = 32 * 1024;
+
+
+// Doing JSON quoting cannot make the string more than this many times larger.
+static const int kJsonQuoteWorstCaseBlowup = 6;
+
+
+// Covers the entire ASCII range (all other characters are unchanged by JSON
+// quoting).
 static const byte JsonQuoteLengths[kQuoteTableLength] = {

[Vyacheslav Egorov (Chromium), 2010/12/08 10:51:31]

I do not like subtle connection between string above and this array.

It's excruciatingly difficult to check correctness (4 in a row vs. 8 in a row).

Can we change it somehow?

[Erik Corry, 2010/12/08 16:35:56]

Changed the string above so it is also 8 per line, to make visual checking
easier. 

     6, 6, 6, 6, 6, 6, 6, 6,
     2, 2, 2, 6, 2, 2, 6, 6,
     6, 6, 6, 6, 6, 6, 6, 6,
     6, 6, 6, 6, 6, 6, 6, 6,
     1, 1, 2, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 2, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1,
 };
 
 
-template <typename Char>
-Char* WriteString(Char* dst, const char* src_string) {
-  char c;
-  for (c = *src_string; c; c = *src_string) {
-    *dst = c;
-    dst++;
-    src_string++;
-  }
-  return dst;
-}
-
-
 template <typename StringType>
 MaybeObject* AllocateRawString(int length);
 
 
 template <>
 MaybeObject* AllocateRawString<SeqTwoByteString>(int length) {
   return Heap::AllocateRawTwoByteString(length);
 }
 
 
 template <>
 MaybeObject* AllocateRawString<SeqAsciiString>(int length) {
   return Heap::AllocateRawAsciiString(length);
 }
 
 
 template <typename Char, typename StringType>
+static MaybeObject* SlowQuoteJsonString(Vector<const Char> characters) {
+  int length = characters.length();
+  const Char* read_cursor = characters.start();
+  const Char* end = read_cursor + length;
+  const int kSpaceForQuotes = 2;
+  int quoted_length = kSpaceForQuotes;
+  while (read_cursor < end) {
+    Char c = *(read_cursor++);
+    if (sizeof(Char) > 1u && static_cast<unsigned>(c) >= kQuoteTableLength) {
+      quoted_length++;
+    } else {
+      quoted_length += JsonQuoteLengths[static_cast<unsigned>(c)];
+    }
+  }
+  MaybeObject* new_alloc = AllocateRawString<StringType>(quoted_length);
+  Object* new_object;
+  if (!new_alloc->ToObject(&new_object)) {
+    return new_alloc;
+  }
+  StringType* new_string = StringType::cast(new_object);
+
+  Char* write_cursor = reinterpret_cast<Char*>(
+      new_string->address() + SeqAsciiString::kHeaderSize);
+  *(write_cursor++) = '"';
+
+  read_cursor = characters.start();
+  while (read_cursor < end) {
+    Char c = *(read_cursor++);
+    if (sizeof(Char) > 1u && static_cast<unsigned>(c) >= kQuoteTableLength) {
+      *(write_cursor++) = c;
+    } else {
+      int len = JsonQuoteLengths[static_cast<unsigned>(c)];
+      const char* replacement = JsonQuotes +
+          static_cast<unsigned>(c) * kJsonQuotesCharactersPerEntry;
+      for (int i = 0; i < len; i++) {
+        *write_cursor++ = *replacement++;
+      }
+    }
+  }
+  *(write_cursor++) = '"';
+  return new_string;
+}
+
+
+template <typename Char, typename StringType>
 static MaybeObject* QuoteJsonString(Vector<const Char> characters) {
   int length = characters.length();
-  int quoted_length = 0;
-  for (int i = 0; i < length; i++) {
-    unsigned int c = characters[i];
-    if (sizeof(Char) > 1u) {
-      quoted_length += (c >= kQuoteTableLength) ? 1 : JsonQuoteLengths[c];
-    } else {
-      quoted_length += JsonQuoteLengths[c];
-    }
+  Counters::quote_json_char_count.Increment(length);
+  const int kSpaceForQuotes = 2;
+  int worst_case_length = length * kJsonQuoteWorstCaseBlowup + kSpaceForQuotes;
+  if (worst_case_length > kMaxGuaranteedNewSpaceString) {
+    return SlowQuoteJsonString<Char, StringType>(characters);
   }
-  Counters::quote_json_char_count.Increment(length);
 
-  // Add space for quotes.
-  quoted_length += 2;
-
-  MaybeObject* new_alloc = AllocateRawString<StringType>(quoted_length);
+  MaybeObject* new_alloc = AllocateRawString<StringType>(worst_case_length);
   Object* new_object;
   if (!new_alloc->ToObject(&new_object)) {
-    Counters::quote_json_char_recount.Increment(length);
     return new_alloc;
   }
   StringType* new_string = StringType::cast(new_object);
-
+  ASSERT(Heap::new_space()->Contains(new_string));
 
   STATIC_ASSERT(SeqTwoByteString::kHeaderSize == SeqAsciiString::kHeaderSize);
   Char* write_cursor = reinterpret_cast<Char*>(
       new_string->address() + SeqAsciiString::kHeaderSize);
   *(write_cursor++) = '"';
+
   const Char* read_cursor = characters.start();
-  if (quoted_length == length + 2) {
-    CopyChars(write_cursor, read_cursor, length);
-    write_cursor += length;
-  } else {
-    const Char* end = read_cursor + length;
-    while (read_cursor < end) {
-      Char c = *(read_cursor++);
-      if (sizeof(Char) > 1u && static_cast<unsigned>(c) >= kQuoteTableLength) {
-        *(write_cursor++) = c;
-      } else {
-        const char* replacement = JsonQuotes[static_cast<unsigned>(c)];
-        if (!replacement) {
-          *(write_cursor++) = c;
-        } else {
-          write_cursor = WriteString(write_cursor, replacement);
-        }
+  const Char* end = read_cursor + length;
+  while (read_cursor < end) {
+    Char c = *(read_cursor++);
+    if (sizeof(Char) > 1u && static_cast<unsigned>(c) >= kQuoteTableLength) {
+      *(write_cursor++) = c;
+    } else {
+      int len = JsonQuoteLengths[static_cast<unsigned>(c)];
+      const char* replacement = JsonQuotes +
+          static_cast<unsigned>(c) * kJsonQuotesCharactersPerEntry;
+      write_cursor[0] = replacement[0];

[Vyacheslav Egorov (Chromium), 2010/12/08 10:51:31]

Some replacements have len == 1.

Why we optimistically write two characters for them and them move write cursor
by 1? This is really confusing.

[Erik Corry, 2010/12/08 16:35:56]

It is in order to remove mispredicted branches in this very hot inner loop. 
However measurements show that the extra writes almost cancel out the benefit of
not having mispredicts so I will remove this trick it for clarity.

+      write_cursor[1] = replacement[1];
+      if (len > 2) {
+        ASSERT(len == 6);
+        write_cursor[2] = replacement[2];
+        write_cursor[3] = replacement[3];
+        write_cursor[4] = replacement[4];
+        write_cursor[5] = replacement[5];
       }
+      write_cursor += len;
     }
   }
   *(write_cursor++) = '"';
-  ASSERT_EQ(SeqAsciiString::kHeaderSize + quoted_length * sizeof(Char),
-            reinterpret_cast<Address>(write_cursor) - new_string->address());
+
+  int final_length =
+      write_cursor - reinterpret_cast<Char*>(
+          new_string->address() + SeqAsciiString::kHeaderSize);
+  Heap::new_space()->ShrinkStringAtAllocationBoundary<StringType>(new_string,
+                                                                  final_length);
   return new_string;
 }
 
 
 static MaybeObject* Runtime_QuoteJSONString(Arguments args) {
   NoHandleAllocation ha;
   CONVERT_CHECKED(String, str, args[0]);
   if (!str->IsFlat()) {
     MaybeObject* try_flatten = str->TryFlatten();
     Object* flat;
@@ skipping 6088 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