Rooftop lab

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.

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.

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.

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 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.

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?

One of the funny little benefits of switching the Mozilla Developer Center from MediaWiki to Deki is that page names can contain actual underscores. The big headline on the JS_EvaluateScript page always used to say “JS EvaluateScript”.

Well, not anymore! Since Deki has an HTTP API, I was able to write a Python script to fix the titles of all the JSAPI pages at once. The source code includes a Python module for loading and saving Deki wiki pages. Enjoy!

Brad Lassey recently vented some understandable frustration with Mercurial, the new distributed version control system we’re using for Mozilla 2 development.

I sympathize with Brad, especially because almost all of the comments seem to be along the lines of “No no, you’re mistaken, Mercurial makes things easier, not harder” or “Well, you should have done X,” without understanding Brad’s problem.

Still, I think Brad’s frustration is somewhat misplaced. The other side of the story involves Windows Vista. Brad did some work in a Mercurial repo on Vista, then zipped up the whole repo and moved it to a Windows XP VM. This is supposed to work just fine. But (and this part, we think, this is due to a brilliant top-secret feature of Windows Vista called virtualization, a feature so awful the mobile developers have resorted to logging in as Administrator all the time) Brad ended up with a zip file that had multiple copies of some files. Whatever Vista put into that zip, extracting it on XP produced a corrupt repository. (Specifically, Mercurial’s working directory was at revision X, but it thought it was at revision Y.)

Mercurial is different in a lot of ways. Compared to CVS, it’s more flexible and more complex. Mercurial vs. CVS reminds me of C++ vs. C:

• There are a lot of quite different ways to use it.
• There are some ease-of-use issues.
• It’s easy to think you understand it, and how to use it, and which features to ignore, and exactly how everyone else should use it, when you really really don’t.
• Conversations about how to use it are not going to be trivial.
• Getting started by using Mercurial as “a better CVS” doesn’t deliver a huge win and is a little frustrating, because some things don’t quite translate.
• Perhaps most importantly, shooting yourself in the foot feels a lot like C++. I’ve done it a few times now—boring stories.

After ten years of ups and downs with C++, I’ve made my peace with it and wouldn’t want to go back to pure C.

Update: It turns out Brad’s problem was at least partly caused by the Mercurial binary distribution he was using. The default hgmerge script was broken in an exciting way. I believe it’s fixed in the latest binary distribution.