Call for Help: Boehm+jemalloc

Wednesday, September 24th, 2008

At the Firefox summit we decided to change tack on XPCOMGC and try to use Boehm instead of MMgc. Overall I think this was a really good decision. With help from Graydon, I even have some Linux builds that use Boehm under the hood (most memory is not considered collectable, only string buffers are collected objects at this point).

Unfortunately, while Boehm is a pretty good collector, it doesn’t do so well at memory allocation and fragmentation. Heap usage is between 1.5x and 2x that of standard Firefox using jemalloc. What I really want is a combination of jemalloc and Boehm, taking the best features from each:

Boehm Features:

  • Fast and threadsafe conservative collector
  • Smart rooting of all thread stacks and static data
  • Incremental marking with hardware write barriers1
  • Option for parallel collection2
  • Ability to intermingle collected and non-collected memory

jemalloc features:

  • Better overall memory usage, primarily due to lower fragmentation
  • Very tight and well-performing allocator

Help Wanted

I’m looking for somebody who’s willing to painstakingly combine the best of these two allocators: either port the jemalloc low-fragmentation design to Boehm, or port the Boehm collection mechanism to the jemalloc allocator. If you’re interested, please contact me. Getting a solution to this problem really blocks any serious plans for further work on XPCOMGC.


  1. The key word is hardware. The MMgc solution failed because altering our codebase to have correct programmatic write barriers was going to involve boiling the ocean. And even with smart pointers, a standard MMgc write barrier involves a lot of overhead.
  2. In Boehm, parallel collection doesn’t work with most incremental collection, and so we may not actually decide to use it; avoiding large pauses with incremental collection is more important.

Merging with Mercurial Queues

Friday, November 30th, 2007

I’ve spent most of the last 2.5 days merging code that lives in mercurial patch queues. It’s been an interesting (and frustrating) experience, but I’ve learned a lot, so I put together this tutorial on maintaining/merging/updating a mercurial patch queue.

The XPCOMGC patch queue

The XPCOMGC patch queue was actually 60+ patches long, but for example purposes let’s simplify to 7. What makes it tricky is that patches “after” the automated rewrites often won’t apply cleanly to the tree before the automatic rewrite. This means that moving patches from “after an automatic rewrite” to “before an automatic rewrite” requires a merge algorithm. Imagine a patch series like this:


You may be wondering about “manual-fixbugA-patch2″… why didn’t I just go back to manual-fixbugA and change it? This is because, once you’ve applied an automatic rewrite, popping/editing/pushing requires not only a complete tree rebuild (20 minutes), but also rebuilding the automated patches (hours). Instead, I create a “patch2” (and sometimes a “patch3” and “patch4”) and later fold the patches together.

Reordering a patch queue

I want to clean up this patch queue and update the “base tree” on which I’m applying patches. To do this, I’m first going to move all the “manual” patches before the automatic rewrites. Some of the patches may not apply cleanly in their new positions, so we prepare for merging. 64

$ hg qpush -a;          # Push all patches
$ hg qsave -e -c;       # Save the patch queue state... this allows for merging later
$ hg update -C qparent; # Move the working directory back to a completely unpatched state

Now we edit the .hg/patches/series file, removing the automatic rewrites. Instead of attempting to merge the automatic rewrites, we will simply regenerate them later.


Now we push the patches back on: if a patch doesn’t apply cleanly, use a three-way merge algorithm based on the saved patch queue state:

hg qpush -m; # applies manual-fixbugA
hg qpush -m; # applies manual-fixbugB
hg qpush -m; # applies manual-fixbugA-patch2 with interactive merging
hg qpush -m; # applies manual-fixbugC with interactive merging

Now, we want to merge the changes from “manual-fixbugA-patch2” into “manual-fixbugA”

hg qgoto manual-fixbugA;
hg qfold manual-fixbugA-patch2;

Now we have a clean patch queue which is ready for updating to a new “base”:

hg qpush -a;    # Push all patches in preparation for our second merge
hg qsave -e -c; # Save the patch queue state (again)
hg pull; # Pull new changesets from actionmonkey
hg up tip;      # Update the working directory to the unpatched actionmonkey tip
hg qpush -m;    # merge the patches one by one, with merging if necessary

In the case of XPCOMGC, “new-base” merges are difficult primarily because of the cycle collector. Cycle-collection is still be actively developed on trunk, with major changes to the xpconnect mark/trace algorithms as well as changes to timing. One of the earliest patches in the XPCOMGC queue removes cycle-collector entirely (when we have a garbage collector for XPCOM objects a cycle collector is no longer needed). Merge conflicts are common not only in the patch which removes the cycle collector, but in subsequent patches which touch xpconnect.

I’ve learned that merging goes much better if every patch in the patch queue produces a building tree. To test whether a merge was performed correctly (or discover which patch was merged incorrectly), simply build the tree at each patch state.


Mercurial patch queues make it possible to merge-update a series of patches against a moving base, which is very cool. But they don’t remove the actual hard work of merging changes that conflict.