Optimize serialization of quoted JSON strings.
authorakling@apple.com <akling@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 8 May 2015 08:44:23 +0000 (08:44 +0000)
committerakling@apple.com <akling@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 8 May 2015 08:44:23 +0000 (08:44 +0000)
<https://webkit.org/b/144754>

Reviewed by Darin Adler.

Source/JavaScriptCore:

Optimized the serialization of quoted strings into JSON by moving the logic into
StringBuilder so it can make smarter decisions about buffering.

12% progression on Kraken/json-stringify-tinderbox (on my Mac Pro.)

* bytecompiler/NodesCodegen.cpp:
(JSC::ObjectPatternNode::toString): Use the new StringBuilder API.

* runtime/JSONObject.h:
* runtime/JSONObject.cpp:
(JSC::Stringifier::Holder::appendNextProperty):
(JSC::appendStringToStringBuilder): Deleted.
(JSC::appendQuotedJSONStringToBuilder): Deleted.
(JSC::Stringifier::appendQuotedString): Deleted.
(JSC::Stringifier::appendStringifiedValue): Moved the bulk of this logic
to StringBuilder and call that from here.

Source/WebKit2:

* NetworkProcess/cache/NetworkCacheEntry.cpp:
(WebKit::NetworkCache::Entry::asJSON): Use the new StringBuilder API.

Source/WTF:

Add a StringBuilder API for appending a quoted JSON string. This is used by
JSON.stringify() to implement efficient appending of strings while escaping
quotes, control characters and \uNNNN-style characters.

The main benefit comes from only doing a single buffer expansion up front,
instead of doing it every time we append something. The fudge factor is pretty
large, since the maximum number of output characters per input character is 6.

The first landing of this patch had two bugs in it:

- Made \uNNNN escapes uppercase hexadecimal instead of lowercase.
- Didn't preallocate enough space for 8-bit input strings.

Both were caught by existing tests on our bots, and both were due to last-minute
changes before landing. :/

* wtf/text/StringBuilder.cpp:
(WTF::appendQuotedJSONStringInternal):
(WTF::StringBuilder::appendQuotedJSONString):
* wtf/text/StringBuilder.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183988 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
Source/JavaScriptCore/runtime/JSONObject.cpp
Source/JavaScriptCore/runtime/JSONObject.h
Source/WTF/ChangeLog
Source/WTF/wtf/text/StringBuilder.cpp
Source/WTF/wtf/text/StringBuilder.h
Source/WebKit2/ChangeLog
Source/WebKit2/NetworkProcess/cache/NetworkCacheEntry.cpp

index 03461b1..008ebee 100644 (file)
@@ -1,3 +1,27 @@
+2015-05-08  Andreas Kling  <akling@apple.com>
+
+        Optimize serialization of quoted JSON strings.
+        <https://webkit.org/b/144754>
+
+        Reviewed by Darin Adler.
+
+        Optimized the serialization of quoted strings into JSON by moving the logic into
+        StringBuilder so it can make smarter decisions about buffering.
+
+        12% progression on Kraken/json-stringify-tinderbox (on my Mac Pro.)
+
+        * bytecompiler/NodesCodegen.cpp:
+        (JSC::ObjectPatternNode::toString): Use the new StringBuilder API.
+
+        * runtime/JSONObject.h:
+        * runtime/JSONObject.cpp:
+        (JSC::Stringifier::Holder::appendNextProperty):
+        (JSC::appendStringToStringBuilder): Deleted.
+        (JSC::appendQuotedJSONStringToBuilder): Deleted.
+        (JSC::Stringifier::appendQuotedString): Deleted.
+        (JSC::Stringifier::appendStringifiedValue): Moved the bulk of this logic
+        to StringBuilder and call that from here.
+
 2015-05-07  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r183961.
index 8fe5b29..39b03cd 100644 (file)
@@ -3087,7 +3087,7 @@ void ObjectPatternNode::toString(StringBuilder& builder) const
     builder.append('{');
     for (size_t i = 0; i < m_targetPatterns.size(); i++) {
         if (m_targetPatterns[i].wasString)
-            appendQuotedJSONStringToBuilder(builder, m_targetPatterns[i].propertyName.string());
+            builder.appendQuotedJSONString(m_targetPatterns[i].propertyName.string());
         else
             builder.append(m_targetPatterns[i].propertyName.string());
         builder.append(':');
index 581bd45..9940658 100644 (file)
@@ -107,8 +107,6 @@ private:
 
     friend class Holder;
 
-    static void appendQuotedString(StringBuilder&, const String&);
-
     JSValue toJSON(JSValue, const PropertyNameForFunctionCall&);
 
     enum StringifyResult { StringifyFailed, StringifySucceeded, StringifyFailedDueToUndefinedValue };
@@ -255,72 +253,6 @@ Local<Unknown> Stringifier::stringify(Handle<Unknown> value)
     return Local<Unknown>(m_exec->vm(), jsString(m_exec, result.toString()));
 }
 
-template <typename CharType>
-static void appendStringToStringBuilder(StringBuilder& builder, const CharType* data, int length)
-{
-    for (int i = 0; i < length; ++i) {
-        int start = i;
-        while (i < length && (data[i] > 0x1F && data[i] != '"' && data[i] != '\\'))
-            ++i;
-        builder.append(data + start, i - start);
-        if (i >= length)
-            break;
-        switch (data[i]) {
-        case '\t':
-            builder.append('\\');
-            builder.append('t');
-            break;
-        case '\r':
-            builder.append('\\');
-            builder.append('r');
-            break;
-        case '\n':
-            builder.append('\\');
-            builder.append('n');
-            break;
-        case '\f':
-            builder.append('\\');
-            builder.append('f');
-            break;
-        case '\b':
-            builder.append('\\');
-            builder.append('b');
-            break;
-        case '"':
-            builder.append('\\');
-            builder.append('"');
-            break;
-        case '\\':
-            builder.append('\\');
-            builder.append('\\');
-            break;
-        default:
-            static const char hexDigits[] = "0123456789abcdef";
-            UChar ch = data[i];
-            LChar hex[] = { '\\', 'u', static_cast<LChar>(hexDigits[(ch >> 12) & 0xF]), static_cast<LChar>(hexDigits[(ch >> 8) & 0xF]), static_cast<LChar>(hexDigits[(ch >> 4) & 0xF]), static_cast<LChar>(hexDigits[ch & 0xF]) };
-            builder.append(hex, WTF_ARRAY_LENGTH(hex));
-            break;
-        }
-    }
-}
-
-void appendQuotedJSONStringToBuilder(StringBuilder& builder, const String& message)
-{
-    builder.append('"');
-
-    if (message.is8Bit())
-        appendStringToStringBuilder(builder, message.characters8(), message.length());
-    else
-        appendStringToStringBuilder(builder, message.characters16(), message.length());
-
-    builder.append('"');
-}
-
-void Stringifier::appendQuotedString(StringBuilder& builder, const String& value)
-{
-    appendQuotedJSONStringToBuilder(builder, value);
-}
-
 inline JSValue Stringifier::toJSON(JSValue value, const PropertyNameForFunctionCall& propertyName)
 {
     ASSERT(!m_exec->hadException());
@@ -385,7 +317,7 @@ Stringifier::StringifyResult Stringifier::appendStringifiedValue(StringBuilder&
 
     String stringValue;
     if (value.getString(m_exec, stringValue)) {
-        appendQuotedString(builder, stringValue);
+        builder.appendQuotedJSONString(stringValue);
         return StringifySucceeded;
     }
 
@@ -556,7 +488,7 @@ bool Stringifier::Holder::appendNextProperty(Stringifier& stringifier, StringBui
         stringifier.startNewLine(builder);
 
         // Append the property name.
-        appendQuotedString(builder, propertyName.string());
+        builder.appendQuotedJSONString(propertyName.string());
         builder.append(':');
         if (stringifier.willIndent())
             builder.append(' ');
index eb6daad..d550525 100644 (file)
@@ -62,8 +62,6 @@ private:
 JS_EXPORT_PRIVATE JSValue JSONParse(ExecState*, const String&);
 JS_EXPORT_PRIVATE String JSONStringify(ExecState*, JSValue, unsigned indent);
 
-JS_EXPORT_PRIVATE void appendQuotedJSONStringToBuilder(StringBuilder&, const String&);
-
     
 } // namespace JSC
 
index 70494cd..829ddda 100644 (file)
@@ -1,3 +1,31 @@
+2015-05-08  Andreas Kling  <akling@apple.com>
+
+        Optimize serialization of quoted JSON strings.
+        <https://webkit.org/b/144754>
+
+        Reviewed by Darin Adler.
+
+        Add a StringBuilder API for appending a quoted JSON string. This is used by
+        JSON.stringify() to implement efficient appending of strings while escaping
+        quotes, control characters and \uNNNN-style characters.
+
+        The main benefit comes from only doing a single buffer expansion up front,
+        instead of doing it every time we append something. The fudge factor is pretty
+        large, since the maximum number of output characters per input character is 6.
+
+        The first landing of this patch had two bugs in it:
+
+        - Made \uNNNN escapes uppercase hexadecimal instead of lowercase.
+        - Didn't preallocate enough space for 8-bit input strings.
+
+        Both were caught by existing tests on our bots, and both were due to last-minute
+        changes before landing. :/
+
+        * wtf/text/StringBuilder.cpp:
+        (WTF::appendQuotedJSONStringInternal):
+        (WTF::StringBuilder::appendQuotedJSONString):
+        * wtf/text/StringBuilder.h:
+
 2015-05-07  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r183961.
index 164b8c3..ff09afc 100644 (file)
@@ -28,6 +28,7 @@
 #include "StringBuilder.h"
 
 #include "IntegerToStringConversion.h"
+#include "MathExtras.h"
 #include "WTFString.h"
 #include <wtf/dtoa.h>
 
@@ -360,4 +361,88 @@ void StringBuilder::shrinkToFit()
     }
 }
 
+template <typename OutputCharacterType, typename InputCharacterType>
+static void appendQuotedJSONStringInternal(OutputCharacterType*& output, const InputCharacterType* input, unsigned length)
+{
+    for (const InputCharacterType* end = input + length; input != end; ++input) {
+        if (*input > 0x1F && *input != '"' && *input != '\\') {
+            *output++ = *input;
+            continue;
+        }
+        switch (*input) {
+        case '\t':
+            *output++ = '\\';
+            *output++ = 't';
+            break;
+        case '\r':
+            *output++ = '\\';
+            *output++ = 'r';
+            break;
+        case '\n':
+            *output++ = '\\';
+            *output++ = 'n';
+            break;
+        case '\f':
+            *output++ = '\\';
+            *output++ = 'f';
+            break;
+        case '\b':
+            *output++ = '\\';
+            *output++ = 'b';
+            break;
+        case '"':
+            *output++ = '\\';
+            *output++ = '"';
+            break;
+        case '\\':
+            *output++ = '\\';
+            *output++ = '\\';
+            break;
+        default:
+            ASSERT((*input & 0xFF00) == 0);
+            static const char hexDigits[] = "0123456789abcdef";
+            *output++ = '\\';
+            *output++ = 'u';
+            *output++ = '0';
+            *output++ = '0';
+            *output++ = static_cast<LChar>(hexDigits[(*input >> 4) & 0xF]);
+            *output++ = static_cast<LChar>(hexDigits[*input & 0xF]);
+            break;
+        }
+    }
+}
+
+void StringBuilder::appendQuotedJSONString(const String& string)
+{
+    // Make sure we have enough buffer space to append this string without having
+    // to worry about reallocating in the middle.
+    // The 2 is for the '"' quotes on each end.
+    // The 6 is for characters that need to be \uNNNN encoded.
+    size_t maximumCapacityRequired = length() + 2 + string.length() * 6;
+    RELEASE_ASSERT(maximumCapacityRequired < std::numeric_limits<unsigned>::max());
+
+    if (is8Bit() && !string.is8Bit())
+        allocateBufferUpConvert(m_bufferCharacters8, roundUpToPowerOfTwo(maximumCapacityRequired));
+    else
+        reserveCapacity(roundUpToPowerOfTwo(maximumCapacityRequired));
+
+    if (is8Bit()) {
+        ASSERT(string.is8Bit());
+        LChar* output = m_bufferCharacters8 + m_length;
+        *output++ = '"';
+        appendQuotedJSONStringInternal(output, string.characters8(), string.length());
+        *output++ = '"';
+        m_length = output - m_bufferCharacters8;
+    } else {
+        UChar* output = m_bufferCharacters16 + m_length;
+        *output++ = '"';
+        if (string.is8Bit())
+            appendQuotedJSONStringInternal(output, string.characters8(), string.length());
+        else
+            appendQuotedJSONStringInternal(output, string.characters16(), string.length());
+        *output++ = '"';
+        m_length = output - m_bufferCharacters16;
+    }
+}
+
 } // namespace WTF
index 93422a2..be5c117 100644 (file)
@@ -159,6 +159,8 @@ public:
         append(U16_TRAIL(c));
     }
 
+    WTF_EXPORT_PRIVATE void appendQuotedJSONString(const String&);
+
     template<unsigned charactersCount>
     ALWAYS_INLINE void appendLiteral(const char (&characters)[charactersCount]) { append(characters, charactersCount - 1); }
 
index bcb34eb..5fd8c0b 100644 (file)
@@ -1,3 +1,13 @@
+2015-05-08  Andreas Kling  <akling@apple.com>
+
+        Optimize serialization of quoted JSON strings.
+        <https://webkit.org/b/144754>
+
+        Reviewed by Darin Adler.
+
+        * NetworkProcess/cache/NetworkCacheEntry.cpp:
+        (WebKit::NetworkCache::Entry::asJSON): Use the new StringBuilder API.
+
 2015-05-08  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r183945.
index c34fc52..7350a5b 100644 (file)
@@ -30,7 +30,6 @@
 #include "NetworkCacheCoders.h"
 #include "NetworkCacheDecoder.h"
 #include "NetworkCacheEncoder.h"
-#include <JavaScriptCore/JSONObject.h>
 #include <WebCore/ResourceRequest.h>
 #include <WebCore/SharedBuffer.h>
 #include <wtf/text/StringBuilder.h>
@@ -159,7 +158,7 @@ void Entry::asJSON(StringBuilder& json, const Storage::RecordInfo& info) const
 {
     json.appendLiteral("{\n");
     json.appendLiteral("\"hash\": ");
-    JSC::appendQuotedJSONStringToBuilder(json, m_key.hashAsString());
+    json.appendQuotedJSONString(m_key.hashAsString());
     json.appendLiteral(",\n");
     json.appendLiteral("\"bodySize\": ");
     json.appendNumber(info.bodySize);
@@ -168,16 +167,16 @@ void Entry::asJSON(StringBuilder& json, const Storage::RecordInfo& info) const
     json.appendNumber(info.worth);
     json.appendLiteral(",\n");
     json.appendLiteral("\"partition\": ");
-    JSC::appendQuotedJSONStringToBuilder(json, m_key.partition());
+    json.appendQuotedJSONString(m_key.partition());
     json.appendLiteral(",\n");
     json.appendLiteral("\"timestamp\": ");
     json.appendNumber(std::chrono::duration_cast<std::chrono::milliseconds>(m_timeStamp.time_since_epoch()).count());
     json.appendLiteral(",\n");
     json.appendLiteral("\"URL\": ");
-    JSC::appendQuotedJSONStringToBuilder(json, m_response.url().string());
+    json.appendQuotedJSONString(m_response.url().string());
     json.appendLiteral(",\n");
     json.appendLiteral("\"bodyHash\": ");
-    JSC::appendQuotedJSONStringToBuilder(json, info.bodyHash);
+    json.appendQuotedJSONString(info.bodyHash);
     json.appendLiteral(",\n");
     json.appendLiteral("\"bodyShareCount\": ");
     json.appendNumber(info.bodyShareCount);
@@ -189,9 +188,9 @@ void Entry::asJSON(StringBuilder& json, const Storage::RecordInfo& info) const
             json.appendLiteral(",\n");
         firstHeader = false;
         json.appendLiteral("    ");
-        JSC::appendQuotedJSONStringToBuilder(json, header.key);
+        json.appendQuotedJSONString(header.key);
         json.appendLiteral(": ");
-        JSC::appendQuotedJSONStringToBuilder(json, header.value);
+        json.appendQuotedJSONString(header.value);
     }
     json.appendLiteral("\n}\n");
     json.appendLiteral("}");