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;
+        // This does speed things up 5 times.

[alph, 2015/03/01 13:26:33]

That's strange provided you're not using buffer in the loop. ;-)

[pfeldman, 2015/03/01 14:04:59]

I was testing it with and without locals and was getting 150ms vs 750ms. Now no
matter how I run it is 150.

+        var buffer = this._buffer;
+        for (var index = this._index; index < lastIndex; ++index) {
+            var character = this._buffer[index];
+            if (character === "\"") {
+                this._closingDoubleQuoteRegex.lastIndex = index;
+                if (!this._closingDoubleQuoteRegex.test(this._buffer))
+                    break;
+                index = this._closingDoubleQuoteRegex.lastIndex - 1;
+            } else if (character === "{") {
+                ++this._balance;
+            } else if (character === "}") {
+                if (--this._balance === 0) {
+                    this._lastBalancedIndex = index + 1;
+                    if (!this._findMultiple) {

[alph, 2015/03/01 13:26:33]

break;

[pfeldman, 2015/03/01 14:04:59]

Done.

+                        this._reportBalanced();
+                        return;
+                    }
+                }
+            }
+        }
+        this._index = index;
+        this._reportBalanced();
+    },
+
+    _reportBalanced: function()
+    {
+        if (this._lastBalancedIndex) {

[alph, 2015/03/01 13:26:33]

nit: if (!...) return;

[pfeldman, 2015/03/01 14:04:59]

Done.

+            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;
+    }
+}