Diff
Modified: trunk/LayoutTests/ChangeLog (184446 => 184447)
--- trunk/LayoutTests/ChangeLog 2015-05-18 06:16:58 UTC (rev 184446)
+++ trunk/LayoutTests/ChangeLog 2015-05-18 06:23:31 UTC (rev 184447)
@@ -1,3 +1,16 @@
+2015-05-17 Benjamin Poulain <[email protected]>
+
+ [JSC] Make StringRecursionChecker faster in the simple cases without any recursion
+ https://bugs.webkit.org/show_bug.cgi?id=145102
+
+ Reviewed by Darin Adler.
+
+ Improve the coverage a tiny bit.
+
+ * js/array-string-recursion-expected.txt: Added.
+ * js/array-string-recursion.html: Added.
+ * js/script-tests/array-string-recursion.js: Added.
+
2015-05-17 Manuel Rego Casasnovas <[email protected]>
[CSS Grid Layout] Add scrollbar width in intrinsic logical widths computation
Added: trunk/LayoutTests/js/array-string-recursion-expected.txt (0 => 184447)
--- trunk/LayoutTests/js/array-string-recursion-expected.txt (rev 0)
+++ trunk/LayoutTests/js/array-string-recursion-expected.txt 2015-05-18 06:23:31 UTC (rev 184447)
@@ -0,0 +1,84 @@
+Verify that we do not recurse infinitely through one of the Array->string conversion.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toString(); is ""
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toLocaleString(); is ""
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.join(","); is ""
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toString(); is "1,,WebKit!,"
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toLocaleString(); is "1,,WebKit!,"
+PASS var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.join("-"); is "1--WebKit!-"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.toString(); is "1,1,2,5,6,,WebKit!"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.toLocaleString(); is "1,1,2,5,6,,WebKit!"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.join("="); is "1=1,2,5,6,=WebKit!"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].toString(); is "z,1,1,2,5,6,,WebKit!,9"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].toLocaleString(); is "z,1,1,2,5,6,,WebKit!,9"
+PASS var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].join("&"); is "z&1,1,2,5,6,,WebKit!&9"
+PASS var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].toString(); is "z,a,,,,WebKit!,9"
+PASS var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].toLocaleString(); is "z,a,,,,WebKit!,9"
+PASS var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].join("*"); is "z*a,,,,WebKit!*9"
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/array-string-recursion.html (0 => 184447)
--- trunk/LayoutTests/js/array-string-recursion.html (rev 0)
+++ trunk/LayoutTests/js/array-string-recursion.html 2015-05-18 06:23:31 UTC (rev 184447)
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/script-tests/array-string-recursion.js (0 => 184447)
--- trunk/LayoutTests/js/script-tests/array-string-recursion.js (rev 0)
+++ trunk/LayoutTests/js/script-tests/array-string-recursion.js 2015-05-18 06:23:31 UTC (rev 184447)
@@ -0,0 +1,87 @@
+description("Verify that we do not recurse infinitely through one of the Array->string conversion.");
+
+// Array that only contains itself.
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toString();`, "");
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toLocaleString();`, "");
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.join(",");`, "");
+
+// Array containing itself and a bunch of other objects.
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toString();`, "1,,WebKit!,");
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.toLocaleString();`, "1,,WebKit!,");
+shouldBeEqualToString(`var arrayDirectlyContainingItself = [];
+ arrayDirectlyContainingItself.push(1);
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.push("WebKit!");
+ arrayDirectlyContainingItself.push(arrayDirectlyContainingItself);
+ arrayDirectlyContainingItself.join("-");`, "1--WebKit!-");
+
+// Array indirectly containing itself.
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.toString();`, "1,1,2,5,6,,WebKit!");
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.toLocaleString();`, "1,1,2,5,6,,WebKit!");
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ arrayIndirectlyContainingItself.join("=");`, "1=1,2,5,6,=WebKit!");
+
+// Array containing another array with recursion.
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].toString();`, "z,1,1,2,5,6,,WebKit!,9");
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].toLocaleString();`, "z,1,1,2,5,6,,WebKit!,9");
+shouldBeEqualToString(`var arrayIndirectlyContainingItself = [];
+ arrayIndirectlyContainingItself.push(1);
+ arrayIndirectlyContainingItself.push([1, 2, [5, 6, [arrayIndirectlyContainingItself]]]);
+ arrayIndirectlyContainingItself.push("WebKit!");
+ ["z", arrayIndirectlyContainingItself, 9].join("&");`, "z&1,1,2,5,6,,WebKit!&9");
+
+// Indirectly recurse to an other of the functions. The object do not contains itself, but contains object that recursively call
+// an array to string conversion.
+shouldBeEqualToString(`var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].toString();`, "z,a,,,,WebKit!,9");
+shouldBeEqualToString(`var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].toLocaleString();`, "z,a,,,,WebKit!,9");
+shouldBeEqualToString(`var arrayIndirectlyConvertingItself = ["a"];
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.toLocaleString() } });
+ arrayIndirectlyConvertingItself.push({ array: arrayIndirectlyConvertingItself, toString: function() { return this.array.join("~") } });
+ arrayIndirectlyConvertingItself.push("WebKit!");
+ ["z", arrayIndirectlyConvertingItself, 9].join("*");`, "z*a,,,,WebKit!*9");
Modified: trunk/Source/_javascript_Core/ChangeLog (184446 => 184447)
--- trunk/Source/_javascript_Core/ChangeLog 2015-05-18 06:16:58 UTC (rev 184446)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-05-18 06:23:31 UTC (rev 184447)
@@ -1,3 +1,29 @@
+2015-05-17 Benjamin Poulain <[email protected]>
+
+ [JSC] Make StringRecursionChecker faster in the simple cases without any recursion
+ https://bugs.webkit.org/show_bug.cgi?id=145102
+
+ Reviewed by Darin Adler.
+
+ In general, the array targeted by Array.toString() or Array.join() are pretty
+ simple. In those simple cases, we spend as much time in StringRecursionChecker
+ as we do on the actual operation.
+
+ The reason for this is the HashSet stringRecursionCheckVisitedObjects used
+ to detect recursion. We are constantly adding and removing objects which
+ dirty buckets and force constant rehash.
+
+ This patch adds a simple shortcut for those simple case: in addition to the HashSet,
+ we keep a pointer to the root object of the recursion.
+ In the vast majority of cases, we no longer touch the HashSet at all.
+
+ This patch is a 12% progression on the overall score of ArrayWeighted.
+
+ * runtime/StringRecursionChecker.h:
+ (JSC::StringRecursionChecker::performCheck):
+ (JSC::StringRecursionChecker::~StringRecursionChecker):
+ * runtime/VM.h:
+
2015-05-17 Filip Pizlo <[email protected]>
Insert store barriers late so that IR transformations don't have to worry about them
Modified: trunk/Source/_javascript_Core/runtime/StringRecursionChecker.h (184446 => 184447)
--- trunk/Source/_javascript_Core/runtime/StringRecursionChecker.h 2015-05-18 06:16:58 UTC (rev 184446)
+++ trunk/Source/_javascript_Core/runtime/StringRecursionChecker.h 2015-05-18 06:23:31 UTC (rev 184447)
@@ -52,7 +52,15 @@
VM& vm = m_exec->vm();
if (!vm.isSafeToRecurse())
return throwStackOverflowError();
- bool alreadyVisited = !vm.stringRecursionCheckVisitedObjects.add(m_thisObject).isNewEntry;
+
+ bool alreadyVisited = false;
+ if (!vm.stringRecursionCheckFirstObject)
+ vm.stringRecursionCheckFirstObject = m_thisObject;
+ else if (vm.stringRecursionCheckFirstObject == m_thisObject)
+ alreadyVisited = true;
+ else
+ alreadyVisited = !vm.stringRecursionCheckVisitedObjects.add(m_thisObject).isNewEntry;
+
if (alreadyVisited)
return emptyString(); // Return empty string to avoid infinite recursion.
return JSValue(); // Indicate success.
@@ -74,8 +82,14 @@
{
if (m_earlyReturnValue)
return;
- ASSERT(m_exec->vm().stringRecursionCheckVisitedObjects.contains(m_thisObject));
- m_exec->vm().stringRecursionCheckVisitedObjects.remove(m_thisObject);
+
+ VM& vm = m_exec->vm();
+ if (vm.stringRecursionCheckFirstObject == m_thisObject)
+ vm.stringRecursionCheckFirstObject = nullptr;
+ else {
+ ASSERT(vm.stringRecursionCheckVisitedObjects.contains(m_thisObject));
+ vm.stringRecursionCheckVisitedObjects.remove(m_thisObject);
+ }
}
}
Modified: trunk/Source/_javascript_Core/runtime/VM.h (184446 => 184447)
--- trunk/Source/_javascript_Core/runtime/VM.h 2015-05-18 06:16:58 UTC (rev 184446)
+++ trunk/Source/_javascript_Core/runtime/VM.h 2015-05-18 06:23:31 UTC (rev 184447)
@@ -453,6 +453,7 @@
VMEntryScope* entryScope;
+ JSObject* stringRecursionCheckFirstObject { nullptr };
HashSet<JSObject*> stringRecursionCheckVisitedObjects;
LocalTimeOffsetCache localTimeOffsetCache;
