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

src/runtime.cc

Index: src/runtime.cc
===================================================================
--- src/runtime.cc	(revision 5937)
+++ src/runtime.cc	(working copy)
@@ -4546,42 +4546,53 @@
 
 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,
@@ -4602,18 +4613,6 @@
 };
 
 
-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);
 
@@ -4631,58 +4630,102 @@
 
 
 template <typename Char, typename StringType>
-static MaybeObject* QuoteJsonString(Vector<const Char> characters) {
+static MaybeObject* SlowQuoteJsonString(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];
+  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[c];
+      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();
   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);
+  }
 
-  // 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;
 }