DevTools: n^2 -> n while loading heap snapshots and timeline files.

Source/devtools/front_end/common/TextUtils.js

Index: Source/devtools/front_end/common/TextUtils.js
diff --git a/Source/devtools/front_end/common/TextUtils.js b/Source/devtools/front_end/common/TextUtils.js
index 5f7f05feaa355bfc845f677c522679db4dd179d7..1e260eba5f9e926e5a1399212258e07c22c9e917 100644
--- a/Source/devtools/front_end/common/TextUtils.js
+++ b/Source/devtools/front_end/common/TextUtils.js
@@ -121,45 +121,6 @@ WebInspector.TextUtils = {
     },
 
     /**
-     * @param {string} source
-     * @param {number=} startIndex
-     * @param {number=} lastIndex
-     * @return {number}
-     */
-    findBalancedCurlyBrackets: function(source, startIndex, lastIndex)
-    {
-        // The function is performance sensitive.
-        lastIndex = lastIndex || source.length;
-        startIndex = startIndex || 0;
-        var counter = 0;
-
-        var index = startIndex;
-        while (index < lastIndex) {
-            // This part counts brackets until end of string or a double quote.
-            for (; index < lastIndex; ++index) {
-                var character = source[index];
-                if (character === "\"")
-                    break;
-                else if (character === "{")
-                    ++counter;
-                else if (character === "}") {
-                    if (--counter === 0)
-                        return index + 1;
-                }
-            }
-            if (index === lastIndex)
-                return -1;
-            // This part seeks the closing double quote which could have even number of back slashes prefix.
-            var regexp = WebInspector.TextUtils._ClosingDoubleQuoteRegexp;
-            regexp.lastIndex = index;
-            if (!regexp.test(source))
-                return -1;
-            index = regexp.lastIndex;
-        }
-        return -1;
-    },
-
-    /**
      * @param {string} line
      * @return {string}
      */
@@ -191,7 +152,6 @@ WebInspector.TextUtils = {
 }
 
 WebInspector.TextUtils._SpaceCharRegex = /\s/;
-WebInspector.TextUtils._ClosingDoubleQuoteRegexp = /[^\\](?:\\\\)*"/g;
 
 /**
  * @enum {string}
@@ -202,3 +162,77 @@ WebInspector.TextUtils.Indent = {
     EightSpaces: "        ",
     TabCharacter: "\t"
 }
+
+/**
+ * @constructor
+ * @param {function(string)} callback
+ * @param {boolean=} findMultiple
+ */
+WebInspector.TextUtils.BalancedJSONTokenizer = function(callback, findMultiple)
+{
+    this._callback = callback;
+    this._index = 0;
+    this._balance = 0;
+    this._buffer = "";
+    this._findMultiple = findMultiple || false;
+    this._closingDoubleQuoteRegex = /[^\\](?:\\\\)*"/g;
+}
+
+WebInspector.TextUtils.BalancedJSONTokenizer.prototype = {
+    /**
+     * @param {string} chunk
+     */
+    write: function(chunk)
+    {
+        this._buffer += chunk;
+        var lastIndex = this._buffer.length;
+
+        while (this._index < lastIndex) {

[alph, 2015/03/01 11:30:13]

this function seems to be performance sensitive ;-)
so could you please put this._index and _buffer to local vars?

[pfeldman, 2015/03/01 12:18:53]

Done.

+            // This part counts brackets until end of string or a double quote.
+            for (; this._index < lastIndex; ++this._index) {
+                var character = this._buffer[this._index];
+                if (character === "\"")
+                    break;
+                else if (character === "{")
+                    ++this._balance;
+                else if (character === "}") {
+                    if (--this._balance === 0) {
+                        this._lastBalancedIndex = this._index + 1;
+                        if (!this._findMultiple) {

[alph, 2015/03/01 11:30:13]

That behavior seems strange.
You report a single balanced substring per chunk. In the case when there are
several per chunk it will be lagging behind more and more with each chunk.
So you will have to call write("") at the end several times to extract all the
pending balanced strings.

[pfeldman, 2015/03/01 12:18:53]

This is a "one shot" operation, there is no accumulated wait. Heap profiler only
wants the first chunk, then it discards this tokenizer.

+                            this._reportBalanced();
+                            return;
+                        }
+                    }
+                }
+            }
+
+            if (this._index === lastIndex)
+                break;
+
+            // This part seeks the closing double quote which could have even number of back slashes prefix.

[alph, 2015/03/01 11:30:13]

Mind to move this part right under the if (character === "\"")
you should be able to get rid of nested loops then.

[pfeldman, 2015/03/01 12:18:53]

This is a great idea! Done.

+            this._closingDoubleQuoteRegex.lastIndex = this._index;
+            if (!this._closingDoubleQuoteRegex.test(this._buffer))
+                break;
+            this._index = this._closingDoubleQuoteRegex.lastIndex;
+        }
+        this._reportBalanced();
+    },
+
+    _reportBalanced: function()
+    {
+        if (this._lastBalancedIndex) {
+            this._callback(this._buffer.slice(0, this._lastBalancedIndex));
+            this._buffer = this._buffer.slice(this._lastBalancedIndex);
+            this._index -= this._lastBalancedIndex;
+            this._lastBalancedIndex = 0;
+        }
+    },
+
+    /**
+     * @return {string}
+     */
+    remainder: function()
+    {
+        return this._buffer;
+    }
+}