Log Message
[JSC] Use table based approach for JSON.stringify's Quote https://bugs.webkit.org/show_bug.cgi?id=176044
Reviewed by Darin Adler. We change escape operation of JSON Quote from branch-based to table-based. This patch partially adopts SpiderMonkey's change to StringBuilderJSON.cpp to optimize this escaping operation. We separate changes from StringBuilder.cpp to apply MPL to StringBuilderJSON.cpp file. Since WebKit already adopts MPL in some files (like, DateMath.h), it is acceptable. Kraken json-stringify-tinderbox shows 7.2% improvement. baseline patched json-stringify-tinderbox 40.429+-0.771 ^ 37.693+-0.862 ^ definitely 1.0726x faster * WTF.xcodeproj/project.pbxproj: * wtf/CMakeLists.txt: * wtf/text/StringBuilder.cpp: (WTF::appendQuotedJSONStringInternalSlow): Deleted. (WTF::appendQuotedJSONStringInternal): Deleted. (WTF::StringBuilder::appendQuotedJSONString): Deleted. * wtf/text/StringBuilderJSON.cpp: Added. (WTF::appendQuotedJSONStringInternal): (WTF::StringBuilder::appendQuotedJSONString):
Modified Paths
- trunk/Source/WTF/ChangeLog
- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj
- trunk/Source/WTF/wtf/CMakeLists.txt
- trunk/Source/WTF/wtf/text/StringBuilder.cpp
Added Paths
Diff
Modified: trunk/Source/WTF/ChangeLog (221329 => 221330)
--- trunk/Source/WTF/ChangeLog 2017-08-30 00:39:26 UTC (rev 221329)
+++ trunk/Source/WTF/ChangeLog 2017-08-30 01:22:33 UTC (rev 221330)
@@ -1,3 +1,32 @@
+2017-08-28 Yusuke Suzuki <utatane....@gmail.com>
+
+ [JSC] Use table based approach for JSON.stringify's Quote
+ https://bugs.webkit.org/show_bug.cgi?id=176044
+
+ Reviewed by Darin Adler.
+
+ We change escape operation of JSON Quote from branch-based to table-based.
+ This patch partially adopts SpiderMonkey's change to StringBuilderJSON.cpp
+ to optimize this escaping operation. We separate changes from StringBuilder.cpp
+ to apply MPL to StringBuilderJSON.cpp file. Since WebKit already adopts MPL in
+ some files (like, DateMath.h), it is acceptable.
+
+ Kraken json-stringify-tinderbox shows 7.2% improvement.
+
+ baseline patched
+
+ json-stringify-tinderbox 40.429+-0.771 ^ 37.693+-0.862 ^ definitely 1.0726x faster
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/text/StringBuilder.cpp:
+ (WTF::appendQuotedJSONStringInternalSlow): Deleted.
+ (WTF::appendQuotedJSONStringInternal): Deleted.
+ (WTF::StringBuilder::appendQuotedJSONString): Deleted.
+ * wtf/text/StringBuilderJSON.cpp: Added.
+ (WTF::appendQuotedJSONStringInternal):
+ (WTF::StringBuilder::appendQuotedJSONString):
+
2017-08-29 Per Arne Vollan <pvol...@apple.com>
[Win] Crash under WorkQueue::performWorkOnRegisteredWorkThread in layout tests.
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (221329 => 221330)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-08-30 00:39:26 UTC (rev 221329)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-08-30 01:22:33 UTC (rev 221330)
@@ -138,6 +138,7 @@
E311FB171F0A568B003C08DE /* ThreadGroup.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E311FB151F0A568B003C08DE /* ThreadGroup.cpp */; };
E38C41251EB4E04C0042957D /* CPUTimeCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = E38C41241EB4E04C0042957D /* CPUTimeCocoa.mm */; };
E38C41281EB4E0680042957D /* CPUTime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E38C41261EB4E0680042957D /* CPUTime.cpp */; };
+ E38D6E271F5522E300A75CC4 /* StringBuilderJSON.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E38D6E261F5522E300A75CC4 /* StringBuilderJSON.cpp */; };
E4A0AD391A96245500536DF6 /* WorkQueue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E4A0AD371A96245500536DF6 /* WorkQueue.cpp */; };
E4A0AD3D1A96253C00536DF6 /* WorkQueueCocoa.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E4A0AD3C1A96253C00536DF6 /* WorkQueueCocoa.cpp */; };
FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEDACD3B1630F83F00C69634 /* StackStats.cpp */; };
@@ -563,6 +564,7 @@
E38C41241EB4E04C0042957D /* CPUTimeCocoa.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = CPUTimeCocoa.mm; sourceTree = "<group>"; };
E38C41261EB4E0680042957D /* CPUTime.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CPUTime.cpp; sourceTree = "<group>"; };
E38C41271EB4E0680042957D /* CPUTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CPUTime.h; sourceTree = "<group>"; };
+ E38D6E261F5522E300A75CC4 /* StringBuilderJSON.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringBuilderJSON.cpp; sourceTree = "<group>"; };
E3E158251EADA53C004A079D /* SystemFree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SystemFree.h; sourceTree = "<group>"; };
E4A0AD371A96245500536DF6 /* WorkQueue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WorkQueue.cpp; sourceTree = "<group>"; };
E4A0AD381A96245500536DF6 /* WorkQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WorkQueue.h; sourceTree = "<group>"; };
@@ -941,7 +943,6 @@
1469419416EAAFF80024E146 /* SchedulePair.h */,
1469419816EAB0410024E146 /* SchedulePairCF.cpp */,
1469419516EAAFF80024E146 /* SchedulePairMac.mm */,
- 795212021F42588800BD6421 /* SingleRootGraph.h */,
1A3524AA1D63A2FF0031729B /* Scope.h */,
0FEC84B01BDACD390080FF74 /* ScopedLambda.h */,
0F66B2841DC97BAB004A1D3F /* Seconds.cpp */,
@@ -953,6 +954,7 @@
A8A47309151A825B004123FF /* SHA1.h */,
0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */,
A8A4730A151A825B004123FF /* SimpleStats.h */,
+ 795212021F42588800BD6421 /* SingleRootGraph.h */,
A8A4730B151A825B004123FF /* SinglyLinkedList.h */,
A748744F17A0BDAE00FA04CB /* SixCharacterHash.cpp */,
A748745017A0BDAE00FA04CB /* SixCharacterHash.h */,
@@ -1079,6 +1081,7 @@
A8A47323151A825B004123FF /* StringBuffer.h */,
A8A47324151A825B004123FF /* StringBuilder.cpp */,
A8A47325151A825B004123FF /* StringBuilder.h */,
+ E38D6E261F5522E300A75CC4 /* StringBuilderJSON.cpp */,
430B47871AAAAC1A001223DA /* StringCommon.h */,
A8A47326151A825B004123FF /* StringConcatenate.h */,
7CD4C26F1E2C82B900929470 /* StringConcatenateNumbers.h */,
@@ -1393,6 +1396,7 @@
FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */,
3337DB9CE743410FAF076E17 /* StackTrace.cpp in Sources */,
A8A4743C151A825B004123FF /* StringBuilder.cpp in Sources */,
+ E38D6E271F5522E300A75CC4 /* StringBuilderJSON.cpp in Sources */,
A5BA15FB182435A600A82E69 /* StringCF.cpp in Sources */,
A8A47440151A825B004123FF /* StringImpl.cpp in Sources */,
A5BA15FC182435A600A82E69 /* StringImplCF.cpp in Sources */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (221329 => 221330)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2017-08-30 00:39:26 UTC (rev 221329)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2017-08-30 01:22:33 UTC (rev 221330)
@@ -284,6 +284,7 @@
text/Base64.cpp
text/CString.cpp
text/StringBuilder.cpp
+ text/StringBuilderJSON.cpp
text/StringImpl.cpp
text/StringView.cpp
text/SymbolImpl.cpp
Modified: trunk/Source/WTF/wtf/text/StringBuilder.cpp (221329 => 221330)
--- trunk/Source/WTF/wtf/text/StringBuilder.cpp 2017-08-30 00:39:26 UTC (rev 221329)
+++ trunk/Source/WTF/wtf/text/StringBuilder.cpp 2017-08-30 01:22:33 UTC (rev 221330)
@@ -385,99 +385,4 @@
}
}
-template <typename OutputCharacterType, typename InputCharacterType>
-static void appendQuotedJSONStringInternalSlow(OutputCharacterType*& output, const InputCharacterType character)
-{
- switch (character) {
- 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;
- default:
- ASSERT(!(character & 0xFF00));
- *output++ = '\\';
- *output++ = 'u';
- *output++ = '0';
- *output++ = '0';
- *output++ = upperNibbleToLowercaseASCIIHexDigit(character);
- *output++ = lowerNibbleToLowercaseASCIIHexDigit(character);
- break;
- }
-}
-
-template <typename OutputCharacterType, typename InputCharacterType>
-static void appendQuotedJSONStringInternal(OutputCharacterType*& output, const InputCharacterType* input, unsigned length)
-{
- for (const InputCharacterType* end = input + length; input != end; ++input) {
- const InputCharacterType character = *input;
- if (LIKELY(character != '"' && character != '\\' && character > 0x1F)) {
- *output++ = character;
- continue;
- }
-
- if (character == '"' || character == '\\') {
- *output++ = '\\';
- *output++ = character;
- continue;
- }
-
- appendQuotedJSONStringInternalSlow(output, character);
- }
-}
-
-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.
- Checked<unsigned> stringLength = string.length();
- Checked<unsigned> maximumCapacityRequired = length();
- maximumCapacityRequired += 2 + stringLength * 6;
- unsigned allocationSize = maximumCapacityRequired.unsafeGet();
- // This max() is here to allow us to allocate sizes between the range [2^31, 2^32 - 2] because roundUpToPowerOfTwo(1<<31 + some int smaller than 1<<31) == 0.
- allocationSize = std::max(allocationSize, roundUpToPowerOfTwo(allocationSize));
-
- if (is8Bit() && !string.is8Bit())
- allocateBufferUpConvert(m_bufferCharacters8, allocationSize);
- else
- reserveCapacity(allocationSize);
- ASSERT(m_buffer->length() >= allocationSize);
-
- 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;
- }
- ASSERT(m_buffer->length() >= m_length);
-}
-
} // namespace WTF
Added: trunk/Source/WTF/wtf/text/StringBuilderJSON.cpp (0 => 221330)
--- trunk/Source/WTF/wtf/text/StringBuilderJSON.cpp (rev 0)
+++ trunk/Source/WTF/wtf/text/StringBuilderJSON.cpp 2017-08-30 01:22:33 UTC (rev 221330)
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2010, 2013, 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2012 Google Inc. All rights reserved.
+ * Copyright (C) 2017 Yusuke Suzuki <utatane....@gmail.com>. All rights reserved.
+ * Copyright (C) 2017 Mozilla Foundation. All rights reserved.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include "config.h"
+#include "StringBuilder.h"
+
+#include "WTFString.h"
+
+namespace WTF {
+
+// This table driven escaping is ported from SpiderMonkey.
+static const constexpr LChar escapedFormsForJSON[0x100] = {
+ 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u',
+ 'b', 't', 'n', 'u', 'f', 'r', 'u', 'u',
+ 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u',
+ 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u',
+ 0, 0, '\"', 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, '\\', 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+};
+
+template<typename OutputCharacterType, typename InputCharacterType>
+ALWAYS_INLINE static void appendQuotedJSONStringInternal(OutputCharacterType*& output, const InputCharacterType* input, unsigned length)
+{
+ for (auto* end = input + length; input != end; ++input) {
+ auto character = *input;
+ auto escaped = escapedFormsForJSON[character & 0xFF];
+ if (LIKELY(!escaped || character > 0xFF)) {
+ *output++ = character;
+ continue;
+ }
+
+ *output++ = '\\';
+ *output++ = escaped;
+ if (UNLIKELY(escaped == 'u')) {
+ *output++ = '0';
+ *output++ = '0';
+ *output++ = upperNibbleToLowercaseASCIIHexDigit(character);
+ *output++ = lowerNibbleToLowercaseASCIIHexDigit(character);
+ }
+ }
+}
+
+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.
+ Checked<unsigned> stringLength = string.length();
+ Checked<unsigned> maximumCapacityRequired = length();
+ maximumCapacityRequired += 2 + stringLength * 6;
+ unsigned allocationSize = maximumCapacityRequired.unsafeGet();
+ // This max() is here to allow us to allocate sizes between the range [2^31, 2^32 - 2] because roundUpToPowerOfTwo(1<<31 + some int smaller than 1<<31) == 0.
+ // FIXME: roundUpToPowerOfTwo should take Checked<unsigned> and abort if it fails to round up.
+ // https://bugs.webkit.org/show_bug.cgi?id=176086
+ allocationSize = std::max(allocationSize, roundUpToPowerOfTwo(allocationSize));
+
+ if (is8Bit() && !string.is8Bit())
+ allocateBufferUpConvert(m_bufferCharacters8, allocationSize);
+ else
+ reserveCapacity(allocationSize);
+ ASSERT(m_buffer->length() >= allocationSize);
+
+ 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;
+ }
+ ASSERT(m_buffer->length() >= m_length);
+}
+
+} // namespace WTF
_______________________________________________ webkit-changes mailing list webkit-changes@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-changes