A lesson of RegExp: 50x faster with just one line patch

While I'm developing WebSHi (which is the fastest syntax highlighter written by JavaScript), I also write many performance testings for other rivals. One of them is SyCODE Syntax Highlighter, which is written by silverdrag (水月). It derives from the famous SyntaxHighlighter 1.5.x (dp.SH for short) and as silverdrag's words, it should be 5x to 10x faster than original dp.SH.

But unfortunately, my testings can't prove it. Though it won't trigger the "script slowly" dialog like dp.SH when highlighting large file, in most cases, it only shows 2x faster than dp.SH on IE6. On the other side, when I tested it on FF, I was so surprised that SyCODE is extremely slow, it will cost 5s+ for processing a 700 lines JavaScript file while the original dp.SH only half second.

It's very strange, so I digged into SyCODE. I found that SyCODE highlights more words for JavaScript language (currently all my testcases are to highlight some JavaScript source code files). The original dp.SH (and most other rivals) only highlights the keywords of JavaScript language. SyCODE also highlights global names like Array, Boolean, String, etc., and properties and methods like alert, charAt, onclick etc.. That means SyCODE need to do more text searching and replacement. I disabled such features and tested again, this time SyCODE is 2x faster than dp.SH.

So you will think the problem is just the extra words replacement. And what interesting is it just affect FF a lot, even SyCODE do more text processing, it's still faster than (or at least as fast as) dp.SH on other browsers (Safari, Chrome, Opera and IE).

I'm curious about the root cause of the problem. After some researching, I located it. Just one simple function:

GetKeywords: function(str) {
 return '\\b' + str.replace(/\s+/g, '\\b|\\b') + '\\b';
},

The function GetKeywords is used to generate a regexp for keywords search and replacement. For example, GetKeywords("abstract break byte case catch") will return a regexp /\babstract\b|\bbreak\b|\bbyte\b|\bcase\b|\bcatch\b/.

The code is straightforward, but it's bad and generate a very inefficient regexp.

The keypoint is \b, \b is a word boundary assertion. To test whether a position is a word boundary, the regexp engine need to consider both the left character of the position and the right character of the position. If one is a word character (aka a-z, A-Z, 0-9 and the underscore "_") and the other is not, then it's a word boundary. You see it need both look forward one char and look backward one char. Though \b assertion is not very expensive, each failed match of /\babstract\b|\bbreak\b|\bbyte\b|\bcase\b|\bcatch\b/ will do such look forward/backward 10 times, and JavaScript language has 50+ keywords means each failed match will do 100 times, and SyCODE add 400+ properties/methods words means extra 800+ times!

Of coz, \b assertion can be easily optimized, but our test result shows that FF's regexp engine doesn't do a good optimization at all.

Anyway, there is a very cheap way to solve the problem. Most of those \b assertions are unnecessary. /\babstract\b|\bbreak\b|\bbyte\b|\bcase\b|\bcatch\b/ can be rewrite as /\b(?:abstract|break|byte|case|catch)\b/, those two regexp are equal, the only difference is the latter only need two \b assertion. Yes, we just need two, even SyCODE add 400+ words, we still just need two.

It's trivial to fix GetKeywords:

GetKeywords: function(str) {
 return '\\b' + str.replace(/\s+/g, '\\b|\\b') + '\\b';
 return '\\b(' + str.replace(/\s+/g, '|') + ')\\b';
},

Let's see the result of applying this one line patch:

Test results of FF3

code lines	original	patched
700	6.7s	0.1s
1600	15.5s	0.3s
4300	41.5s	0.7s

Oops, one line code cause 50x difference.

Besides FF, the patch also help other browsers a lot.

Test results of 4300 lines of code

browser	original	patched
IE6	6.3s	2.8s
Safari3	2.6s	0.8s
Opera9	8.2s	1.7s
Chrome1	2.3s	0.5s

As we can see, even Chrome, which introduce a very optimized regexp engine, also shows at least 4x difference.

SyCODE derives from dp.SH, the GetKeywords function is also the legacy from dp.SH, and even the new SyntaxHighlighter 2 still use the similar code. Because dp.SH only highlight about 50 keywords for JavaScript langauge, you will not see performance issue like SyCODE, but applying this one line patch still introduce 20% faster on most browsers.

But this patch is not the end. In next article, I will discuss a complex technique to get another 10% to 40% faster for keywords search/replacement.

Transfer Arguments with showModelessDialog and window.open

The document of showModelessDialog on MSDN said:

Because a modeless dialog box can include a URL to a resource in a different domain, do not pass information through the vArguments parameter that the user might consider private. The vArguments parameter can be referenced within the modeless dialog box using the dialogArguments property of the window object.

But, again, MS lies. showModelessDialog can't pass arguments to a different domain . If you open a dialog in a diff domain, window.dialogArguments of the dialog will be undefined (even dialogArguments is a literal string).

In fact, because dialogArguments could be an javascript object, there would be a security issue if such transfer is allowed.

To create a return value for showModelessDialog, set the vArguments parameter to a callback function or an object in the showModelessDialog call. In the modeless dialog box, you can reference this function or object through the dialogArguments property of the window object.

Imagine your site has a dialog use such callback method descripted above. But the hacker can easily get the name of the callback function from the source code of the dialog page. If cross domain access is allowed, the hacker could write his own page, provide his evil callback via dialogArguments and open your dialog page. Then he can publish his troy page in somewhere and fish your customers. If the users open his page, the best case would be leaking some info (but maybe password, if it's a login dialog), and in the worst case, the evil code is executed, hacker can do everything, such as transfer the user's money to his account (if it's a bank site).

Thanks to God, the hackers are disappointed because MS lied in their documents :P

BTW, I found some changes from IE6 to IE7. It is summarized in the below table. The similar functionality(window.open with dependent feature) in FF and Opera also tested here.

	same domain	same domain with diff port	diff domain
showModelessDialog (IE6)	Y	N	N
showModelessDialog (IE7)	Y	Y	N
window.open (Firefox2)	Y	N	N
window.open (Opera9)	Y	Y	N

For showModelessDialog, Y means the script in the dialog window can get dialogArguments.

For window.open, Y means the script in new window can access the variables which the parent window assigned to dialog window object. Code sample:

page1
=====
var newWin = window.open(page2, features);
newWin.abc = {toString:function(){return 'abc'}}

page2
=====
alert(window.abc); // return 'abc'

At last, IE have a timer issue. Code sample:

page1
=====
var newWin = window.showModelessDialog(page2, args, features);
newWin.abc = {toString:function(){return 'abc'}}

page2
=====
alert(window.abc); // return 'abc' when first access, otherwise undefined

window.onload = function () {

  alert(window.abc); // return 'abc' when first access, otherwise undefined

  setTimeout(function () {
    alert(window.abc); // return 'abc'
  }, 10);

}

Apparently, this issue is related to the cache issue of the showModelessDialog. If the page is loaded from the cache, all scripts in the page1 will executed before the second line of the page2 unless it is deferred by a timer.

Mozilla Bug 314874 Fixed

15 months ago, I submitted this bug. I'm very glad to see it is finally solved.

A bug of Douglas Crockford's uber

In Douglas Crockford's famous Classical Inheritance in JavaScript, he write a function named 'uber' which simulate 'super' for OO programming. Someone pointed out a bug of it, but don't understand why and just try to write his own OO solution.

Below is the test case:

function BaseClass() {}
BaseClass.prototype.getName = function() {
    return "BaseClass(" + this.getId() + ")";
}
BaseClass.prototype.getId = function() {
    return 1;
}

function SubClass() {}
SubClass.inherits(BaseClass);
SubClass.prototype.getName = function() {
    return "SubClass(" + this.getId() + ") extends " +
        this.uber("getName");
}
SubClass.prototype.getId = function() {
    return 2;
}

function MyClass() {}
MyClass.inherits(SubClass);
MyClass.prototype.getName = function() {
    return "MyClass(" + this.getId() + ") extends " +
        this.uber("getName");
}
MyClass.prototype.getId = function() {
    // Should always return 2 which is the result of SubClass.getId()
    return this.uber("getId");
}

alert(new TopClass().getName());

//Expect result: "MyClass(2) extends SubClass(2) extends BaseClass(2)"
//Actual result："MyClass(2) extends SubClass(1) extends BaseClass(1)"

I did some research about this interesting bug, and got the patch.

Douglas Crockford's original source

Function.prototype.inherits = function (parent) {
    var d = 0, p = (this.prototype = new parent());
    this.prototype.uber = function (name) {
        var f, r, t = d, v = parent.prototype;
        if (t) {
            while (t) {
                v = v.constructor.prototype;
                t -= 1;
            }
            f = v[name];
        } else {
            f = p[name];
            if (f == this[name]) {
                f = v[name];
            }
        }
        d += 1;
        r = f.apply(this, Array.prototype.slice.apply(arguments, [1]));
        d -= 1;
        return r;
    }
    return this;
}

My patched version

Function.prototype.inherits = function(parent) {
    var d = {}, p = (this.prototype = new parent());
    
    this.prototype.uber = function(name) {
     if (!(name in d)) d[name] = 0;
        var f, r, t = d[name], v = parent.prototype;
        if (t) {
            while (t) {
                v = v.constructor.prototype;
                t -= 1;
            }
            f = v[name];
        } else {
            f = p[name];
            if (f == this[name]) {
                f = v[name];
            }
        }
        d[name] += 1;
        r = f.apply(this, Array.prototype.slice.apply(arguments, [1]));
        d[name] -= 1;
        return r;
    }
}

The problem is because of d, which indicates the depth of supercall. In original code, every method share the same d, which will cause bug when nest call (one method call another). So give every method their own counter, solves the problem.

String format function for JavaScript

Note: This artical is the republication of my two posts A high performance string format function for JavaScript and Just another high performance string format function for JavaScript on csdn blog.

---

Last month, I wrote a logging tool for js, and to avoid performance depression, I need a string formatter function.

I found that though many js toolkit or framework provide string format function, such as Atlas, but they r not quite fast. Most r using String.replace(regex, func) to replace the placeholder(such as '{n}' or '$n'), but this function tend to slow, because every match will call the func, and js function calling is very expensive.

On the contrary, native functions r very fast, so to improve performance, we should utilize the native functions as possible as we can. A wonderful example is StringBuilder which use Array.join to concat the string.

So I create my String.format(), it's very fast.

Usage:

var name = 'world';
var result = 'Hello $1!'.format(name);
// result = "Hello world!"

var letters = String.format(
 '$1$2$3$4$5$6$7$8$9$10$11$12$13$14$15\
 $16$17$18$19$20$21$22$23$24$25$26',
 'a', 'b', 'c', 'd', 'e', 'f', 'g',
 'h', 'i', 'j', 'k', 'l', 'm', 'n',
 'o', 'p', 'q', 'r', 's', 't',
 'u', 'v', 'w', 'x', 'y', 'z');
// letters = "abcdefghijklmnopqrstuvwxyz"

The later one almost same fast as the former one, no other implementation can have the same performance as I know.

Note:

• It's depend on String.replace(regex, string), so u can use at most 99 placeholder($1 to $99), but if the script engine is too old, it maybe only support nine ($1 to $9) or not work at all (eg. JScript before 5.5?).
• literal $ should be escape into $$ (two $).
• $` and $' will be reomoved, and $& will replaced into some strange things :)
• '$1 1'.format('a') result in 'a 1', if you want to strip the space, u can't write '$11'.format(...) because it will try to match the 11nd parameter, u should write '$011'.format(...) instead.
• There is a magic character which you can't use anyway, currently I choose 0x1f (which means data separator in ascii and unicode).

Source code:

// Copyright (c) HE Shi-Jun , 2006
// Below codes can be used under GPL (v2 or later) or LGPL (v2.1 or later) license

if (!String._FORMAT_SEPARATOR) ...{
    String._FORMAT_SEPARATOR = String.fromCharCode(0x1f);
    String._FORMAT_ARGS_PATTERN = new RegExp('^[^' + String._FORMAT_SEPARATOR + ']*'
      + new Array(100).join('(?:.([^' + String._FORMAT_SEPARATOR + ']*))?'));
}
if (!String.format)
    String.format = function (s) ...{
    return Array.prototype.join.call(arguments, String._FORMAT_SEPARATOR).
    replace(String._FORMAT_ARGS_PATTERN, s);
}
if (!''.format)
    String.prototype.format = function () ...{
    return (String._FORMAT_SEPARATOR +
    Array.prototype.join.call(arguments, String._FORMAT_SEPARATOR)).
    replace(String._FORMAT_ARGS_PATTERN, this);
}

Below is just another format function:

// Copyright (c) HE Shi-Jun , 2006
// Below codes can be used under GPL (v2 or later) or LGPL (v2.1 or later) license

format2.cache = ...{};
function format2(pattern) ...{
    if (!(pattern in format2.cache)) ...{
        format2.cache[pattern] = new Function('"' + pattern.replace(/"/g, '\"').replace(/$([0-9]+)/g, '" + arguments[$1] + "').replace(/$$/g, '$') + '"');
    }
    return format2.cache[pattern](arguments);
}

Compare to previous method, it's even more fast in heavy using (especially on FireFox and Opera), because it's compile the pattern to function and cache it. But this method will waste memory. So the best practice is combining these two methods.

And the no cache version here, but not helpful, because it's lose the advantage of cacheable and will be very slow on Opera:

// Copyright (c) HE Shi-Jun , 2006
// Below codes can be used under GPL (v2 or later) or LGPL (v2.1 or later) license

function format3(pattern) ...{
    return eval('"' + pattern.replace(/"/g, '\"').replace(/$([0-9]+)/g, '" + arguments[$1] + "').replace(/$$/g, '$') + '"');
}