How to fix a bug, episode 434494, part 2

At the end of part 1, Cameron McCormack had just tracked bug 434494 down to two .focus() calls in browser.js. It was a race condition: whichever .focus() call happened to run last got to keep the focus.

You might have wondered why these calls were happening in a random order to begin with. As we’ll see, Cameron was able to fix the bug without investigating this! But I’ll talk a little bit about it because it’s interesting, and it can bite ordinary web pages, too.

Opening files is a very common cause of non-determinism. You call a function like window.open() or XMLHttpRequest().open to make it happen, and the call returns right away, even though the document hasn’t finished loading yet, so the application can remain responsive. The system will send a load event later, when it’s done. Because loading a file takes a small but somewhat random amount of time, the order of that load event compared to other events can be slightly random.

The root cause of bug 434494 is indeed the timing of load events. But Cameron found a way to fix the bug without having to track down the root cause, as we’ll see—after a little detour…

       <heycam> ok, so we know we have these two focus calls running in either
                order
   <jorendorff> hang on
   <jorendorff> I've got a Firefox 4 nightly on my Mac. So I suppose I have a
                browser.js in here somewhere.
   <jorendorff> One hesitates to encourage people to edit their browser app
       <heycam> ah yes, if you want to try it
       <heycam> heh
   <jorendorff> but just for my entertainment...
   <jorendorff> I can just throw an alert() in here?
       <heycam> I don't know how well it works to just edit the browser.js in
                whatever jar it lives in
       <heycam> it might work
       <heycam> I tended to just do a rebuild
   <jorendorff> you edited the source file?
       <heycam> yeah
       <heycam> then make, as usual
       <heycam> but probably editing browser.js in situ is fine
   <jorendorff> ...What about a chrome debugger? Ever use one of those?
       <heycam> no, well only just yesterday
   <jorendorff> heh
   <jorendorff> let's try editing it in place ;)
       <heycam> ok :)
   <jorendorff>  /Applications/Nightly.app/Contents/MacOS/
   <jorendorff> omni.jar
       <heycam> I'm guessing so
   <jorendorff> chrome/browser/content/browser/browser.js
   <jorendorff> now to see if Emacs will let me edit this file in the middle
                of a jar
   <jorendorff> gosh, I think it will
       <heycam> would surprise me if it didn't ;)

If you’re on Mac or Linux, and you have Emacs, go ahead and find omni.jar in your Firefox installation directory, make yourself a nice backup copy, and poke around inside. If you like, you can make the exact change I made. Search the archive for browser.js, open it, then search for BrowserSearch_webSearch. Add an alert, like so:

in situ, as they say in auckland

Save it… and…

   <jorendorff> restarting... *fingers crossed*
   <jorendorff> hmm, no good.

It didn’t work. But are we discouraged? We are not. Later I asked about this on irc.mozilla.org, and I found out that you can force Firefox to read omni.jar again by passing the right command-line flag. First make sure Firefox is closed. Then:

  $ cd /Applications/Nightly.app/Contents/MacOS
  $ ./firefox --purgecaches

If you’re on Mac OS 10.5, you need to use a slightly different command to start Firefox:

  $ arch -i386 ./firefox-bin --purgecaches

And of course if you are using the official Firefox 4 instead of the unstable Nightly, you’ll find the file under /Applications/Firefox.app instead.

Then, when you hit Cmd+K:

achievement unlocked: hack

You might want to put your original omni.jar back when you’re done. Software updates run a bit more smoothly when you haven’t been manually editing the programs. :)

Back to the bug:

   <jorendorff> so did you manage to convince yourself that this is what was
                happening by using alerts?
       <heycam> yes
       <heycam> alerting what the currently focused element was, at the time
                of the gURLBar.focus call
       <heycam> my thought was, not knowing anything about the random
                ordering, to ensure that the gURLBar isn't focused if we'd
                already done the search bar focusing
       <heycam> so I made an assumption, which I verified
       <heycam> that I could tell whether something had been focused already,
                by seeing if commandDispatcher.focusedElement was null
   <jorendorff> ah
       <heycam> alerting just before gURLBar.focus is called, in say a
                Cmd+N new window, showed me that focusedElement was null

This led to Cameron’s first patch for the problem. He wrapped the code that calls gURLBar.focus() in an if block, so that it only happens if we haven’t already focused something else. You can see those changes here. (The left side shows the code before the fix; the right side is how it looks after the fix. Incidentally you can find that page yourself by visiting bug 434494, then clicking “Show obsolete patches”, then clicking on the word “Diff” next to the first patch.)

   <jorendorff> the first part, i see the if statement you added
   <jorendorff> but what is that second change?
       <heycam> see the comment above the setTimeout 0 call
       <heycam> clearly it's trying to do something to avoid the url bar focus
   <jorendorff> oh
   <jorendorff> heh - yeah, it looks like someone thought they fixed this
                before. :)
       <heycam> initially I only wrote the first hunk, and that worked.
   <jorendorff> That being done, the old setTimeout hack wasn't needed
                anymore, so you ripped it out.
       <heycam> exactly
       <heycam> there's no point in delaying the webSearch call in the
                setTimeout

The second half of the patch was just a little code cleanup.

Now Cameron had a working fix. He posted it in Bugzilla and requested a code review from Gavin Sharp, a long-time Firefox hacker who’s an expert in this area of the code. Gavin lives in Toronto.

Code reviews are interesting. You almost always learn something.

   <jorendorff> It looks like you spoke with gavin about this first patch
   <jorendorff> and you decided to make a few changes based on that.
       <heycam> yes
   <jorendorff> I don't suppose you have that chatlog...?
       <heycam> I do, hang on

Here is what Gavin said…

            <gavin> hm, that patch seems to be relying on the ordering of the load events
           <heycam> how's that?
            <gavin> and I'm not sure that it's safe to assume that focusedElement will be null on initial load
            <gavin> BrowserStartup runs off a load event
            <gavin> so does BrowserSearch.webSearch, with your change
           <heycam> I see
           <heycam> is there something I can listen for once the browser startup is done?
            <gavin> not at the moment
           <heycam> or maybe a way I could pass an argument into the browser
           <heycam> rather than listening for an event
            <gavin> oh, I lied
            <gavin> you could use browser-delayed-startup-finished
            <gavin> slightly messy because it's an observer notification, but doable
           <heycam> ok
           <heycam> I'll try that and post another patch. thanks!

Depending on .focusedElement was too iffy. Gavin suggested a different approach, which led Cameron to make a second version of the patch.

   <jorendorff> gavin left some new comments in the bug :)
       <heycam> yes, I plan to get to them today :)

Since my chat with Cameron last week, he posted a third version, which now bears Gavin’s seal of approval. It might be checked in by the time you read this. Sweet!

the plus means quality
       <heycam> the one hiccup was the time between my posting the original
                patch, and getting comments from gavin
   <jorendorff> Was that due to the Firefox 4 crunch?
       <heycam> probably. gavin also seems to have a long request queue.
       <heycam> so a week ago I pinged him on email
   <jorendorff> ah

So I glossed over something: the three months between Cameron’s first patch and his chat with Gavin.

I hate to admit it, but I still have review requests from that era too. Firefox 4 was in beta, monopolizing developers’ time, for months. A lot of valuable work got put on hold. We’re never doing that again, thank goodness.

But sometimes a code review gets lost in the shuffle anyway. If yours takes more than a few days, it’s important to speak up:

       <heycam> although I'm usually hesitant to prod people
       <heycam> but that mail got swallowed :(
       <heycam> so I pinged him on irc yesterday to ask him about it
       <heycam> in general I have no idea how long I should be letting my
                patches sit in someones queue before bugging them about it :)
   <jorendorff> At least 3 days. But never 2 weeks.
       <heycam> I think that aspect of the process should be emphasised to new
                contributors
       <heycam> getting review, expectations of turnaround time
   <jorendorff> As long as you're super nice about it, a reminder is usually
                welcome, in my experience
       <heycam> ok

So this is what open source development is like. There is some stuff that looks like work, stuff that takes multiple tries, delays and waiting. There are also cool things to tinker with, puzzles waiting to be solved, useful skills to learn, and smart people around the world who would love to help you.

Don’t be shy.

How to fix a bug, episode 434494, part 1

This is a true story about fixing a bug.

In this story, we’ll see that a bunch of the Firefox UI is written in JavaScript. We’ll do something extremely inadvisable but sort of cool. And we’ll hit on one of the key life lessons of open source development.

 


 

Our hero is New Zealand-based Mozilla hacker Cameron McCormack. Cameron knew about this bug in the first place because someone (Marco De Vitis, to be specific) took the time to report it at bugzilla.mozilla.org. It’s bug 434494.

I chatted with Cameron about the bug and what happened next.

   <jorendorff> So this bug is about what happens when you have no windows open
                and you hit Cmd+K
       <heycam> right
   <jorendorff> which I guess only really happens on the mac, right?
       <heycam> yeah
       <heycam> where closing all the browser windows doesn't quit the app

It’s normal on the Mac for an application to stay open when its last window is closed. So in Firefox on the Mac, if you close all your tabs, Firefox is still there, and you can open a new browser window from the menu or by using a keyboard shortcut. Cmd+K is the shortcut for the search bar.

   <jorendorff> OK. So Cmd+K creates a new window in that case, and the bug
                was, sometimes it would focus the search box as desired,
                sometimes the location bar instead.
(picture of a new browser window with the location bar focused)
omg firefox, what part of cmd+K did you not understand
   <jorendorff> how did you track it down?
       <heycam> I *think* I searched for where the location bar got its focus,
                first

(Cameron doesn’t remember clearly because it was a month or two ago. More about that in part 2.)

       <heycam> ok
       <heycam> http://mxr.mozilla.org/mozilla-central/source/browser/base/content/browser.js#1485
       <heycam> so that's the only line that focuses the url bar
       <heycam> (it seems)
   <jorendorff> aha

I clicked the link and there was browser.js: nine thousand lines of JavaScript code that implement a lot of the UI around the edges of your browser window.

(a bunch of browser.js source code)
so that is what the tubes look like

Well there you go. Focus the URL bar. There’s your bug, right?

But this can’t be the whole story, because in other circumstances, Cmd+K works. Somewhere there must be code for focusing the search bar that isn’t being called or isn’t working properly in this case. Cameron had no idea where that code might be.

So he went to mxr.mozilla.org and searched for it.

(mxr.mozilla.org search results for 'Cmd+K')
only two hits for cmd+K
       <heycam> that's right
       <heycam> there's a file that has a whole bunch of keyboard mappings to
                actions
       <heycam> something.inc
       <heycam> browser-sets.inc
   <jorendorff> http://mxr.mozilla.org/mozilla-central/source/browser/base/content/browser-sets.inc
       <heycam> yeah
       <heycam> I still have no idea how all the xul things fit together
       <heycam> but having found this file, I could see that it associates
                Cmd+K with a "command"
       <heycam> Tools:Search
       <heycam> http://mxr.mozilla.org/mozilla-central/source/browser/base/content/browser-sets.inc#230
(some source code from browser-sets.inc where the Cmd+K keyboard shortcut is defined)
hipster caption writer says xml is not retro yet, still just uggs
       <heycam> and then my thinking is "what defines commands"
       <heycam> so I'd grep that directory for Tools:Search
       <heycam> $ cd browser/base/content
       <heycam> $ grep Tools:Search *
       <heycam> browser-menubar.inc: command="Tools:Search"/>
       <heycam> browser-sets.inc:    <command id="Tools:Search" oncommand="BrowserSearch.webSearch();"/>
       <heycam> browser-sets.inc:    <key id="key_search" key="&searchFocus.commandkey;" command="Tools:Search" modifiers="accel"/>
       <heycam> browser-sets.inc:    <key id="key_search2" key="&findOnCmd.commandkey;" command="Tools:Search" modifiers="accel,alt"/>
       <heycam> browser-sets.inc:    <key id="key_search2" key="&searchFocusUnix.commandkey;" command="Tools:Search" modifiers="accel"/>
       <heycam> that <command> element looks right
       <heycam> that gets us to the webSearch function in browser.js

Cameron saw oncommand="BrowserSearch.webSearch()", guessed correctly that it was a snippet of JavaScript, and with a bit more searching, tracked down the webSearch function. It also lives in browser.js, it turns out.

   <jorendorff> so now we know two things
   <jorendorff> We know where focusing on the search bar is supposed to happen
                (and roughly what pointers the system is chasing to get from
                Cmd+K to this JS function)
   <jorendorff> we also know there's some other code in browser.js that
                focuses on the url bar.
       <heycam> right
   <jorendorff> and the hunch is then "i bet both are happening"?
       <heycam> both are happening, but in an order that's not fixed
   <jorendorff> now what?
       <heycam> I may have put some debugging code in to make sure that both
                are running, not sure
       <heycam> like an alert or something
   <jorendorff> That was the next thing I was going to ask about.
       <heycam> without knowing how chrome js works, it's hard to know how to
                even do simple printf debugging
   <jorendorff> Of course anybody reading this--certainly if they happen to be
                running Firefox 4 on mac -- would like to watch this happening
       <heycam> yeah

Would you? Maybe we’ll do that in part 2. :)

       <heycam> will you be making a guided tutorial to fixing this bug?
   <jorendorff> Weelll, It depends on how much time I end up with :-\
       <heycam> I think UI stuff is a great place for new people to start
                working on, because it's very immediate
       <heycam> and you can see if things are working or not
   <jorendorff> i agree!
       <heycam> but, there's an awful lot of complexity in there
   <jorendorff> well, that's how it is
       <heycam> undocumented too :)
   <jorendorff> but what you're showing people is how to ignore things rather
                than get overwhelmed
   <jorendorff> this is valuable
       <heycam> yeah, I think that's the key
       <heycam> ignoring things, plowing on
       <heycam> and if you miss important things, others will let you know
       <heycam> that's how I try to approach areas I'm unfamiliar with
       <heycam> I'll have a bash at it, post it for review, and learn what
                things I didn't know from review comments :)
   <jorendorff> as in this case :)
       <heycam> yeah
   <jorendorff> but that gets ahead of the story

We’ll get there in part 2.

Now about that life lesson.

You probably noticed Cameron has been tracking down the problem by randomly searching the code for words that might be relevant. This might not seem worth documenting. In fact it may seem a little embarrassing—you mean he didn’t know the code well enough to figure out where the bug was using only his enormous brain? But this is exactly what I think is most important about this story. What Cameron is doing requires some programming chops, and it requires the ability to navigate undocumented monster-infested waters—but it’s not magic.

You could do this.

Maybe you are not an expert in everything. Maybe (like me) you’re a shy person working in a complicated world with incomplete knowledge. How can you function like that? How do you know if you have anything to contribute? How can you get involved in new things?

Step 1: Don’t panic.

Step 2:

  • search for the answer
  • try something and see what happens
  • ask someone

To be continued.

Update: Part 2 is up.

Wanted: An extension for profiling Firefox

Firefox needs an extension that can produce very high-level performance profiling numbers with only casual effort.

We often get bug reports that say “Firefox is painfully slow on site X”. It takes rather a lot of effort just to direct this kind of bug to the right person, because it’s usually not immediately clear why the site is so slow. It would be awfully nice to be able to load a page and see not only how much time Firefox spends waiting for the network (something Firebug can already do) but also how much time we spend doing style resolution, reflow, frame construction, garbage collection, compiling JavaScript, running JavaScript, and so on. Even Boris Zbarsky, who’s probably as comfortable using a profiler as anyone I work with, says such an extension would save him time.

On Mac, you could get this information using dtrace. If you’re a programmer, you have a Mac, and you’re interested in a fun side project, please get in touch with Boris or me.

Seven things

I got tagged to tell you seven things about myself back in January, and I finally found a seventh, mildly interesting thing to write. So here you go.

The rules

  1. Link back to your original tagger and list the rules in your post.
  2. Share seven facts about yourself.
  3. Tag some (seven?) people by leaving names and links to their blogs.
  4. Let them know they’ve been tagged.

Seven things

  1. I’m married and have three kids. All our noses make a different noise when squeezed, except that mine goes “AWOOOGA” and the baby’s goes “awooga”. He has my nose.
  2. I love math. I have a shirt with Łukasiewicz’s axioms of propositional calculus on it. (Incidentally, if you take Pascal’s triangle and color the even numbers black, you get Sierpinski’s gasket. Who knew?)
  3. My memory for appointments, names, and faces is amazingly bad. I also have an innate incompetence for using calendaring software. I somehow manage to convince it not to alert me about a meeting; or I miss the alerts; or they go off at maximum volume but only in the middle of the night or when I’m at the store; or I see the alerts but can’t decipher what I wrote; or my calendar gets so full of obsolete recurring appointments that I ignore all the alerts (which is the steady state and current situation).
  4. I am such a slow reader that I rarely finish a book. This is especially true of nonfiction books (I like to read “hard” nonfiction, like textbooks). There’s no big payoff ahead, pulling me toward the end. At some point it seems more worthwhile to start reading some other book (which I also won’t finish).
  5. I used to really like table-top games, like board games, back when I had time to play them. Now I only like games that are actually fun, which is a different scene. My favorites include 1000 Blank White Cards and a roleplaying game named EARS, about which details are available on request.
  6. I love making up stories and telling them to my kids. I keep thinking I’ll write them down someday. I probably won’t. But I write down the outlines, hoping I can piece them back together later.
  7. I live in the country about half an hour outside of Nashville, Tennessee. There’s a room in my house where you can watch the sunrise and the sunset. We’ve seen deer, rabbits, and a whole family of wild turkeys in our yard, to say nothing of lizards, turtles, and birds. In spring, the birds get so loud around eight in the morning that it’s hard to work. On summer evenings there are hundreds of fireflies.

If you want to know more about me, you could read my other blog. Why do I have two? I don’t know.

I can’t bring myself to tag anybody, since this took so many months of my time. But if you’d like to play, and somehow missed all the action back in January, do feel free.

Mercurial qtop in your prompt

I use Mercurial Queues. Sometimes I make a bunch of changes intended for one patch when in fact the currently applied patch is something else. If I manage to run hg qrefresh before detecting the mistake, it munges my new work with the unrelated patch.  The damage is a huge pain to undo.

One day we were all complaining about this on IRC, and Chris Jones wrote this line of code (at Graydon’s suggestion):

PS1='\u@\h:\w[\[`hg qtop 2>/dev/null`\]]\$ '

Put it in your .bashrc and your bash prompt will look like this:

cjones@hell:~/porky[bug-545432-newexprs]$

Check that out, qtop in your prompt!  The idea is to stop you before you hit enter.  Maybe it’ll work for you, maybe not.

I use something a bit more complicated, but it amounts to the same thing:

function mercurial-qtop() {
    qtop=`hg qtop 2>/dev/null`
    if [ "$qtop" != "" ]; then
        echo " (+$qtop)"
    fi
}

PROMPT_COMMAND='MERCURIAL_QTOP=`mercurial-qtop`'
PS1='\[\e[1m\]\w$MERCURIAL_QTOP\$\[\e[0m\] '

Update: Changed my code snippet to use PROMPT_COMMAND. bash is amazingly bad at guessing how long your prompt is, even though it knows PS1. This seems to make readline do bizarre things when you cut and paste, resize the window, or exceed a single line of input.

What’s the opposite of open source hacking?

I recently read Chris Tyler‘s paper, “A Model for Sustainable Student Involvement in Community Open Source”. Chris writes:

To effectively teach Open Source, it’s necessary to move each student into the role of contributor. At first blush this appears straightforward, but it ultimately proves to be an enormous challenge because Open Source is as much a social movement as a technical one and because many Open Source practices are the exact opposite of traditional development practices.

I like this paragraph, but something struck me as not quite right about it.  Open Source practices don’t really feel like the opposite of traditional development practices to me.  What I think they’re the opposite of, actually, is homework.

If your programming experience is limited to homework assignments, working on a real-world software project is going to be overwhelming for you, whether it’s open source or proprietary—and for the same reasons.  You’re used to writing small programs, individually, completely from scratch.  The software companies I’ve worked for all had teams of developers working cooperatively on a large, existing codebase, with version control, complex build systems, not enough tests, bug trackers, thousands of known bugs, good code, bad code, and way too much of the stuff for any one person to understand.

Did I mention working cooperatively?  Traditional software development really is supposed to be done that way, I promise.  Well, maybe it depends on where you work.

Later, Chris writes, “[E]ven students who don’t continue working with Open Source take an understanding of Open Source into their career, along with an understanding of how to work at scale — which is applicable even in closed-source projects.”  That’s the stuff!  Open source development is different.  But it’s not that different.

Mozilla summer internships

This summer, thirty interns participated in the Mozilla summer internship program. They worked in virtually every area of the Mozilla project: Firefox, Thunderbird, testing, the build system, marketing, analytics, web development, IT. You can read their blogs here.

If you’re a college student, you can apply now for a Mozilla internship in summer 2009.

Sound good? Keep in mind that:

  • you will have to spend about twelve weeks in sunny Mountain View, California.
  • you’ll be surrounded by some of the most brilliant minds in Open Source software.
  • you could have a lasting impact on the way over a hundred million people use the web.

If you think you can live with all that, apply online (that web site is kind of weird; poke around for “Intern” positions) or send email to julie at mozilla dot com.  Internships will be awarded by the end of February 2009 or so.

Anatomy of a JavaScript object

This post is about how the JavaScript engine represents JS objects in memory. I’m afraid a lot of it will seem obscure and opaque unless you already know a bit about SpiderMonkey internals, or you have the perseverance to click some of the links below and read the documentation.

First of all, what is a JavaScript object? Paraphrasing the documentation for JSObject, objects are made up of the following parts:

  • Most objects have a prototype. An object inherits properties, including methods, from its prototype (which is another object).
  • Most objects have a parent. An object’s parent is another object, usually either the global object or an object that represents an activation record. The JavaScript engine uses this relationship to implement lexical scoping.
  • Almost every object can have any number of its own properties. The term own property refers to a property of an object that is not inherited from its prototype. Each property has a name, a getter, a setter, and property attributes. Most properties also have a stored value.
  • Every object is associated with a JSClass and a JSObjectOps. These are C/C++ hooks that implement details of the object’s behavior. An object may also have other private fields, depending on its JSClass.

So you might imagine a JavaScript object would look something like this:

    struct JSObject {
        JSObject *proto;
        JSObject *parent;
	map<jsid, JSProperty> ownProperties;
        JSClass *cls;
        ...
    };

This being SpiderMonkey, none of the details are quite as straightforward as that, but the real struct JSObject does in fact contain a word that points to the object’s prototype, one that points to its parent, and one that points to its class. The part that represents an object’s own properties isn’t like a C++ map at all, and that’s the part I’d like to focus on here. Certainly a JavaScript engine could store each object’s own properties in a map or hash table. What we actually do is quite different and rather clever.

How properties are stored

First of all, and mostly just to get this out of the way, there is an abstraction layer around properties: JSObjectOps. By implementing this interface, an object can store its own properties in its own custom, non-default way. Apart from arrays and maybe XPCOM wrapper objects, I think this is very rare.

A nice, gentle way to learn about JSObject is by reading the source code of js_DumpObject, a debugging function that walks the data structures I’m about to describe and prints out some of the details.

In SpiderMonkey, properties are divided into two parts which are stored in separate data structures: the stored value and everything else. Each object has a growable array of jsvals. That’s where the stored values live. Each object also has a pointer to an object map, which contains the property names, getters, setters, and attributes. For native objects, this object map is a linked list of property descriptors (of type struct JSScopeProperty). Each property descriptor also tells whether the property has a stored value, and if so, its offset in the stored value array. When a new property is created on an object, the property descriptor pointer is changed. The new head of the list is a property descriptor containing information about the new property, but the tail of the list contains all the same information about existing properties as before.

Got it? OK. Now for the fun part.

Why

This turns out to be a nice way to store properties for a few reasons.

  • It turns out we can share the hefty property descriptors among objects. If many objects have the same properties, in the same order, they have the same linked list of property descriptors. So the per-object cost of a property in this case is just one word—the stored value itself. (By contrast, in a hash table implementation, a property would have to cost at least two words—plus a few extra bytes of hash table overhead, depending on the load factor of the table.) The mechanism by which these lists are shared is called the property tree, and it’s a pretty sweet idea. It’s what I originally set out to describe in this post, actually. The details, though, are mind-bogglingly intricate. An epic comment in jsscope.h dishes the dirt.
  • When we share property descriptor lists among similar objects, what we’re really doing is classifying objects by the properties they have. This is such a useful concept that the SpiderMonkey developers have a succinct term for “everything about an object’s properties except their values”: shape. Objects of the same shape all have the same own properties, and their values are stored at the same offsets. It turns out we can cache the results of property lookups by shape, so in many cases the interpreter doesn’t have to walk the linked list of properties at all. SpiderMonkey’s property cache is another nice topic for a post sometime.
  • Another consequence of objects of the same shape having the same layout is that you can treat them like structs. This is useful if you’re a JIT. A property access could be as little as a single machine instruction. (In practice, JITted code has to check the type of every property value it reads, so we don’t normally achieve this ideal. Still, eliminating the overhead of groping about for a property in a hash table or linked list is a huge win.)

Any questions?

Quick stubs

Quick stubs are an optimization, so you probably shouldn’t care about them. For the curious few, here’s an explanation.

XPConnect, the main customs office on the border between JavaScript and C++, is bureaucratic and slow. When JavaScript calls a method or accesses a property of an XPCOM object—for example, the nodeType property of a DOM node—this happens:

  1. The JavaScript engine looks for a property named nodeType on the node and sees that it isn’t there. So it goes off looking for it, and after checking for a number of possible special cases and querying several interested parties, XPConnect detects that there’s an XPIDL property with that name on one of the interfaces the object implements. It creates a getter function and a setter function and defines the property on the node’s prototype. Later nodeType accesses in the same context, on nodes of the same class, will perform some parts of this search again but will ultimately find the property created the first time through. Are we having fun yet?
  2. The getter function is called. The same getter function, XPC_WN_GetterSetter, is used for all JS-to-C++ getters and setters, so this is some very generic code.
  3. The getter creates an XPCCallContext. Hundreds of lines of code execute, gathering all sorts of information about the current property access and storing them in this object, which is added to a XPConnect context stack. (Most of this information probably won’t be used.)
  4. Now XPCWrappedNative::CallMethod is called. This code is even more generic. It’s about 700 lines of code, but packed with branches, so on any given call, most of it is skipped. It checks the JavaScript arguments, handles errors, converts the types of arguments from JavaScript values to C++, performs security checks, and so on. When executing a getter, there are no arguments; we skip most of it. About 500 lines in, we call the C++ method. This happens via the magic of xptcall, which knows how to fake the C++ calling convention and call a specific virtual method of a C++ object.
  5. A one-line DOM method executes, returning a constant value.
  6. XPCWrappedNative::CallMethod cleans up any data structures it allocated and converts the return value and any out parameters back from C++ to JavaScript.
  7. The XPCCallContext object is removed from the context stack and dismantled. Control returns to JavaScript.

This seemed like a pretty fat optimization target. The trick was to make this faster while retaining as much of XPConnect’s behavior as possible.

There’s a long comment in js/src/xpconnect/src/qsgen.py that explains what quick stubs are and how they work. I’ll quote that here.

About quick stubs

qsgen.py generates “quick stubs”, custom SpiderMonkey getters, setters, and methods for specified XPCOM interface members. These quick stubs serve at runtime as replacements for the XPConnect functions XPC_WN_GetterSetter and XPC_WN_CallMethod, which are the extremely generic (and slow) SpiderMonkey getter/setter/methods otherwise used for all XPCOM member accesses from JS.

There are two ways quick stubs win:

  1. Pure, transparent optimization by partial evaluation.
  2. Cutting corners.
Partial evaluation

Partial evaluation is when you execute part of a program early (before or at compile time) so that you don’t have to execute it at run time. In this case, everything that involves interpreting xptcall data (for example, the big methodInfo loops in XPCWrappedNative::CallMethod and the switch statement in XPCConert::JSData2Native) might as well happen at build time, since all the type information for any given member is already known. That’s what this script does. It gets the information from IDL instead of XPT files. Apart from that, the code in this script is very similar to what you’ll find in XPConnect itself. The advantage is that it runs once, at build time, not in tight loops at run time.

Cutting corners

The XPConnect versions have to be slow because they do tons of work that’s only necessary in a few cases. The quick stubs skip a lot of that work. So quick stubs necessarily differ from XPConnect in potentially observable ways. For many specific interface members, the differences are not observable from scripts or don’t matter enough to worry about; but you do have to be careful which members you decide to generate quick stubs for.

The complete list of known differences is in qsgen.py for the curious. That list is the fine print of quick stubs. It is long; the gist is that many methods should not have quick stubs.

The end result was a speed-up of about 20% on the Dromaeo DOM benchmark suite. Some of those tests spend lots of time in a single DOM call, not in thousands of quick calls from JS to C++. Quick stubs are no win there. But some tests gained 60% or more, indicating that most of the time was being spent in XPConnect.

Peter Van der Beken and I met in Mountain View last week and did some work on bug 457897, a follow-up to quick stubs that will likely win another 20%.

Like most native methods, XPCOM methods, including quick stubs, cannot be JITted in TraceMonkey as it stands. More on that later.

What should we change about the Mercurial Web UI?

Great news! Siddharth Kalra, a student at Seneca College, is going to work on Mercurial history browsing this semester.

The (vague) goal of the project is to take the now-familiar mercurial-central shortlog page and make it awesome. In case you haven’t seen it, Dirkjan Ochtman’s graph view is already a step in the right direction. It’ll probably be a starting point for Sid’s work.

What should Sid change? I have a few ideas:

  • It would be great to have the history scroll “forever” up and down, like a tumblelog.
  • Sometimes when I’m looking at history, I can’t tell if the changes I’m looking at happened in the mainline or in a branch. So ideally the page would show major lines of development in different colors–for example, blue for mozilla-central, orange for tracemonkey. This is possible using information from those repos’ pushlogs.
  • Pushlog information could also be used to make those special paths relatively straight, with other smaller branches and mini-merges happening to the side or hidden by default with some kind of collapse/expand widget.
  • It should show more information about each changeset, if it can be done in an unobtrusive way. I would like to know which directories were touched and roughly the size of the diffs.
  • Often I wish I could filter the history by file or directory.
  • A vertical timeline would be nice, so the location of a changeset on screen would tell something about when it was developed or pushed.
  • It would be great to be able to zoom in and out and see weeks, months, years of work.

This is a call for ideas. What would you like to see? How can hgweb do a better job mapping the multiple timelines of this sci-fi adventure?