Five Free Copies of Upcoming O’Reilly Book ‘High Performance JavaScript’

Update (2010-02-25): This contest is now closed.

Book cover: High Performance JavaScript

Last year, Yahoo! engineer and all-around JavaScript badass Nicholas Zakas asked if I was interested in writing a chapter for a new book on JavaScript performance that he was working on. I agreed, and that book, High Performance JavaScript, is now available for preorder at Amazon and other fine book retailers.

In addition to the wide-ranging content by Nicholas and a chapter on string and regular expression performance by yours truly, chapters were also contributed by an awesome lineup of JavaScript performance gurus: Ross Harmes, Julien Lecomte, Stoyan Stefanov, and Matt Sweeney. This book is unique in its laser-focus on optimizing the performance of your JavaScript applications, and covers many advanced topics in the process. The chapter on strings and regular expressions provides what I think is easily the most in-depth coverage of cross-browser JavaScript regex performance currently available.

Here's the list of chapters:

  1. Loading and Execution
  2. Data Access
  3. DOM Scripting (Stoyan Stefanov)
  4. Algorithms and Flow Control
  5. Strings and Regular Expressions (Steven Levithan)
  6. Responsive Interfaces
  7. Ajax (Ross Harmes)
  8. Programming Practices
  9. Build and Deployment (Julien Lecomte)
  10. Tools (Matt Sweeney)

To celebrate the completion of this book, I'm giving away three copies. O'Reilly Media increased the offer to five books! All you need to do is comment on this post by February 24th, and I'll pick five people to send a copy to as soon as it's released (Amazon says March 15th). If you prefer, I'd be happy to send you a copy of Regular Expressions Cookbook instead (please note which book you want in your comment). Four winners will be chosen at random from the pool of unique commenters (I'll be tracking IPs), and the fifth based on the reason given for why you want a copy.

Make sure to include your email address in the comment form, since I'll need it to contact you if you're selected (your email address won't be used for any other purpose). Good luck, and congratulations to Nicholas Zakas and all the other authors on completing a fantastic new book!

Edit (2010-02-05): My blog has been offline more often than not for the first two days after posting this, and many people have reported that they were unable to post a comment. I apologize for the screw-up—my blog is now on a different server, and the problems should be resolved. Please try again!

Edit (2010-02-08): O'Reilly Media kindly offered to pick up the tab for this giveaway, and increased the winnings to five books!

Edit (2010-02-09): Nicholas Zakas posted more information about High Performance JavaScript on his blog: Announcing High Performance JavaScript.

Edit (2010-02-25): This contest is now closed. Winners will be announced here shortly.

Edit (2010-03-03): Following are the winners of this giveaway (the first four were chosen randomly):

  1. David Henderson
  2. Daniel Trebbien
  3. Lea Verou
  4. Stefan "schnalle" Schallerl
  5. Adam Crabtree

No. 5 Adam Crabtree, who wants to review the book and share it with members of the DallasJS Meetup Group, wins the nonrandom drawing for the best reason to win a copy. Runners up for this selection were Yoav, who promised to donate the book to a high school library after he's done with it; Nick Carter, who threatened me with his wrath if he doesn't win (I'll have to endure); Paul Irish, who kindly offered to have my last name corrected (to that of a sea monster) in exchange for winning; Alexei, a technical editor of a couple of Nicholas Zakas's previous books who'd like to know how many errors this one contains; and Marcel Korpel, who wants to improve his users' health by reducing the "headaches, general stress and insomnia" they suffer while waiting on his websites. 🙂

The winners have been informed by email about how to collect their prize. Thanks to everyone for playing!

Timed Memoization

Certain operations are computationally expensive, but because their results might change over time or due to outside influences, they don't lend themselves to typical memoization — take for example getElementsByClassName. Here's a JavaScript timed memoization decorator / higher-order-function I made to help with these cases, which accepts an optional expiration argument in milliseconds.

function memoize (functor, expiration) {
	var memo = {};
	return function () {
		var key = Array.prototype.join.call(arguments, "§");
		if (key in memo)
			return memo[key];
		if (expiration)
			setTimeout(function () {delete memo[key];}, expiration);
		return memo[key] = functor.apply(this, arguments);
	};
}

This approach allows you to turn any function into a memoizing function. Note that return values are memoized for each set of arguments. However, due to technical constraints it's only reliable when the arguments are arrays or scalar values, but you could easily use e.g. a toJSON method rather than join to serialize objects as part of the cache key (at some additional overhead cost).

You can use the above code like this:

// Make a function which memoizes for 1000 milliseconds at a time
var fn = memoize(function () {
	Array(500000).join("."); // slow
	return true;
}, 1000);

…Or leave out the expiration argument to permanently memoize.

Here are a couple more posts on JavaScript memoization:

Performance of Greedy vs. Lazy Regex Quantifiers

A common misconception about regular expression performance is that lazy quantifiers (also called non-greedy, reluctant, minimal, or ungreedy) are faster than their greedy equivalents. That's generally not true, but with an important qualifier: in practice, lazy quantifiers often are faster. This seeming contradiction is due to the fact that many people rely on backtracking to compensate for the impreciseness of their patterns, often without realizing this is what they're doing. Hence, the previously mentioned misconception stems from that fact that lazy quantifiers often result in much less backtracking when combined with long subject strings and the (mis)use of overly flexible regex tokens such as the dot.

Consider the following simple example: When the regexes <.*?> and <[^>]*> are applied to the subject string "<0123456789>", they are functionally equivalent. The only difference is how the regex engine goes about generating the match. However, the latter regex (which uses a greedy quantifier) is more efficient, because it describes what the user really means: match the character "<", followed by any number of characters which are not ">", and finally, match the character ">". Defined this way, it requires no backtracking in the case of any successful match, and only one backtracking step in the case of any unsuccessful match. Hand-optimization of regex patterns largely revolves around the ideas of reducing backtracking and the steps which are potentially required to match or fail at any given character position, and here we've reduced both cases to the absolute minimum.

So what exactly is different about how a backtracking, leftmost-first regex engine (your traditional NFA engine type, which describes most modern, Perl-derivative flavors) goes about matching our subject text when working with these two regexes? Let's first take a look at what happens with <.*?>. I'll use the RegexBuddy debugger style to illustrate each step.

Note: If you're reading this in a feed reader or aggregator which strips out inline styles, see the original post, which should make things much easier to follow.

  1. Beginning match attempt at character 0
  2. <
  3. <ok
  4. <backtrack
  5. <0
  6. <0backtrack
  7. <01
  8. <01backtrack
  9. <012
  10. <012backtrack
  11. <0123
  12. <0123backtrack
  13. <01234
  14. <01234backtrack
  15. <012345
  16. <012345backtrack
  17. <0123456
  18. <0123456backtrack
  19. <01234567
  20. <01234567backtrack
  21. <012345678
  22. <012345678backtrack
  23. <0123456789
  24. <0123456789>
  25. Match found

The text ok means the engine completed a successful, zero-length match, and backtrack shows where the engine backtracks to the last choice point, which it does after trying and failing to match the next token (>). As you can see here, with lazy quantification the engine backtracks forward after each character which is not followed by ">".

Here's what happens with <[^>]*>:

  1. Beginning match attempt at character 0
  2. <
  3. <0123456789
  4. <0123456789>
  5. Match found

As you can see, 20 fewer steps are required, and there is no backtracking. This is faster, and can also increase the potential for internal optimization of the matching process. As a simple example, when greedily quantifying an any-character token, the engine can simply move the read-head to the end of the string, rather than testing every character along the way (this is an oversimplification of the process taken by modern regex engines, but you get the idea). You can see this exact kind of internal optimization occurring in IE with the "trim8" pattern in my Faster JavaScript Trim post from a while back.

You might be wondering what happens if we use the regex <.*>. Take a look:

  1. Beginning match attempt at character 0
  2. <
  3. <0123456789>
  4. <0123456789>backtrack
  5. <0123456789
  6. <0123456789>
  7. Match found

Although the output didn't change much when used with our subject string of "<0123456789>", you can see that the .* caused the engine to trek all the way to the end of the string, then backtrack from the right. If we'd used a 10,000-character string without newlines or other ">" characters, that would've resulted in nearly 10,000 backtracks.

In short:

  • Make your patterns more explicit where it makes sense, to better guide the regex engine and avoid backtracking.
  • Be careful about using the more appropriate type of quantification (to your best approximation, since this often depends on the subject string) even when it has no impact on the text matched by your regex.
  • If possible, avoid greedy quantification of the dot and other needlessly flexible tokens.

JavaScript String Multiplication Performance Exploration

Since JavaScript concatenates strings with the + operator, it would be nifty if it would also let you multiply strings using e.g. str * 10 (as can be done in Python, at least). Since you can't do that, and no native string multiplication method is provided, I recently explored a few ways to pull it off…

A naive approach to writing a string multiplier function goes something like this:

function mul0 (str, num) {
	if (!num) return "";
	var newStr = str;
	while (--num) newStr += str;
	return newStr;
}

As many JavaScripters are aware, that isn't the best approach since string concatenation can be quite slow in Internet Explorer. And while IE tends to get a bad rap for this (fortunately, the IE team is fixing the problem in the next version of their browser), Firefox isn't exactly blazing fast at string concatenation either. Due to the performance issues, the typical string multiplication approach is to build an array and join it. Here's a nice, short way to do that:

function mul1 (str, num) {
	return num ? Array(num + 1).join(str) : "";
}

Note that the falsy num handling is probably not warranted in this case since the function would handle value 0 correctly without it. It's done anyway to keep functionality equivalent across the variations.

Unfortunately, mul1 can still be pretty slow in Firefox 2 when multiplying large strings many times. It might be unnoticeable with small strings and repetition numbers, but the completion time goes up at a super-linear rate as the numbers increase. In search of a faster solution, I tried using a regex to keep down the size of the string being worked with:

var mul2 = function () {
	function mul (str, num) {
		return Array(num + 1).join(str);
	}
	return function (str, num) {
		return num ? str.replace(/^/, mul("$'", num - 1)) : "";
	};
}();

The above multiplies the two-character string "$'" num - 1 times, then uses that as the replacement for a regex which just matches the start of the string ($' returns the text to the right of the match). How does that perform? It delivers in Firefox 2 on my Windows Vista system, with numbers like 95ms vs. 29800ms (mul1) when using a 2700x2700 string length/multiplier. However, based on my testing, that sort of speed gain appears to be limited to Firefox, and in Safari 3 beta mul2 is considerably slower that the alternative versions.

Finally, I tried creating a version which multiplied the string at an exponential rate:

function mul3 (str, num) {
	if (!num) return "";
	var	orig = str,
		soFar = [str],
		added = 1,
		left, i;
	while (added < num) {
		left = num - added;
		str = orig;
		for (i = 2; i < left; i *= 2) {
			str += str;
		}
		soFar.push(str);
		added += (i / 2);
	}
	return soFar.join("");
}

Although that might be more code than you're willing to dedicate to a string multiplication method, it's the fastest of the above versions on average cross-browser. I've also tried a few variations using from zero to two arrays and various array methods (push, concat, etc.), but the above seems to be the fastest on average across the big four browsers.

Make sure to try the tests for yourself, and let me know your thoughts and how you would improve the code.


Edit: Kris Kowal contributed mul4 (shown below, and added to the test page). It uses binary interpolation, and in Kris's words "it takes advantage of a fun bitwise identity: (1 << n) == Math.pow(2, n)". On my system it's significantly faster than mul3 in Firefox, but a little slower than mul3 in IE, Safari, and Opera. Due to its high speed and lighter weight, this looks like the one to beat. Try the test page in several browsers and see what you think.

function mul4 (str, num) {
	var acc = [];
	for (var i = 0; (1 << i) <= num; i++) {
		if ((1 << i) & num)
			acc.push(str);
		str += str;
	}
	return acc.join("");
}

Edit 2: LiuCougar of the Dojo development team posted a follow-up which includes several additional variations, and David Andersson emailed me an additional four variations including this one:

function mul8 (str, num) {
	var	i = Math.ceil(Math.log(num) / Math.LN2),
		res = str;
	do {
		res += res;
	} while (0 < --i);
	return res.slice(0, str.length * num);
}

I should clarify however that this is mostly just academic discussion, since repeating the kinds of strings in the test page as many times as it does is a pretty crazy idea. Still, it's fun to experiment. smile


Edit 3: All the variations posted or emailed in response to this post can be seen at stevenlevithan.com/demo/mul/all.js. For the sake of consistency I've made a few minor adjustments to some of the functions such as whitespace tweaks and renaming the input arguments to str and num.

Regex Performance Optimization

Crafting efficient regular expressions is somewhat of an art. In large part, it centers around controlling/minimizing backtracking and the number of steps it takes the regex engine to match or fail, but the fact that most engines implement different sets of internal optimizations (which can either make certain operations faster, or avoid work by performing simplified pre-checks or skipping unnecessary operations, etc.) also makes the topic dependent on the particular regex flavor and implementation you're using to a significant extent. Most developers aren't deeply aware of regex performance issues, so when they run into problems with regular expressions running slowly, their first thought is to remove the regexes. In reality, most non-trivial regexes I've seen could be significantly optimized for efficiency, and I've frequently seen dramatic improvements as a result of doing so.

The best discussion of regex optimization I've seen is chapter six (a good 60 pages) of Mastering Regular Expressions, Third Edition by Jeffrey Friedl. Unfortunately, other good material on the subject is fairly scarce, so I was pleasantly surprised to stumble upon the recent article Optimizing regular expressions in Java by Cristian Mocanu. Of course, it is in part Java specific, but for the most part it is a good article on the basics of optimization for traditional NFA regex engines. Check it out.

Have you seen any good articles or discussions about regular expression performance or efficiency optimization recently? Do you have any questions about the subject? Experience or pointers to share? Let me know. (I hope to eventually write up an in-depth article on JavaScript regex optimization, with lots of tips, techniques, and cross-browser benchmarks.)