Optimizing JavaScript Performance Through Custom Memory Allocation

(Translations available, see the end of the post)

Mozilla’s Kannan Vijayan had an intriguing result in running SunSpider ported to C++, asm.js and Dalvik. In the “Binary Trees” test, asm.js was the fastest by far. Kannan’s untested theory is that it boils down to memory allocation performance:

In asm.js, the compiled C++ is executed using a Javascript typed array as the “machine memory”. The machine memory is allocated once and then used for the entire program runtime. Calls to malloc from asm.js programs perform no syscalls. This may be the reason behind asm.js-compiled C++ doing better than native-compiled C++, but requires further investigation to confirm.

In the Hacker News discussion there were some comments there about the memory performance. duaneb said:

Anyone who has implemented a memory allocator knows how expensive it can be. If you have a simpler algorithm that works with your data, allocate a huge chunk and manage it yourself.

Some game developers reuse objects as a way to avoid unnecessary allocations/GC. An article was just posted in Smashing Magazine about Emmet LiveStyle which talks about how they reused objects in order to save allocations.

I don’t think that selective reuse of big chunks of memory is a tool in most JavaScript developers’ toolboxes right now, but it seems like a good idea in cases where you need consistent and smooth performance.

Update: Vyacheslav Egorov emailed me a link to Kannan’s graph that includes the JavaScript engine performance. In the binary tree case, the JavaScript implementation was the fastest by far. Perhaps the C++ was not well-tuned.

I don’t want to get too hung up on the benchmarks, because my main point is not “asm.js is faster than C++” (in fact, I’m not stating that at all). My point is that there ways to control memory management in JS that may be a non-obvious way to improve responsiveness.

(Russian translation available)

???? ???????? ?? ??????? ????? via ?????????????? ?? Softdroid: ???????????
?????????????????? JavaScript

Speaking at Adobe MAX (Extending Brackets)

In just a few weeks, I’ll be giving a talk at the Adobe MAX conference about extending Brackets with JavaScript. Web developers will find that Brackets is pretty easy to extend using techniques they already know. That’s probably why there are a lot of Brackets extensions already.

People who come to my session will learn how to build Brackets extensions. I plan to have plenty of code samples drawn from real extensions.

If you’re interested in attending, you can still register. Use the code MXSM13 to save $300. (Note also that a MAX pass comes with 1 year of Creative Cloud, which gives you access to a huge amount of software and services.)

If you do come to MAX, definitely find me and say hi!

Brackets Quick Open: That’s No Regex!

Ever since I first used TextMate several years ago, I’ve been hooked on “Quick Open” (the feature that lets you jump to any file in your project with just a few keystrokes). I have worked on Brackets’ version of this feature and I thought I’d take advantage of Brackets being open source to talk about how it works.

The current incarnation of Quick Open in Brackets is the third. It started very simply, just matching substrings in the filename if I remember correctly. Today, it relies on a module called StringMatch which:

  • searches across the entire file path, not just the name
  • gives preference to matches in the last part of the path (the name)
  • gives preference to matches on “special characters”
  • produces a score that attempts to get at a most likely match

Those “give preferences” bits are what make StringMatch a lot trickier than just applying a regex and my goal with this post is to touch upon some of what went in to producing good results. While working on Quick Open, which is in src/search/QuickOpen.js, I wanted to be able to type “qo” and have that file be the top match. With thousands of files in our repository, there are doubtless quite a few that match “qo”. Getting to the best match was key.

StringMatch in Action

StringMatch in Action

The stringMatch function

The StringMatch module has a function called stringMatch that takes a string to match against, the query string and an optional “specials” data structure. The function is stateless and doesn’t use any indexes (see the section on speed toward the end).

stringMatch returns information about the match (if the query matches the string) to allow highlighting and sorting by score. stringMatch itself doesn’t do very much. It’s job is to glue together the other functions in the module.

Special Characters

I mentioned a “specials” data structure and how preference is given to “special” characters. What are these mysterious special beings? As stated in the comments for findSpecialCharacters:

  • the first character
  • “/” and the character following the “/” (path separators)
  • “_”, “.” and “-” and the character following it (other characters used to separate parts of filenames)
  • an uppercase character that follows a lowercase one (think camelCase)

So, the job of findSpecialCharacters is to create a list of indexes of these special characters of the string that is being checked against the query. Additionally, findSpecialCharacters returns the index into the list of special characters that represents the beginning of the “last segment”. The code in findSpecialCharacters is straightforward, simply reading each character of the string and keeping track of what it sees as it goes along.

The stringMatch function will call findSpecialCharacters if it’s not given the specials data structure at the beginning. But, as we’ll see in the section on speed, hanging on to the result of findSpecialCharacters gives us a bit of a boost.

Searching the String

stringMatch calls a function called _wholeStringSearch which is responsible for taking the string and the query and producing the list of matches. This happens in two steps:

  1. the query is run against the “last segment” (the file name)
  2. anything that’s left over from that search is matched against the part of the string before the last segment

There’s a separate function (_lastSegmentSearch) that’s responsible for trying the query against the last segment, which is not as simple as it might seem.

With a query of “qo”, it’s easy to see how that can match in the last segment of src/search/QuickOpen.js. But, imagine that I typed “sqo” instead. “sqo” is clearly still a match, but searching for “sqo” in just the last segment fails. So, it seeks out the largest match that it can get in the last segment. It would find that “qo” matches in QuickOpen.js and hunt starting at the beginning of the string for the remaining “s”.

It’s entirely possible that the entire query doesn’t match against the last segment, which means that all of the work of checking each substring of the query against the last segment was a waste. On the other hand, users will generally have a certain file in mind that they want to open and I’d be surprised if they weren’t typing any characters from the file name.

Generating the Matches

The _generateMatchList function is the craziest bit in the file. There’s a reason it has 70 lines of comments preceding the function.

Why does it have to be so crazy? It all comes back to those preferences of which characters to search first. If I have a file called QuoteOpus.js and I search for “qo”, I want the match to be QuoteOpus, not QuoteOpus. I also want QuickOpen.js to be a better match than Quote.js, even though both of those match “qo”.

There’s a loop toward the bottom of the function that is responsible for doggedly trying everything until it finds a match that works:


    while (true) {
        // keep looping until we've either exhausted the query or the string
        while (queryCounter < query.length && strCounter < str.length && strCounter <= deadBranches[queryCounter]) {
            if (state === SPECIALS_MATCH) {
                if (!findMatchingSpecial()) {
                    state = ANY_MATCH;

            if (state === ANY_MATCH) {
                // we look character by character for matches
                if (query[queryCounter] === str[strCounter]) {
                    // got a match! record it, and switch back to searching specials
                    result.push(new NormalMatch(strCounter++));
                    state = SPECIALS_MATCH;
                } else {
                    // no match, keep looking

        // if we've finished the query, or we haven't finished the query but we have no
        // more backtracking we can do, then we're all done searching.
        if (queryCounter >= query.length || (queryCounter < query.length && !backtrack())) {

We’re going to keep looking at characters until we hit the end of the string or the end of the query. We start out looking for matches among the special characters. Failing that, we’ll start looking character-by-character through the string until we find a match among the non-special characters. Searching for “qo” in Quote.js is going to find a match at the “Q” which it’s perfectly happy with. Then, it’ll try to match the “o” against the “.” (the next special character). Nope. No luck with the “j”, which is also special because it comes after the “.”. So, then it goes back and checks out the “u” before finally finding the “o” that matches.

Finding the special character matches is pretty straightforward, because we already have a list of indexes into the string where the special characters are located. The findMatchingSpecial function uses a counter to keep track of which special matched last and then proceeds to walk through the list of specials from there.

I rather wish the story could end there: scan through the matching specials and then scan through the non-special characters when that fails. In fact, I did initially end there. But, it turned out that there were cases that I missed entirely when I did that. And that’s where the deadBranches and backtrack() come into play in the loop above.

Here’s the example pulled from the comments of _generateMatchList:

 * A contrived example will help illustrate how the searching and backtracking works. It's a bit long,
 * but it illustrates different pieces of the algorithm which can be tricky. Let's say that we're
 * searching the string "AzzBzzCzdzezzDgxgEF" for "abcdex".
 * To start with, it will match "abcde" from the query to "A B C D E" in the string (the spaces 
 * represent gaps in the matched part of the string), because those are all "special characters".
 * However, the "x" in the query doesn't match the "F" which is the only character left in the
 * string.
 * Backtracking kicks in. The "E" is pulled off of the match list.
 * deadBranches[4] is set to the "g" before the "E". This means that for the 5th
 * query character (the "e") we know that we don't have a match beyond that point in the string.
 * To resume searching, the backtrack function looks at the previous match (the "D") and starts
 * searching in character-by-character (ANY_MATCH) mode right after that. It fails to find an
 * "e" before it gets to deadBranches[4], so it has to backtrack again.
 * This time, the "D" is pulled off the match list.
 * deadBranches[3] is set to the "z" before the "D", because we know that for the "dex" part of the
 * query, we can't make it work past the "D". We'll resume searching with the "z" after the "C".
 * Doing an ANY_MATCH search, we find the "d". We then start searching specials for "e", but we
 * stop before we get to "E" because deadBranches[4] tells us that's a dead end. So, we switch
 * to ANY_MATCH and find the "e".
 * Finally, we search for the "x". We don't find a special that matches, so we start an ANY_MATCH
 * search. Then we find the "x", and we have a successful match.

In the process of working on this, I read a bit about dynamic programming, which is an interesting topic and one of the ways in which you can solve the longest common substring problem (something I initially thought might be valuable for StringMatch). The idea that I ended up applying is that when we’re searching the string we can keep track of parts of the query that we’ve tried and found do not work past a certain point of the string. Those are the deadBranches. When we hit one, we know we need to backtrack farther.

What does backtracking look like?

    // This function implements the backtracking that is done when we fail to find
    // a match with the query using the "search for specials first" approach.
    // returns false when it is not able to backtrack successfully
    function backtrack() {

        // The idea is to pull matches off of our match list, rolling back
        // characters from the query. We pay special attention to the special
        // characters since they are searched first.
        while (result.length > 0) {
            var item = result.pop();

            // nothing in the list? there's no possible match then.
            if (!item) {
                return false;

            // we pulled off a match, which means that we need to put a character
            // back into our query. strCounter is going to be set once we've pulled
            // off the right special character and know where we're going to restart
            // searching from.

            if (item instanceof SpecialMatch) {
                // pulled off a special, which means we need to make that special available
                // for matching again

                // check to see if we've gone back as far as we need to
                if (item.index < deadBranches[queryCounter]) {
                    // we now know that this part of the query does not match beyond this
                    // point
                    deadBranches[queryCounter] = item.index - 1;

                    // since we failed with the specials along this track, we're
                    // going to reset to looking for matches consecutively.
                    state = ANY_MATCH;

                    // we figure out where to start looking based on the new
                    // last item in the list. If there isn't anything else
                    // in the match list, we'll start over at the starting special
                    // (which is generally the beginning of the string, or the
                    // beginning of the last segment of the string)
                    item = result[result.length - 1];
                    if (!item) {
                        strCounter = specials[startingSpecial] + 1;
                        return true;
                    strCounter = item.index + 1;
                    return true;
        return false;

The basic idea here is that we see that we’ve reached a point after which our query doesn’t match the remaining bit of the string, so we rewind any matches that we found to take us back before the last deadBranches point. After we’ve done that, we hang on to our newly identified “if you reach this part of the string with that part of the query, all hope is lost” point.

_generateMatchList returns a list of SpecialMatch and NormalMatch objects. We just need to return the list of matched indexes and the type of object shows whether the index was a special character or not (which is used in scoring).

Turning Matched Characters into Ranges and a Score

The _computeRangesAndScore function does a fairly straightforward transformation of the matched characters list into a set of ranges in the string that are used in highlighting which parts matched and the final score. There’s nothing very magical here, but you can see that there are 7 different components that go into the score at this point:

    if (DEBUG_SCORES) {
        scoreDebug = {
            special: 0,
            match: 0,
            lastSegment: 0,
            beginning: 0,
            lengthDeduction: 0,
            consecutive: 0,
            notStartingOnSpecial: 0

You can also see that with 7 different parts of the score, being able to set a flag to see how each part adds to the whole would come in handy. Coming up with the exact numbers used in scoring was not very scientific, instead coming as a result of looking at various comparisons and adjusting the parameters until the results felt like the kind of results we wanted to see.

Test-driven to Get It Right

I used test-driven development to create StringMatch (you can check out the tests), and I’m really glad that I did. As I was working out the algorithm, I was able to keep iterating to improve it with the confidence that previous cases that worked well were continuing to work well.


On the one hand, we’re just matching up characters. But, as you can tell from the preceding sections, we’re doing a lot of character comparisons. We keep trying to fit the query string into the subject string in different ways until we find the one that fits best. Luckily, computers are fast and JavaScript just-in-time compilers are pretty good, so this code has generally performed well enough for now.

At this point, we’ve only picked up the low hanging fruit in making StringMatch performance better. In profiling, I found that _findSpecialCharacters was taking around 8% of the total time when searching normally and that only needs to run once per string that we’re testing against, rather than for each character typed, making it easy to cache during the lifetime of a search.

Another simple optimization we’ve implemented takes advantage of the fact that items are eliminated as possible matches as the user types. As long as the user is adding more characters to the query, anything that didn’t match previously is not going to be a match now and we don’t even need to check.

The StringMatcher class implements these optimizations in a neatly compartmentalized way. Brackets creates a StringMatcher for a single query and throws it away at the end, so that it does not need to worry about stale caches.

StringMatch all the things!

StringMatch is also used in Brackets’ Go To Definition feature (which finds functions in your JavaScript files, for example). StringMatch is better than regex and substring searching when you’ve got an idea of the structure of the string being searched and what the users will expect the results to look like.

Brackets is open source! Have ideas on how to improve StringMatch or anything else? Join in the fun!

(Special thanks to Peter Flynn for a very thorough review of the StringMatch code which resulted in a good deal of cleanup in both the code and algorithm. Thanks also to Randy Edmunds for providing feedback on the first draft of this post.)

Test driving Brackets

I got test infected a number of years ago, so it was perfectly natural for me to want to test-drive changes to Brackets, now that I’m back into writing code. In fact, I had a perfect bug to work on for test-driven development: improving the QuickOpen heuristics. This code needs to be able to return proper matches with reasonable scores, something that is very easily tested.

When I started working on this bug, QuickOpen did not have any tests. Additionally, running the tests required reaching for the mouse every single time. That’s more irritating than you might expect if you’ve never done test driven development. So, I created a Brackets extension called TestQuickly that lets me run tests appropriate for the current file with a quick keystroke. I made the QuickOpen.js and QuickOpen-test.js files both run the QuickOpen test suite when I hit that key with the file open.

After that bit of setup, I had to start writing tests for the QuickOpen (there weren’t any tests already) and I had to learn Jasmine’s style as well. Writing the tests proved to be straightforward indeed. Alas, improving the QuickOpen heuristics was not quite so easy, but the new results are much better. You can take a look at the code I ended up with in this commit.

I made a screencast with a quick demo of the workflow I used:

My next career step: Adobe’s Brackets project

Mozilla has been an extraordinary place to work over the nearly 4 years that I have been with the organization. Many times that I’ve been out and about wearing a Firefox shirt, random strangers would talk to me about Firefox. Some of those times, it has proven to be a great opportunity to tell people about how Mozilla is a non-profit organization that’s out to make the web better for everyone.

A lot of people seem surprised that there’s a software company with widely used software that is truly built for the public good, but it’s absolutely true. As a product manager, I’ve been involved in many discussions where we talk about what Mozilla should build next and we are always working on behalf of users. It can be refreshing to not have to think about “where does the money come from?” for once. Of course, cultivating a very user-centric view of the world is a positive thing in general, even in for-profit enterprises.

How great is it to work with a large community of people, all focused on helping everyone experience a better web and building some awesome open source software? It’s truly amazing.

Over the past few months, I’ve been thinking that I wanted to get back into software development. There’s something magical about the hands-on building of software, and I think that the right thing for me at this time is to get back to it. I considered a number of interesting options to get back to building software within Mozilla.

Ultimately, though, I just couldn’t pass up the chance to work on Adobe’s open source Brackets project. You may remember that I worked on a browser-based code editor when I started at Mozilla (Bespin, later renamed to Skywriter and ultimately merged with Ace). Brackets is a fairly new project, but it’s already surfacing interesting ideas and has a great dogfooding experience. The development team is really sharp and the community is active and wonderful and I think we’re going to have a good time together building an awesome code editor for web projects. It’s already quite usable, so give it a spin!

Adobe, in general, has tons of work going on “to help move the web forward” and their long history of awesome tools for creative people can help feed a lot of new ideas to the web.

I’ll be starting work on Brackets on Monday.

A big thank you to all of my friends and colleagues at Mozilla for four fabulous years. I wouldn’t hesitate to recommend working there… there’s a ton of work to do in desktop browsing still, mobile browsing is also hot, oh and there’s that little bit about cracking open the whole mobile ecosystem… not to mention plenty of new possibilities in developer tools!

Web developer personas (are you in there?)

User personas are a useful tool for when you want to discuss needs that users  have and, ultimately, features that meet those needs. Personas help keep you talking about real people versus some random “user”.

I’d like to build up a collection of web developer personas that we can use in our product and feature planning. The idea is that each persona will represent a (largely)[1] distinct collection of web developers.  We can use these personas when we’re crafting product requirements, though we will likely need to customize them to properly describe specific kinds of problems we’re trying to solve.

Are you a web developer? If so, please take a quick look at the initial set of personas I’ve created and let me know if none of these would be able to reflect the workflows and tools you use regularly.

Footnotes    (↵ returns to text)

  1. There’s actually quite a bit of overlap in terms of tools that different web developers regularly use, but there is also a wide range of workflows and a wide variety of tools at the edges. For example, almost everyone uses browser-based styling tools for making tweaks to their styles. But, for editing their CSS files, people use all kinds of different editors. Some people might use the ReCSS bookmarklet to reload their CSS automatically. Others use LESS or SASS with some kind of build step before they preview their pages. This variety is part of the reason it’s helpful to have some representative personas and talk in terms of what they’re trying to accomplish, rather than how they do it.

r2d2b2g is becoming the Firefox OS Simulator!

It’s been a month since Myk Melez posted an introduction to r2d2b2g, a prototype Firefox add-on that makes it easy to try out B2G (Mozilla’s new, completely web platform-based mobile OS) on your desktop/laptop computer. Just as B2G is growing up to become Firefox OS, r2d2b2g is growing up to become the Firefox OS Simulator.

The work of Myk, Harald and Matt is coming along nicely, and you can try it out today by picking up Wednesday’s r2d2b2g 0.6 release.

Quite a bit has changed since Myk’s blog post, so I’ll give a run through of the Simulator as it stands today. The biggest difference between the early r2d2b2g releases and the latest is that it is now much easier to install apps that you’re working on into the Simulator. Let’s take a look!

The Simulator has moved into the Web Developer menu.


The Simulator also integrates with the command line on the Developer Toolbar. Use the firefoxos manager command to jump into the Simulator Manager, just as the menu item does.

Here’s the Simulator Manager itself:


On the left, you’ll find some navigation controls including a switch that lets you start and stop the Simulator. The Simulator itself is still B2G Desktop, which is a build of B2G that runs natively on Windows, Mac and Linux. You can also start and stop the Simulator using the firefoxos start and firefoxos stop commands in the Developer Toolbar. The “JS Console” checkbox allows you to start up B2G Desktop’s Error Console so that you can spot errors that might arise while you’re working on your apps.

In the screenshot above, you’ll see that I’ve already installed a couple of apps. You can add apps by providing a URL to a site (with autocompletion based on your open tabs) or, even better, a URL to a manifest (so that the app can have a proper icon and such). You’ll need a manifest file anyhow to submit to the Firefox Marketplace, so you might as well start out with that early on.

You can also locate a manifest file on your local computer so that you can create a packaged app (no web server required!).

In the screenshot above, you’ll see that I installed James Long’s Weather Me app straight from GitHub and Fred Wenzel’s Serpent game from a local clone of its git repository. I’ll note that I did have to tweak the manifest for Serpent a little bit, because it was set up to deploy to GitHub rather than from its local directory. Changing just a couple of fields was all it took and then it worked great!

With those set up, I clicked the switch that says “Stopped” to fire up the Simulator. Then, I unlocked it with a swipe of the mouse, and swiped left on the home screen to get to my apps:

As you can see, the Weather Me and Serpent apps are installed and ready for testing! One new feature I’d like to point out is the home button at the bottom of the Simulator. You no longer have to guess which key to press on your keyboard… just click the on-screen button as you would on a phone.

While hacking away on these apps, if I make changes I just have to follow some simple rules to see my changes. Hosted apps follow the usual rules for website caching and for working with appcache (which you should!). You can update packaged apps just by clicking the Update button in the dashboard and restarting the Simulator.

Once you’re done working with an app, you can remove it from the manager, which will also remove it from the Simulator (though you made need to restart your Simulator to see it disappear).

The Firefox OS Simulator is the easiest way to try out Firefox OS apps today and to verify how they’ll look before submitting them to the Marketplace.

Install it today and let us know if you run into any problems. There are currently known issues on Windows XP and Linux that we’re working to resolve, but Windows 7 and Mac users should try it now!

New device and a multifactor nuisance

Two-factor authentication (2FA) is great. Thanks to 2FA, even if someone manages to figure out my password, they still need to have physical access to my phone. Well, I actually have two phones that I switch between, so they need access to one of those two phones. I just got a new phone to replace an aging one. I use three different services that support Google Authenticator. Guess what? Now I need to reset the 2FA on all three of those services so that my new device has the secret.

Sure, this is a first world problem, blah blah. But, what I’d really love to see is 2FA tied into Persona (BrowserID) and all of the sites I log into support Persona. Then I only have one password to know, one 2FA secret. It would eliminate the need for a password manager. Convenience and security. Sounds grand, doesn’t it?

What is a “developer”?

My goal as a product manager at Mozilla is to represent the needs of web developers well and make sure that Mozilla is doing what we can to help them.

I came to the realization last night that when I talk with others about what “developers” need, the picture of that “developer” that appears in different people’s minds can be quite different from my own. In fact, while I may imagine someone sitting at a keyboard getting frustrated at trying to make something work, someone else may be thinking of a company that “wants” to get an app into Mozilla’s Marketplace.

In my view, when you’re figuring out what you need to build, imagining a company is almost always not what you want. Companies don’t do anything. People do. People have a variety of reasons for doing the things they do, and understanding what those people are trying to accomplish is key to building good products.

This is what I like about personas [1]. Personas describe realistic people, allowing you to empathize with them and ensuring that you’d never mistake a person for a company. They can help give clarity to which things are important to build and also help catch gaps. Imagine a coworker coming up to you and saying “Can you believe I just met someone who was trying to make our product [do something outlandish]?”. It’s possible that the person in question is an outlier that you can safely ignore. But, it’s also possible that there are other, similar people out there and adding a new persona to the mix may open up a whole new market.

All of that said, it’s perfectly reasonable in many contexts to talk about a company as a “developer”. “Mozilla is the developer of the popular Firefox web browser”, for example. There are certainly times in product development where talking about a developer as the entity that controls an app in the Marketplace is perfectly reasonable. But, when you get down to planning features, I think it pays to think about individual people.

Footnotes    (↵ returns to text)

  1. In this use, “persona” is a generic industry term, not to be confused with Mozilla Persona, the awesome identity system for the web.

GitHub adds a command line, and so should you!

Yesterday, GitHub announced their new “Command Bar”. I am a fan of command lines, and this is an awesome addition for navigating GitHub. I love being able to get more done without pulling my hands away from the keyboard.

You may remember that we’ve added a command line to the Firefox developer tools. It’s currently in beta, slated for release in about 3 weeks.

My reason in bringing this up is that if you want to add keyboard controlled command line goodness to your webapp, you can do so easily. The command line in Firefox is actually a separate open source (BSD-licensed) project called GCLI that you can incorporate into your own webapps!

Fork GCLI on GitHub and let’s see a thousand command lines, um, bloom.