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 03461b1b73c9bebf6df5bd8666a1f310e10db5d9..008ebee4571d57a8a59ff72ce564ab9115d4e9ca 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 8fe5b29065be6e7ae01fded753556f4b505cee84..39b03cddcfb2310334a1d63c83f8f3853d16c6fc 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 581bd45705a77d44ea4517d910a48992b83f5fab..99406581de7ea3c8ec948b93cae369e85f4d81b0 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 eb6daad9d925f19bea25f7834908860ca1a7815d..d550525c9e71d85abcf41a8d18a90017a1bb30ad 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 70494cd3078b462da0ed4586c2ea4aa3f7429d97..829ddda75a5f51e7643eea72995d24c7ab01284e 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 164b8c3c120c20e2b26c20a2027407588c0c3ec9..ff09afc51dc1ed8060f7b4084e74227dab8f53b9 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 93422a2462631f307c0c13f28cb3b561d476aef1..be5c1172cccb998a410580345af40c29cb13498e 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 bcb34eb3e0579112fd0a3937756a9bfb3209bb15..5fd8c0b4929e5175e89dfc5785225c39d6f88741 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 c34fc52a37cc348f8db483dc04a9250f24edd515..7350a5b756df980440d4ffdd678dbacff33baecc 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("}");