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

Source/devtools/front_end/common/TextUtils.js

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 103 matching lines @@
                     wordCallback(text.substring(startWord, i));
                 startWord = -1;
             } else if (startWord === -1)
                 startWord = i;
         }
         if (startWord !== -1)
             wordCallback(text.substring(startWord));
     },
 
     /**
-     * @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}
      */
     lineIndent: function(line)
     {
         var indentation = 0;
         while (indentation < line.length && WebInspector.TextUtils.isSpaceChar(line.charAt(indentation)))
             ++indentation;
         return line.substr(0, indentation);
     },
@@ skipping 11 matching lines @@
      * @param {string} text
      * @return {boolean}
      */
     isLowerCase: function(text)
     {
         return text === text.toLowerCase();
     }
 }
 
 WebInspector.TextUtils._SpaceCharRegex = /\s/;
-WebInspector.TextUtils._ClosingDoubleQuoteRegexp = /[^\\](?:\\\\)*"/g;
 
 /**
  * @enum {string}
  */
 WebInspector.TextUtils.Indent = {
     TwoSpaces: "  ",
     FourSpaces: "    ",
     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;
+    }
+}