internal fragmentation

Mercurial: adding ‘unified’ tests

Wed, 4 Aug 2010 16:26 by mpm in Uncategorized (link)

Mercurial’s testing framework just got better. Since the beginning, the basic approach has been to run a test script and compare its output with known good output. This works great most of the time, but when things do change, it can be quite hard to figure out where because there’s no easy way to match the test commands with their output. If, for instance, you had a test script that said:

hg frob a
hg frob b

and the output:

abort: something bad happened

..you wouldn’t be able to tell which command caused the error.

Based on an idea from the 1.5 sprint, I’ve implemented a way to combine the input and the output in the same file in a ‘literate programming’ style. So the above example would look like this:

Try frobbing a:

  $ hg frob a

Try frobbing b (it shouldn't succeed):

  $ hg frob b
  abort: something bad happened

The test engine finds all of the lines prefixed with “ $ ” and assembles a script to run and then reassembles an output test with the results of the test. The real trick of course, is lining up the input with the output. To do that, we simply inject line markers into the script of the form:

echo SALT <some random number> <line number>

..which we can easily locate in the output and strip out.

Another problem this new approach addresses is cleaning up non-repeatable output such as dates and names of temporary files. Our traditional approach is for the test script to filter output through sed or grep to clean it up or redirect it. But as we’re already massaging output, it’s very easy for us to simply throw in regular expressions on the bits we don’t care about. For instance:

Check the log:

  $ hg log -r 1
  changeset:   1:.*
  user:        test
  date:        .*
  summary:     commit test

With any luck, this change will also make tests slightly faster, as we’ll need to run fewer copies of sed.

Here’s an example of a full-blown test before and after.

Comments (0)

Mercurial Fellowship status for July

Sun, 1 Aug 2010 15:31 by mpm in mercurial (link)

A quick summary of what I’ve been up to in July:

1.6 release
reviewed and merged 171 changesets
authored 29 changesets
83 mailing list messages
major refactoring of Mercurial protocol support
in-depth investigation of the notorious issue1327
lots of bug triage
started 1.7 sprint planning
started developing 2010 user survey
4 GSoC meetings
daily IRC office hours
interview with students from ETNA

Comments (0)

Python optimization note: function calls are slow

Mon, 26 Jul 2010 10:01 by mpm in Uncategorized (link)

In Mercurial, we do a lot of gathering and filtering of long lists of things – filenames, revision numbers, etc. A typical pattern is something like this:

l = []
for f in files:
    if f.startswith(foo):
        l.append(f)

Usually it’s more involved than that – there’s often multiple lists to track and several tests, so a simple comprehension won’t help. And usually performance of these loops is pretty critical. If we can shave 10% off a call to status when there are 50,000 files, we’ll do it. So one of the first things we do is:

l = []
la = l.append
for f in files:
    if f.startswith(foo):
        la(f)

This saves a lookup in the inner loop, and that’s often a very measurable win. Another pattern is that sometimes one or more of the lists isn’t going to be needed, so we’ll avoid appending to it at all. So is it better to call a dummy function or stick an if statement in the inner loop? Let’s consider variations on this simple test:

a = []
f = False
aa = a.append
for x in xrange(1000000):
    if f:
        aa(x)

Let’s explore some possibilities and time them with timeit (Python 2.6.5):

append function	flag	test	time
None	True	if f: a.append	216 msec
None	True	a.append	197 msec
a.append	True	if f: la(x)	133 msec
a.append	False	if f: la(x)	63 msec
a.append	True	f and la(x)	133 msec
a.append	False	f and la(x)	65 msec
a.append	True	la(x)	113 msec
lambda x: None	False	la(x)	239 msec
id	False	la(x)	110 msec

The fastest way to add to a list (flag is True) is with a pre-looked-up list append function and no test. But the fastest way to not add to our list is with the if test. And both of these are significantly faster than the naive ‘if f: a.append(x)’ approach.

Thus, if we expect to usually be adding to a given list, we should set la to a handy dummy function like the ‘id’ built-in when our flag tells us not to gather to a list. This is much faster than the obvious lambda function by virtue of being a trivial built-in, and gives us a ‘balanced’ 113/110 msec split between keep and discard. But if we usually don’t want a list (for instance, Mercurial usually doesn’t report ‘clean’ files), then an if statement is best, with a 133/63 keep/discard split.

Comments (1)

Mercurial Fellowship status for June

Thu, 15 Jul 2010 17:53 by mpm in mercurial (link)

As I announced back in April, I’ve been putting together funding to work on Mercurial development and project leadership full-time for the next year without the usual distractions like finding support clients or working on embedded Linux products. That’s more or less come together, and I started working at the beginning of June. You can see most of my awesome sponsors here though there’s still one big one that the paperwork isn’t finished with yet that I’ll hopefully be announcing shortly.

Meanwhile, our project’s nonprofit home, the Software Freedom Conservancy has asked that I post some monthly status reports to give some visibility into what it is I actually do. So here’s a quick summary of what I did in June:

1.5.4 release
1.6 release code freeze
reviewed and merged 144 changesets
authored 61 changesets
introduced two major features (pushable bookmarks and revsets)
numerous bug fixes and other improvements
some wiki improvements (like the Trust page)
5 weekly meetings with our GSoC students and related mentoring
123 messages to the mercurial-devel list (out of 929)
65 to the main list (out of 909)
3 blog posts
daily “office hours” for developers and users on IRC
a Mercurial live video interview on FLOSS Weekly

The 1.6 release of course came out right on time on July 1st, and I’m pretty pleased with it.

Comments (2)

Unifying the Mercurial wire protocol

17:18 by mpm in Uncategorized (tagged mercurial) (link)

One Crazy Summer

The Mercurial ‘wire protocol’ is the set of commands that Mercurial uses to discover changesets to push and pull and actually exchange changesets with remote hosts. It was developed surprisingly rapidly, given that everything else in the project was also brand new:

April 20 2005: first Mercurial release
April 21 2005: static http pull support
May 10 2005: changeset bundle format created
May 11 2005: hgweb merged
May 12 2005: added smart http protocol to hgweb
May 25 2005: hg serve stand-alone server added
June 12 2005: crazy tunnel-http-over-ssh push hack
July 5 2005: ssh smart server support
July 6 2005: real ssh push

And that gets us up to the 0.6b release, less than three months after the 0.1 release.

Steady As She Goes

Because ssh push was good enough for most of our users at the time, not much happened with our wire protocol until about a year later when we finally got around to working on http push:

June 10 2006: add capability detection to protocol
June 15 2006: new push approach for ssh
June 20 2006: real http/https push
July 14 2006: add support for –uncompressed clones for fast networks

And again, the wire protocol hasn’t changed much since then. A branchmap command was added in May 2009 to improve named branch support, and pushkey was added a couple weeks ago to support bookmarks. We’ve also been careful to keep the protocol backwards compatible: Mercurial 0.5 can interoperate with even the most recent versions.

Preparing for the New Frontier

But there are a number of big projects on the horizon that will require extending the wire protocol, including:

a new, faster discovery algorithm
improved compression with parent deltas
support for shallow clones
support for lightweight copies

Which means its high time that the wire protocol got cleaned up! Currently adding a new command to the protocol means adding code in four different places: the ssh client code, the ssh server code, the http client code, and the http server code. And those interfaces aren’t exactly pretty. Here’s what the old ssh and http server support for lookup looks like:

ssh:
    def do_lookup(self):
        arg, key = self.getarg()
        assert arg == 'key'
        try:
            r = hex(self.repo.lookup(key))
            success = 1
        except Exception, inst:
            r = str(inst)
            success = 0
        self.respond("%s %s\n" % (success, r))
http:
def lookup(repo, req):
    try:
        r = hex(repo.lookup(req.form['key'][0]))
        success = 1
    except Exception, inst:
        r = str(inst)
        success = 0
    resp = "%s %s\n" % (success, r)
    req.respond(HTTP_OK, HGTYPE, length=len(resp))
    yield resp

Fortunately, we’ve been careful to keep the ssh and http ‘calling convention’ very similar. The bulk of the code is similar but there are some basic differences in how arguments are retrieved and how results are returned. Similar things need to be changed on the client side. Adding new commands meant writing one protocol implementation, then copy&pasting it into the other protocol and tweaking it.

Unification

So a long-standing wishlist item has been to unify these implementations, which is what I’ve been working on this week. Now the above command is implemented just once like this:

def lookup(repo, proto, key):
    try:
         r = hex(repo.lookup(key))
         success = 1
    except Exception, inst:
         r = str(inst)
         success = 0
    return "%s %s\n" % (success, r)

Note that the output is now delivered via return and the argument is now passed in as a parameter. A central dispatcher now handles argument unpacking and delivering results and has a table of all the function parameter lists (including support for variable-length argument lists!). Each function also has a ‘proto’ option which gives it access to an abstracted interface for various http- or ssh-specific methods, like doing bulk data transfers. Similarly, the client-side support is also unified, and both the client and server support is now all in one file: wireproto.py. This will hopefully make future extensions to the wire protocol much less painful.

The tricky part of course with a big change like this is how to break it down into pieces. Simply trying to refactor it all in one go might be possible, but it’s much safer to do it in a step by step process, testing each step along the way. So I started by making a new ssh argument parser, hooking that into a generic command dispatcher, and hooking that dispatcher into the existing ssh infrastructure. Now I could move commands out of the ssh framework and into the generic framework one by one. Once I’d moved a bunch of the simpler ssh commands, I went and tackled merging them on the http side with a similar approach. Overall, the process took a total of 18 changesets.

Comments (3)

Extending the Mercurial protocol with pushkey and bookmarks

Mon, 28 Jun 2010 14:17 by mpm in mercurial (link)

Historically, Mercurial can send and receive precisely one type of data when pushing and pulling: changesets. As just about everything that you’d ever want to push and pull is recorded in a project’s history (including tags and branches), this works out very cleanly and simply.

But recently (ok, 2008), we’ve borrowed a concept from Git for lightweight markers that aren’t part of history and leave no mark when they’re added, changed, or removed. Git calls these ‘branches’, though Mercurial already has a notion of branches that’s much more in keeping with the permanent markers used in other systems (and Mercurial’s general philosophy of permanent history), so Mercurial has named these ‘bookmarks‘. Like real bookmarks, Mercurial bookmarks mark your place, but can be moved around or removed without altering the book.

The only problem was that there was no way to push and pull these things in the protocol, so sharing your bookmarks with other users was tedious. And as sometimes happens with open source, we had a plan for a solution, but the implementor became too busy with other things for quite a while. Fortunately, extending Mercurial’s protocol isn’t terribly difficult so a couple weeks ago, I sat down to do it myself. Here’s how I did it.

First, I introduced a generic notion called “pushkeys”. Pushkeys are key/value pairs that can be pushed to the server and listed back. There are multiple namespaces and any service or extension can register a namespace. There’s also a special “namespaces” namespace that shows the registered namespaces. To set a key, you have to also send along the old value to avoid races. The whole of is about 30 lines long and is introduced in this changeset.

Next we add the pushkey capability and pushkey/listkey command support to the local repository, the ssh client and server, and the http client and server. Finally, the debugpushkey lets us test the new support from the command line:

$ hg debugpushkey ~/hg namespaces
bookmarks
namespaces
$ hg debugpushkey ~/hg bookmarks
test-bookmark    ff2704a8ded37fbebd8b6eb5ec733731d725da8a
$ hg debugpushkey ~/hg bookmarks test-bookmark ff2704a8ded37fbebd8b6eb5ec733731d725da8a ''
True
$ hg debugpushkey ~/hg bookmarks
$

The above shows off the bookmark namespace service for pushkeys, which is added in the next changeset. Now all that remains is to add client support for bookmarks. This has a few different pieces:

default push and pull behavior: update bookmarks that are already present on both sides
push and pull -B: copy over specific bookmarks while pulling
in and out -B: list unique bookmarks on the client or server

These changes can be found starting here. The improved bookmark support will show up in Mercurial 1.6, due to be released on July 1st, but you can download a copy for testing today. Note that you’ll also need bookmark support enabled on your server (services like Google Code and Bitbucket may take a bit to catch up!).

There’s more to be done with bookmarks support, and there are a lot of other interesting things that can be done pretty easily with the pushkey protocol (for instance, those horrible advisory locks CVS folks always think they want). I’m sure we’ll be seeing some interesting ideas appear here soon.

Comments (4)

Mapping import graphs

Sat, 5 Jun 2010 11:42 by mpm in mercurial (tagged python mercurial) (link)

Occasionally when adding features to Mercurial, we’ll run into interesting circular dependencies. For instance, repositories want to know about subrepositories, which naturally want to know about repositories. Often this manifests as a traceback when trying to import. And because the main Mercurial tool uses demand-loading to avoid wasting time on unused imports, this often isn’t caught until we run the test suite (which has a couple non-demand-loading scripts) or even later.

Fixing these problems usually involves moving some code around to make the dependencies more hierarchical. But figuring out what the hierarchy looks like can be tricky: there are about 70 modules in the core. But with the help of Graphviz and the following quick helper script, we can start to get a handle on things:

import re, sys
ignore = set("".split())

watch = set()
for fn in sys.argv[1:]:
    watch.add(fn[:-3])

print "digraph G {"
for fn in sys.argv[1:]:
    f = open(fn)
    mod = fn[:-3]
    if mod in ignore:
        continue
    for l in f:
        m = re.match("^\s*import (.*?)( as .*)?$", l)
        if not m:
	    m = re.match("^\s*from (.*?)( import .*)?$", l)
        if m:
            s = m.group(1).split(",")
            for i in s:
                i = i.strip()
		if i in ignore or i not in watch:
                    continue
                print '"%s" -> "%s"' % (mod, i)
print "}"

Here’s what that looks like (click through to zoom in):

Ouch! With a bit of ignoring of some of the leaf nodes and minor modules, we can reduce it to this:

And finally, by using Graphviz’ tred filter (which removes edges that are reachable through other routes) and ignoring explicitly delayed imports, we can get down to something nice and tidy like this:

Now it’s fairly easy to find the trouble spots and think about how to fix them. Ideally all the arrows in this graph would point downward, but we can easily see a couple that point upward for help and templatekw.

Comments (1)

FLOSS Weekly

Wed, 2 Jun 2010 11:16 by mpm in Uncategorized (link)

I’ll be appearing “live” on the FLOSS Weekly show today at 11:30 CST (ie in a few minutes), talking about Mercurial. If you can’t tune in to the live video recording, you can watch it later in the podcast edition.

Update: the video can be found here.

Comments (0)

Mercurial: tracking down a performance regression

Fri, 28 May 2010 16:49 by mpm in mercurial (tagged bisect, mercurial, performance, subrepos) (link)

Today on the Mercurial-devel list, Jason Harris of MacHg noted:

In reference to matching the current version of Mercurial I noticed in my quick
testing that for quick status commands 1.4.2 was some 20% faster than 1.5.3.

That definitely shouldn’t happen. So I hopped over to a handy large repository and tried a quick test. I keep around builds of each Mercurial release for quick testing:

$ for i in `seq 5` ; do time hg153 st --all > /dev/null; done

real	0m1.754s
user	0m1.403s
sys	0m0.333s

real	0m1.749s
user	0m1.467s
sys	0m0.273s

real	0m1.741s
user	0m1.413s
sys	0m0.320s

real	0m1.761s
user	0m1.373s
sys	0m0.360s

real	0m1.772s
user	0m1.437s
sys	0m0.303s

$ for i in `seq 5` ; do time hg143 st --all > /dev/null; done

real	0m1.598s
user	0m1.283s
sys	0m0.297s

real	0m1.427s
user	0m1.070s
sys	0m0.343s

real	0m1.434s
user	0m1.127s
sys	0m0.293s

real	0m1.468s
user	0m1.127s
sys	0m0.307s

real	0m1.436s
user	0m1.100s
sys	0m0.313s

And indeed there’s a performance regression here. But as it happens, our normal performance-measuring tool doesn’t see any significant difference:

$ hg14 perfstatus
! result: 4156
! wall 0.664630 comb 0.660000 user 0.420000 sys 0.240000 (best of 15)
$ hg153 perfstatus
! result: 4156
! wall 0.674376 comb 0.670000 user 0.440000 sys 0.230000 (best of 14)

‘Perfstatus’ is part of contrib/perf.py, which an extension we use to benchmark some of most performance-critical code. It automates the process of choosing a reasonable sample size, much like Python’s timeit module. Note that it reports only the fastest time: practically all sources of noise in performance measurement (scheduling, power-saving, interrupts, cache effects) only make things slower, not faster. Thus picking the fastest result lets you focus on the least noisy measurement.

So something interesting is happening outside the status fast path. And we also get a null result measuring normal startup time via ‘perfstartup’. This calls for running bisect on the Mercurial repo itself:

$ cd ~/hg
$ hg bisect -r  # reset the bisection state
$ hg bisect -b tip  # latest version is bad
$ hg bisect -g 1.4
Testing changeset 10549:b97736016273 (1359 changesets remaining, ~10 tests)
332 files updated, 0 files merged, 27 files removed, 0 files unresolved

After marking a bad and a good revision, Mercurial jumps me to a revision in the middle for me to test. To run a test, I simply hop over to another terminal and run my for loop from earlier, then hop back and report ‘hg bisect -g’ or ‘hg bisect -b’. After about 10 iterations, Mercurial reports:

The first bad revision is:
changeset:   10176:24ce8f0c0a39
user:        Augie Fackler <durin42@gmail.com>
date:        Thu Dec 31 17:19:30 2009 -0600
summary:     dirstate: don't check state of subrepo directories

Hmm, this changeset seems innocent enough. And the repo we’re testing against doesn’t use subrepositories anyway. But closer inspection finds:

+            subrepos = ctx1.substate.keys()

And looking at how substate works, we see that it’s doing:

if '.hgsub' in ctx:
     read('.hgsub')

Hidden in that ‘in’ operation is a call into the context class that demand-loads the manifest for the parent changeset to check if a file is present. This isn’t showing up in the perfstatus benchmark because the first call is priming our internal manifest cache. Reading a manifest is one of the more expensive operations in Mercurial’s core and on large repositories can take a substantial fraction of a second, so we generally try to avoid. Can we avoid it here?

The answer is: yes, sometimes. When subrepos are in use, we do need to consult the committed .hgsub file. But in most cases, we can do a quick check in the dirstate (which we already have to demand-load for status checks) before going deeper:

 if working: # we need to scan the working dir
-            subrepos = ctx1.substate.keys()
+            subrepos = []
+            if '.hgsub' in self.dirstate:
+                subrepos = ctx1.substate.keys()
 s = self.dirstate.status(match, subrepos, listignored,
 listclean, listunknown)

(This patch is now in stable and will be part of the scheduled monthly minor release of 1.5.4 on June 1st.)

Comments (0)

Mercurial: extending revision specifiers and a dilemma

Wed, 26 May 2010 15:56 by mpm in mercurial (tagged mercurial) (link)

Right now we’re working on a way to greatly extend the way sets of revisions are specified in Mercurial. Currently most commands can take one or more ‘-r’ arguments that take single revisions and ranges of the form ‘start:end’, and revisions can be specified as a revision number, a relative revision number (eg -2), a changeset hash, a tag, a bookmark, a branch name, or built-ins like ‘.’, ‘null’, and ‘tip’.

This is good enough for many purposes, but we often get requests for more flexibility. These requests usually show up as new options for the log command, which has now grown a small army of them. The more popular of these will also trickle over into other commands. This is less than ideal because it means we have lots of options and potentially lots of duplicated and hairy code.

The new plan is to have a simple query language that lets you easily specify more complex queries anywhere a revision option is taken. The query language looks like this:

all changes on a branch: branch(foo)
all descendants of 1.0: descendants(1.0)
all ancestors of 1.1 and descendants of 1.0:
ancestors(1.1 ) and descendants(1.0) or 1.0..1.1
all ancestors of the working directory: ancestors(.) or follow()
all changesets from May containing the keyword ‘bug’: date(“may”) and keyword(“bug”)
all changeset from Bob or Alice: user(“bob”) or user(“alice”)
a complicated query:
(user(“bob”) or user(“alice”)) and not merge() and 1.0..stable and keyword(“foo.py”) and not date(“may 10-may 20″)

This just begins to scratch the surface of what we can do with this scheme. We’ve actually made quite a lot of progress on this in the past week. In fact we now have two nearly complete rival implementations, each with their own tokenizer, parser, evaluator, predicates, and query optimization strategy. The most interesting piece here is the approach to parsing.

My version uses a simple ‘Pratt Parser‘ that I wrote for this purpose. It makes parsing algebraic and query-like expressions very simple. On the upside, this parser is very small: the parser module itself is only 75 lines and can be driven entirely by data rather than by verbose code. On the downside, it’s rather mysterious to the uninitiated. The ‘grammar’ that I pass to the parsing engine looks like this in its entirety:

elements = {
    "(": (20, ("group", 1, ")"), ("func", 1, ")")),
    "..": (17, None, ("dagrange", 17)),
    "not": (15, ("not", 15)),
    ":": (10, None, ("range", 10)),
    "and": (5, None, ("and", 5)),
    "or": (4, None, ("or", 4)),
    ",": (2, None, ("list", 2)),
    ")": (0, None, None),
    "end": (0, None, None),
    "symbol": (0, ("symbol",), None),
    "string": (0, ("string",), None),
}

(The magic numbers here are operator precedence and associativity, with clauses specifying how the symbol works in infix or prefix situations.)

Henrik Stuart has taken a more conventional approach. He’s taken the full-featured Parsing.py LR(1) parser and built a BNF-style grammar based on it. On the upside, everyone who knows anything about parsing knows how BNF works. On the downside, the parser itself weighs in at ~2000 lines of third-party not-recently-updated code, with the Mercurial-specific query grammar adding a few hundred more.

It’s clear that both versions are well up to the task at hand (and the other parsing-related task I’m looking at, hgweb’s templating engine), which means we have to weigh the strangeness and simplicity of the Pratt Parser against the size and conventionality of the Parsing.py approach.

Comments (6)

Older Posts »