Rooftop lab

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!

Thanks to Ben Hearsum and Ted Mielczarek, the Try server has a cool new feature: you can now try out some changes without manually creating and uploading a patch. Just hg commit or hg qrefresh your work, and then

    hg push -f ssh://hg.mozilla.org/try/

The Try server will kick off Linux, Windows, and Mac builds with all your latest changes. Specifically, it’ll build your hg tip revision.

Details:

• If you’re using Mercurial Queues, this push command pushes any patches that are currently applied, and the Try server will build the result. (This is an awesome feature, not a bug!)

• If you’ve ever pushed anything to mozilla-central, you already have the right permissions to do this. If not, see the Mercurial FAQ for more information about pushing.

• The Try server wiki page has more information about the Try server, including where to find the finished builds.

• You don’t need to clone or pull from the try repo, and you probably don’t want to. You’d get every half-baked changeset anybody ever tested.

• You can abbreviate the push command even further. If you add these lines to your $HOME/.hgrc file:

  [paths]
  try = ssh://hg.mozilla.org/try/

  then the command becomes hg push -f try. Or you could use a script or an alias.

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.

This is cool (if you care how malloc() works, always a big if), but it requires a lot of background.

Background

One very common way to implement malloc() is to use size classes and freelists. If you already know all about this, skip this section.

Here’s a sample malloc() that uses size classes and freelists. (Note that size classes have nothing to do with the object-oriented notion of a class.)

void * malloc(size_t nbytes)
{
    /* Say you want 24 bytes.  Well, there's an allocator that
     * specifically serves up 24-byte chunks of memory.  (Actually
     * if you ask for 21, 22, or 23 bytes, you'll probably get the
     * same allocator.) This is what I mean by size classes.
     */
    FixedSizeAllocator *allocator = getAllocatorForSize(nbytes);

    /* Each allocator maintains a linked list of free buffers.
     * This is what I mean by freelists.  Usually there's
     * something in the freelist, so allocation
     * is super-fast.  But occasionally it's empty.
     */
    if (allocator->freelist == NULL)
        return allocateNewBuf(allocator);  /* (the slow path) */

    /* The super-fast path.  Just pop the first item off the freelist. */
    void *item = allocator->freelist;
    allocator->freelist = LINKED_LIST_NEXT(item);
    return item;  /* man, that was fast! */
}

/* free() is super-fast, too. */
void free(void *buf)
{
    /* First get the allocator... */
    size_t bufsize = GET_SIZE_OF_BUF(buf);  /* (usually stashed nearby) */
    FixedSizeAllocator *allocator = getAllocatorForSize(bufsize);

    /* Then just push this buffer back onto the freelist.  Zoom zoom! */
    LINKED_LIST_NEXT(item) = allocator->freelist;
    allocator->freelist = item;
}

See how simple and fast that is? Even if all the freelists are initially empty, each time you free() memory, it goes on a freelist. So pretty soon, almost every call to malloc() is just popping a ready buffer off a linked list.

I’m glossing over allocateNewBuf() here, but it doesn’t have to be complicated. Basically it just asks the OS for pages of memory in chunks of, say, 4KB; and treats it as an array of smaller chunks, returning the next chunk in the array each time it’s called.

The locality problem

It all seems pretty awesome, right? It did to me. Then one day Brendan Eich mentioned to me that this approach can lead to fragmentation.

That surprised me. After all, the point of size classes is to avoid the fragmentation you get if you try to allocate buffers of all sizes from the same heap. Google for “best-fit” or “first-fit”—the results are all about heap fragmentation.

Now, in case you haven’t met Brendan, I should explain a bit. He talks fast and he says amazing things. His speech is full of metaphors you might need to think about for a while in a quiet room and examples you’ve never heard of. The average word Brendan uses is rarer than the average word you or I use. So Brendan’s output is ludicrously high-bandwidth, often impossible to keep up with; but at least you can Google what you don’t understand. Spending a few days puzzling over what Brendan meant by some five-word off-the-cuff remark, and ultimately decompressing it into a rewarding insight, is merely typical. At least, for me. No exaggeration.

In this case, I eventually found out Brendan was referring to a different, and potentially much worse kind of heap fragmentation than the kind I was familiar with. At program startup, ten calls to malloc(24) will typically return ten buffers that are close together in memory. Maybe even right next to each other, like an array. This is by design. It provides great cache locality and page locality. But as time goes by, the application free()s buffers in no particular order, so the freelists tend to get shuffled. Eventually, ten calls to malloc(24) might return pointers into ten different pages of otherwise unused memory: the worst possible locality.

This weekend I suddenly realized that MMgc’s fast malloc-like allocator, MMgc::FixedMalloc—a piece of code I read months ago—contains a clever workaround for this problem!

FixedMalloc uses per-page freelists. Each fixed-size allocator has a linked list of pages. Each page has a freelist for the buffers in that page. malloc() always consumes one page’s freelist completely before going to another page.

I’m sure this trick is well-known in the field, but what’s a blog for, if not advertising your own ignorance?

I just posted to mozilla.dev.platform about Mozilla 2 platform changes. In short: Mercurial is coming, Tamarin is coming, and we’re going to give garbage collection a chance to prove itself.

Want to help the Mozilla project? Here’s something anyone with a web browser can help with.

A lot of technical documents still live on www.mozilla.org. This is bad for a lot of reasons, but fundamentally it’s just the wrong place for them. developer.mozilla.org is their proper home. The pages will be much easier for us all to find, improve, and maintain there.

You can help migrate this content.

• Find a page to migrate. MDC:Existing Content is the nerve center of this operation and contains a huge list. (Seasoned hackers might prefer to grab the source code for the entire www.mozilla.org web site from CVS and use their best judgment about what to migrate. Some things are clearly technical docs; some aren’t.)
• View → Page Source. Copy the HTML code for the page.
• Paste it into an HTML to Wiki converter. (Unfortunately, this one has a few bugs. Watch for glitches with non-ASCII characters like  . It also converts + signs to spaces. Quaint bug, very 1995. If you know of a better converter that requires no download, let me know.)
• Make a new page on developer.mozilla.org. The easiest way is to edit MDC:Existing Content, find the link that you’re about to migrate, and add: - now migrating to [[Title of the new page you want to make]]. Click Save Page. Now MDC:Existing Content should have a red link (you just added it). Click the link to go to the new, empty page, then click “edit this page”.
• Paste in the Wiki code. In the Summary field, write “migrated from ” and paste in the URL of the old www.mozilla.org page. Click “Save Page”.
• Look at the new page. If it looks awful in any way, click the “Edit” link on the right-hand side and clean it up. (the “Editing help” link might help you figure out what’s wrong).
• Follow the 5 After Document Migration steps to make sure (a) people can find your new page; and (b) nobody else does the same work all over again.

See? Easy and fun. This is what I do now when something’s building. So far I’ve migrated 23 pages.

If you really want a new best friend, write an extension to make this process less ridiculous.

Maybe you’re curious about how the MMgc garbage collector works. Here’s my rambling attempt to explain it on IRC this morning (edited for clarity and layout).

(Note: The MMgc documentation is another good place to start, if you already know all about the C++ stack and heap.)

peter: this "scanning the C stack" is a mystery to me
peter: I had no idea C was reflective like this
jorendorff: Oh, it's not 
peter: ok good because I never heard of such things!
jorendorff: Happy to explain.  
jorendorff: Or try. 
jorendorff: But you need to understand a little about how C works in practice.
jorendorff: What do you know about "the stack"?
peter: not much I guess
peter: I know about regular C dynamic memory use
jorendorff: Well, when your program runs, and main() gets called,
jorendorff: say you've got some local variables in there.
jorendorff: C has to store them somewhere.  What happens is
jorendorff: ...C has some memory, maybe 64K bytes, set aside
jorendorff: ...for local variables.
peter: yep
peter: set aside by the OS, correct?
jorendorff: eh, not exactly
jorendorff: C asks the OS for 64K bytes, the OS says sure, here you go,
peter: right
peter: ok
jorendorff: ...and C uses those for the stack.
jorendorff: But the OS doesn't know what C is doing with them.
peter: ok

Here when I talk about “C” doing things, I really mean “the C language runtime”. This is code that the C linker automatically links into every C/C++ program. It’s called libc on Unix. On Windows, they call it the CRT.

jorendorff: So.  C remembers how much of the stack is in use.
jorendorff: (It has a machine register pointing to "the top of the stack")
jorendorff: (...on intel x86, this is ESP)
peter: C's malloc asks for memory from this 64kb and manages it
peter: making sure things that need to be in even alignment, are
peter: and so on
jorendorff: Well, the stack is separate from all malloc'd memory.
peter: ahh ok
jorendorff: Local variables don't go in malloc'd memory.
peter: gotcha
jorendorff: C actually sets up both the stack and the malloc() heap
jorendorff: before main even runs.
peter: ok
peter: and the stack is the automanaged part for locals
jorendorff: exactly
peter: thats the part everyone likes 
jorendorff: right.
jorendorff: OK.  So when main() calls another function,
jorendorff: ...say it calls printf()
jorendorff: C does all this automatically
jorendorff: ...*before* any code in printf() actually executes:
jorendorff: (1) stores a "return address"
jorendorff: so it knows where to pick up again when printf() eventually returns
jorendorff: (2) sets aside some stack space for printf's local variables.
jorendorff: I guess (2) actually happens in some code within printf
jorendorff: ...that is generated automatically by the compiler.
jorendorff: Then printf() runs.
peter: ok
jorendorff: When printf() returns, all those local variables go away.
jorendorff: My point is--
jorendorff: can you see what the data structure for this is like?
jorendorff: "The stack" is just a contiguous chunk of memory.
jorendorff: main()'s locals are at the bottom.
peter: sure
jorendorff: If main() calls another function, those locals are adjacent
jorendorff: and so on
peter: makes sense
jorendorff: it's actually a "stack" in the data structures sense.
jorendorff: ok, what this means is
jorendorff: all local variables, both for the current function
jorendorff: and all its callers,
jorendorff: are in this contiguous chunk of memory.
jorendorff: For each platform (meaning, OS + CPU + compiler)
jorendorff: ...there's a way to find out where that chunk of memory is.
jorendorff: Tamarin does that,
jorendorff: then it scans all that memory during GC
jorendorff: to see where the locals point to.
peter: there is some C header can be included that allows access to all this?
jorendorff: peter: not standard C, no
peter: no but some header
jorendorff: yeah, look in the tamarin source  

This magic lives in a macro, MMGC_GET_STACK_EXTENTS, defined in the header MMgc/GC.h. As you can see, there’s a separate implementation for each platform.

At any given moment, some locals might be in CPU registers and not on the stack. To cope with this, the macro uses a few lines of assembly code to dump the contents of all the registers onto the stack. That way MMgc can just scan the stack and it’ll see all local variables.

peter: I have been thinking there would be ways to fool this stack scan
jorendorff: peter: Yes, there would be.  
jorendorff: Can you give me an example, though?
peter: if a local pointer points to  dynamically allocated bit of memory
peter: that points to other dynamically allocated bits
peter: that should not be garbage collected
peter: and there have been a bunch of type casts along the way
jorendorff: Oh, type casts don't affect MMgc at all.
jorendorff: MMgc doesn't look at C/C++ code.
jorendorff: It's looking at raw memory.
peter: ahh right
peter: just inference by bit patterns?
jorendorff: yep
peter: and it follows from local pointers to malloc()ed memory,
peter: and follows the pointers in that memory to other memory, and so on?
jorendorff: yes, in principle -- but
jorendorff: MMgc has its own allocator
jorendorff: that you must use instead of malloc().
peter: ahh
peter: ok
jorendorff: Since it knows all the internal data structures
jorendorff: used by that allocator,
jorendorff: when it follows pointers
jorendorff: it knows the size of every region
jorendorff: and can scan each reachable region for further pointers.

In addition, MMgc does enough bookkeeping that it knows exactly which parts of memory are GC-managed. So it can’t be fooled into following a pointer into bad memory (such as NULL or a pointer to a page of memory that has been returned to the operating system, either of which would immediately crash the process). The same bookkeeping information helps MMgc avoid mistakenly writing to non-GC-managed memory. (This matters because it does write to GC-managed memory, just like any other mark-and-sweep garbage collector.)

There are other ways to fool MMgc. Simply using malloc() is enough —MMgc never scans memory allocated using malloc(). It’s up to the programmer to avoid fooling MMgc. This is not such a heavy burden in practice.

peter: fascinating stuff
peter: who's the genius that thought up all this stuff?
jorendorff: Some Lisp hacker in prehistory 
jorendorff: 
jorendorff: Lisp was the first language with GC
jorendorff: you can look up garbage collection online
jorendorff: It's a whole field of computer science.
jorendorff: It *is* fascinating.
peter: do you know the proper comp sci terminology
peter: for this stack-scan style of GC?
peter: or is it just part of the collective knowledge?
jorendorff: Um,
jorendorff: What MMgc does is called "conservative GC"
jorendorff: which means (a) it doesn't really know the types of variables,
jorendorff: so it scans everything whether it's really a pointer variable or not
peter: ok I've seen that written in a few places recently
jorendorff: and usually (b) it treats all the likely places as "roots"
jorendorff: including the stack
peter: The root of the issue is I had no idea C could analyze it's own stack
jorendorff: heh
jorendorff: C can do anything  

Indeed it can—which is why, despite their many deep, fundamental problems, C and C++ remain the weapons of choice for operating system and VM designers.

For the past 4 weeks or so, Ed Lee and I have been incrementally nudging the actionmonkey repository toward a state where we can switch over from SpiderMonkey’s existing memory management routines to Tamarin’s memory management library, MMgc.

Today some key patches for ActionMonkey Stage 0 were posted on bug 391211. These patches delete the old JSGCArena scheme and start allocating everything—JavaScript strings, functions, objects, and more—from MMgc.

This change will lead to several simplifications. For example, SpiderMonkey currently saves a reference to every new object as it’s created. This reference keeps the object alive in case GC happens while it’s new, before it’s reachable from other data. The reference lasts until the next object is created. So as long as you know SpiderMonkey internals reeeally well, and you’re dead certain no new objects are being created, you can sometimes avoid explicitly rooting an object. Hmmm, maybe this sounds a little crazy and brittle… anyway, these “newborn roots” will be unnecessary with MMgc, because MMgc scans the C stack. Even if your new object isn’t reachable from anywhere else yet, there will be a pointer to it from the stack or registers, so it won’t be unexpectedly collected. Similarly, throughout SpiderMonkey, JSTempValueRooters are used to pin objects referenced by local variables in C code. These temporary roots are generally short-lived, whereas GC happens rarely; so adding and removing the temporary root is just useless bookkeeping most of the time. Thanks to MMgc’s stack scanning, these TempValueRooters can be deleted altogether. And third, we’re planning to delete some bits called GCThingFlags that currently cost us 4 to 8 bytes per allocation. I’m curious to see how these simplifications will affect performance.

These cleanup tasks are an easy way to get involved in ActionMonkey, by the way. Leave a comment if you’d like to lend a hand.