research!rsc

Glob Matching Can Be Simple And Fast Too

2017-04-24T10:00:00-04:00

Here’s a straightforward benchmark. Time how long it takes to run ls (a*)ⁿb in a directory with a single file named a¹⁰⁰, compared to running ls | grep (a.*)ⁿb. Superscripts denote string repetition and parentheses are for grouping only, so that when n is 3, we’re running ls a*a*a*b in a directory containing the single file aaa…aaa (100 a’s), compared against ls | grep a.*a.*a.*b in the same directory.

For n = 8, ls takes 7.19 minutes while ls | grep runs in 1.56 milliseconds, making it 276,538X faster. If you’ve read my 2007 article “Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …),” those graphs may look familiar. Clearly the ls command is using an exponential pattern-matching algorithm, while the ls | grep command is using a nearly linear one.

Shells

In fact it’s the shell that evaluates the glob pattern in the first command, not ls, so let’s repeat the experiment with a variety of shells. All the tests were run on an HP Z440 workstation with 3.5 GHz Intel Xeon E5-1650 v3 processors running Ubuntu 14.04.

Time to match (a*)ⁿb against a¹⁰⁰ in shells

Basically, the same thing is going on here as in my regular expression article: backtracking was an obvious implementation strategy, so most implementations use it, causing the performance cliffs.

The exception seems to be the original Berkeley csh, which runs in linear time (more precisely, time linear in n). Looking at the source code, it doesn’t attempt to perform glob expansion itself. Instead it calls the C library implementation glob(3), which runs in linear time, at least on this Linux system. So maybe we should look at programming language implementations too.

Programming Languages

Most programming languages provide some kind of glob expansion, like C’s glob. Let’s repeat the experiment in a variety of different programming languages:

Time to match (a*)ⁿb against a¹⁰⁰ in programming languages

Perhaps the most interesting fact evident in the graph is that GNU glibc, the C library used on Linux systems, has a linear-time glob implementation, but BSD libc, the C library used on BSD and macOS systems, has an exponential-time implementation.

PHP is not shown in the graph, because its glob function simply invokes the host C library’s glob(3), so that it runs in linear time on Linux and in exponential time on non-Linux systems. (I have not tested what happens on Windows.) All the languages shown in the graph, however, implement glob matching without using the host C library, so the results should not vary by host operating system.

FTP Servers

It’s not just shells and programming languages that implement glob matching. Although not mandated by the FTP RFC, most FTP servers allow glob patterns as the argument to commands like LIST and STAT. Let’s repeat the experiment with a variety of FTP server implementations:

Time to match (a*)ⁿb against a¹⁰⁰ in FTP servers

On Linux, Pure-FTPd would probably have run for a hundred or more seconds for n = 7, but instead it died and hung up the connection after 17 seconds. All the tests were run on the same Linux system as before, except tnftpd, which was run on a mid-2015 MacBook Pro with a 2.8 GHz Intel Core i7 processor running macOS 10.12.4. On that Mac system, tnftpd (which can only be enabled using the command-line, so most people don’t run it) has no such time limit: even if a client times out and hangs up (as the command-line ftp client does after 30 seconds), the server side still consumes CPU until the full pattern match finishes.

The netkit ftpd runs quickly on Linux because it relies on the host C library’s glob function. If run on BSD, the netkit ftpd would take exponential time. ProFTPD ships a copy of the glibc glob, so it should run quickly even on BSD systems. Ironically, Pure-FTPd and tnftpd take exponential time on Linux because they ship a copy of the BSD glob function. Presumably they do this to avoid assuming that the host C library is bug-free, but, at least in this one case, the host C library is better than the one they ship.

Obviously not many servers have a file named a¹⁰⁰, but the pattern can be adapted to shorter, less unusual names. This gives a denial of service attack against some anonymous FTP servers. It appears that tnftpd is derived from the standard FreeBSD ftpd, so BSD systems may be affected as well.

FTP servers and C libraries have a long history of problems with glob patterns, including buffer and heap overflows causing crashes or even remote code execution. But here let’s focus on CPU exhaustion issues around pattern matching.

In 2001, CVE-2001-1501 was issued for a vulnerability in ProFTPD 1.2.1, because it could run for a very long time finding and recording the very many matches for a pattern like:

ls */../*/../*/../*/../*/../*/../*/../*/../*/../*

In response, most glob implementations added a GLOB_LIMIT flag that can be used to limit the number of matches returned, controlling both the CPU and the memory usage for such a pattern.

Unfortunately, a pattern like that can cause a lot of effort without finding any matches. In 2010, CVE-2010-2632 was issued for a variant with no matches:

ls */../*/../*/../*/../*/../*/../*/../*/../*blablahaha

In response, most glob implementations expanded GLOB_LIMIT to count directory read and file stat operations in addition to matches.

In 2015, CVE-2015-5917 was issued for the same vulnerability in OS X 10.10.5’s FTP server (reported in 2013), which had its own copy of the glob implementation and had not been patched in 2010. There have also been similar problems around FTP servers implementing brace expansion, such as CVE-2011-0418 (details).

Unfortunately, none of these protections address the cost of matching a single path element of a single file name. In 2005, CVE-2005-0256 was issued for a DoS vulnerability in WU-FTPD 2.6.2, because it ran for a very long time finding even a single match during:

ftp> dir ************************************************
         ************************************************
         ************************************************
         **.*

The apparent “fix” used in some implementations is to collapse multiple adjacent stars into a single star. That solves one test case, but not the general problem. In particular it doesn’t help a*a*a*a*a*a*a*a*b.

The next section discusses ways to implement glob patterns efficiently, but if you have an anonymous FTP server accepting glob patterns, there are two more fundamental questions to ask: Do you really need to run an anonymous FTP server anymore? Does it really need to accept glob patterns?

At the very least, most FTP servers should probably reject glob patterns with more than, say, 3 stars. Note that glob patterns are only provided as a convenience for command-line FTP users. Graphical FTP clients typically use the MLST and MLSD commands, which have a machine-readable output format and are defined not to interpret their arguments as glob patterns.

Implementation Details

How do these implementations work? What’s going on here?

The obvious implementation of glob pattern matching against a single path element is to walk the pattern and the name together, matching letters or wildcards in the pattern to letters in the name. If the walk reaches the end of the pattern at the same time as the end of the name, they match.

Here’s a basic outline of that algorithm, in Go:

func match(pattern, name string) bool {
    px := 0
    nx := 0
    for px < len(pattern) || nx < len(name) {
        if px < len(pattern) {
            c := pattern[px]
            switch c {
            default: // ordinary character
                if nx < len(name) && name[nx] == c {
                    px++
                    nx++
                    continue
                }
            case '?': // single-character wildcard
                if nx < len(name) {
                    px++
                    nx++
                    continue
                }
            case '*': // zero-or-more-character wildcard
                ...
            }
        }
        // Mismatch.
        return false
    }
    // Matched all of pattern to all of name. Success.
    return true
}

In this code, px is the index into the pattern and nx the index into the name. The loop runs until both pattern and name are exhausted, meaning px == len(pattern) and nx == len(name). If it does happen that both pattern and name are exhausted at the same time, then we have a match (the final return true). Inside the loop, the code must make progress (advance px or nx or both) and continue on each iteration. If not, the control flow ends up at the bottom of the loop body (marked // Mismatch.) and reports no match.

The only difficulty is in the implementation of the variable-length wildcard pattern (case '*'): how much of the name should that match? In general, the code must try all possibilities from matching nothing to matching the entire remainder of the string. The obvious way to do that is with recursion:

func match(pattern, name string) bool {
    px := 0
    nx := 0
    for px < len(pattern) || nx < len(name) {
        if px < len(pattern) {
            c := pattern[px]
            switch c {
            default: // ordinary character
                if nx < len(name) && name[nx] == c {
                    px++
                    nx++
                    continue
                }
            case '?': // single-character wildcard
                if nx < len(name) {
                    px++
                    nx++
                    continue
                }
            case '*': // zero-or-more-character wildcard
                // Try to match at nx, nx+1, and so on.
                for ; nx <= len(name); nx++ {
                    if match(pattern[px+1:], name[nx:]) {
                        return true
                    }
                }
            }
        }
        // Mismatch.
        return false
    }
    // Matched all of pattern to all of name. Success.
    return true
}

If there are e stars that can each potentially end their matches at n positions in the string, that gives n^e possibilities to explore, leading to the exponential run times observed earlier. However, most of these possibilities are not worth exploring. Because * is the only variable-sized wildcard in the pattern syntax and therefore the only source of possible backtracking, there’s an even easier implementation: don’t backtrack to an earlier star.

Consider the pattern a*bx*cy*d. If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a*bx*cy*d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.”

We can implement this algorithm by replacing the handling of the star wildcard in our Go program:

func match(pattern, name string) bool {
    px := 0
    nx := 0
    nextPx := 0
    nextNx := 0
    for px < len(pattern) || nx < len(name) {
        if px < len(pattern) {
            c := pattern[px]
            switch c {
            default: // ordinary character
                if nx < len(name) && name[nx] == c {
                    px++
                    nx++
                    continue
                }
            case '?': // single-character wildcard
                if nx < len(name) {
                    px++
                    nx++
                    continue
                }
            case '*': // zero-or-more-character wildcard
                // Try to match at nx.
                // If that doesn't work out,
                // restart at nx+1 next.
                nextPx = px
                nextNx = nx + 1
                px++
                continue
            }
        }
        // Mismatch. Maybe restart.
        if 0 < nextNx && nextNx <= len(name) {
            px = nextPx
            nx = nextNx
            continue
        }
        return false
    }
    // Matched all of pattern to all of name. Success.
    return true
}

Each time the code encounters a star, it implements the repeated trials needed for that star by recording in nextPx, nextNx where to restart the search if the current match fails. Each subsequent star encountered overwrites the restart information for the previous star, in effect locking in the choice made for the previous star. If you’d like to experiment, I’ve posted both of these programs and a test harness.

An alternate implementation of the algorithm would be to split the pattern on stars and then consider each of the star-separated subpatterns in turn, special-casing the first subpattern and the last, which must be anchored at the start and end of the name, respectively. Go’s src/path/filepath/match.go is an example of this implementation.

Go’s filepath.Match (used by filepath.Glob), glibc’s glob, and vsftpd’s pattern matcher all use this algorithm.

A more straightforward approach is to translate the glob pattern to a regular expression and then invoke a linear-time regular expression match. Plan 9’s ftpd does this, as does the ls | grep example above. (Python also does this, but then it runs the regular expression with an exponential-time matching engine.)

I have not looked at the other linear-time implementations to see what they do, but I expect they all use one of these two approaches.

Additional Reading

This post is an elaboration of an informal 2012 Google+ post showing that most shells used exponential-time glob expansion. At the time, Tom Duff, the author of Plan 9’s rc shell, commented that, “I can confirm that rc gets it wrong. My excuse, feeble as it is, is that doing it that way meant that the code took 10 minutes to write, but it took 20 years for someone to notice the problem. (That’s 10 ‘programmer minutes’, i.e. less than a day.)” I agree that’s a reasonable decision for a shell. In contrast, a language library routine, not to mention a network server, today needs to be robust against worst-case inputs that might be controlled by remote attackers, but nearly all of the code in question predates that kind of concern. I didn’t realize the connection to FTP servers until I started doing additional research for this post and came across a reference to CVE-2010-2632 in FreeBSD’s glob implementation.

Dave Presotto, the author of Plan 9’s ftpd, avoided rc’s glob implementation not because of the algorithmic complexity but to make sure that long strings were handled safely (using a Plan 9 library for handling long strings in C). He wrote this comment at the top of Plan 9’s /sys/src/cmd/ip/glob.c, which converts glob expressions into regular expressions:

/*
 *  I wrote this glob so that there would be no limit
 *  on element or path size.  The one in rc is probably
 *  better, certainly faster. - presotto
 */

As it turns out, this is untrue: the one in rc is certainly slower, at least in terms of worst-case asymptotics.

If you liked this post, you may also like to browse Nelson Elhage’s Accidentally Quadratic collection. (Of course, here the glob pattern matching is accidentally exponential.)

Updates, as of April 28, 2017.

NetBSD has an updated glob pending for the next release.

Perl has an updated glob pending for the next release.

Pure-FTPd 1.0.46 has added a check that patterns must not have more than three stars.

Thanks to js2 on Hacker News for pointing out that Python translates globs to regular expressions.

My Go Resolutions for 2017

2017-01-18T09:00:00-05:00

’Tis the season for resolutions, and I thought it would make sense to write a little about what I hope to work on this year as far as Go is concerned.

My goal every year is to help Go developers. I want to make sure that the work we do on the Go team has a significant, positive impact on Go developers. That may sound obvious, but there are a variety of common ways to fail to achieve that: for example, spending too much time cleaning up or optimizing code that doesn’t need it; responding only to the most common or recent complaints or requests; or focusing too much on short-term improvements. It’s important to step back and make sure we’re focusing our development work where it does the most good.

This post outlines a few of my own major focuses for this year. This is only my personal list, not the Go team’s list.

One reason for posting this is to gather feedback. If these spark any ideas or suggestions of your own, please feel free to comment below or on the linked GitHub issues.

Another reason is to make clear that I’m aware of these issues as important. I think too often people interpret lack of action by the Go team as a signal that we think everything is perfect, when instead there is simply other, higher priority work to do first.

Type aliases

There is a recurring problem with moving types from one package to another during large codebase refactorings. We tried to solve it last year with general aliases, which didn’t work for at least two reasons: we didn’t explain the change well enough, and we didn’t deliver it on time, so it wasn’t ready for Go 1.8. Learning from that experience, I gave a talk and wrote an article about the underlying problem, and that started a productive discussion on the Go issue tracker about the solution space. It looks like more limited type aliases are the right next step. I want to make sure those land smoothly in Go 1.9. #18130.

Package management

I designed the Go support for downloading published packages (“goinstall”, which became “go get”) in February 2010. A lot has happened since then. In particular, other language ecosystems have really raised the bar for what people expect from package management, and the open source world has mostly agreed on semantic versioning, which provides a useful base for inferring version compatibility. Go needs to do better here, and a group of contributors have been working on a solution. I want to make sure these ideas are integrated well into the standard Go toolchain and to make package management a reason that people love Go.

Build improvements

There are a handful of shortcomings in the design of the go command’s build system that are overdue to be fixed. Here are three representative examples that I intend to address with a bit of a redesign of the internals of the go command.

Builds can be too slow, because the go command doesn’t cache build results as aggressively as it should. Many people don’t realize that go install saves its work while go build does not, and then they run repeated go build commands that are slow because the later builds do more work than they should need to. The same for repeated go test without go test -i when dependencies are modified. All builds should be as incremental as possible. #4719.

Test results should be cached too: if none of the inputs to a test have changed, then usually there is no need to rerun the test. This will make it very cheap to run “all tests” when little or nothing has changed. #11193.

Work outside GOPATH should be supported nearly as well as work inside GOPATH. In particular, it should be possible to git clone a repo, cd into it, and run go commands and have them work fine. Package management only makes that more important: you’ll need to be able to work on different versions of a package (say, v1 and v2) without having entirely separate GOPATHs for them. #17271.

Code corpus

I think it helped to have concrete examples from real projects in the talk and article I prepared about codebase refactoring (see above). We’ve also defined that additions to vet must target problems that happen frequently in real programs. I’d like to see that kind of analysis of actual practice—examining the effects on and possible improvements to real programs—become a standard way we discuss and evaluate changes to Go.

Right now there’s not an agreed-upon representative corpus of code to use for those analyses: everyone must first create their own, which is too much work. I’d like to put together a single, self-contained Git repo people can check out that contains our official baseline corpus for those analyses. A possible starting point could be the top 100 Go language repos on GitHub by stars or forks or both.

Automatic vet

The Go distribution ships with this powerful tool, go vet, that points out correctness bugs. We have a high bar for checks, so that when vet speaks, you should listen. But everyone has to remember to run it. It would be better if you didn’t have to remember. In particular, I think we could probably run vet in parallel with the final compile and link of the test binary during go test without slowing the compile-edit-test cycle at all. If we can do that, and if we limit the enabled vet checks to a subset that is essentially 100% accurate, we can make passing vet a precondition for running a test at all. Then developers don’t need to remember to run go vet. They run go test, and once in a while vet speaks up with something important and avoids a debugging session. #18084, #18085.

Errors & best practices

Part of the intended contract for error reporting in Go is that functions include relevant available context, including the operation being attempted (such as the function name and its arguments). For example, this program:

err := os.Remove("/tmp/nonexist")
fmt.Println(err)

prints this output:

remove /tmp/nonexist: no such file or directory

Not enough Go code adds context like os.Remove does. Too much code does only

if err != nil {
    return err
}

all the way up the call stack, discarding useful context that should be reported (like remove /tmp/nonexist: above). I would like to try to understand whether our expectations for including context are wrong, or if there is something we can do to make it easier to write code that returns better errors.

There are also various discussions in the community about agreed-upon interfaces for stripping error context. I would like to try to understand when that makes sense and whether we should adopt an official recommendation.

Context & best practices

We added the new context package in Go 1.7 for holding request-scoped information like timeouts, cancellation state, and credentials. An individual context is immutable (like an individual string or int): it is only possible to derive a new, updated context and pass that context explicitly further down the call stack or (less commonly) back up to the caller. The context is now carried through APIs such as database/sql and net/http, mainly so that those can stop processing a request when the caller is no longer interested in the result. Timeout information is appropriate to carry in a context, but—to use a real example we removed—database options are not, because they are unlikely to apply equally well to all possible database operations carried out during a request. What about the current clock source, or logging sink? Is either of those appropriate to store in a context? I would like to try to understand and characterize the criteria for what is and is not an appropriate use of context.

Memory model

Go’s memory model is intentionally low-key, making few promises to users, compared to other languages. In fact it starts by discouraging people from reading the rest of the document. At the same time, it demands more of the compiler than other languages: in particular, a race on an integer value is not sufficient license for your program to misbehave in arbitrary ways. But there are some complete gaps, in particular no mention of the sync/atomic package. I think the core compiler and runtime developers all agree that the behavior of those atomics should be roughly the same as C++ seqcst atomics or Java volatiles, but we still need to write that down carefully in the memory model, and probably also in a long blog post. #5045, #7948, #9442.

Immutability

The race detector is one of Go’s most loved features. But not having races would be even better. I would love it if there were some reasonable way to integrate reference immutability into Go, so that programmers can make clear, checked assertions about what can and cannot be written and thereby eliminate certain races at compile time. Go already has one immutable type, string; it would be nice to retroactively define that string is a named type (or type alias) for immutable []byte. I don’t think that will happen this year, but I’d like to understand the solution space better. Javari, Midori, Pony, and Rust have all staked out interesting points in the solution space, and there are plenty of research papers beyond those.

In the long-term, if we could statically eliminate the possibility of races, that would eliminate the need for most of the memory model. That may well be an impossible dream, but again I’d like to understand the solution space better.

Generics

Nothing sparks more heated arguments among Go and non-Go developers than the question of whether Go should have support for generics (or how many years ago that should have happened). I don’t believe the Go team has ever said “Go does not need generics.” What we have said is that there are higher-priority issues facing Go. For example, I believe that better support for package management would have a much larger immediate positive impact on most Go developers than adding generics. But we do certainly understand that for a certain subset of Go use cases, the lack of parametric polymorphism is a significant hindrance.

Personally, I would like to be able to write general channel-processing functions like:

// Join makes all messages received on the input channels
// available for receiving from the returned channel.
func Join(inputs ...<-chan T) <-chan T

// Dup duplicates messages received on c to both c1 and c2.
func Dup(c <-chan T) (c1, c2 <-chan T)

I would also like to be able to write Go support for high-level data processing abstractions, analogous to FlumeJava or C#’s LINQ, in a way that catches type errors at compile time instead of at run time. There are also any number of data structures or generic algorithms that might be written, but I personally find these broader applications more compelling.

We’ve struggled off and on for years to find the right way to add generics to Go. At least a few of the past proposals got hung up on trying to design something that provided both general parametric polymorphism (like chan T) and also a unification of string and []byte. If the latter is handled by parameterization over immutability, as described in the previous section, then maybe that simplifies the demands on a design for generics.

When I first started thinking about generics for Go in 2008, the main examples to learn from were C#, Java, Haskell, and ML. None of the approaches in those languages seemed like a perfect fit for Go. Today, there are newer attempts to learn from as well, including Dart, Midori, Rust, and Swift.

It’s been a few years since we ventured out and explored the design space. It is probably time to look around again, especially in light of the insight about mutability and the additional examples set by newer languages. I don’t think generics will happen this year, but I’d like to be able to say I understand the solution space better.

Go and Dogma

2017-01-09T09:00:00-05:00

[Cross-posting from last year’s Go contributors AMA on Reddit, because it’s still important to remember.]

One of the perks of working on Go these past years has been the chance to have many great discussions with other language designers and implementers, for example about how well various design decisions worked out or the common problems of implementing what look like very different languages (for example both Go and Haskell need some kind of “green threads”, so there are more shared runtime challenges than you might expect). In one such conversation, when I was talking to a group of early Lisp hackers, one of them pointed out that these discussions are basically never dogmatic. Designers and implementers remember working through the good arguments on both sides of a particular decision, and they’re often eager to hear about someone else’s experience with what happens when you make that decision differently. Contrast that kind of discussion with the heated arguments or overly zealous statements you sometimes see from users of the same languages. There’s a real disconnect, possibly because the users don’t have the experience of weighing the arguments on both sides and don’t realize how easily a particular decision might have gone the other way.

Language design and implementation is engineering. We make decisions using evaluations of costs and benefits or, if we must, using predictions of those based on past experience. I think we have an important responsibility to explain both sides of a particular decision, to make clear that the arguments for an alternate decision are actually good ones that we weighed and balanced, and to avoid the suggestion that particular design decisions approach dogma. I hope the Reddit AMA as well as discussion on golang-nuts or StackOverflow or the Go Forum or at conferences help with that.

But we need help from everyone. Remember that none of the decisions in Go are infallible; they’re just our best attempts at the time we made them, not wisdom received on stone tablets. If someone asks why Go does X instead of Y, please try to present the engineering reasons fairly, including for Y, and avoid argument solely by appeal to authority. It’s too easy to fall into the “well that’s just not how it’s done here” trap. And now that I know about and watch for that trap, I see it in nearly every technical community, although some more than others.

Lock-Free Bugs

2017-01-04T00:00:00-05:00

[I wrote this post in mid-2014 for debuggers.co, which seems to have gone at least partly defunct, so I am reproducing it here. That site collected answers from programmers to the prompt “What’s the most interesting bug you’ve encountered?”]

To me, the most interesting bugs are the ones that reveal fundamental, subtle misunderstandings about the way a program works. A good bug is like a good science experiment: through it, you learn something unexpected about the virtual world you are exploring.

About ten years ago I was working on a networked server that used threads, coordinating with locks and condition variables. This server was part of Plan 9 and was written in C. Occasionally it would crash inside malloc, which usually means some kind of memory corruption due to a write-after-free error. One day, while benchmarking with the bulk of the server disabled, I was lucky enough to have the crash happen reproducibly. The server being mostly disabled gave me a head start in isolating the bug, and the reproducibility made it possible to cut code out, piece by piece, until one section was very clearly implicated.

The code in question was cleaning up after a client that had recently disconnected. In the server, there is a per-client data structure shared by two threads: the thread R reads from the client connection, and the thread W writes to it. R notices the disconnect as an EOF from a read, notifies W, waits for an acknowledgement from W, and then frees the per-client structure.

To acknowledge the disconnect, W ran code like:

qlock(&conn->lk);
conn->writer_done = 1;
qsignal(&conn->writer_ack);
qunlock(&conn->lk);
thread_exit();

And to wait for the acknowledgement, R ran code like:

qlock(&conn->lk);
while(!conn->writer_done)
    qwait(&conn->writer_ack);

// The writer is done, and so are we:
// free the connection.
free(conn);

This is a standard locks and condition variables piece of code: qwait is defined to release the lock (here, conn->lk), wait, and then reacquire the lock before returning. Once R observes that writer_done is set, R knows that W is gone, so R can free the per-connection data structure.

R does not call qunlock(&conn->lk). My reasoning was that calling qunlock before free sends mixed messages: qunlock suggests coordination with another thread using conn, but free is only safe if no other thread is using conn. W was the other thread, and W is gone. But somehow, when I added qunlock(&conn->lk) before free(conn), the crashes stopped. Why?

To answer that, we have to look at how locks are implemented.

Conceptually, the core of a lock is a variable with two markings unlocked and locked. To acquire a lock, a thread checks that the core is marked unlocked and, if so, marks it locked, in one atomic operation. Because the operation is atomic, if two (or more) threads are attempting to acquire the lock, only one can succeed. That thread—let’s call it thread A—now holds the lock. Another thread vying for the lock—thread B—sees the core is marked locked and must now decide what to do.

The first, simplest approach, is to try again, and again, and again. Eventually thread A will release the lock (by marking the core unlocked), at which point thread B’s atomic operation will succeed. This approach is called spinning, and a lock using this approach is called a spin lock.

A simple spin lock implementation looks like:

struct SpinLock
{
    int bit;
};

void
spinlock(SpinLock *lk)
{
    for(;;) {
        if(atomic_cmp_and_set(&lk->bit, 0, 1))
            return;
    }
}

void
spinunlock(SpinLock *lk)
{
    atomic_set(&lk->bit, 0);
}

The spin lock’s core is the bit field. It is 0 or 1 to indicate unlocked or locked. The atomic_cmp_and_set and atomic_set use special machine instructions to manipulate lk->bit atomically.

Spinning only makes sense if the lock is never held for very long, so that B’s spin loop only executes a small number of times. If the lock can be held for longer periods of time, spinning while it is held wastes CPU and can interact badly with the operating system scheduler.

The second, more general approach is to maintain a queue of threads interested in acquiring the lock. In this approach, when thread B finds the lock already held, it adds itself to the queue and uses an operating system primitive to go to sleep. When thread A eventually releases the lock, it checks the queue, finds B, and uses an operating system primitive to wake B. This approach is called queueing, and a lock using this approach is called a queue lock. Queueing is more efficient than spinning when the lock may be held for a long time.

The queue lock’s queue needs its own lock, almost always a spin lock. In the library I was using, qlock and qunlock were implemented as:

struct QLock
{
    SpinLock spin;
    Thread *owner;
    ThreadQueue queue;
};

void
qlock(QLock *lk)
{
    spinlock(&lk->spin);
    if(lk->owner == nil) {
        lk->owner = current_thread();
        spinunlock(&lk->spin);
        return;
    }
    push(&lk->queue, current_thread());
    spinunlock(&lk->spin);
    os_sleep();
}

void
qunlock(QLock *lk)
{
    Thread *t;

    spinlock(&lk->spin);
    t = pop(&lk->queue);
    lk->owner = t;
    if(t != nil)
        os_wakeup(t);
    spinunlock(&lk->spin);
}

The queue lock’s core is the owner field. If owner is nil, the lock is unlocked; otherwise owner records the thread that holds the lock. The operations on lk->owner are made atomic by holding the spin lock lk->spin.

Back to the bug.

The locks in the crashing code were queue locks. The acknowledgement protocol between R and W sets up a race between W’s call to qunlock and R’s call to qlock (either the explicit call in the code or the implicit call inside qwait). Which call happens first?

If W’s qunlock happens first, then R’s qlock finds the lock unlocked, locks it, and everything proceeds uneventfully.

If R’s qlock happens first, it finds the lock held by W, so it adds R to the queue and puts R to sleep. Then W’s qunlock executes. It sets the owner to R, wakes up R, and unlocks the spin lock. By the time W unlocks the spin lock, R may have already started running, and R may have already called free(conn). The spinunlock’s atomic_set writes a zero to conn->lk.spin.bit. That’s the write-after-free, and if the memory allocator didn’t want a zero there, the zero may cause a crash (or a memory leak, or some other behavior).

But is the server code wrong or is qunlock wrong?

The fundamental misunderstanding here is in the definition of the queue lock API. Is a queue lock required to be unlocked before being freed? Or is a queue lock required to support being freed while locked? I had written the queue lock routines as part of a cross-platform library mimicking Plan 9’s, and this question had not occurred to me when I was writing qunlock.

One one hand, if the queue lock must be freed only when unlocked, then qunlock’s implementation is correct and the server must change. If R calls qunlock before free, then R’s qunlock’s spinlock must wait for W’s qunlock’s spinunlock, so that W will really be gone by the time R calls free.

On the other hand, if the queue lock can be freed while locked, then the server is correct and qunlock must change: the os_wakeup gives up control of lk and must be delayed until after the spinunlock.

The Plan 9 documentation for queue locks does not address the question directly, but the implementation was such that freeing locked queue locks was harmless, and since I was using my library to run unmodified Plan 9 software, I changed the lock implementation to call os_wakeup after spinunlock. Two years later, while fixing a different bug, I defensively changed the server implementation to call qunlock too, just in case. The definition of the POSIX pthread_mutex_destroy function gives a different answer to the same design question: “It is safe to destroy an initialised mutex that is unlocked. Attempting to destroy a locked mutex results in undefined behaviour.”

What did we learn?

The rationale I gave for not calling qunlock before free made an implicit assumption that the two were independent. After looking inside an implementation, we can see why the two are intertwined and why an API might specify, as POSIX does, that you must unlock a lock before destroying it. This is an example of implementation concerns influencing an API, creating a “leaky abstraction.”

What makes this bug interesting is that it was caused by a complex interaction between manual memory management and concurrency. Obviously a program must stop using a resource before freeing it. But a concurrent program must stop all threads from using a resource before freeing it. On a good day, that can require bookkeeping or careful coordination to track which threads are still using the resource. On a bad day, that can require reading the lock implementation to understand the exact order of operations carried out in the different threads.

In the modern computing world of clients and servers and clouds, concurrency is a fundamental concern for most programs. In that world, choosing garbage collection instead of manual memory management eliminates a source of leaky abstractions and makes programs simpler and easier to reason about.

I started the post by saying that good bugs help you learn something unexpected about the virtual world you are exploring. This was especially true for Maurice Wilkes and his team, who built EDSAC, the first practical stored-program computer. The first program they ran on EDSAC (printing square numbers) ran correctly, but the second did not: the log for May 7, 1949 reads “Table of primes attempted - programme incorrect.” That was a Saturday, making this the first weekend spent working on a buggy program.

What did they learn? Wilkes later recalled,

“By June 1949, people had begun to realize that it was not so easy to get a program right as had at one time appeared. … It was on one of my journeys between the EDSAC room and the punching equipment that the realization came over me with full force that a good part of the remainder of my life was going to be spent in finding errors in my own programs.” (Wilkes, p. 145)

For more about this early history, see Brian Hayes’s “The Discovery of Debugging” and Martin Campbell-Kelly’s “The Airy Tape: An Early Chapter in the History of Debugging.”

Version SAT

2016-12-13T10:00:00-05:00

Dependency hell is NP-complete. But maybe we can climb out.

The package version selection problem is to find a set of dependencies that can be used to build a top-level package P that is complete (all dependencies satisfied) and compatible (no two incompatible packages are selected). There may be no such set, because of the diamond dependency problem: perhaps A needs B and C; B needs D version 1, not 2; and C needs D version 2, not 1. In this case, assuming it’s not possible to choose both versions of D, there is no way to build A.

A package manager needs an algorithm to select package versions: when you run apt-get install perl, it may assume you mean the latest version of Perl, but then it has to find a way to satisfy Perl’s transitive dependencies, or else to print an understandable explanation of why Perl can’t be installed. You might reasonably wonder: how expensive is it to solve this problem, in the worst case? You probably don’t want your package manager to take hours or days or years to decide whether it can install Perl.

Unfortunately, the version selection problem is NP-complete, which means that we’re exceedingly unlikely to find an algorithm guaranteed to run quickly on every input. This post gives a proof of NP-completeness for version selection, looks at how existing package managers cope, and briefly discusses possible approaches to avoid an NP-complete task.

Proof of NP-Completeness

To consider NP-completeness, we need to shift from our modern world of algorithms with rich outputs to the limited world of complexity theory, where algorithms have one boolean output: yes or no. In this world of complexity theory, we’ll define the VERSION problem (they’re always all caps) to ask whether there is a valid version selection. This boolean VERSION problem is only half of our original problem, and we can prove that it’s NP-complete. To do so, we need to prove two separate facts: that VERSION is in NP and that VERSION is NP-hard.

A problem is in NP if every “yes” answer has an easily-checked polynomial-size explanation.

VERSION is in NP, because any “yes” answer can be explained by listing the selected package versions. This list is no bigger than the input and can be checked for correctness in time no worse than quadratic in the input (probably linear, depending on details of the computing model).

A problem is NP-hard if an efficient solution for that problem can be adapted into an efficient solution to every other problem in NP. That’s a pretty tall order, but it is enough for us to show how to adapt an efficient solution for VERSION into an efficient solution for one other NP-hard problem (call it HARD) and then rely on the fact that someone else has proven that an efficient solution for HARD can be adapted into an efficient solution for every other problem in NP.

A useful example of an NP-complete (in NP and NP-hard) problem is 3-SAT. In 3-SAT, the input is a boolean formula over some number of boolean variables, constrained to be a conjunction (an AND) of some number of disjunctions (ORs) of three literals each, where a literal is a variable or its negation. For example, here is an input for 3-SAT (∧ means AND, ∨ means OR, and ¬ means NOT):

(¬ x₁ ∨ ¬ x₂ ∨ ¬ x₃) ∧ (¬ x₂ ∨ ¬ x₃ ∨ ¬ x₄) ∧ (¬ x₂ ∨ ¬ x₂ ∨ x₃) ∧ (x₂ ∨ x₂ ∨ x₂)

It is satisfiable by exactly one assignment to the variables—x₁ = 0, x₂ = 1, x₃ = 1, x₄ = 0—so the answer is yes.

If we extend it to add one more clause,

(¬ x₁ ∨ ¬ x₂ ∨ ¬ x₃) ∧ (¬ x₂ ∨ ¬ x₃ ∨ ¬ x₄) ∧ (¬ x₂ ∨ ¬ x₂ ∨ x₃) ∧ (x₂ ∨ x₂ ∨ x₂) ∧ (x₁ ∨ ¬ x₂ ∨ x₄)

then it is unsatisfiable by any assignment to the variables, so the answer is no.

The general form of a 3-SAT instance is a formula F that is the conjunction of clauses C₁ through C_n over variables V₁ through V_m, where each C_i is a disjunction of three literals, each of the form x_j or ¬ x_j for some variable x_j . Duplicate literals in a clause are allowed, as in (¬ x₂ ∨ ¬ x₂ ∨ x₃) and (x₂ ∨ x₂ ∨ x₂) above.

We can convert any 3-SAT instance to a VERSION instance with the same answer. About the package manager we will assume only that:

A package can list zero or more packages or specific package versions as dependencies.
To install a package, all its dependencies must be installed.
Each version of a package can have different dependencies.
Two different versions of a package cannot be installed simultaneously.

We’ll abbreviate package P version V as P:V (now using fixed-width font for packages to distinguish from the standard math italics for formulas). A dependency on P:V must be satisfied by version V exactly, not V-1 and not V+1.

Given a 3-SAT formula, we can create a package F representing the whole formula, packages C1, C2, …, Cn representing each clause, and packages X1, X2, …, Xm representing each variable.

Each package Xj has two versions Xj:0 and Xj:1. As assumed above, Xj:0 and Xj:1 conflict and cannot both be installed. Xj:1 being installed corresponds to x_j = 1 in the original formula.

Package Ci has three versions numbered 0, 1, 2, each of which depends on a literal from the corresponding clause. For example, if C₅ is (x₁ ∨ ¬ x₂ ∨ x₄), then C5:0 depends on X1:1, C5:1 depends on X2:0, and C5:2 depends on X4:1. Ci:k being installed corresponds to C_i’s k’th literal being true (and therefore C_i being true) in the original formula.

Package F depends on C1, C2, …, Cn. F being installed implies that all the Ci are installed, which corresponds to all the C_i being true and therefore to F being true.

If the package manager can find a way to install package F, then a satisfying assignment for the original formula can be read out from the install status of Xj:1 for each variable x_j. Similarly, if the formula is satisfiable, the satisfying assignment gives one way the package manager could successfully install F. Therefore, we’ve converted the 3-SAT instance into a corresponding VERSION instance with the same answer, which establishes that 3-SAT can be solved using VERSION, so VERSION is NP-hard.

Since VERSION is in NP and is NP-hard, VERSION is NP-complete.

Implementations

The assumptions above are quite minimal: packages have a list of dependencies, a package’s dependencies can change with its own version to version, a package’s dependencies can be restricted to specific versions of those dependencies, and it is possible for two versions of a package to conflict with each other. That may be the bare minimum for a package manager to be useful. Some package managers might not allow a dependency to list a specific version, instead requiring a range, but we can easily change the version requirements 0 and 1 to ≤ 0 and ≥ 1. Some package managers might not assume that different versions of a package conflict by default, but it must be at least possible to specify such a conflict: there can’t be two /bin/bash on a Unix system, or two definitions of printf built into a C program.

The assumptions are true of every package manager I have looked at: Debian’s APT, RedHat’s RPM, Rust’s Cargo, Node’s npmjs, Java’s Maven, Haskell’s Cabal, and more. The implication is that these package managers faces an NP-complete task. Each must choose between possibly taking a very long time to decide on an installation strategy or possibly reporting an installable package as uninstallable. (Of course, a given implementation may inadvertently do both.)

Knuth writes in Volume 4, Fascicle 6:

The story of satisfiability is the tale of a triumph of software engineering, blended with rich doses of beautiful mathematics. Thanks to elegant new data structures and other techniques, modern SAT solvers are able to deal routinely with practical problems that involve many thousands of variables, although such problems were regarded as hopeless just a few years ago.

In practice, it does seem that modern package managers are moving toward using SAT solvers:

0install started with heuristics but found it necessary to switch to a SAT solver.

Chef, a systems integration framework, uses the dep-selector Ruby bindings for the Gecode constraint solver.

Dart’s pub includes a backtracking solver that often takes a long time.

Debian’s apt-get uses heuristics by default but can invoke a SAT solver and can take user preferences into account. The Debian Quality Assurance team also runs a solver to identify uninstallable packages in their repos.

Eclipse uses the sat4j SAT solver to manage installation of its plugins.

Fedora’s DNF (“Dandified yum”) uses a SAT solver in an experimental mode.

FreeBSD’s pkg, also used by DragonflyBSD, uses the picosat SAT solver.

OCaml’s OPAM can invoke a SAT solver locally or remotely over a network. Like with Debian’s apt-get, OPAM’s solver can take user preferences into account, and the OPAM repos are scanned for uninstallable packages.

OpenSUSE’s package manager uses libsolv, “a free package dependency solver using a satisfiability algorithm.” There is also OpenSUSE’s zypper, which uses its own libzypp SAT solver.

Python’s Anaconda uses a SAT solver but can take a long time.

Rust’s Cargo uses a basic backtracking solver. It also allows multiple versions of a crate to be linked into the final binary.

Solaris’s pkg, also used by Illumos and sometimes known as IPS, uses the minisat SAT solver.

Swift’s package manager uses a basic backtracking solver.

[I would like to add more package managers here. If you know details for one (or something here is wrong), please email me or send a tweet. Thanks.]

Alternatives?

How should we react to the fact that package version selection is NP-complete? One reaction is to embrace the complexity and be thankful that SAT solvers are as good as they are. Another reaction is to ask whether this can possibly be a good idea. Maybe we should not be building tools that require solving this problem. Maybe something has gone wrong in the way we develop software.

If package version selection is NP-complete, that means the search space of possible package combinations is too large and intricate for efficient systematic analysis; what about efficient systematic testing? If a search finds a conflict-free combination, why should we believe the combination will work? The absence of a version conflict may indicate only that the combination is untested. If a search doesn’t find a conflict-free combination, how can that failure be explained to a developer in a way that makes it clear what to do next? Software is hard enough to get right without admitting NP-complete problems into our software configuration decisions. Let’s reexamine how we got here and how we might escape.

The proof above depends on these of assumptions, copied from above:

A package can list zero or more packages or specific package versions as dependencies.
To install a package, all its dependencies must be installed.
Each version of a package can have different dependencies.
Two different versions of a package cannot be installed simultaneously.

The conventional wisdom, as I suggested above, is that these are roughly the “the bare minimum for a package manager to be useful,” but maybe we can find a way to reduce them after all.

One way to avoid NP-completeness is to attack assumption 1: what if, instead of allowing a dependency to list specific package versions, a dependency can only specify a minimum version? Then there is a trivial algorithm for finding the packages to use: start with the newest version of what you want to install, and then get the newest version of all its dependencies, recursively. In the original diamond dependency at the beginning of this article, A needs B and C, and B and C need different versions of D. If B needs D 1.5 and C needs D 1.6, the build can use D 1.6 for both. If B doesn’t work with D 1.6, then either the version of B we’re considering is buggy or D 1.6 is buggy. The buggy version should be removed from circulation entirely, and then a new released version should fix the problem. Adding a conflict to the dependency graph instead is like documenting a bug instead of fixing it.

Another way to avoid NP-completeness is to attack assumption 4: what if two different versions of a package could be installed simultaneously? Then almost any search algorithm will find a combination of packages to build the program; it just might not be the smallest possible combination (that’s still NP-complete). If B needs D 1.5 and C needs D 2.2, the build can include both packages in the final binary, treating them as distinct packages. I mentioned above that there can’t be two definitions of printf built into a C program, but languages with explicit module systems should have no problem including separate copies of D (under different fully-qualified names) into a program.

Another way to avoid NP-completeness is to combine the previous two. As the examples already hint at, if packages follow semantic versioning, a package manager might automatically use the newest version of a dependency within a major version but then treat different major versions as different packages.

One rationale for such restrictions is that developers are likely not thinking about the entire space of all possible package combinations when building or testing software. It would help for the developers and their tools to agree about how software is built. If any of these approaches can be made to work in practice, it could go a long way toward simplifying the operation and understandability of language package managers.

Related Work

Proofs that Debian and RedHat package installation are both NP-complete are given in “EDOS deliverable WP2-D2.1: Report on Formal Management of Software Dependencies” (2005), pages 49-50. The difficult step in the reduction of 3-SAT to package installation is how to construct a disjunction. The EDOS proofs encode the disjunction using the package manager’s ability to specify a list of alternatives for a single dependency, either directly (in Debian) or using “provides” directives (in RedHat). For example, these systems allow a pseudo-package text-editor to be defined that is considered installed when any of the real packages ed, vi, or acme is installed.

The dependency specifications for a language package manager like Rust’s Cargo are dramatically simpler than those for Debian and RedHat, and so the EDOS proofs do not apply. One might therefore hope that language package managers face an easier (not NP-complete) job. The new proof above dashes that hope. (One way to view the proof above is that it simulates the “provides” directive in the last example by defining a text-editor package with three versions, one of which depends on ed, one on vi, and one on acme.)

By encoding the disjunction in the changing dependencies of different versions of a package, the new proof works without modification for both Debian’s and RedHat’s package managers but also applies to essentially any foreseeable operating system or language package manager. I suspect that most language package manager authors assumed the problem they faced was NP-complete, but I’ve been unable to find prior written proofs of that fact.

A few dependency systems use constraint solvers instead of SAT solvers, but the underlying problem is still NP-complete.

In 2008, Daniel Burrows wrote a blog post about using dpkg to solve Sudoku problems.

Thanks to Sam Boyer for pointing me at the EDOS report and for his excellent overview of package management.

Roberto Di Cosmo has written a number of followups to the EDOS report, listed here, in particular, “Dependency solving: a separate concern in component evolution management,” which contains an updated proof. That line of research applies SAT solvers but also works to take user preferences into account.

Another related line of work is “OPIUM: Optimal Package Install/Uninstall Manager” by Tucker et al., ICSE 2007. OPIUM was the starting point for 0install’s solver.

Jaroslav Tulach discovered the same proof as above in 2009. Thanks to HN reader edwintorok for the link.

The discussion of Tulach’s proof on LtU mentions Daniel Burrows’s 2005 paper “Modelling and Resolving Software Dependencies,” but that paper’s proof is more like the EDOS proof than Tulach’s proof / the proof above.

Many readers sent additional links to references and to package managers with SAT solvers. Thanks to all.

Hacking the OS X Kernel for Fun and Profiles

2013-08-13T11:00:00-04:00

My last post described how user-level CPU profilers work, and specifically how Google’s pprof profiler gathers its CPU profiles with the help of the operating system. The specific feature needed from the operating system is the profiling timer provided by setitimer(2) and the SIGPROF signals that it delivers.

If the operating system’s implementation of that feature doesn’t work, then the profiler doesn’t work. This post looks at a common bug in Unix implementations of profiling signals and the fix for OS X, applied by editing the OS X kernel binary.

If you haven’t read “How to Build a User-Level CPU Profiler,’’ you might want to start there.

Unix and Signals and Threads

My earlier post referred to profiling programs, without mention of processes or threads. Unix in general and SIGPROF in particular predate the idea of threads. SIGPROF originated in the 4.2BSD release of Berkeley Unix, published in 1983. In Unix at the time, a process was a single thread of execution.

Threads did not come easily to Unix. Early implementations were slow and buggy and best avoided. Each of the popular Unix variants added thread support independently, with many shared mistakes.

Even before we get to implementation, many of the original Unix APIs are incompatible with the idea of threads. Multithreaded processes allow multiple threads of execution in a single process address space. Unix maintains much per-process state, and the kernel authors must decide whether each piece of state should remain per-process or change to be per-thread.

For example, the single process stack must be split into per-thread stacks: it is impossible for independently executing threads to be running on a single stack. Because there are many threads, thread stacks tend to be smaller than the one big process stack that non-threaded Unix programs had. As a result, it can be important to define a separate stack for running signal handlers. That setting is per-thread, for the same reason that ordinary stacks are per-thread. But the choice of handler is per-process.

File descriptors are per-process, but then one thread might open a file moments before another thread forks and execs a new program. In order for the open file not to be inherited by the new program, we must introduce a new variant of open(2) that can open a file descriptor atomically marked “close on exec.’’ And not just open: every system call that creates a new file descriptor needs a variant that creates the file descriptor “close on exec.’’

Memory is per-process, so malloc must use a lock to serialize access by independent threads. But again, one thread might acquire the malloc lock moments before another thread forks and execs a new program. The fork makes a new copy of the current process memory, including the locked malloc lock, and that copy will never see the unlock by the thread in the original program. So the child of fork can no longer use malloc without occasional deadlocks.

That’s just the tip of the iceberg. There are a lot of changes to make, and it’s easy to miss one.

Profiling Signals

Here’s a thread-related change that is easy to miss.

The goal of the profiling signal is to enable user-level profiling. The signal is sent in response to a program using up a certain amount of CPU time. More specifically, in a multithreaded kernel, the profiling signal is sent when the hardware timer interrupts a thread and the timer interrupt handler finds that the execution of that thread has caused the thread’s process’s profiling timer to expire. In order to profile the code whose execution triggered the timer, the profiling signal must be sent to the thread that is running. If the signal is sent to a thread that is not running, the profile will record idleness such as being blocked on I/O or sleeping as execution and will be neither accurate nor useful.

Modern Unix kernels support sending a signal to a process, in which case it can be delivered to an arbitrary thread, or to a specific thread. Kill(2) sends a signal to a process, and pthread_kill(2) sends a signal to a specific thread within a process.

Before Unix had threads, the code that delivered a profiling signal looked like psignal(p, SIGPROF), where psignal is a clearer name for the implementation of the kill(2) system call and p is the process with the timer that just expired. If there is just one thread per process, delivering the signal to the process cannot possibly deliver it to the wrong thread.

In multithreaded programs, the SIGPROF must be delivered to the running thread: the kernel must call the internal equivalent of pthread_kill(2), not kill(2).

FreeBSD and Linux deliver profiling signals correctly. Empirically, NetBSD, OpenBSD, and OS X do not. (Here is a simple C test program.) Without correct delivery of profiling signals, it is impossible to build a correct profiler.

OS X Signal Delivery

To Apple’s credit, the OS X kernel sources are published and open source, so we can look more closely at the buggy OS X implementation.

The profiling signals are delivered by the function bsd_ast in the file kern_sig.c. Here is the relevant bit of code:

void
bsd_ast(thread_t thread)
{
    proc_t p = current_proc();
    ...
    if (timerisset(&p->p_vtimer_prof.it_value)) {
        uint32_t    microsecs;

        task_vtimer_update(p->task, TASK_VTIMER_PROF, &microsecs);

        if (!itimerdecr(p, &p->p_vtimer_prof, microsecs)) {
            if (timerisset(&p->p_vtimer_prof.it_value))
                task_vtimer_set(p->task, TASK_VTIMER_PROF);
            else
                task_vtimer_clear(p->task, TASK_VTIMER_PROF);

            psignal(p, SIGPROF);
        }
    }
    ...
}

The bsd_ast function is the BSD half of the OS X timer interrupt handler. If profiling is enabled, bsd_ast decrements the timer and sends the signal if the timer expires. The innermost if statement is resetting the the timer state, because setitimer(2) allows both one-shot and periodic timers.

As predicted, the code is sending the profiling signal to the process, not to the current thread. There is a function psignal_uthread defined in the same source file that sends a signal instead to a specific thread. One possible fix is very simple: change psignal to psignal_uthread.

I filed a report about this bug as Apple Bug Report #9177434 in March 2011, but the bug has persisted in subsequent releases of OS X. In my report, I suggested a different fix, inside the implementation of psignal, but changing psignal to psignal_uthread is even simpler. Let’s do that.

Patching the Kernel

It should be possible to rebuild the OS X kernel from the released sources. However, I do not know whether the sources are complete, and I do not know what configuration I need to use to recreate the kernel on my machine. I have no confidence that I’d end up with a kernel appropriate for my computer. Since the fix is so simple, it should be possible to just modify the standard OS X kernel binary directly. That binary lives in /mach_kernel on OS X computers.

If we run gdb on /mach_kernel we can see the compiled machine code for bsd_ast and find the section we care about.

$ gdb /mach_kernel
(gdb) disas bsd_ast
Dump of assembler code for function bsd_ast:
0xffffff8000568a50 <bsd_ast+0>: push   %rbp
0xffffff8000568a51 <bsd_ast+1>: mov    %rsp,%rbp
...
if (timerisset(&p->p_vtimer_prof.it_value))
0xffffff8000568b7b <bsd_ast+299>:       cmpq   $0x0,0x1e0(%r15)
0xffffff8000568b83 <bsd_ast+307>:       jne    0xffffff8000568b8f <bsd_ast+319>
0xffffff8000568b85 <bsd_ast+309>:       cmpl   $0x0,0x1e8(%r15)
0xffffff8000568b8d <bsd_ast+317>:       je     0xffffff8000568b9f <bsd_ast+335>
task_vtimer_set(p->task, TASK_VTIMER_PROF);
0xffffff8000568b8f <bsd_ast+319>:       mov    0x18(%r15),%rdi
0xffffff8000568b93 <bsd_ast+323>:       mov    $0x2,%esi
0xffffff8000568b98 <bsd_ast+328>:       callq  0xffffff80002374f0 <task_vtimer_set>
0xffffff8000568b9d <bsd_ast+333>:       jmp    0xffffff8000568bad <bsd_ast+349>
task_vtimer_clear(p->task, TASK_VTIMER_PROF);
0xffffff8000568b9f <bsd_ast+335>:       mov    0x18(%r15),%rdi
0xffffff8000568ba3 <bsd_ast+339>:       mov    $0x2,%esi
0xffffff8000568ba8 <bsd_ast+344>:       callq  0xffffff8000237660 <task_vtimer_clear>
psignal(p, SIGPROF);
0xffffff8000568bad <bsd_ast+349>:       mov    %r15,%rdi
0xffffff8000568bb0 <bsd_ast+352>:       xor    %esi,%esi
0xffffff8000568bb2 <bsd_ast+354>:       xor    %edx,%edx
0xffffff8000568bb4 <bsd_ast+356>:       xor    %ecx,%ecx
0xffffff8000568bb6 <bsd_ast+358>:       mov    $0x1b,%r8d
0xffffff8000568bbc <bsd_ast+364>:       callq  0xffffff8000567340 <threadsignal+224>
...

I’ve annotated the assembly with the corresponding C code in italics. The final sequence is odd. It should be a call to psignal but instead it is a call to code 224 bytes beyond the start of the threadsignal function. What’s going on is that psignal is a thin wrapper around psignal_internal, and that wrapper has been inlined. Since psignal_internal is a static function, it does not appear in the kernel symbol table, and so gdb doesn’t know its name.

The definitions of psignal and psignal_uthread are:

void
psignal(proc_t p, int signum)
{
    psignal_internal(p, NULL, NULL, 0, signum);
}

static void
psignal_uthread(thread_t thread, int signum)
{
    psignal_internal(PROC_NULL, TASK_NULL, thread, PSIG_THREAD, signum);
}

With the constants expanded, the call we’re seeing is psignal_internal(p, 0, 0, 0, 0x1b) and the call we want to turn it into is psignal_internal(0, 0, thread, 4, 0x1b). All we need to do is prepare the different argument list.

Unfortunately, the thread variable was passed to bsd_ast in a register, and since it is no longer needed where we are in the function, the register has been reused for other purposes: thread is gone.

Fortunately, bsd_ast’s one and only invocation in the kernel is bsd_ast(current_thread()), so we can reconstruct the value by calling current_thread ourselves.

Unfortunately, there is no room in the 15 bytes from bsd_ast+349 to bsd_ast+364 to insert such a call and still prepare the other arguments.

Fortunately, we can optimize a bit of the preceding code to make room. Notice that the calls to task_vtimer_set and task_vtimer_clear are passing the same argument list, and that argument list is prepared in both sides of the conditional:

...
if (timerisset(&p->p_vtimer_prof.it_value))
0xffffff8000568b7b <bsd_ast+299>:       cmpq   $0x0,0x1e0(%r15)
0xffffff8000568b83 <bsd_ast+307>:       jne    0xffffff8000568b8f <bsd_ast+319>
0xffffff8000568b85 <bsd_ast+309>:       cmpl   $0x0,0x1e8(%r15)
0xffffff8000568b8d <bsd_ast+317>:       je     0xffffff8000568b9f <bsd_ast+335>
task_vtimer_set(p->task, TASK_VTIMER_PROF);
0xffffff8000568b8f <bsd_ast+319>:       mov    0x18(%r15),%rdi
0xffffff8000568b93 <bsd_ast+323>:       mov    $0x2,%esi
0xffffff8000568b98 <bsd_ast+328>:       callq  0xffffff80002374f0 <task_vtimer_set>
0xffffff8000568b9d <bsd_ast+333>:       jmp    0xffffff8000568bad <bsd_ast+349>
task_vtimer_clear(p->task, TASK_VTIMER_PROF);
0xffffff8000568b9f <bsd_ast+335>:       mov    0x18(%r15),%rdi
0xffffff8000568ba3 <bsd_ast+339>:       mov    $0x2,%esi
0xffffff8000568ba8 <bsd_ast+344>:       callq  0xffffff8000237660 <task_vtimer_clear>
psignal(p, SIGPROF);
0xffffff8000568bad <bsd_ast+349>:       mov    %r15,%rdi
0xffffff8000568bb0 <bsd_ast+352>:       xor    %esi,%esi
0xffffff8000568bb2 <bsd_ast+354>:       xor    %edx,%edx
0xffffff8000568bb4 <bsd_ast+356>:       xor    %ecx,%ecx
0xffffff8000568bb6 <bsd_ast+358>:       mov    $0x1b,%r8d
0xffffff8000568bbc <bsd_ast+364>:       callq  0xffffff8000567340 <threadsignal+224>
...

We can pull that call setup above the conditional, eliminating one copy and giving ourselves nine bytes to use for delivering the signal. A call to current_thread would take five bytes, and then moving the result into an appropriate register would take two more, so nine is plenty. In fact, since we have nine bytes, we can inline the body of current_thread—a single nine-byte mov instruction—and change it to store the result to the correct register directly. That avoids needing to prepare a position-dependent call instruction.

The final version is:

...
0xffffff8000568b7b <bsd_ast+299>:       mov    0x18(%r15),%rdi
0xffffff8000568b7f <bsd_ast+303>:       mov    $0x2,%esi
0xffffff8000568b84 <bsd_ast+308>:       cmpq   $0x0,0x1e0(%r15)
0xffffff8000568b8c <bsd_ast+316>:       jne    0xffffff8000568b98 <bsd_ast+328>
0xffffff8000568b8e <bsd_ast+318>:       cmpl   $0x0,0x1e8(%r15)
0xffffff8000568b96 <bsd_ast+326>:       je     0xffffff8000568b9f <bsd_ast+335>
0xffffff8000568b98 <bsd_ast+328>:       callq  0xffffff80002374f0 <task_vtimer_set>
0xffffff8000568b9d <bsd_ast+333>:       jmp    0xffffff8000568ba4 <bsd_ast+340>
0xffffff8000568b9f <bsd_ast+335>:       callq  0xffffff8000237660 <task_vtimer_clear>
0xffffff8000568ba4 <bsd_ast+340>:       xor    %edi,%edi
0xffffff8000568ba6 <bsd_ast+342>:       xor    %esi,%esi
0xffffff8000568ba8 <bsd_ast+344>:       mov    %gs:0x8,%rdx
0xffffff8000568bb1 <bsd_ast+353>:       mov    $0x4,%ecx
0xffffff8000568bb6 <bsd_ast+358>:       mov    $0x1b,%r8d
0xffffff8000568bbc <bsd_ast+364>:       callq  0xffffff8000567340 <threadsignal+224>
...

If we hadn’t found the duplicate call setup to factor out, another possible approach would have been to factor the two very similar code blocks handling SIGVTALRM and SIGPROF into a single subroutine, sitting in the middle of the bsd_ast function code, and to call it twice. Removing the second copy of the code would leave plenty of space for the longer psignal_uthread call setup.

The code we’ve been using is from OS X Mountain Lion, but all versions of OS X have this bug, and the relevant bits of bsd_ast haven’t changed from version to version, although the compiler and therefore the generated code do change. Even so, all have the basic pattern and all can be fixed with the same kind of rewrite.

Using the Patch

If you use the Go or the C++ gperftools and want accurate CPU profiles on OS X, I’ve packaged up the binary patcher as code.google.com/p/rsc/cmd/pprof_mac_fix. It can handle OS X Snow Leopard, Lion, and Mountain Lion. Will OS X Mavericks need a fix too? We’ll see.

How To Build a User-Level CPU Profiler

2013-08-08T13:00:00-04:00

When I spent a summer as a Google intern in 2006, one of the many pleasant surprises was Google’s pprof tool, which makes profiling a C++ program’s CPU and memory usage incredibly easy. It had already been open sourced, and when I returned to grad school, I incorporated pprof into my standard development toolbox when writing C programs. Later, when I was back at Google working on Go, implementing support for pprof was a must. Now it’s part of the standard development toolbox for any Go programmer.

I’ve written on the Go blog about what it’s like to use pprof to profile Go programs. This post is about how pprof gathers the CPU profile, with the help of hardware timers and the operating system.

Hardware Timers

One of the key jobs of an operating system is to allow multiple programs to run on a computer at the same time, each under the illusion that they have continuous access to one or more CPUs, even though in practice each CPU can only be running one program at a time. On most systems, what happens is that the operating system asks the computer’s timer chip to interrupt normal execution every so often (every 10 milliseconds is common) and run a small piece of the operating system called, appropriately enough, the timer interrupt handler. The timer interrupt handler checks to see if other programs are waiting to run. If so, and if the current program has used up its turn on the CPU, the handler saves the CPU registers of the current program and loads the CPU registers for another program that has been waiting. Shuffling the programs on and off the CPUs is called multitasking, and doing it based on hardware interrupts like this is called preemptive multitasking: one running program is preempted to make room for another.

Not all operating systems provide preemptive multitasking. Some, like MS-DOS or iOS 3, have no multitasking, so only one program can run at a time. Others, like Windows 3.1 and Mac OS 9, use cooperative multitasking, in which programs voluntarily relinquish the CPU at certain points. Cooperative multitasking avoids the complexity of using the timer, but it means that one badly written program can hang a machine.

Another useful thing you can do with a hardware interrupt is gather a profile of a running program. Every time the hardware interrupt happens, the operating system can record what the program was doing. A collection of these samples makes up a (hopefully representative) profile of where the program spends its time.

A Simple Profiler

Since the operating system moderates access to the hardware, it must be involved to use the hardware timer to implement a profiler. The simplest approach is for the operating system to collect the profile. To illustrate this approach, I’ll describe what the Plan 9 kernel does for user-level profiling. This is little changed from the original Unix profil(2) scheme.

When a program is running, writing to a control file in the /proc file system enables profiling. At that point, the operating system allocates an array of counts with one count for every 8-byte section of the program code, and attaches it to the program. Then, each time a timer interrupt happens, the handler uses the program counter—the address of the instruction in the code that the program is currently executing—divided by 8 as an index into that array and increments that entry. Later, another program (on Plan 9, called tprof) can be run to read the profile from the kernel and determine the function and specific line in the original source code corresponding to each counter and summarize the results.

This design keeps the kernel very simple: the timer handler only adds an increment instruction. However, it is also inflexible: that’s all the kernel will do for a program. And there are potential improvements that could be made with more flexibility. For example, in programs that use libraries, the profiles may not have enough context to be useful. If you find your program is spending 30% of its time in memset but you don’t know what is calling memset, you can’t fix the problem.

The next step forward is to move profiling logic out of the kernel, so that it is easier to customize.

User-Level Timers

Modern Unix systems move profiling logic out of the kernel by providing a timer abstraction to user programs. The programs can then build whatever they want, including profiling. (Another use might be to build preemptive scheduling in a user-level lightweight thread scheduler.)

On these systems, setitimer(2) provides three timers, for “real time,’’ “virtual time,’’ and “profiling time.’’ The “real time’’ timer counts down in real (wall clock) time. If it is set for 5 seconds, it fires 5 seconds from now. The “virtual time’’ timer counts down in program execution time. If it is set for 5 seconds, it fires after the program has executed for 5 seconds. The “profiling time’’ timer is similar except that it also counts down when the kernel is executing a system call on behalf of the program. When any of these timers fires, the kernel stops what the program is doing and invokes a special routine in the program called a signal handler. The signal handler in a program is analogous to the timer interrupt handler in the kernel. The signal being delivered depends on the kind of timer: SIGALRM, SIGVTALRM, or SIGPROF for the three kinds.

A program that wants to profile its own execution can set a profiling timer and then arrange to record a profiling sample in its signal handler. Because the profiling is being done by the program, not by the kernel, it can be replaced without kernel changes and reboots, by changing the program and recompiling. This allows experimentation and in turn the construction of richer profiles. In particular, it allows gathering more information in each profiling sample.

Profiling with pprof

In pprof, each profiling sample records not just the current program counter but also the program counter for each frame in the current call stack.

Obtaining the current call stack is not always trivial: typically it requires arranging for the code being executed to maintain a certain form (for example, to use a frame pointer in all functions) or arranging for additional metadata to be available during the trace. But modern computers are incredibly fast: even walking the call stack using metadata lookups can be done in well under 100 microseconds, which would correspond to only a 1% slowdown for a 10 millisecond profiling period.

Recording a sampled stack is a little tricky. The signal handler, because it interrupts normal program execution, is limited in what it can do. In particular, the signal handler cannot even allocate memory or acquire locks, so the stored profile cannot grow dynamically.

In pprof, the profile is maintained in a hash table in which each entry records a distinct stack. Specifically, in the Go pprof, each stack hashes to a specific hash value denoting one of 1024 buckets in a hash table, and in that bucket are four entries for stacks with that hash. If the stack being recorded is already present, the existing entry’s count is simply incremented. Otherwise, the stack must replace one of the four entries. If one or more is unused, the decision is easy. If all four entries are in use, pprof evicts the entry with the smallest count. The evicted entry is appended to a fixed-size log with space for 2¹⁸ entries, and then its space is reused for the stack we want to record. A background goroutine, not running as a signal handler, copies entries out of the log and into the saved profile data. If the goroutine cannot keep up with the rate at which the log is filling, the counts for the entries that are lost are assigned to a special “lost profile’’ function. In practice, most programs spend their time doing the same thing over and over again, so the active work of the program fits in the hash table, the log grows slowly, and the log draining goroutine has no problem keeping up. In C++ pprof, there is no log-draining goroutine. Instead, the signal handler writes the log to an already open file when it fills.

Interpreting the data

A pprof profile, then, is a set of stack traces with each mapped to the count of the number of times that trace was seen. The usual way this profile is presented is to create a graph in which each function is a node and an edge between nodes denotes a call. Each function node has two counts: first the sum of the counts of all the profiles in which it was the final entry and second the sum of the counts of all the profiles in which it appeared. These correspond to time executing that function and cumulative time executing that function and the things it called. The edges are given counts corresponding to the number of samples in which that call was observed somewhere on the stack. Sizing the nodes and edges based on their counts makes the expensive parts of the program stand out. This example should view nicely in most web browsers; use the scroll wheel to zoom and click and drag to pan. In that profile, it is apparent that hash_lookup called from mapaccess1 is taking the most time, and we can use the call context to see that about 40% of the calls are from code in main.FindLoops while 60% of the calls are from code in main.DFS.

Of course, there is also a command-line interface, tabular results, and annotated source code. See the Profiling Go Programs post.

A Tour of Acme

2012-09-17T11:00:00-04:00

People I work with recognize my computer easily: it's the one with nothing but yellow windows and blue bars on the screen. That's the text editor acme, written by Rob Pike for Plan 9 in the early 1990s. Acme focuses entirely on the idea of text as user interface. It's difficult to explain acme without seeing it, though, so I've put together a screencast explaining the basics of acme and showing a brief programming session. Remember as you watch the video that the 854x480 screen is quite cramped. Usually you'd run acme on a larger screen: even my MacBook Air has almost four times as much screen real estate.

The video doesn't show everything acme can do, nor does it show all the ways you can use it. Even small idioms like where you type text to be loaded or executed vary from user to user. To learn more about acme, read Rob Pike's paper “Acme: A User Interface for Programmers” and then try it.

Acme runs on most operating systems. If you use Plan 9 from Bell Labs, you already have it. If you use FreeBSD, Linux, OS X, or most other Unix clones, you can get it as part of Plan 9 from User Space. If you use Windows, I suggest trying acme as packaged in acme stand alone complex, which is based on the Inferno programming environment.

Mini-FAQ:

Q. Can I use scalable fonts? A. On the Mac, yes. If you run acme -f /mnt/font/Monaco/16a/font you get 16-point anti-aliased Monaco as your font, served via fontsrv. If you'd like to add X11 support to fontsrv, I'd be happy to apply the patch.
Q. Do I need X11 to build on the Mac? A. No. The build will complain that it cannot build ‘snarfer’ but it should complete otherwise. You probably don't need snarfer.

If you're interested in history, the predecessor to acme was called help. Rob Pike's paper “A Minimalist Global User Interface” describes it. See also “The Text Editor sam”

Correction: the smiley program in the video was written by Ken Thompson. I got it from Dennis Ritchie, the more meticulous archivist of the pair.

A Tour of Go

2012-06-21T00:00:00-04:00

Last week, I gave a talk about Go at the Boston Google Developers Group meeting. There were some problems with the recording, so I have rerecorded the talk as a screencast and posted it on YouTube.

Here are the answers to questions asked at the end of the talk.

Q. How does Go work with debuggers?

To start, both Go toolchains include debugging information that gdb can read in the final binaries, so basic gdb functionality works on Go programs just as it does on C programs.

We’ve talked for a while about a custom Go debugger, but there isn’t one yet.

Many of the programs we want to debug are live, running programs. The net/http/pprof package provides debugging information like goroutine stacks, memory profiling, and cpu profiling in response to special HTTP requests.

Q. If a goroutine is stuck reading from a channel with no other references, does the goroutine get garbage collected?

No. From the garbage collection point of view, both sides of the channel are represented by the same pointer, so it can’t distinguish the receive and send sides. Even if we could detect this situation, we’ve found that it’s very useful to keep these goroutines around, because the program is probably heading for a deadlock. When a Go program deadlocks, it prints all its goroutine stacks and then exits. If we garbage collected the goroutines as they got stuck, the deadlock handler wouldn’t have anything useful to print except "your entire program has been garbage collected".

Q. Can a C++ program call into Go?

We wrote a tool called cgo so that Go programs can call into C, and we’ve implemented support for Go in SWIG, so that Go programs can call into C++. In those programs, the C or C++ can in turn call back into Go. But we don’t have support for a C or C++ program—one that starts execution in the C or C++ world instead of the Go world—to call into Go.

The hardest part of the cross-language calls is converting between the C calling convention and the Go calling convention, specifically with the regard to the implementation of segmented stacks. But that’s been done and works.

Making the assumption that these mixed-language binaries start in Go has simplified a number of parts of the implementation. I don’t anticipate any technical surprises involved in removing these assumptions. It’s just work.

Q. What are the areas that you specifically are trying to improve the language?

For the most part, I’m not trying to improve the language itself. Part of the effort in preparing Go 1 was to identify what we wanted to improve and do it. Many of the big changes were based on two or three years of experience writing Go programs, and they were changes we’d been putting off because we knew that they’d be disruptive. But now that Go 1 is out, we want to stop changing things and spend another few years using the language as it exists today. At this point we don’t have enough experience with Go 1 to know what really needs improvement.

My Go work is a small amount of fixing bugs in the libraries or in the compiler and a little bit more work trying to improve the performance of what’s already there.

Q. What about talking to databases and web services?

For databases, one of the packages we added in Go 1 is a standard database/sql package. That package defines a standard API for interacting with SQL databases, and then people can implement drivers that connect the API to specific database implementations like SQLite or MySQL or Postgres.

For web services, you’ve seen the support for JSON and XML encodings. Those are typically good enough for ad hoc REST services. I recently wrote a package for connecting to the SmugMug photo hosting API, and there’s one generic call that unmarshals the response into a struct of the appropriate type, using json.Unmarshal. I expect that XML-based web services like SOAP could be framed this way too, but I’m not aware of anyone who’s done that.

Inside Google, of course, we have plenty of services, but they’re based on protocol buffers, so of course there’s a good protocol buffer library for Go.

Q. What about generics? How far off are they?

People have asked us about generics from day 1. The answer has always been, and still is, that it’s something we’ve put a lot of thought into, but we haven’t yet found an approach that we think is a good fit for Go. We’ve talked to people who have been involved in the design of generics in other languages, and they’ve almost universally cautioned us not to rush into something unless we understand it very well and are comfortable with the implications. We don’t want to do something that we’ll be stuck with forever and regret.

Also, speaking for myself, I don’t miss generics when I write Go programs. What’s there, having built-in support for arrays, slices, and maps, seems to work very well.

Finally, we just made this promise about backwards compatibility with the release of Go 1. If we did add some form of generics, my guess is that some of the existing APIs would need to change, which can’t happen until Go 2, which I think is probably years away.

Q. What types of projects does Google use Go for?

Most of the things we use Go for I can’t talk about. One notable exception is that Go is an App Engine language, which we announced at I/O last year. Another is vtocc, a MySQL load balancer used to manage database lookups in YouTube’s core infrastructure.

Q. How does the Plan 9 toolchain differ from other compilers?

It’s a completely incompatible toolchain in every way. The main difference is that object files don’t contain machine code in the sense of having the actual instruction bytes that will be used in the final binary. Instead they contain a custom encoding of the assembly listings, and the linker is in charge of turning those into actual machine instructions. This means that the assembler, C compiler, and Go compiler don’t all duplicate this logic. The main change for Go is the support for segmented stacks.

I should add that we love the fact that we have two completely different compilers, because it keeps us honest about really implementing the spec.

Q. What are segmented stacks?

One of the problems in threaded C programs is deciding how big a stack each thread should have. If the stack is too small, then the thread might run out of stack and cause a crash or silent memory corruption, and if the stack is too big, then you’re wasting memory. In Go, each goroutine starts with a small stack, typically 4 kB, and then each function checks if it is about to run out of stack and if so allocates a new stack segment that gets recycled once it’s not needed anymore.

Gccgo supports segmented stacks, but it requires support added recently to the new GNU linker, gold, and that support is only implemented for x86-32 and x86-64.

Segmented stacks are something that lots of people have done before in experimental or research systems, but they have never made it into the C toolchains.

Q. What is the overhead of segmented stacks?

It’s a few instructions per function call. It’s been a long time since I tried to measure the precise overhead, but in most programs I expect it to be not more than 1-2%. There are definitely things we could do to try to reduce that, but it hasn’t been a concern.

Q. Do goroutine stacks adapt in size?

The initial stack allocated for a goroutine does not adapt. It’s always 4k right now. It has been other values in the past but always a constant. One of the things I’d like to do is to look at what the goroutine will be running and adjust the stack accordingly, but I haven’t.

Q. Are there any short-term plans for dynamic loading of modules?

No. I don’t think there are any technical surprises, but assuming that everything is statically linked simplified some of the implementation. Like with calling Go from C++ programs, I believe it’s just work.

Gccgo might be closer to support for this, but I don’t believe that it supports dynamic loading right now either.

Q. How much does the language spec say about reflection?

The spec is intentionally vague about reflection, but package reflect’s API is definitely part of the Go 1 definition. Any conforming implementation would need to implement that API. In fact, gc and gccgo do have different implementations of that package reflect API, but then the packages that use reflect like fmt and json can be shared.

Q. Do you have a release schedule?

We don’t have any fixed release schedule. We’re not keeping things secret, but we’re also not making commitments to specific timelines.

Go 1 was in progress publicly for months, and if you watched you could see the bug count go down and the release candidates announced, and so on.

Right now we’re trying to slow down. We want people to write things using Go, which means we need to make it a stable foundation to build on. Go 1.0.1, the first bug release, was released four weeks after Go 1, and Go 1.0.2 was seven weeks after Go 1.0.1.

Q. Where do you see Go in five years? What languages will it replace?

I hope that it will still be at golang.org, that the Go project will still be thriving and relevant. We built it to write the kinds of programs we’ve been writing in C++, Java, and Python, but we’re not trying to go head-to-head with those languages. Each of those has definite strengths that make them the right choice for certain situations. We think that there are plenty of situations, though, where Go is a better choice.

If Go doesn’t work out, and for some reason in five years we’re programming in something else, I hope the something else would have the features I talked about, specifically the Go way of doing interfaces and the Go way of handling concurrency.

If Go fails but some other language with those two features has taken over the programming landscape, if we can move the computing world to a language with those two features, then I’d be sad about Go but happy to have gotten to that situation.

Q. What are the limits to scalability with building a system with many goroutines?

The primary limit is the memory for the goroutines. Each goroutine starts with a 4kB stack and a little more per-goroutine data, so the overhead is between 4kB and 5kB. That means on this laptop I can easily run 100,000 goroutines, in 500 MB of memory, but a million goroutines is probably too much.

For a lot of simple goroutines, the 4 kB stack is probably more than necessary. If we worked on getting that down we might be able to handle even more goroutines. But remember that this is in contrast to C threads, where 64 kB is a tiny stack and 1-4MB is more common.

Q. How would you build a traditional barrier using channels?

It’s important to note that channels don’t attempt to be a concurrency Swiss army knife. Sometimes you do need other concepts, and the standard sync package has some helpers. I’d probably use a sync.WaitGroup.

If I had to use channels, I would do it like in the web crawler example, with a channel that all the goroutines write to, and a coordinator that knows how many responses it expects.

Q. What is an example of the kind of application you’re working on performance for? How will you beat C++?

I haven’t been focusing on specific applications. Go is still young enough that if you run some microbenchmarks you can usually find something to optimize. For example, I just sped up floating point computation by about 25% a few weeks ago. I’m also working on more sophisticated analyses for things like escape analysis and bounds check elimination, which address problems that are unique to Go, or at least not problems that C++ faces.

Our goal is definitely not to beat C++ on performance. The goal for Go is to be near C++ in terms of performance but at the same time be a much more productive environment and language, so that you’d rather program in Go.

Q. What are the security features of Go?

Go is a type-safe and memory-safe language. There are no dangling pointers, no pointer arithmetic, no use-after-free errors, and so on.

You can break the rules by importing package unsafe, which gives you a special type unsafe.Pointer. You can convert any pointer or integer to an unsafe.Pointer and back. That’s the escape hatch, which you need sometimes, like for extracting the bits of a float64 as a uint64. But putting it in its own package means that unsafe code is explicitly marked as unsafe. If your program breaks in a strange way, you know where to look.

Isolating this power also means that you can restrict it. On App Engine you can’t import package unsafe in the code you upload for your app.

I should point out that the current Go implementation does have data races, but they are not fundamental to the language. It would be possible to eliminate the races at some cost in efficiency, and for now we’ve decided not to do that. There are also tools such as Thread Sanitizer that help find these kinds of data races in Go programs.

Q. What language do you think Go is trying to displace?

I don’t think of Go that way. We were writing C++ code before we did Go, so we definitely wanted not to write C++ code anymore. But we’re not trying to displace all C++ code, or all Python code, or all Java code, except maybe in our own day-to-day work.

One of the surprises for me has been the variety of languages that new Go programmers used to use. When we launched, we were trying to explain Go to C++ programmers, but many of the programmers Go has attracted have come from more dynamic languages like Python or Ruby.

Q. How does Go make it possible to use multiple cores?

Go lets you tell the runtime how many operating system threads to use for executing goroutines, and then it muxes the goroutines onto those threads. So if you’ve written a program that has four or more goroutines executing simultaneously, you can tell the runtime to use four OS threads and then you’re running on four cores.

We’ve been pleasantly surprised by how easy people find it to write these kinds of programs. People who have not written parallel or concurrent programs before write concurrent Go programs using channels that can take advantage of multiple cores, and they enjoy the experience. That’s more than you can usually say for C threads. Joe Armstrong, one of the creators of Erlang, makes the point that thinking about concurrency in terms of communication might be more natural for people, since communication is something we’ve done for a long time. I agree.

Q. How does the muxing of goroutines work?

It’s not very smart. It’s the simplest thing that isn’t completely stupid: all the scheduling operations are O(1), and so on, but there’s a shared run queue that the various threads pull from. There’s no affinity between goroutines and threads, there’s no attempt to make sophisticated scheduling decisions, and there’s not even preemption.

The goroutine scheduler was the first thing I wrote when I started working on Go, even before I was working full time on it, so it’s just about four years old. It has served us surprisingly well, but we’ll probably want to replace it in the next year or so. We’ve been having some discussions recently about what we’d want to try in a new scheduler.

Q. Is there any plan to bootstrap Go in Go, to write the Go compiler in Go?

There’s no immediate plan. Go does ship with a Go program parser written in Go, so the first piece is already done, and there’s an experimental type checker in the works, but those are mainly for writing program analysis tools. I think that Go would be a great language to write a compiler in, but there’s no immediate plan. The current compiler, written in C, works well.

I’ve worked on bootstrapped languages in the past, and I found that bootstrapping is not necessarily a good fit for languages that are changing frequently. It reminded me of climbing a cliff and screwing hooks into the cliff once in a while to catch you if you fall. Once or twice I got into situations where I had identified a bug in the compiler, but then trying to write the code to fix the bug tickled the bug, so it couldn’t be compiled. And then you have to think hard about how to write the fix in a way that avoids the bug, or else go back through your version control history to find a way to replay history without introducing the bug. It’s not fun.

The fact that Go wasn’t written in itself also made it much easier to make significant language changes. Before the initial release we went through a handful of wholesale syntax upheavals, and I’m glad we didn’t have to worry about how we were going to rebootstrap the compiler or ensure some kind of backwards compatibility during those changes.

Finally, I hope you’ve read Ken Thompson’s Turing Award lecture, Reflections on Trusting Trust. When we were planning the initial open source release, we liked to joke that no one in their right mind would accept a bootstrapped compiler binary written by Ken.

Q. What does Go do to compile efficiently at scale?

This is something that we talked about a lot in early talks about Go. The main thing is that it cuts off transitive dependencies when compiling a single module. In most languages, if package A imports B, and package B imports C, then the compilation of A reads not just the compiled form of B but also the compiled form of C. In large systems, this gets out of hand quickly. For example, in C++ on my Mac, including <iostream> reads 25,326 lines from 131 files. (C and C++ headers aren't “compiled form,” but the problem is the same.) Go promises that each import reads a single compiled package file. If you need to know something about other packages to understand that package’s API, then the compiled file includes the extra information you need, but only that.

Of course, if you are building from scratch and package A imports B which imports C, then of course C has to be compiled first, and then B, and then A. The import point is that when you go to compile A, you don’t reload C’s object file. In a real program, the dependencies are usually not a chain like this. We might have A1, A2, A3, and so on all importing B. It’s a significant win if none of them need to reread C.

Q. How do you identify a good project for Go?

I think a good project for Go is one that you’re excited about writing in Go. Go really is a general purpose programming language, and except for the compiler work, it’s the only language I’ve written significant programs in for the past four years.

Most of the people I know who are using Go are using it for networked servers, where the concurrency features have something contribute, but it’s great for other contexts too. I’ve used it to write a simple mail reader, file system implementations to read old disks, and a variety of other unnetworked programs.

Q. What is the current and future IDE support for Go?

I’m not an IDE user in the modern sense, so really I don’t know. We think that it would be possible to write a really nice IDE specifically for Go, but it’s not something we’ve had time to explore. The Go distribution has a misc directory that contains basic Go support for common editors, and there is a Goclipse project to write an Eclipse-based IDE, but I don’t know much about those.

The development environment I use, acme, is great for writing Go code, but not because of any custom Go support.

If you have more questions, please consult these resources.

QArt Codes

2012-04-12T15:00:00-04:00

QR codes are 2-dimensional bar codes that encode arbitrary text strings. A common use of QR codes is to encode URLs so that people can scan a QR code (for example, on an advertising poster, building roof, volleyball bikini, belt buckle, or airplane banner) to load a web site on a cell phone instead of having to “type” in a URL.

QR codes are encoded using Reed-Solomon error-correcting codes, so that a QR scanner does not have to see every pixel correctly in order to decode the content. The error correction makes it possible to introduce a few errors (fewer than the maximum that the algorithm can fix) in order to make an image. For example, in 2008, Duncan Robertson took a QR code for “http://bbc.co.uk/programmes” (left) and introduced errors in the form of a BBC logo (right):

That's a neat trick and a pretty logo, but it's uninteresting from a technical standpoint. Although the BBC logo pixels look like QR code pixels, they are not contribuing to the QR code. The QR reader can't tell much difference between the BBC logo and the Union Jack. There's just a bunch of noise in the middle either way.

Since the BBC QR logo appeared, there have been many imitators. Most just slap an obviously out-of-place logo in the middle of the code. This Disney poster is notable for being more in the spirit of the BBC code.

There's a different way to put pictures in QR codes. Instead of scribbling on redundant pieces and relying on error correction to preserve the meaning, we can engineer the encoded values to create the picture in a code with no inherent errors, like these:

This post explains the math behind making codes like these, which I call QArt codes. I have published the Go programs that generated these codes at code.google.com/p/rsc and created a web site for creating these codes.

Background

For error correction, QR uses Reed-Solomon coding (like nearly everything else). For our purposes, Reed-Solomon coding has two important properties. First, it is what coding theorists call a systematic code: you can see the original message in the encoding. That is, the Reed-Solomon encoding of “hello” is “hello” followed by some error-correction bytes. Second, Reed-Solomon encoded messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (Here, ⊕ means XOR.) If you are curious about why these two properties are true, see my earlier post, Finite Field Arithmetic and Reed-Solomon Coding.

QR Codes

A QR code has a distinctive frame that help both people and computers recognize them as QR codes. The details of the frame depend on the exact size of the code—bigger codes have room for more bits—but you know one when you see it: the outlined squares are the giveaway. Here are QR frames for a sampling of sizes:

The colored pixels are where the Reed-Solomon-encoded data bits go. Each code may have one or more Reed-Solomon blocks, depending on its size and the error correction level. The pictures show the bits from each block in a different color. The L encoding is the lowest amount of redundancy, about 20%. The other three encodings increase the redundancy, using 38%, 55%, and 65%.

(By the way, you can read the redundancy level from the top pixels in the two leftmost columns. If black=0 and white=1, then you can see that 00 is L, 01 is M, 10 is Q, and 11 is H. Thus, you can tell that the QR code on the T-shirt in this picture is encoded at the highest redundancy level, while this shirt uses the lowest level and therefore might take longer or be harder to scan.

As I mentioned above, the original message bits are included directly in the message's Reed-Solomon encoding. Thus, each bit in the original message corresponds to a pixel in the QR code. Those are the lighter pixels in the pictures above. The darker pixels are the error correction bits. The encoded bits are laid down in a vertical boustrophedon pattern in which each line is two columns wide, starting at the bottom right corner and ending on the left side:

We can easily work out where each message bit ends up in the QR code. By changing those bits of the message, we can change those pixels and draw a picture. There are, however, a few complications that make things interesting.

QR Masks

The first complication is that the encoded data is XOR'ed with an obfuscating mask to create the final code. There are eight masks:

An encoder is supposed to choose the mask that best hides any patterns in the data, to keep those patterns from being mistaken for framing boxes. In our encoder, however, we can choose a mask before choosing the data. This violates the spirit of the spec but still produces legitimate codes.

QR Data Encoding

The second complication is that we want the QR code's message to be intelligible. We could draw arbitrary pictures using arbitrary 8-bit data, but when scanned the codes would produce binary garbage. We need to limit ourselves to data that produces sensible messages. Luckily for us, QR codes allow messages to be written using a few different alphabets. One alphabet is 8-bit data, which would require binary garbage to draw a picture. Another is numeric data, in which every run of 10 bits defines 3 decimal digits. That limits our choice of pixels slightly: we must not generate a 10-bit run with a value above 999. That's not complete flexibility, but it's close: 9.96 bits of freedom out of 10. If, after encoding an image, we find that we've generated an invalid number, we pick one of the 5 most significant bits at random—all of them must be 1s to make an invalid number—hard wire that bit to zero, and start over.

Having only decimal messages would still not be very interesting: the message would be a very large number. Luckily for us (again), QR codes allow a single message to be composed from pieces using different encodings. The codes I have generated consist of an 8-bit-encoded URL ending in a # followed by a numeric-encoded number that draws the actual picture:

http://swtch.com/pjw/#123456789...

The leading URL is the first data encoded; it takes up the right side of the QR code. The error correction bits take up the left side.

When the phone scans the QR code, it sees a URL; loading it in a browser visits the base page and then looks for an internal anchor on the page with the given number. The browser won't find such an anchor, but it also won't complain.

The techniques so far let us draw codes like this one:

The second copy darkens the pixels that we have no control over: the error correction bits on the left and the URL prefix on the right. I appreciate the cyborg effect of Peter melting into the binary noise, but it would be nice to widen our canvas.

Gauss-Jordan Elimination

The third complication, then, is that we want to draw using more than just the slice of data pixels in the middle of the image. Luckily, we can.

I mentioned above that Reed-Solomon messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (In the notation of the previous post, this happens because Reed-Solomon blocks correspond 1:1 with multiples of g(x). Since b₁ and b₂ are multiples of g(x), their sum is a multiple of g(x) too.) This property means that we can build up a valid Reed-Solomon block from other Reed-Solomon blocks. In particular, we can construct the sequence of blocks b₀, b₁, b₂, ..., where b_i is the block whose data bits are all zeros except for bit i and whose error correction bits are then set to correspond to a valid Reed-Solomon block. That set is a basis for the entire vector space of valid Reed-Solomon blocks. Here is the basis matrix for the space of blocks with 2 data bytes and 2 checksum bytes:


1																1		1			1	1	1			1			1	1	1

	1															1	1		1	1	1		1	1			1	1	1		1

		1														1	1	1						1	1

			1														1	1	1						1	1

				1														1	1	1						1	1

					1														1	1	1						1	1

						1														1	1	1						1	1

							1														1	1	1						1	1

								1								1			1	1	1		1				1	1	1		1

									1							1	1							1

										1							1	1							1

											1							1	1							1

												1							1	1							1

													1							1	1							1

														1							1	1							1

															1							1	1							1

The missing entries are zeros. The gray columns highlight the pixels we have complete control over: there is only one row with a 1 for each of those pixels. Each time we want to change such a pixel, we can XOR our current data with its row to change that pixel, not change any of the other controlled pixels, and keep the error correction bits up to date.

So what, you say. We're still just twiddling data bits. The canvas is the same.

But wait, there's more! The basis we had above lets us change individual data pixels, but we can XOR rows together to create other basis matrices that trade data bits for error correction bits. No matter what, we're not going to increase our flexibility—the number of pixels we have direct control over cannot increase—but we can redistribute that flexibility throughout the image, at the same time smearing the uncooperative noise pixels evenly all over the canvas. This is the same procedure as Gauss-Jordan elimination, the way you turn a matrix into row-reduced echelon form.

This matrix shows the result of trying to assert control over alternating pixels (the gray columns):


1	1						1				1		1				1						1	1			1		1

	1	1									1		1										1		1	1	1		1		1

				1							1		1								1						1	1

						1	1						1								1		1							1

	1							1									1							1

										1	1						1		1						1	1

												1	1						1		1						1	1

							1							1									1							1

	1												1			1	1		1				1	1			1		1		1

											1							1	1							1

													1							1	1							1

							1														1	1	1						1	1

	1								1				1						1				1				1		1		1

					1								1						1								1

							1								1						1								1

			1								1						1								1

The matrix illustrates an important point about this trick: it's not completely general. The data bits are linearly independent, but there are dependencies between the error correction bits that mean we often can't have every pixel we ask for. In this example, the last four pixels we tried to get were unavailable: our manipulations of the rows to isolate the first four error correction bits zeroed out the last four that we wanted.

In practice, a good approach is to create a list of all the pixels in the Reed-Solomon block sorted by how useful it would be to be able to set that pixel. (Pixels from high-contrast regions of the image are less important than pixels from low-contrast regions.) Then, we can consider each pixel in turn, and if the basis matrix allows it, isolate that pixel. If not, no big deal, we move on to the next pixel.

Applying this insight, we can build wider but noisier pictures in our QR codes:

The pixels in Peter's forehead and on his right side have been sacrificed for the ability to draw the full width of the picture.

We can also choose the pixels we want to control at random, to make Peter peek out from behind a binary fog:

Rotations

One final trick. QR codes have no required orientation. The URL base pixels that we have no control over are on the right side in the canonical orientation, but we can rotate the QR code to move them to other edges.

Further Information

All the source code for this post, including the web server, is at code.google.com/p/rsc/source/browse/qr. If you liked this, you might also like Zip Files All The Way Down.

Acknowledgements

Alex Healy pointed out that valid Reed-Solomon encodings are closed under XOR, which is the key to spreading the picture into the error correction pixels. Peter Weinberger has been nothing but gracious about the overuse of his binary likeness. Thanks to both.

Minimal Boolean Formulas

2011-05-18T00:00:00-04:00

28. That's the minimum number of AND or OR operators you need in order to write any Boolean function of five variables. Alex Healy and I computed that in April 2010. Until then, I believe no one had ever known that little fact. This post describes how we computed it and how we almost got scooped by Knuth's Volume 4A which considers the problem for AND, OR, and XOR.

A Naive Brute Force Approach

Any Boolean function of two variables can be written with at most 3 AND or OR operators: the parity function on two variables X XOR Y is (X AND Y') OR (X' AND Y), where X' denotes “not X.” We can shorten the notation by writing AND and OR like multiplication and addition: X XOR Y = X*Y' + X'*Y.

For three variables, parity is also a hardest function, requiring 9 operators: X XOR Y XOR Z = (X*Z'+X'*Z+Y')*(X*Z+X'*Z'+Y).

For four variables, parity is still a hardest function, requiring 15 operators: W XOR X XOR Y XOR Z = (X*Z'+X'*Z+W'*Y+W*Y')*(X*Z+X'*Z'+W*Y+W'*Y').

The sequence so far prompts a few questions. Is parity always a hardest function? Does the minimum number of operators alternate between 2ⁿ−1 and 2ⁿ+1?

I computed these results in January 2001 after hearing the problem from Neil Sloane, who suggested it as a variant of a similar problem first studied by Claude Shannon.

The program I wrote to compute a(4) computes the minimum number of operators for every Boolean function of n variables in order to find the largest minimum over all functions. There are 2⁴ = 16 settings of four variables, and each function can pick its own value for each setting, so there are 2¹⁶ different functions. To make matters worse, you build new functions by taking pairs of old functions and joining them with AND or OR. 2¹⁶ different functions means 2¹⁶·2¹⁶ = 2³² pairs of functions.

The program I wrote was a mangling of the Floyd-Warshall all-pairs shortest paths algorithm. That algorithm is:

// Floyd-Warshall all pairs shortest path
func compute():
    for each node i
        for each node j
            dist[i][j] = direct distance, or ∞
    
    for each node k
        for each node i
            for each node j
                d = dist[i][k] + dist[k][j]
                if d < dist[i][j]
                    dist[i][j] = d
    return

The algorithm begins with the distance table dist[i][j] set to an actual distance if i is connected to j and infinity otherwise. Then each round updates the table to account for paths going through the node k: if it's shorter to go from i to k to j, it saves that shorter distance in the table. The nodes are numbered from 0 to n, so the variables i, j, k are simply integers. Because there are only n nodes, we know we'll be done after the outer loop finishes.

The program I wrote to find minimum Boolean formula sizes is an adaptation, substituting formula sizes for distance.

// Algorithm 1
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each function f
            for each function g
                d = size[f] + 1 + size[g]
                if d < size[f OR g]
                    size[f OR g] = d
                    changed = true
                if d < size[f AND g]
                    size[f AND g] = d
                    changed = true
        if not changed
            return

Algorithm 1 runs the same kind of iterative update loop as the Floyd-Warshall algorithm, but it isn't as obvious when you can stop, because you don't know the maximum formula size beforehand. So it runs until a round doesn't find any new functions to make, iterating until it finds a fixed point.

The pseudocode above glosses over some details, such as the fact that the per-function loops can iterate over a queue of functions known to have finite size, so that each loop omits the functions that aren't yet known. That's only a constant factor improvement, but it's a useful one.

Another important detail missing above is the representation of functions. The most convenient representation is a binary truth table. For example, if we are computing the complexity of two-variable functions, there are four possible inputs, which we can number as follows.

X	Y	Value
false	false	00₂ = 0
false	true	01₂ = 1
true	false	10₂ = 2
true	true	11₂ = 3

The functions are then the 4-bit numbers giving the value of the function for each input. For example, function 13 = 1101₂ is true for all inputs except X=false Y=true. Three-variable functions correspond to 3-bit inputs generating 8-bit truth tables, and so on.

This representation has two key advantages. The first is that the numbering is dense, so that you can implement a map keyed by function using a simple array. The second is that the operations “f AND g” and “f OR g” can be implemented using bitwise operators: the truth table for “f AND g” is the bitwise AND of the truth tables for f and g.

That program worked well enough in 2001 to compute the minimum number of operators necessary to write any 1-, 2-, 3-, and 4-variable Boolean function. Each round takes asymptotically O(2^2ⁿ·2^2ⁿ) = O(2^2ⁿ⁺¹) time, and the number of rounds needed is O(the final answer). The answer for n=4 is 15, so the computation required on the order of 15·2^2⁵ = 15·2³² iterations of the innermost loop. That was plausible on the computer I was using at the time, but the answer for n=5, likely around 30, would need 30·2⁶⁴ iterations to compute, which seemed well out of reach. At the time, it seemed plausible that parity was always a hardest function and that the minimum size would continue to alternate between 2ⁿ−1 and 2ⁿ+1. It's a nice pattern.

Exploiting Symmetry

Five years later, though, Alex Healy and I got to talking about this sequence, and Alex shot down both conjectures using results from the theory of circuit complexity. (Theorists!) Neil Sloane added this note to the entry for the sequence in his Online Encyclopedia of Integer Sequences:

%E A056287 Russ Cox conjectures that X₁ XOR ... XOR X_n is always a worst f and that a(5) = 33 and a(6) = 63. But (Jan 27 2006) Alex Healy points out that this conjecture is definitely false for large n. So what is a(5)?

Indeed. What is a(5)? No one knew, and it wasn't obvious how to find out.

In January 2010, Alex and I started looking into ways to speed up the computation for a(5). 30·2⁶⁴ is too many iterations but maybe we could find ways to cut that number.

In general, if we can identify a class of functions f whose members are guaranteed to have the same complexity, then we can save just one representative of the class as long as we recreate the entire class in the loop body. What used to be:

for each function f
    for each function g
        visit f AND g
        visit f OR g

can be rewritten as

for each canonical function f
    for each canonical function g
        for each ff equivalent to f
            for each gg equivalent to g
                visit ff AND gg
                visit ff OR gg

That doesn't look like an improvement: it's doing all the same work. But it can open the door to new optimizations depending on the equivalences chosen. For example, the functions “f” and “¬f” are guaranteed to have the same complexity, by DeMorgan's laws. If we keep just one of those two on the lists that “for each function” iterates over, we can unroll the inner two loops, producing:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f OR g
        visit ¬f AND g
        visit f OR ¬g
        visit f AND ¬g
        visit ¬f OR ¬g
        visit ¬f AND ¬g

That's still not an improvement, but it's no worse. Each of the two loops considers half as many functions but the inner iteration is four times longer. Now we can notice that half of tests aren't worth doing: “f AND g” is the negation of “¬f OR ¬g,” and so on, so only half of them are necessary.

Let's suppose that when choosing between “f” and “¬f” we keep the one that is false when presented with all true inputs. (This has the nice property that f ^ (int32(f) >> 31) is the truth table for the canonical form of f.) Then we can tell which combinations above will produce canonical functions when f and g are already canonical:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f AND g
        visit f AND ¬g

That's a factor of two improvement over the original loop.

Another observation is that permuting the inputs to a function doesn't change its complexity: “f(V, W, X, Y, Z)” and “f(Z, Y, X, W, V)” will have the same minimum size. For complex functions, each of the 5! = 120 permutations will produce a different truth table. A factor of 120 reduction in storage is good but again we have the problem of expanding the class in the iteration. This time, there's a different trick for reducing the work in the innermost iteration. Since we only need to produce one member of the equivalence class, it doesn't make sense to permute the inputs to both f and g. Instead, permuting just the inputs to f while fixing g is guaranteed to hit at least one member of each class that permuting both f and g would. So we gain the factor of 120 twice in the loops and lose it once in the iteration, for a net savings of 120. (In some ways, this is the same trick we did with “f” vs “¬f.”)

A final observation is that negating any of the inputs to the function doesn't change its complexity, because X and X' have the same complexity. The same argument we used for permutations applies here, for another constant factor of 2⁵ = 32.

The code stores a single function for each equivalence class and then recomputes the equivalent functions for f, but not g.

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g
            visit ff OR g
            visit ff AND g
            visit ¬ff AND g
            visit ff AND ¬g

In all, we just got a savings of 2·120·32 = 7680, cutting the total number of iterations from 30·2⁶⁴ = 5×10²⁰ to 7×10¹⁶. If you figure we can do around 10⁹ iterations per second, that's still 800 days of CPU time.

The full algorithm at this point is:

// Algorithm 2
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g
                    d = size[ff] + 1 + size[g]
                    changed |= visit(d, ff OR g)
                    changed |= visit(d, ff AND g)
                    changed |= visit(d, ff AND ¬g)
                    changed |= visit(d, ¬ff AND g)
        if not changed
            return

func visit(d, fg):
    if size[fg] != ∞
        return false
    
    record fg as canonical

    for each function ffgg equivalent to fg
        size[ffgg] = d
    return true

The helper function “visit” must set the size not only of its argument fg but also all equivalent functions under permutation or inversion of the inputs, so that future tests will see that they have been computed.

Methodical Exploration

There's one final improvement we can make. The approach of looping until things stop changing considers each function pair multiple times as their sizes go down. Instead, we can consider functions in order of complexity, so that the main loop builds first all the functions of minimum complexity 1, then all the functions of minimum complexity 2, and so on. If we do that, we'll consider each function pair at most once. We can stop when all functions are accounted for.

Applying this idea to Algorithm 1 (before canonicalization) yields:

// Algorithm 3
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each function f
            for each function g of size k − size(f) − 1
                if size[f AND g] == ∞
                    size[f AND g] = k
                    nsize++
                if size[f OR g] == ∞
                    size[f OR g] = k
                    nsize++
        if nsize == 2^2ⁿ
            return

Applying the idea to Algorithm 2 (after canonicalization) yields:

// Algorithm 4
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)
        if nvisited == 2^2ⁿ
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

The original loop in Algorithms 1 and 2 considered each pair f, g in every iteration of the loop after they were computed. The new loop in Algorithms 3 and 4 considers each pair f, g only once, when k = size(f) + size(g) + 1. This removes the leading factor of 30 (the number of times we expected the first loop to run) from our estimation of the run time. Now the expected number of iterations is around 2⁶⁴/7680 = 2.4×10¹⁵. If we can do 10⁹ iterations per second, that's only 28 days of CPU time, which I can deliver if you can wait a month.

Our estimate does not include the fact that not all function pairs need to be considered. For example, if the maximum size is 30, then the functions of size 14 need never be paired against the functions of size 16, because any result would have size 14+1+16 = 31. So even 2.4×10¹⁵ is an overestimate, but it's in the right ballpark. (With hindsight I can report that only 1.7×10¹⁴ pairs need to be considered but also that our estimate of 10⁹ iterations per second was optimistic. The actual calculation ran for 20 days, an average of about 10⁸ iterations per second.)

Endgame: Directed Search

A month is still a long time to wait, and we can do better. Near the end (after k is bigger than, say, 22), we are exploring the fairly large space of function pairs in hopes of finding a fairly small number of remaining functions. At that point it makes sense to change from the bottom-up “bang things together and see what we make” to the top-down “try to make this one of these specific functions.” That is, the core of the current search is:

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g of size k − size(f) − 1
            visit(k, ff OR g)
            visit(k, ff AND g)
            visit(k, ff AND ¬g)
            visit(k, ¬ff AND g)

We can change it to:

for each missing function fg
    for each canonical function g
        for all possible f such that one of these holds
                * fg = f OR g
                * fg = f AND g
                * fg = ¬f AND g
                * fg = f AND ¬g
            if size[f] == k − size(g) − 1
                visit(k, fg)
                next fg

By the time we're at the end, exploring all the possible f to make the missing functions—a directed search—is much less work than the brute force of exploring all combinations.

As an example, suppose we are looking for f such that fg = f OR g. The equation is only possible to satisfy if fg OR g == fg. That is, if g has any extraneous 1 bits, no f will work, so we can move on. Otherwise, the remaining condition is that f AND ¬g == fg AND ¬g. That is, for the bit positions where g is 0, f must match fg. The other bits of f (the bits where g has 1s) can take any value. We can enumerate the possible f values by recursively trying all possible values for the “don't care” bits.

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

It doesn't matter which 1 bit we choose for the recursion, but finding the rightmost 1 bit is cheap: it is isolated by the (admittedly surprising) expression “any AND −any.”

Given find, the loop above can try these four cases:

Formula	Condition	Base x	“Any” bits
fg = f OR g	fg OR g == fg	fg AND ¬g	g
fg = f OR ¬g	fg OR ¬g == fg	fg AND g	¬g
¬fg = f OR g	¬fg OR g == fg	¬fg AND ¬g	g
¬fg = f OR ¬g	¬fg OR ¬g == ¬fg	¬fg AND g	¬g

Rewriting the Boolean expressions to use only the four OR forms means that we only need to write the “adding bits” version of find.

The final algorithm is:

// Algorithm 5
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    // Generate functions.
    for k = 1 to max_generate
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)

    // Search for functions.
    for k = max_generate+1 to ∞
        for each missing function fg
            for each canonical function g
                fsize = k − size(g) − 1
                if fg OR g == fg
                    if f = find(fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if fg OR ¬g == fg
                    if f = find(fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR g == ¬fg
                    if f = find(¬fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR ¬g == ¬fg
                    if f = find(¬fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
        if nvisited == 2^2ⁿ
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

To get a sense of the speedup here, and to check my work, I ran the program using both algorithms on a 2.53 GHz Intel Core 2 Duo E7200.

	————— # of Functions —————			———— Time ————
Size	Canonical	All	All, Cumulative	Generate	Search
0	1	10	10
1	2	82	92	< 0.1 seconds	3.4 minutes
2	2	640	732	< 0.1 seconds	7.2 minutes
3	7	4420	5152	< 0.1 seconds	12.3 minutes
4	19	25276	29696	< 0.1 seconds	30.1 minutes
5	44	117440	147136	< 0.1 seconds	1.3 hours
6	142	515040	662176	< 0.1 seconds	3.5 hours
7	436	1999608	2661784	0.2 seconds	11.6 hours
8	1209	6598400	9260184	0.6 seconds	1.7 days
9	3307	19577332	28837516	1.7 seconds	4.9 days
10	7741	50822560	79660076	4.6 seconds	[ 10 days ? ]
11	17257	114619264	194279340	10.8 seconds	[ 20 days ? ]
12	31851	221301008	415580348	21.7 seconds	[ 50 days ? ]
13	53901	374704776	790285124	38.5 seconds	[ 80 days ? ]
14	75248	533594528	1323879652	58.7 seconds	[ 100 days ? ]
15	94572	667653642	1991533294	1.5 minutes	[ 120 days ? ]
16	98237	697228760	2688762054	2.1 minutes	[ 120 days ? ]
17	89342	628589440	3317351494	4.1 minutes	[ 90 days ? ]
18	66951	468552896	3785904390	9.1 minutes	[ 50 days ? ]
19	41664	287647616	4073552006	23.4 minutes	[ 30 days ? ]
20	21481	144079832	4217631838	57.0 minutes	[ 10 days ? ]
21	8680	55538224	4273170062	2.4 hours	2.5 days
22	2730	16099568	4289269630	5.2 hours	11.7 hours
23	937	4428800	4293698430	11.2 hours	2.2 hours
24	228	959328	4294657758	22.0 hours	33.2 minutes
25	103	283200	4294940958	1.7 days	4.0 minutes
26	21	22224	4294963182	2.9 days	42 seconds
27	10	3602	4294966784	4.7 days	2.4 seconds
28	3	512	4294967296	[ 7 days ? ]	0.1 seconds

The bracketed times are estimates based on the work involved: I did not wait that long for the intermediate search steps. The search algorithm is quite a bit worse than generate until there are very few functions left to find. However, it comes in handy just when it is most useful: when the generate algorithm has slowed to a crawl. If we run generate through formulas of size 22 and then switch to search for 23 onward, we can run the whole computation in just over half a day of CPU time.

The computation of a(5) identified the sizes of all 616,126 canonical Boolean functions of 5 inputs. In contrast, there are just over 200 trillion canonical Boolean functions of 6 inputs. Determining a(6) is unlikely to happen by brute force computation, no matter what clever tricks we use.

Adding XOR

We've assumed the use of just AND and OR as our basis for the Boolean formulas. If we also allow XOR, functions can be written using many fewer operators. In particular, a hardest function for the 1-, 2-, 3-, and 4-input cases—parity—is now trivial. Knuth examines the complexity of 5-input Boolean functions using AND, OR, and XOR in detail in The Art of Computer Programming, Volume 4A. Section 7.1.2's Algorithm L is the same as our Algorithm 3 above, given for computing 4-input functions. Knuth mentions that to adapt it for 5-input functions one must treat only canonical functions and gives results for 5-input functions with XOR allowed. So another way to check our work is to add XOR to our Algorithm 4 and check that our results match Knuth's.

Because the minimum formula sizes are smaller (at most 12), the computation of sizes with XOR is much faster than before:

	————— # of Functions —————
Size	Canonical	All	All, Cumulative	Time
0	1	10	10
1	3	102	112	< 0.1 seconds
2	5	1140	1252	< 0.1 seconds
3	20	11570	12822	< 0.1 seconds
4	93	109826	122648	< 0.1 seconds
5	366	936440	1059088	0.1 seconds
6	1730	7236880	8295968	0.7 seconds
7	8782	47739088	56035056	4.5 seconds
8	40297	250674320	306709376	24.0 seconds
9	141422	955812256	1262521632	95.5 seconds
10	273277	1945383936	3207905568	200.7 seconds
11	145707	1055912608	4263818176	121.2 seconds
12	4423	31149120	4294967296	65.0 seconds

Knuth does not discuss anything like Algorithm 5, because the search for specific functions does not apply to the AND, OR, and XOR basis. XOR is a non-monotone function (it can both turn bits on and turn bits off), so there is no test like our “if fg OR g == fg” and no small set of “don't care” bits to trim the search for f. The search for an appropriate f in the XOR case would have to try all f of the right size, which is exactly what Algorithm 4 already does.

Volume 4A also considers the problem of building minimal circuits, which are like formulas but can use common subexpressions additional times for free, and the problem of building the shallowest possible circuits. See Section 7.1.2 for all the details.

Code and Web Site

The web site boolean-oracle.swtch.com lets you type in a Boolean expression and gives back the minimal formula for it. It uses tables generated while running Algorithm 5; those tables and the programs described in this post are also available on the site.

Postscript: Generating All Permutations and Inversions

The algorithms given above depend crucially on the step “for each function ff equivalent to f,” which generates all the ff obtained by permuting or inverting inputs to f, but I did not explain how to do that. We already saw that we can manipulate the binary truth table representation directly to turn f into ¬f and to compute combinations of functions. We can also manipulate the binary representation directly to invert a specific input or swap a pair of adjacent inputs. Using those operations we can cycle through all the equivalent functions.

To invert a specific input, let's consider the structure of the truth table. The index of a bit in the truth table encodes the inputs for that entry. For example, the low bit of the index gives the value of the first input. So the even-numbered bits—at indices 0, 2, 4, 6, ...—correspond to the first input being false, while the odd-numbered bits—at indices 1, 3, 5, 7, ...—correspond to the first input being true. Changing just that bit in the index corresponds to changing the single variable, so indices 0, 1 differ only in the value of the first input, as do 2, 3, and 4, 5, and 6, 7, and so on. Given the truth table for f(V, W, X, Y, Z) we can compute the truth table for f(¬V, W, X, Y, Z) by swapping adjacent bit pairs in the original truth table. Even better, we can do all the swaps in parallel using a bitwise operation. To invert a different input, we swap larger runs of bits.

Function		Truth Table (`f` = f(V, W, X, Y, Z))
f(¬V, W, X, Y, Z)		`(f&0x55555555)<< 1 \| (f>> 1)&0x55555555`
f(V, ¬W, X, Y, Z)		`(f&0x33333333)<< 2 \| (f>> 2)&0x33333333`
f(V, W, ¬X, Y, Z)		`(f&0x0f0f0f0f)<< 4 \| (f>> 4)&0x0f0f0f0f`
f(V, W, X, ¬Y, Z)		`(f&0x00ff00ff)<< 8 \| (f>> 8)&0x00ff00ff`
f(V, W, X, Y, ¬Z)		`(f&0x0000ffff)<<16 \| (f>>16)&0x0000ffff`

Being able to invert a specific input lets us consider all possible inversions by building them up one at a time. The Gray code lets us enumerate all possible 5-bit input codes while changing only 1 bit at a time as we move from one input to the next:

0, 1, 3, 2, 6, 7, 5, 4,
12, 13, 15, 14, 10, 11, 9, 8,
24, 25, 27, 26, 30, 31, 29, 28,
20, 21, 23, 22, 18, 19, 17, 16

This minimizes the number of inversions we need: to consider all 32 cases, we only need 31 inversion operations. In contrast, visiting the 5-bit input codes in the usual binary order 0, 1, 2, 3, 4, ... would often need to change multiple bits, like when changing from 3 to 4.

To swap a pair of adjacent inputs, we can again take advantage of the truth table. For a pair of inputs, there are four cases: 00, 01, 10, and 11. We can leave the 00 and 11 cases alone, because they are invariant under swapping, and concentrate on swapping the 01 and 10 bits. The first two inputs change most often in the truth table: each run of 4 bits corresponds to those four cases. In each run, we want to leave the first and fourth alone and swap the second and third. For later inputs, the four cases consist of sections of bits instead of single bits.

Function		Truth Table (`f` = f(V, W, X, Y, Z))
f(W, V, X, Y, Z)		`f&0x99999999 \| (f&0x22222222)<<1 \| (f>>1)&0x22222222`
f(V, X, W, Y, Z)		`f&0xc3c3c3c3 \| (f&0x0c0c0c0c)<<1 \| (f>>1)&0x0c0c0c0c`
f(V, W, Y, X, Z)		`f&0xf00ff00f \| (f&0x00f000f0)<<1 \| (f>>1)&0x00f000f0`
f(V, W, X, Z, Y)		`f&0xff0000ff \| (f&0x0000ff00)<<8 \| (f>>8)&0x0000ff00`

Being able to swap a pair of adjacent inputs lets us consider all possible permutations by building them up one at a time. Again it is convenient to have a way to visit all permutations by applying only one swap at a time. Here Volume 4A comes to the rescue. Section 7.2.1.2 is titled “Generating All Permutations,” and Knuth delivers many algorithms to do just that. The most convenient for our purposes is Algorithm P, which generates a sequence that considers all permutations exactly once with only a single swap of adjacent inputs between steps. Knuth calls it Algorithm P because it corresponds to the “Plain changes” algorithm used by bell ringers in 17th century England to ring a set of bells in all possible permutations. The algorithm is described in a manuscript written around 1653!

We can examine all possible permutations and inversions by nesting a loop over all permutations inside a loop over all inversions, and in fact that's what my program does. Knuth does one better, though: his Exercise 7.2.1.2-20 suggests that it is possible to build up all the possibilities using only adjacent swaps and inversion of the first input. Negating arbitrary inputs is not hard, though, and still does minimal work, so the code sticks with Gray codes and Plain changes.

Zip Files All The Way Down

2010-03-18T00:00:00-04:00

Stephen Hawking begins A Brief History of Time with this story:

A well-known scientist (some say it was Bertrand Russell) once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: “What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise.” The scientist gave a superior smile before replying, “What is the tortoise standing on?” “You're very clever, young man, very clever,” said the old lady. “But it's turtles all the way down!”

Scientists today are pretty sure that the universe is not actually turtles all the way down, but we can create that kind of situation in other contexts. For example, here we have video monitors all the way down and set theory books all the way down, and shopping carts all the way down.

And here's a computer storage equivalent: look inside r.zip. It's zip files all the way down: each one contains another zip file under the name r/r.zip. (For the die-hard Unix fans, r.tar.gz is gzipped tar files all the way down.) Like the line of shopping carts, it never ends, because it loops back onto itself: the zip file contains itself! And it's probably less work to put together a self-reproducing zip file than to put together all those shopping carts, at least if you're the kind of person who would read this blog. This post explains how.

Before we get to self-reproducing zip files, though, we need to take a brief detour into self-reproducing programs.

Self-reproducing programs

The idea of self-reproducing programs dates back to the 1960s. My favorite statement of the problem is the one Ken Thompson gave in his 1983 Turing Award address:

In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. Since this is an exercise divorced from reality, the usual vehicle was FORTRAN. Actually, FORTRAN was the language of choice for the same reason that three-legged races are popular.

More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source. If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to do it. The part about “shortest” was just an incentive to demonstrate skill and determine a winner.

Spoiler alert! I agree: if you have never done this, I urge you to try it on your own. The internet makes it so easy to look things up that it's refreshing to discover something yourself once in a while. Go ahead and spend a few days figuring out. This blog will still be here when you get back. (If you don't mind the spoilers, the entire Turing award address is worth reading.)

(Spoiler blocker.)

http://www.robertwechsler.com/projects.html

Let's try to write a Python program that prints itself. It will probably be a print statement, so here's a first attempt, run at the interpreter prompt:

>>> print 'hello'
hello

That didn't quite work. But now we know what the program is, so let's print it:

>>> print "print 'hello'"
print 'hello'

That didn't quite work either. The problem is that when you execute a simple print statement, it only prints part of itself: the argument to the print. We need a way to print the rest of the program too.

The trick is to use recursion: you write a string that is the whole program, but with itself missing, and then you plug it into itself before passing it to print.

>>> s = 'print %s'; print s % repr(s)
print 'print %s'

Not quite, but closer: the problem is that the string s isn't actually the program. But now we know the general form of the program: s = '%s'; print s % repr(s). That's the string to use.

>>> s = 's = %s; print s %% repr(s)'; print s % repr(s)
s = 's = %s; print s %% repr(s)'; print s % repr(s)

Recursion for the win.

This form of self-reproducing program is often called a quine, in honor of the philosopher and logician W. V. O. Quine, who discovered the paradoxical sentence:

“Yields falsehood when preceded by its quotation”
yields falsehood when preceded by its quotation.

The simplest English form of a self-reproducing quine is a command like:

Print this, followed by its quotation:
“Print this, followed by its quotation:”

There's nothing particularly special about Python that makes quining possible. The most elegant quine I know is a Scheme program that is a direct, if somewhat inscrutable, translation of that sentiment:

((lambda (x) `(,x ',x))
'(lambda (x) `(,x ',x)))

I think the Go version is a clearer translation, at least as far as the quoting is concerned:

/* Go quine */
package main
import "fmt"
func main() {
 fmt.Printf("%s%c%s%c\n", q, 0x60, q, 0x60)
}
var q = `/* Go quine */
package main
import "fmt"
func main() {
 fmt.Printf("%s%c%s%c\n", q, 0x60, q, 0x60)
}
var q = `

(I've colored the data literals green throughout to make it clear what is program and what is data.)

The Go program has the interesting property that, ignoring the pesky newline at the end, the entire program is the same thing twice (/* Go quine */ ... q = `). That got me thinking: maybe it's possible to write a self-reproducing program using only a repetition operator. And you know what programming language has essentially only a repetition operator? The language used to encode Lempel-Ziv compressed files like the ones used by gzip and zip.

Self-reproducing Lempel-Ziv programs

Lempel-Ziv compressed data is a stream of instructions with two basic opcodes: literal(n) followed by n bytes of data means write those n bytes into the decompressed output, and repeat(d, n) means look backward d bytes from the current location in the decompressed output and copy the n bytes you find there into the output stream.

The programming exercise, then, is this: write a Lempel-Ziv program using just those two opcodes that prints itself when run. In other words, write a compressed data stream that decompresses to itself. Feel free to assume any reasonable encoding for the literal and repeat opcodes. For the grand prize, find a program that decompresses to itself surrounded by an arbitrary prefix and suffix, so that the sequence could be embedded in an actual gzip or zip file, which has a fixed-format header and trailer.

Spoiler alert! I urge you to try this on your own before continuing to read. It's a great way to spend a lazy afternoon, and you have one critical advantage that I didn't: you know there is a solution.

(Spoiler blocker.)

http://www.robertwechsler.com/thebest.html

By the way, here's r.gz, gzip files all the way down.

$ gunzip < r.gz > r
$ cmp r r.gz
$

The nice thing about r.gz is that even broken web browsers that ordinarily decompress downloaded gzip data before storing it to disk will handle this file correctly!

Enough stalling to hide the spoilers. Let's use this shorthand to describe Lempel-Ziv instructions: Ln and Rn are shorthand for literal(n) and repeat(n, n), and the program assumes that each code is one byte. L0 is therefore the Lempel-Ziv no-op; L5 hello prints hello; and so does L3 hel R1 L1 o.

Here's a Lempel-Ziv program that prints itself. (Each line is one instruction.)

	Code	Output
no-op	`L0`
no-op	`L0`
no-op	`L0`
print 4 bytes	`L4 L0 L0 L0 L4`	`L0 L0 L0 L4`
repeat last 4 printed bytes	`R4`	`L0 L0 L0 L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 L0 L0 L0 L0`	`L0 L0 L0 L0`

(The two columns Code and Output contain the same byte sequence.)

The interesting core of this program is the 6-byte sequence L4 R4 L4 R4 L4 R4, which prints the 8-byte sequence R4 L4 R4 L4 R4 L4 R4 L4. That is, it prints itself with an extra byte before and after.

When we were trying to write the self-reproducing Python program, the basic problem was that the print statement was always longer than what it printed. We solved that problem with recursion, computing the string to print by plugging it into itself. Here we took a different approach. The Lempel-Ziv program is particularly repetitive, so that a repeated substring ends up containing the entire fragment. The recursion is in the representation of the program rather than its execution. Either way, that fragment is the crucial point. Before the final R4, the output lags behind the input. Once it executes, the output is one code ahead.

The L0 no-ops are plugged into a more general variant of the program, which can reproduce itself with the addition of an arbitrary three-byte prefix and suffix:

	Code	Output
print 4 bytes	`L4 aa bb cc L4`	`aa bb cc L4`
repeat last 4 printed bytes	`R4`	`aa bb cc L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 R4 xx yy zz`	`R4 xx yy zz`
repeat last 4 printed bytes	`R4`	`R4 xx yy zz`

(The byte sequence in the Output column is aa bb cc, then the byte sequence from the Code column, then xx yy zz.)

It took me the better part of a quiet Sunday to get this far, but by the time I got here I knew the game was over and that I'd won. From all that experimenting, I knew it was easy to create a program fragment that printed itself minus a few instructions or even one that printed an arbitrary prefix and then itself, minus a few instructions. The extra aa bb cc in the output provides a place to attach such a program fragment. Similarly, it's easy to create a fragment to attach to the xx yy zz that prints itself, minus the first three instructions, plus an arbitrary suffix. We can use that generality to attach an appropriate header and trailer.

Here is the final program, which prints itself surrounded by an arbitrary prefix and suffix. [P] denotes the p-byte compressed form of the prefix P; similarly, [S] denotes the s-byte compressed form of the suffix S.

	Code	Output
print prefix	`[P]`	`P`
print p+1 bytes	`L`p+1 `[P] L`p+1	`[P] L`p+1
repeat last p+1 printed bytes	`R`p+1	`[P] L`p+1
print 1 byte	`L1 R`p+1	`R`p+1
print 1 byte	`L1 L1`	`L1`
print 4 bytes	`L4 R`p+1 `L1 L1 L4`	`R`p+1 `L1 L1 L4`
repeat last 4 printed bytes	`R4`	`R`p+1 `L1 L1 L4`
print 4 bytes	`L4 R4 L4 R4 L4`	`R4 L4 R4 L4`
repeat last 4 printed bytes	`R4`	`R4 L4 R4 L4`
print 4 bytes	`L4 R4 L0 L0 L`s+1	`R4 L0 L0 L`s+1
repeat last 4 printed bytes	`R4`	`R4 L0 L0 L`s+1
no-op	`L0`
no-op	`L0`
print s+1 bytes	`L`s+1 `R`s+1 `[S]`	`R`s+1 `[S]`
repeat last s+1 bytes	`R`s+1	`R`s+1 `[S]`
print suffix	`[S]`	`S`

(The byte sequence in the Output column is P, then the byte sequence from the Code column, then S.)

Self-reproducing zip files

Now the rubber meets the road. We've solved the main theoretical obstacle to making a self-reproducing zip file, but there are a couple practical obstacles still in our way.

The first obstacle is to translate our self-reproducing Lempel-Ziv program, written in simplified opcodes, into the real opcode encoding. RFC 1951 describes the DEFLATE format used in both gzip and zip: a sequence of blocks, each of which is a sequence of opcodes encoded using Huffman codes. Huffman codes assign different length bit strings to different opcodes, breaking our assumption above that opcodes have fixed length. But wait! We can, with some care, find a set of fixed-size encodings that says what we need to be able to express.

In DEFLATE, there are literal blocks and opcode blocks. The header at the beginning of a literal block is 5 bytes:

If the translation of our L opcodes above are 5 bytes each, the translation of the R opcodes must also be 5 bytes each, with all the byte counts above scaled by a factor of 5. (For example, L4 now has a 20-byte argument, and R4 repeats the last 20 bytes of output.) The opcode block with a single repeat(20,20) instruction falls well short of 5 bytes:

Luckily, an opcode block containing two repeat(20,10) instructions has the same effect and is exactly 5 bytes:

Encoding the other sized repeats (Rp+1 and Rs+1) takes more effort and some sleazy tricks, but it turns out that we can design 5-byte codes that repeat any amount from 9 to 64 bytes. For example, here are the repeat blocks for 10 bytes and for 40 bytes:

The repeat block for 10 bytes is two bits too short, but every repeat block is followed by a literal block, which starts with three zero bits and then padding to the next byte boundary. If a repeat block ends two bits short of a byte but is followed by a literal block, the literal block's padding will insert the extra two bits. Similarly, the repeat block for 40 bytes is five bits too long, but they're all zero bits. Starting a literal block five bits too late steals the bits from the padding. Both of these tricks only work because the last 7 bits of any repeat block are zero and the bits in the first byte of any literal block are also zero, so the boundary isn't directly visible. If the literal block started with a one bit, this sleazy trick wouldn't work.

The second obstacle is that zip archives (and gzip files) record a CRC32 checksum of the uncompressed data. Since the uncompressed data is the zip archive, the data being checksummed includes the checksum itself. So we need to find a value x such that writing x into the checksum field causes the file to checksum to x. Recursion strikes back.

The CRC32 checksum computation interprets the entire file as a big number and computes the remainder when you divide that number by a specific constant using a specific kind of division. We could go through the effort of setting up the appropriate equations and solving for x. But frankly, we've already solved one nasty recursive puzzle today, and enough is enough. There are only four billion possibilities for x: we can write a program to try each in turn, until it finds one that works.

If you want to recreate these files yourself, there are a few more minor obstacles, like making sure the tar file is a multiple of 512 bytes and compressing the rather large zip trailer to at most 59 bytes so that Rs+1 is at most R64. But they're just a simple matter of programming.

So there you have it: r.gz (gzip files all the way down), r.tar.gz (gzipped tar files all the way down), and r.zip (zip files all the way down). I regret that I have been unable to find any programs that insist on decompressing these files recursively, ad infinitum. It would have been fun to watch them squirm, but it looks like much less sophisticated zip bombs have spoiled the fun.

If you're feeling particularly ambitious, here is rgzip.go, the Go program that generated these files. I wonder if you can create a zip file that contains a gzipped tar file that contains the original zip file. Ken Thompson suggested trying to make a zip file that contains a slightly larger copy of itself, recursively, so that as you dive down the chain of zip files each one gets a little bigger. (If you do manage either of these, please leave a comment.)

P.S. I can't end the post without sharing my favorite self-reproducing program: the one-line shell script #!/bin/cat.

UTF-8: Bits, Bytes, and Benefits

2010-03-05T00:00:00-05:00

UTF-8 is a way to encode Unicode code points—integer values from 0 through 10FFFF—into a byte stream, and it is far simpler than many people realize. The easiest way to make it confusing or complicated is to treat it as a black box, never looking inside. So let's start by looking inside. Here it is:


Unicode code points		UTF-8 encoding (binary)

00-7F	(7 bits)	0tuvwxyz
0080-07FF	(11 bits)	110pqrst 10uvwxyz
0800-FFFF	(16 bits)	1110jklm 10npqrst 10uvwxyz
010000-10FFFF	(21 bits)	11110efg 10hijklm 10npqrst 10uvwxyz

The convenient properties of UTF-8 are all consequences of the choice of encoding.

All ASCII files are already UTF-8 files.
The first 128 Unicode code points are the 7-bit ASCII character set, and UTF-8 preserves their one-byte encoding.
ASCII bytes always represent themselves in UTF-8 files. They never appear as part of other UTF-8 sequences.
All the non-ASCII UTF-8 sequences consist of bytes with the high bit set, so if you see the byte 0x7A in a UTF-8 file, you can be sure it represents the character z.
ASCII bytes are always represented as themselves in UTF-8 files. They cannot be hidden inside multibyte UTF-8 sequences.
The ASCII z 01111010 cannot be encoded as a two-byte UTF-8 sequence 11000001 10111010. Code points must be encoded using the shortest possible sequence. A corollary is that decoders must detect long-winded sequences as invalid. In practice, it is useful for a decoder to use the Unicode replacement character, code point FFFD, as the decoding of an invalid UTF-8 sequence rather than stop processing the text.
UTF-8 is self-synchronizing.
Let's call a byte of the form 10xxxxxx a continuation byte. Every UTF-8 sequence is a byte that is not a continuation byte followed by zero or more continuation bytes. If you start processing a UTF-8 file at an arbitrary point, you might not be at the beginning of a UTF-8 encoding, but you can easily find one: skip over continuation bytes until you find a non-continuation byte. (The same applies to scanning backward.)
Substring search is just byte string search.
Properties 2, 3, and 4 imply that given a string of correctly encoded UTF-8, the only way those bytes can appear in a larger UTF-8 text is when they represent the same code points. So you can use any 8-bit safe byte at a time search function, like strchr or strstr, to run the search.
Most programs that handle 8-bit files safely can handle UTF-8 safely.
This also follows from Properties 2, 3, and 4. I say “most” programs, because programs that take apart a byte sequence expecting one character per byte will not behave correctly, but very few programs do that. It is far more common to split input at newline characters, or split whitespace-separated fields, or do other similar parsing around specific ASCII characters. For example, Unix tools like cat, cmp, cp, diff, echo, head, tail, and tee can process UTF-8 files as if they were plain ASCII files. Most operating system kernels should also be able to handle UTF-8 file names without any special arrangement, since the only operations done on file names are comparisons and splitting at /. In contrast, tools like grep, sed, and wc, which inspect arbitrary individual characters, do need modification.
UTF-8 sequences sort in code point order.
You can verify this by inspecting the encodings in the table above. This means that Unix tools like join, ls, and sort (without options) don't need to handle UTF-8 specially.
UTF-8 has no “byte order.”
UTF-8 is a byte encoding. It is not little endian or big endian. Unicode defines a byte order mark (BOM) code point FFFE, which are used to determine the byte order of a stream of raw 16-bit values, like UCS-2 or UTF-16. It has no place in a UTF-8 file. Some programs like to write a UTF-8-encoded BOM at the beginning of UTF-8 files, but this is unnecessary (and annoying to programs that don't expect it).

UTF-8 does give up the ability to do random access using code point indices. Programs that need to jump to the nth Unicode code point in a file or on a line—text editors are the canonical example—will typically convert incoming UTF-8 to an internal representation like an array of code points and then convert back to UTF-8 for output, but most programs are simpler when written to manipulate UTF-8 directly.

Programs that make UTF-8 more complicated than it needs to be are typically trying to be too general, not wanting to make assumptions that might not be true of other encodings. But there are good tools to convert other encodings to UTF-8, and it is slowly becoming the standard encoding: even the fraction of web pages written in UTF-8 is nearing 50%. UTF-8 was explicitly designed to have these nice properties. Take advantage of them.

For more on UTF-8, see “Hello World or Καλημέρα κόσμε or こんにちは世界,” by Rob Pike and Ken Thompson, and also this history.

Notes: Property 6 assumes the tools do not strip the high bit from each byte. Such mangling was common years ago but is very uncommon now. Property 7 assumes the comparison is done treating the bytes as unsigned, but such behavior is mandated by the ANSI C standard for memcmp, strcmp, and strncmp.

Computing History at Bell Labs

2008-04-09T00:00:00-04:00

In 1997, on his retirement from Bell Labs, Doug McIlroy gave a fascinating talk about the “History of Computing at Bell Labs.” That page contains audio for the talk in Real Audio format (it was 1997). Almost ten years ago I transcribed the audio but never did anything with it. The transcript is below.

My favorite parts of the talk are the description of the bi-quinary decimal relay calculator and the description of a team that spent over a year tracking down a race condition bug in a missile detector (reliability was king: today you'd just stamp “cannot reproduce” and send the report back). But the whole thing contains many fantastic stories. It's well worth the read or listen. I also like his recollection of programming using cards: “It's the kind of thing you can be nostalgic about, but it wasn't actually fun.”

For more information, Bernard D. Holbrook and W. Stanley Brown's 1982 technical report “A History of Computing Research at Bell Laboratories (1937-1975)” covers the earlier history in more detail.

Corrections added August 19, 2009.

Transcript of “History of Computing at Bell Labs:”

Computing at Bell Labs is certainly an outgrowth of the mathematics department, which grew from that first hiring in 1897, G A Campbell. When Bell Labs was formally founded in 1925, what it had been was the engineering department of Western Electric. When it was formally founded in 1925, almost from the beginning there was a math department with Thornton Fry as the department head, and if you look at some of Fry's work, it turns out that he was fussing around in 1929 with trying to discover information theory. It didn't actually gel until twenty years later with Shannon.

1:10 Of course, most of the mathematics at that time was continuous. One was interested in analyzing circuits and propagation. And indeed, this is what led to the growth of computing in Bell Laboratories. The computations could not all be done symbolically. There were not closed form solutions. There was lots of numerical computation done. The math department had a fair stable of computers, which in those days meant people. [laughter]

2:00 And in the late '30s, George Stibitz had an idea that some of the work that they were doing on hand calculators might be automated by using some of the equipment that the Bell System was installing in central offices, namely relay circuits. He went home, and on his kitchen table, he built out of relays a binary arithmetic circuit. He decided that binary was really the right way to compute. However, when he finally came to build some equipment, he determined that binary to decimal conversion and decimal to binary conversion was a drag, and he didn't want to put it in the equipment, and so he finally built in 1939, a relay calculator that worked in decimal, and it worked in complex arithmetic. Do you have a hand calculator now that does complex arithmetic? Ten-digit, I believe, complex computations: add, subtract, multiply, and divide. The I/O equipment was teletypes, so essentially all the stuff to make such machines out of was there. Since the I/O was teletypes, it could be remotely accessed, and there were in fact four stations in the West Street Laboratories of Bell Labs. West Street is down on the left side of Manhattan. I had the good fortune to work there one summer, right next to a district where you're likely to get bowled over by rolling ?beads? hanging from racks or tumbling ?cabbages?. The building is still there. It's called Westbeth Apartments. It's now an artist's colony.

4:29 Anyway, in West Street, there were four separate remote stations from which the complex calculator could be accessed. It was not time sharing. You actually reserved your time on the machine, and only one of the four terminals worked at a time. In 1940, this machine was shown off to the world at the AMS annual convention, which happened to be held in Hanover at Dartmouth that year, and mathematicians could wonder at remote computing, doing computation on an electromechanical calculator at 300 miles away.

5:22 Stibitz went on from there to make a whole series of relay machines. Many of them were made for the government during the war. They were named, imaginatively, Mark I through Mark VI. I have read some of his patents. They're kind of fun. One is a patent on conditional transfer. [laughter] And how do you do a conditional transfer? Well these gadgets were, the relay calculator was run from your fingers, I mean the complex calculator. The later calculators, of course, if your fingers were a teletype, you could perfectly well feed a paper tape in, because that was standard practice. And these later machines were intended really to be run more from paper tape. And the conditional transfer was this: you had two teletypes, and there's a code that says "time to read from the other teletype". Loops were of course easy to do. You take paper and [laughter; presumably Doug curled a piece of paper to form a physical loop]. These machines never got to the point of having stored programs. But they got quite big. I saw, one of them was here in 1954, and I did see it, behind glass, and if you've ever seen these machines in the, there's one in the Franklin Institute in Philadelphia, and there's one in the Science Museum in San Jose, you know these machines that drop balls that go wandering sliding around and turning battle wheels and ringing bells and who knows what. It kind of looked like that. It was a very quiet room, with just a little clicking of relays, which is what a central office used to be like. It was the one air-conditioned room in Murray Hill, I think. This machine ran, the Mark VI, well I think that was the Mark V, the Mark VI actually went to Aberdeen. This machine ran for a good number of years, probably six, eight. And it is said that it never made an undetected error. [laughter]

8:30 What that means is that it never made an error that it did not diagnose itself and stop. Relay technology was very very defensive. The telephone switching system had to work. It was full of self-checking, and so were the calculators, so were the calculators that Stibitz made.

9:04 Arithmetic was done in bi-quinary, a two out of five representation for decimal integers, and if there weren't exactly two out of five relays activated it would stop. This machine ran unattended over the weekends. People would bring their tapes in, and the operator would paste everybody's tapes together. There was a beginning of job code on the tape and there was also a time indicator. If the machine ran out of time, it automatically stopped and went to the next job. If the machine caught itself in an error, it backed up to the current job and tried it again. They would load this machine on Friday night, and on Monday morning, all the tapes, all the entries would be available on output tapes.

Question: I take it they were using a different representation for loops and conditionals by then.

Doug: Loops were done actually by they would run back and forth across the tape now, on this machine.

10:40 Then came the transistor in '48. At Whippany, they actually had a transistorized computer, which was a respectable minicomputer, a box about this big, running in 1954, it ran from 1954 to 1956 solidly as a test run. The notion was that this computer might fly in an airplane. And during that two-year test run, one diode failed. In 1957, this machine called TRADIC, did in fact fly in an airplane, but to the best of my knowledge, that machine was a demonstration machine. It didn't turn into a production machine. About that time, we started buying commercial machines. It's wonderful to think about the set of different architectures that existed in that time. The first machine we got was called a CPC from IBM. And all it was was a big accounting machine with a very special plugboard on the side that provided an interpreter for doing ten-digit decimal arithmetic, including opcodes for the trig functions and square root.

12:30 It was also not a computer as we know it today, because it wasn't stored program, it had twenty-four memory locations as I recall, and it took its program instead of from tapes, from cards. This was not a total advantage. A tape didn't get into trouble if you dropped it on the floor. [laughter]. CPC, the operator would stand in front of it, and there, you would go through loops by taking cards out, it took human intervention, to take the cards out of the output of the card reader and put them in the ?top?. I actually ran some programs on the CPC ?...?. It's the kind of thing you can be nostalgic about, but it wasn't actually fun. [laughter]

13:30 The next machine was an IBM 650, and here, this was a stored program, with the memory being on drum. There was no operating system for it. It came with a manual: this is what the machine does. And Michael Wolontis made an interpreter called the L1 interpreter for this machine, so you could actually program in, the manual told you how to program in binary, and L1 allowed you to give something like 10 for add and 9 for subtract, and program in decimal instead. And of course that machine required interesting optimization, because it was a nice thing if the next program step were stored somewhere -- each program step had the address of the following step in it, and you would try to locate them around the drum so to minimize latency. So there were all kinds of optimizers around, but I don't think Bell Labs made ?...? based on this called "soap" from Carnegie Mellon. That machine didn't last very long. Fortunately, a machine with core memory came out from IBM in about '56, the 704. Bell Labs was a little slow in getting one, in '58. Again, the machine came without an operating system. In fact, but it did have Fortran, which really changed the world. It suddenly made it easy to write programs. But the way Fortran came from IBM, it came with a thing called the Fortran Stop Book. This was a list of what happened, a diagnostic would execute the halt instruction, the operator would go read the panel lights and discover where the machine had stopped, you would then go look up in the stop book what that meant. Bell Labs, with George Mealy and Glenn Hanson, made an operating system, and one of the things they did was to bring the stop book to heel. They took the compiler, replaced all the stop instructions with jumps to somewhere, and allowed the program instead of stopping to go on to the next trial. By the time I arrived at Bell Labs in 1958, this thing was running nicely.

16:36 Bell Labs continued to be a major player in operating systems. This was called BESYS. BE was the share abbreviation for Bell Labs. Each company that belonged to Share, which was the IBM users group, ahd a two letter abbreviation. It's hard to imagine taking all the computer users now and giving them a two-letter abbreviation. BESYS went through many generations, up to BESYS 5, I believe. Each one with innovations. IBM delivered a machine, the 7090, in 1960. This machine had interrupts in it, but IBM didn't use them. But BESYS did. And that sent IBM back to the drawing board to make it work. [Laughter]

17:48 Rob Pike: It also didn't have memory protection.

Doug: It didn't have memory protection either, and a lot of people actually got IBM to put memory protection in the 7090, so that one could leave the operating system resident in the presence of a wild program, an idea that the PC didn't discover until, last year or something like that. [laughter]

Big players then, Dick Hamming, a name that I'm sure everybody knows, was sort of the numerical analysis guru, and a seer. He liked to make outrageous predictions. He predicted in 1960, that half of Bell Labs was going to be busy doing something with computers eventually. ?...? exaggerating some ?...? abstract in his thought. He was wrong. Half was a gross underestimate. Dick Hamming retired twenty years ago, and just this June he completed his full twenty years term in the Navy, which entitles him again to retire from the Naval Postgraduate Institute in Monterey. Stibitz, incidentally died, I think within the last year. He was doing medical instrumentation at Dartmouth essentially, near the end.

20:00 Various problems intrigued, besides the numerical problems, which in fact were stock in trade, and were the real justification for buying machines, until at least the '70s I would say. But some non-numerical problems had begun to tickle the palette of the math department. Even G A Campbell got interested in graph theory, the reason being he wanted to think of all the possible ways you could take the three wires and the various parts of the telephone and connect them together, and try permutations to see what you could do about reducing side ?...? by putting things into the various parts of the circuit, and devised every possibly way of connecting the telephone up. And that was sort of the beginning of combinatorics at Bell Labs. John Reardon, a mathematician parlayed this into a major subject. Two problems which are now deemed as computing problems, have intrigued the math department for a very long time, and those are the minimum spanning tree problem, and the wonderfully ?comment about Joe Kruskal, laughter?

21:50 And in the 50s Bob Prim and Kruskal, who I don't think worked on the Labs at that point, invented algorithms for the minimum spanning tree. Somehow or other, computer scientists usually learn these algorithms, one of the two at least, as Dijkstra's algorithm, but he was a latecomer.

Another pet was the traveling salesman. There's been a long list of people at Bell Labs who played with that: Shen Lin and Ron Graham and David Johnson and dozens more, oh and ?...?. And then another problem is the Steiner minimum spanning tree, where you're allowed to add points to the graph. Every one of these problems grew, actually had a justification in telephone billing. One jurisdiction or another would specify that the way you bill for a private line network was in one jurisdiction by the minimum spanning tree. In another jurisdiction, by the traveling salesman route. NP-completeness wasn't a word in the vocabulary of ?...? [laughter]. And the Steiner problem came up because customers discovered they could beat the system by inventing offices in the middle of Tennessee that had nothing to do with their business, but they could put the office at a Steiner point and reduce their phone bill by adding to what the service that the Bell System had to give them. So all of these problems actually had some justification in billing besides the fun.

24:15 Come the 60s, we actually started to hire people for computing per se. I was perhaps the third person who was hired with a Ph.D. to help take care of the computers and I'm told that the then director and head of the math department, Hendrick Bode, had said to his people, "yeah, you can hire this guy, instead of a real mathematician, but what's he gonna be doing in five years?" [laughter]

25:02 Nevertheless, we started hiring for real in about '67. Computer science got split off from the math department. I had the good fortune to move into the office that I've been in ever since then. Computing began to make, get a personality of its own. One of the interesting people that came to Bell Labs for a while was Hao Wang. Is his name well known? [Pause] One nod. Hao Wang was a philosopher and logician, and we got a letter from him in England out of the blue saying "hey you know, can I come and use your computers? I have an idea about theorem proving." There was theorem proving in the air in the late 50s, and it was mostly pretty thin stuff. Obvious that the methods being proposed wouldn't possibly do anything more difficult than solve tic-tac-toe problems by enumeration. Wang had a notion that he could mechanically prove theorems in the style of Whitehead and Russell's great treatise Principia Mathematica in the early patr of the century. He came here, learned how to program in machine language, and took all of Volume I of Principia Mathematica -- if you've ever hefted Principia, well that's about all it's good for, it's a real good door stop. It's really big. But it's theorem after theorem after theorem in propositional calculus. Of course, there's a decision procedure for propositional calculus, but he was proving them more in the style of Whitehead and Russell. And when he finally got them all coded and put them into the computer, he proved the entire contents of this immense book in eight minutes. This was actually a neat accomplishment. Also that was the beginning of all the language theory. We hired people like Al Aho and Jeff Ullman, who probed around every possible model of grammars, syntax, and all of the things that are now in the standard undergraduate curriculum, were pretty well nailed down here, on syntax and finite state machines and so on were pretty well nailed down in the 60s. Speaking of finite state machines, in the 50s, both Mealy and Moore, who have two of the well-known models of finite state machines, were here.

28:40 During the 60s, we undertook an enormous development project in the guise of research, which was MULTICS, and it was the notion of MULTICS was computing was the public utility of the future. Machines were very expensive, and ?indeed? like you don't own your own electric generator, you rely on the power company to do generation for you, and it was seen that this was a good way to do computing -- time sharing -- and it was also recognized that shared data was a very good thing. MIT pioneered this and Bell Labs joined in on the MULTICS project, and this occupied five years of system programming effort, until Bell Labs pulled out, because it turned out that MULTICS was too ambitious for the hardware at the time, and also with 80 people on it was not exactly a research project. But, that led to various people who were on the project, in particular Ken Thompson -- right there -- to think about how to -- Dennis Ritchie and Rudd Canaday were in on this too -- to think about how you might make a pleasant operating system with a little less resources.

30:30 And Ken found -- this is a story that's often been told, so I won't go into very much of unix -- Ken found an old machine cast off in the corner, the PDP-7, and put up this little operating system on it, and we had immense GE635 available at the comp center at the time, and I remember as the department head, muscling in to use this little computer to be, to get to be Unix's first user, customer, because it was so much pleasanter to use this tiny machine than it was to use the big and capable machine in the comp center. And of course the rest of the story is known to everybody and has affected all college campuses in the country.

31:33 Along with the operating system work, there was a fair amount of language work done at Bell Labs. Often curious off-beat languages. One of my favorites was called Blodi, B L O D I, a block diagram compiler by Kelly and Vyssotsky. Perhaps the most interesting early uses of computers in the sense of being unexpected, were those that came from the acoustics research department, and what the Blodi compiler was invented in the acoustic research department for doing digital simulations of sample data system. DSPs are classic sample data systems, where instead of passing analog signals around, you pass around streams of numerical values. And Blodi allowed you to say here's a delay unit, here's an amplifier, here's an adder, the standard piece parts for a sample data system, and each one was described on a card, and with description of what it's wired to. It was then compiled into one enormous single straight line loop for one time step. Of course, you had to rearrange the code because some one part of the sample data system would feed another and produce really very efficient 7090 code for simulating sample data systems. By in large, from that time forth, the acoustic department stopped making hardware. It was much easier to do signal processing digitally than previous ways that had been analog. Blodi had an interesting property. It was the only programming language I know where -- this is not my original observation, Vyssotsky said -- where you could take the deck of cards, throw it up the stairs, and pick them up at the bottom of the stairs, feed them into the computer again, and get the same program out. Blodi had two, aside from syntax diagnostics, it did have one diagnostic when it would fail to compile, and that was "somewhere in your system is a loop that consists of all delays or has no delays" and you can imagine how they handled that.

35:09 Another interesting programming language of the 60s was Ken Knowlten's Beflix. This was for making movies on something with resolution kind of comparable to 640x480, really coarse, and the programming notion in here was bugs. You put on your grid a bunch of bugs, and each bug carried along some data as baggage, and then you would do things like cellular automata operations. You could program it or you could kind of let it go by itself. If a red bug is next to a blue bug then it turns into a green bug on the following step and so on. 36:28 He and Lillian Schwartz made some interesting abstract movies at the time. It also did some interesting picture processing. One wonderful picture of a reclining nude, something about the size of that blackboard over there, all made of pixels about a half inch high each with a different little picture in it, picked out for their density, and so if you looked at it close up it consisted of pickaxes and candles and dogs, and if you looked at it far enough away, it was a reclining nude. That picture got a lot of play all around the country.

Lorinda Cherry: That was with Leon, wasn't it? That was with Leon Harmon.

Doug: Was that Harmon?

Lorinda: ?...?

Doug: Harmon was also an interesting character. He did more things than pictures. I'm glad you reminded me of him. I had him written down here. Harmon was a guy who among other things did a block diagram compiler for writing a handwriting recognition program. I never did understand how his scheme worked, and in fact I guess it didn't work too well. [laughter] It didn't do any production ?things? but it was an absolutely immense sample data circuit for doing handwriting recognition. Harmon's most famous work was trying to estimate the information content in a face. And every one of these pictures which are a cliche now, that show a face digitized very coarsely, go back to Harmon's first psychological experiments, when he tried to find out how many bits of picture he needed to try to make a face recognizable. He went around and digitized about 256 faces from Bell Labs and did real psychological experiments asking which faces could be distinguished from other ones. I had the good fortune to have one of the most distinguishable faces, and consequently you'll find me in freshman psychology texts through no fault of my own.

39:15 Another thing going on the 60s was the halting beginning here of interactive computing. And again the credit has to go to the acoustics research department, for good and sufficient reason. They wanted to be able to feed signals into the machine, and look at them, and get them back out. They bought yet another weird architecture machine called the Packard Bell 250, where the memory elements were mercury delay lines.

Question: Packard Bell?

Doug: Packard Bell, same one that makes PCs today.

40:10 They hung this off of the comp center 7090 and put in a scheme for quickly shipping jobs into the job stream on the 7090. The Packard Bell was the real-time terminal that you could play with and repair stuff, ?...? off the 7090, get it back, and then you could play it. From that grew some graphics machines also, built by ?...? et al. And it was one of the old graphics machines in fact that Ken picked up to build Unix on.

40:55 Another thing that went on in the acoustics department was synthetic speech and music. Max Mathews, who was the the director of the department has long been interested in computer music. In fact since retirement he spent a lot of time with Pierre Boulez in Paris at a wonderful institute with lots of money simply for making synthetic music. He had a language called Music 5. Synthetic speech or, well first of all simply speech processing was pioneered particularly by John Kelly. I remember my first contact with speech processing. It was customary for computer operators, for the benefit of computer operators, to put a loudspeaker on the low bit of some register on the machine, and normally the operator would just hear kind of white noise. But if you got into a loop, suddenly the machine would scream, and this signal could be used to the operator "oh the machines in a loop. Go stop it and go on to the next job." I remember feeding them an Ackermann's function routine once. [laughter] They were right. It was a silly loop. But anyway. One day, the operators were ?...?. The machine started singing. Out of the blue. “Help! I'm caught in a loop.”. [laughter] And in a broad Texas accent, which was the recorded voice of John Kelly.

43:14 However. From there Kelly went on to do some speech synthesis. Of course there's been a lot more speech synthesis work done since, by 43:31 folks like Cecil Coker, Joe Olive. But they produced a record, which unfortunately I can't play because records are not modern anymore. And everybody got one in the Bell Labs Record, which is a magazine, contained once a record from the acoustics department, with both speech and music and one very famous combination where the computer played and sang "A Bicycle Built For Two".

?...?

44:32 At the same time as all this stuff is going on here, needless to say computing is going on in the rest of the Labs. it was about early 1960 when the math department lost its monopoly on computing machines and other people started buying them too, but for switching. The first experiments with switching computers were operational in around 1960. They were planned for several years prior to that; essentially as soon as the transistor was invented, the making of electronic rather than electromechanical switching machines was anticipated. Part of the saga of the switching machines is cheap memory. These machines had enormous memories -- thousands of words. [laughter] And it was said that the present worth of each word of memory that programmers saved across the Bell System was something like eleven dollars, as I recall. And it was worthwhile to struggle to save some memory. Also, programs were permanent. You were going to load up the switching machine with switching program and that was going to run. You didn't change it every minute or two. And it would be cheaper to put it in read only memory than in core memory. And there was a whole series of wild read-only memories, both tried and built. The first experimental Essex System had a thing called the flying spot store which was large photographic plates with bits on them and CRTs projecting on the plates and you would detect underneath on the photodetector whether the bit was set or not. That was the program store of Essex. The program store of the first ESS systems consisted of twistors, which I actually am not sure I understand to this day, but they consist of iron wire with a copper wire wrapped around them and vice versa. There were also experiments with an IC type memory called the waffle iron. Then there was a period when magnetic bubbles were all the rage. As far as I know, although microelectronics made a lot of memory, most of the memory work at Bell Labs has not had much effect on ?...?. Nice tries though.

48:28 Another thing that folks began to work on was the application of (and of course, right from the start) computers to data processing. When you owned equipment scattered through every street in the country, and you have a hundred million customers, and you have bills for a hundred million transactions a day, there's really some big data processing going on. And indeed in the early 60s, AT&T was thinking of making its own data processing computers solely for billing. Somehow they pulled out of that, and gave all the technology to IBM, and one piece of that technology went into use in high end equipment called tractor tapes. Inch wide magnetic tapes that would be used for a while.

49:50 By in large, although Bell Labs has participated until fairly recently in data processing in quite a big way, AT&T never really quite trusted the Labs to do it right because here is where the money is. I can recall one occasion when during strike of temporary employees, a fill-in employee like from the Laboratories and so on, lost a day's billing tape in Chicago. And that was a million dollars. And that's generally speaking the money people did not until fairly recently trust Bell Labs to take good care of money, even though they trusted the Labs very well to make extremely reliable computing equipment for switches. The downtime on switches is still spectacular by any industry standards. The design for the first ones was two hours down in 40 years, and the design was met. Great emphasis on reliability and redundancy, testing.

51:35 Another branch of computing was for the government. The whole Whippany Laboratories [time check] Whippany, where we took on contracts for the government particularly in the computing era in anti-missile defense, missile defense, and underwater sound. Missile defense was a very impressive undertaking. It was about in the early '63 time frame when it was estimated the amount of computation to do a reasonable job of tracking incoming missiles would be 30 M floating point operations a second. In the day of the Cray that doesn't sound like a great lot, but it's more than your high end PCs can do. And the machines were supposed to be reliable. They designed the machines at Whippany, a twelve-processor multiprocessor, to no specs, enormously rugged, one watt transistors. This thing in real life performed remarkably well. There were sixty-five missile shots, tests across the Pacific Ocean ?...? and Lorinda Cherry here actually sat there waiting for them to come in. [laughter] And only a half dozen of them really failed. As a measure of the interest in reliability, one of them failed apparently due to processor error. Two people were assigned to look at the dumps, enormous amounts of telemetry and logging information were taken during these tests, which are truly expensive to run. Two people were assigned to look at the dumps. A year later they had not found the trouble. The team was beefed up. They finally decided that there was a race condition in one circuit. They then realized that this particular kind of race condition had not been tested for in all the simulations. They went back and simulated the entire hardware system to see if its a remote possibility of any similar cases, found twelve of them, and changed the hardware. But to spend over a year looking for a bug is a sign of what reliability meant.

54:56 Since I'm coming up on the end of an hour, one could go on and on and on,

Crowd: go on, go on. [laughter]

55:10 Doug: I think I'd like to end up by mentioning a few of the programs that have been written at Bell Labs that I think are most surprising. Of course there are lots of grand programs that have been written.

I already mentioned the block diagram compiler.

Another really remarkable piece of work was eqn, the equation typesetting language, which has been imitated since, by Lorinda Cherry and Brian Kernighan. The notion of taking an auditory syntax, the way people talk about equations, but only talk, this was not borrowed from any written notation before, getting the auditory one down on paper, that was very successful and surprising.

Another of my favorites, and again Lorinda Cherry was in this one, with Bob Morris, was typo. This was a program for finding spelling errors. It didn't know the first thing about spelling. It would read a document, measure its statistics, and print out the words of the document in increasing order of what it thought the likelihood of that word having come from the same statistical source as the document. The words that did not come from the statistical source of the document were likely to be typos, and now I mean typos as distinct from spelling errors, where you actually hit the wrong key. Those tend to be off the wall, whereas phonetic spelling errors you'll never find. And this worked remarkably well. Typing errors would come right up to the top of the list. A really really neat program.

57:50 Another one of my favorites was by Brenda Baker called struct, which took Fortran programs and converted them into a structured programming language called Ratfor, which was Fortran with C syntax. This seemed like a possible undertaking, like something you do by the seat of the pants and you get something out. In fact, folks at Lockheed had done things like that before. But Brenda managed to find theorems that said there's really only one form, there's a canonical form into which you can structure a Fortran program, and she did this. It took your Fortran program, completely mashed it, put it out perhaps in almost certainly a different order than it was in Fortran connected by GOTOs, without any GOTOs, and the really remarkable thing was that authors of the program who clearly knew the way they wrote it in the first place, preferred it after it had been rearranged by Brendan. I was astonished at the outcome of that project.

59:19 Another first that happened around here was by Fred Grampp, who got interested in computer security. One day he decided he would make a program for sniffing the security arrangements on a computer, as a service: Fred would never do anything crooked. [laughter] This particular program did a remarkable job, and founded a whole minor industry within the company. A department was set up to take this idea and parlay it, and indeed ever since there has been some improvement in the way computer centers are managed, at least until we got Berkeley Unix.

60:24 And the last interesting program that I have time to mention is one by Ken Church. He was dealing with -- text processing has always been a continuing ?...? of the research, and in some sense it has an application to our business because we're handling speech, but he got into consulting with the department in North Carolina that has to translate manuals. There are millions of pages of manuals in the Bell System and its successors, and ever since we've gone global, these things had to get translated into many languages.

61:28 To help in this, he was making tools which would put up on the screen, graphed on the screen quickly a piece of text and its translation, because a translator, particularly a technical translator, wants to know, the last time we mentioned this word how was it translated. You don't want to be creative in translating technical text. You'd like to be able to go back into the archives and pull up examples of translated text. And the neat thing here is the idea for how do you align texts in two languages. You've got the original, you've got the translated one, how do you bring up on the screen, the two sentences that go together? And the following scam worked beautifully. This is on western languages. 62:33 Simply look for common four letter tetragrams, four letter combinations between the two and as best as you can, line them up as nearly linearly with the lengths of the two types as possible. And this very simple idea works like storm. Something for nothing. I like that.

63:10 The last thing is one slogan that sort of got started with Unix and is just rife within the industry now. Software tools. We were making software tools in Unix before we knew we were, just like the Molière character was amazed at discovering he'd been speaking prose all his life. [laughter] But then Kernighan and Plauger came along and christened what was going on, making simple generally useful and compositional programs to do one thing and do it well and to fit together. They called it software tools, made a book, wrote a book, and this notion now is abroad in the industry. And it really did begin all up in the little attic room where you [points?] sat for many years writing up here.

Oh I forgot to. I haven't used any slides. I've brought some, but I don't like looking at bullets and you wouldn't either, and I forgot to show you the one exhibit I brought, which I borrowed from Bob Kurshan. When Bell Labs was founded, it had of course some calculating machines, and it had one wonderful computer. This. That was bought in 1918. There's almost no other computing equipment from any time prior to ten years ago that still exists in Bell Labs. This is an integraph. It has two styluses. You trace a curve on a piece of paper with one stylus and the other stylus draws the indefinite integral here. There was somebody in the math department who gave this service to the whole company, with about 24 hours turnaround time, calculating integrals. Our recent vice president Arno Penzias actually did, he calculated integrals differently, with a different background. He had a chemical balance, and he cut the curves out of the paper and weighed them. This was bought in 1918, so it's eighty years old. It used to be shiny metal, it's a little bit rusty now. But it still works.

66:30 Well, that's a once over lightly of a whole lot of things that have gone on at Bell Labs. It's just such a fun place that one I said I just could go on and on. If you're interested, there actually is a history written. This is only one of about six volumes, this is the one that has the mathematical computer sciences, the kind of things that I've mostly talked about here. A few people have copies of them. For some reason, the AT&T publishing house thinks that because they're history they're obsolete, and they stopped printing them. [laughter]

Thank you, and that's all.

Using Uninitialized Memory for Fun and Profit

2008-03-14T00:00:00-04:00

This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improvements: some important operations change from linear to constant time.

Alfred Aho, John Hopcroft, and Jeffrey Ullman's 1974 book The Design and Analysis of Computer Algorithms hints at the trick in an exercise (Chapter 2, exercise 2.12):

Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(||V||²) time to initialize an adjacency matrix.

Jon Bentley's 1986 book Programming Pearls expands on the exercise (Column 1, exercise 8; exercise 9 in the Second Edition):

One problem with trading more space for less time is that initializing the space can itself take a great deal of time. Show how to circumvent this problem by designing a technique to initialize an entry of a vector to zero the first time it is accessed. Your scheme should use constant time for initialization and each vector access; you may use extra space proportional to the size of the vector. Because this method reduces initialization time by using even more space, it should be considered only when space is cheap, time is dear, and the vector is sparse.

Aho, Hopcroft, and Ullman's exercise talks about a matrix and Bentley's exercise talks about a vector, but for now let's consider just a simple set of integers.

One popular representation of a set of n integers ranging from 0 to m is a bit vector, with 1 bits at the positions corresponding to the integers in the set. Adding a new integer to the set, removing an integer from the set, and checking whether a particular integer is in the set are all very fast constant-time operations (just a few bit operations each). Unfortunately, two important operations are slow: iterating over all the elements in the set takes time O(m), as does clearing the set. If the common case is that m is much larger than n (that is, the set is only sparsely populated) and iterating or clearing the set happens frequently, then it could be better to use a representation that makes those operations more efficient. That's where the trick comes in.

Preston Briggs and Linda Torczon's 1993 paper, “An Efficient Representation for Sparse Sets,” describes the trick in detail. Their solution represents the sparse set using an integer array named dense and an integer n that counts the number of elements in dense. The dense array is simply a packed list of the elements in the set, stored in order of insertion. If the set contains the elements 5, 1, and 4, then n = 3 and dense[0] = 5, dense[1] = 1, dense[2] = 4:

Together n and dense are enough information to reconstruct the set, but this representation is not very fast. To make it fast, Briggs and Torczon add a second array named sparse which maps integers to their indices in dense. Continuing the example, sparse[5] = 0, sparse[1] = 1, sparse[4] = 2. Essentially, the set is a pair of arrays that point at each other:

Adding a member to the set requires updating both of these arrays:

add-member(i):
    dense[n] = i
    sparse[i] = n
    n++

It's not as efficient as flipping a bit in a bit vector, but it's still very fast and constant time.

To check whether i is in the set, you verify that the two arrays point at each other for that element:

is-member(i):
    return sparse[i] < n && dense[sparse[i]] == i

If i is not in the set, then it doesn't matter what sparse[i] is set to: either sparse[i] will be bigger than n or it will point at a value in dense that doesn't point back at it. Either way, we're not fooled. For example, suppose sparse actually looks like:

Is-member knows to ignore members of sparse that point past n or that point at cells in dense that don't point back, ignoring the grayed out entries:

Notice what just happened: sparse can have any arbitrary values in the positions for integers not in the set, those values actually get used during membership tests, and yet the membership test behaves correctly! (This would drive valgrind nuts.)

Clearing the set can be done in constant time:

clear-set():
    n = 0

Zeroing n effectively clears dense (the code only ever accesses entries in dense with indices less than n), and sparse can be uninitialized, so there's no need to clear out the old values.

This sparse set representation has one more trick up its sleeve: the dense array allows an efficient implementation of set iteration.

iterate():
    for(i=0; i<n; i++)
        yield dense[i]

Let's compare the run times of a bit vector implementation against the sparse set:

Operation	Bit Vector	Sparse set
is-member	O(1)	O(1)
add-member	O(1)	O(1)
clear-set	O(m)	O(1)
iterate	O(m)	O(n)

The sparse set is as fast or faster than bit vectors for every operation. The only problem is the space cost: two words replace each bit. Still, there are times when the speed differences are enough to balance the added memory cost. Briggs and Torczon point out that liveness sets used during register allocation inside a compiler are usually small and are cleared very frequently, making sparse sets the representation of choice.

Another situation where sparse sets are the better choice is work queue-based graph traversal algorithms. Iteration over sparse sets visits elements in the order they were inserted (above, 5, 1, 4), so that new entries inserted during the iteration will be visited later in the same iteration. In contrast, iteration over bit vectors visits elements in integer order (1, 4, 5), so that new elements inserted during traversal might be missed, requiring repeated iterations.

Returning to the original exercises, it is trivial to change the set into a vector (or matrix) by making dense an array of index-value pairs instead of just indices. Alternately, one might add the value to the sparse array or to a new array. The relative space overhead isn't as bad if you would have been storing values anyway.

Briggs and Torczon's paper implements additional set operations and examines performance speedups from using sparse sets inside a real compiler.

Play Tic-Tac-Toe with Knuth

2008-01-25T00:00:00-05:00

Section 7.1.2 of the Volume 4 pre-fascicle 0A of Donald Knuth's The Art of Computer Programming is titled “Boolean Evaluation.” In it, Knuth considers the construction of a set of nine boolean functions telling the correct next move in an optimal game of tic-tac-toe. In a footnote, Knuth tells this story:

This setup is based on an exhibit from the early 1950s at the Museum of Science and Industry in Chicago, where the author was first introduced to the magic of switching circuits. The machine in Chicago, designed by researchers at Bell Telephone Laboratories, allowed me to go first; yet I soon discovered there was no way to defeat it. Therefore I decided to move as stupidly as possible, hoping that the designers had not anticipated such bizarre behavior. In fact I allowed the machine to reach a position where it had two winning moves; and it seized both of them! Moving twice is of course a flagrant violation of the rules, so I had won a moral victory even though the machine had announced that I had lost.

That story alone is fairly amusing. But turning the page, the reader finds a quotation from Charles Babbage's Passages from the Life of a Philosopher, published in 1864:

I commenced an examination of a game called “tit-tat-to” ... to ascertain what number of combinations were required for all the possible variety of moves and situations. I found this to be comparatively insignificant. ... A difficulty, however, arose of a novel kind. When the automaton had to move, it might occur that there were two different moves, each equally conducive to his winning the game. ... Unless, also, some provision were made, the machine would attempt two contradictory motions.

The only real winning move is not to play.

Crabs, the bitmap terror!

2008-01-09T00:00:00-05:00

Today, window systems seem as inevitable as hierarchical file systems, a fundamental building block of computer systems. But it wasn't always that way. This paper could only have been written in the beginning, when everything about user interfaces was up for grabs.

A bitmap screen is a graphic universe where windows, cursors and icons live in harmony, cooperating with each other to achieve functionality and esthetics. A lot of effort goes into making this universe consistent, the basic law being that every window is a self contained, protected world. In particular, (1) a window shall not be affected by the internal activities of another window. (2) A window shall not be affected by activities of the window system not concerning it directly, i.e. (2.1) it shall not notice being obscured (partially or totally) by other windows or obscuring (partially or totally) other windows, (2.2) it shall not see the image of the cursor sliding on its surface (it can only ask for its position).

Of course it is difficult to resist the temptation to break these rules. Violations can be destructive or non-destructive, useful or pointless. Useful non-destructive violations include programs printing out an image of the screen, or magnifying part of the screen in a lens window. Useful destructive violations are represented by the pen program, which allows one to scribble on the screen. Pointless non-destructive violations include a magnet program, where a moving picture of a magnet attracts the cursor, so that one has to continuously pull away from it to keep working. The first pointless, destructive program we wrote was crabs.

As the crabs walk over the screen, they leave gray behind, “erasing” the apps underfoot:

For the rest of the story, see Luca Cardelli's “Crabs: the bitmap terror!” (6.7MB). Additional details in “Crabs (History and Screen Dumps)” (57.1MB).


1																1		1			1	1	1			1			1	1	1

	1															1	1		1	1	1		1	1			1	1	1		1

		1														1	1	1						1	1

			1														1	1	1						1	1

				1														1	1	1						1	1

					1														1	1	1						1	1

						1														1	1	1						1	1

							1														1	1	1						1	1

								1								1			1	1	1		1				1	1	1		1

									1							1	1							1

										1							1	1							1

											1							1	1							1

												1							1	1							1

													1							1	1							1

														1							1	1							1

															1							1	1							1


1	1						1				1		1				1						1	1			1		1

	1	1									1		1										1		1	1	1		1		1

				1							1		1								1						1	1

						1	1						1								1		1							1

	1							1									1							1

										1	1						1		1						1	1

												1	1						1		1						1	1

							1							1									1							1

	1												1			1	1		1				1	1			1		1		1

											1							1	1							1

													1							1	1							1

							1														1	1	1						1	1

	1								1				1						1				1				1		1		1

					1								1						1								1

							1								1						1								1

			1								1						1								1


1																1		1			1	1	1			1			1	1	1

	1															1	1		1	1	1		1	1			1	1	1		1

		1														1	1	1						1	1

			1														1	1	1						1	1

				1														1	1	1						1	1

					1														1	1	1						1	1

						1														1	1	1						1	1

							1														1	1	1						1	1

								1								1			1	1	1		1				1	1	1		1

									1							1	1							1

										1							1	1							1

											1							1	1							1

												1							1	1							1

													1							1	1							1

														1							1	1							1

															1							1	1							1


1	1						1				1		1				1						1	1			1		1

	1	1									1		1										1		1	1	1		1		1

				1							1		1								1						1	1

						1	1						1								1		1							1

	1							1									1							1

										1	1						1		1						1	1

												1	1						1		1						1	1

							1							1									1							1

	1												1			1	1		1				1	1			1		1		1

											1							1	1							1

													1							1	1							1

							1														1	1	1						1	1

	1								1				1						1				1				1		1		1

					1								1						1								1

							1								1						1								1

			1								1						1								1