research!rsc

Go’s Version Control History

2022-02-14T10:00:00-05:00

Every once in a while someone notices the first commit in the Go repo is dated 1972:

% git log --reverse --stat
commit 7d7c6a97f815e9279d08cfaea7d5efb5e90695a8
Author:     Brian Kernighan <bwk>
AuthorDate: Tue Jul 18 19:05:45 1972 -0500
Commit:     Brian Kernighan <bwk>
CommitDate: Tue Jul 18 19:05:45 1972 -0500

    hello, world

    R=ken
    DELTA=7  (7 added, 0 deleted, 0 changed)

 src/pkg/debug/macho/testdata/hello.b | 7 +++++++
 1 file changed, 7 insertions(+)

...

Obviously something silly is going on, and people usually stop there. But Go’s actual version control history is richer and more interesting. For example, there are a few more fake commits and then the fifth commit is the first real one:

commit 18c5b488a3b2e218c0e0cf2a7d4820d9da93a554
Author:     Robert Griesemer <gri@golang.org>
AuthorDate: Sun Mar 2 20:47:34 2008 -0800
Commit:     Robert Griesemer <gri@golang.org>
CommitDate: Sun Mar 2 20:47:34 2008 -0800

    Go spec starting point.

    SVN=111041

 doc/go_spec | 1197 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 1197 insertions(+)

Why does that commit have a different trailer than the three fake commits?

Subversion

Go started out using Subversion, as part of a small experiment to evaluate Subversion for wider use inside Google. The experiment did not result in wider Subversion use, but the SVN=111041 tag in the first real commit above records that on the original Subversion server, that Go commit was revision 111,041. (Subversion assigns revision numbers in increasing order, and the server was a small monorepo being used for a few other projects besides Go. There were not 111,040 other Go commits that didn’t make it out.)

Perforce

The SVN tags continue in the logs until July 2008, where we see one last SVN commit and then a new form:

commit 777ee7163bba96f2c9b3dfe135d8ad4ab837c062
Author:     Rob Pike <r@golang.org>
AuthorDate: Mon Jul 21 16:18:04 2008 -0700
Commit:     Rob Pike <r@golang.org>
CommitDate: Mon Jul 21 16:18:04 2008 -0700

    map delete

    SVN=128258

 doc/go_lang.txt | 6 ++++++
 1 file changed, 6 insertions(+)

commit 05caa7f82030327ccc9ae63a2b0121a029286501
Author:     Rob Pike <r@golang.org>
AuthorDate: Mon Jul 21 17:10:49 2008 -0700
Commit:     Rob Pike <r@golang.org>
CommitDate: Mon Jul 21 17:10:49 2008 -0700

    help management of empty pkg and lib directories in perforce

    R=gri
    DELTA=4  (4 added, 0 deleted, 0 changed)
    OCL=13328
    CL=13328

 lib/place-holder      | 2 ++
 pkg/place-holder      | 2 ++
 src/cmd/gc/mksys.bash | 0
 3 files changed, 4 insertions(+)

This was the first commit after Go moved from a lightly-used Subversion server to a lightly-used Perforce server. Google was a very heavy Perforce user due to its use of a single giant monorepo for most code. Go was not part of that monorepo world, and at the time, projects that didn’t have to be on the heavily-loaded main server were hosted instead on secondary ones.

At the transition to Perforce, you can see the introduction of telltale DELTA=, OCL=, and CL= tags. Perforce imposes a linear ordering on change lists, like Subversion revisions, but each change list ends up with two sequence numbers: it is assigned one when it is created and uses that number while it is a local, pending change list, including in our code review systems. Then, when it is submitted and becomes part of the official history, it is assigned a new number, to keep submitted changes in order. The OCL= is the original change list number, while the CL= is the final one. The R= line means that gri (Robert Griesemer) reviewed the change before it was submitted, using our internal code review system, then called Mondrian. Because the server was so lightly used (and presumably the review so quick), no new change lists had been created or submitted while this one was pending, and its final submission reused its original number instead of needing to create a new one.

Many other changes have the same OCL= and CL= because they were created and submitted in a single Perforce command, without review, like the next one:

commit c1f5eda7a2465dae196d1fa10baf6bfa9253808a
Author:     Rob Pike <r@golang.org>
AuthorDate: Mon Jul 21 18:06:39 2008 -0700
Commit:     Rob Pike <r@golang.org>
CommitDate: Mon Jul 21 18:06:39 2008 -0700

    change date

    OCL=13331
    CL=13331

 doc/go_lang.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

You can also see from this that the DELTA= line is added by the code review system, not Perforce: this unreviewed change doesn’t have it. (The last two lines are being provided by the git log --stat command as we explore the Git version of these changes.)

The bulk of the pre-open-source development of Go was done on that Perforce server.

Mercurial

The OCL= and CL= lines continue until we get to October 2009, when they switch to a new form:

commit 942d6590d9005f89e971ed5af0374439a264a20e
Author:     Kai Backman <kaib@golang.org>
AuthorDate: Fri Oct 23 11:03:16 2009 -0700
Commit:     Kai Backman <kaib@golang.org>
CommitDate: Fri Oct 23 11:03:16 2009 -0700

    one more argsize fix. we were copying with the correct
    alignment but not enough (duh).

    R=rsc
    APPROVED=rsc
    DELTA=16  (13 added, 0 deleted, 3 changed)
    OCL=36020
    CL=36024

 src/cmd/5g/ggen.c |  2 +-
 test/arm-pass.txt | 17 +++++++++++++++--
 2 files changed, 16 insertions(+), 3 deletions(-)

commit b74fd8ecb17c1959bbf2dbba6ccb8bae6bfabeb8
Author:     Kai Backman <kaib@golang.org>
AuthorDate: Fri Oct 23 12:43:01 2009 -0700
Commit:     Kai Backman <kaib@golang.org>
CommitDate: Fri Oct 23 12:43:01 2009 -0700

    fix build issue cause by transition to hg

    R=rsc
    http://go/go-review/1013012

 src/make-arm.bash | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

That commit introduces yet another kind of trailer line, which says http://go/go-review/1013012. At one point that link pointed, inside Google, to an internal version of the Rietveld App Engine app, which we used for code review on the way to submission to a private Mercurial repo on Google Code Project Hosting. We were doing that conversion, in October 2009, as part of the preparation to open-source Go in November.

It was at this point, during the conversion to Mercurial, that I introduced the “hello, world” commits. The Subversion and Perforce repos had been Google-internal servers, and we had stored essentially all the Go code in the world alongside the Go implementation. We each had “user directories” like /usr/rsc in the repo. Those directories contained various code that wasn’t going out in the release, whether because it was targeting Google-internal technologies or because it was simply not worth publishing. (You can still see references to /usr in a few commit messages that did make it out.)

For the conversion, I ended up with a directory full of patches, one per commit, and a script to run the patches to create a new Mercurial repository. Then I edited the patches (with automated help) to remove the files that weren’t being released, including the entire /usr tree, and to add the new open-source copyright notices to every file.

This took me about a week, and it was annoyingly difficult. If I removed a file from some patches but then it got renamed in others, Mercurial would complain about the rename using a file that hadn’t been created in the first place. And if I added a copyright notice when the file was created, I had to be careful to update later patches to not have merge conflicts when changing the top of the file. And so on. I remember thinking that it was like being a con man who constructs an elaborate false identity and struggles to keep it all straight.

Hello, world

A month earlier, I had created object file parsing packages like debug/macho, and as test data for each of those packages I checked in an object file compiled from a trivial “hello, world” program, along with the source code for them:

commit bf69025825fd2b8e7aac01f27d5c974bd30af542
Author:     Russ Cox <rsc@golang.org>
AuthorDate: Fri Sep 18 11:49:22 2009 -0700
Commit:     Russ Cox <rsc@golang.org>
CommitDate: Fri Sep 18 11:49:22 2009 -0700

    Mach-O file reading

    R=r
    DELTA=784  (784 added, 0 deleted, 0 changed)
    OCL=34715
    CL=34788

 src/pkg/debug/macho/Makefile                       |  12 +
 src/pkg/debug/macho/file.go                        | 374 +++++++++++++++++++++
 src/pkg/debug/macho/file_test.go                   | 159 +++++++++
 src/pkg/debug/macho/macho.go                       | 230 +++++++++++++
 src/pkg/debug/macho/testdata/gcc-386-darwin-exec   | Bin 0 -> 12588 bytes
 src/pkg/debug/macho/testdata/gcc-amd64-darwin-exec | Bin 0 -> 8512 bytes
 .../macho/testdata/gcc-amd64-darwin-exec-debug     | Bin 0 -> 4540 bytes
 7 files changed, 775 insertions(+)

This was the original commit that introduced src/pkg/debug/macho/testdata/hello.c, of course. As I added copyright notices to files, it seemed wrong to add a copyright notice to that hello.c file. Instead, since I had the repo split into this patch-file-per-commit form, it was easy to create a few fake commits that showed at least part of the real history of that program, as an Easter egg for people who looked that closely:

commit 7d7c6a97f815e9279d08cfaea7d5efb5e90695a8
Author:     Brian Kernighan <bwk>
AuthorDate: Tue Jul 18 19:05:45 1972 -0500
Commit:     Brian Kernighan <bwk>
CommitDate: Tue Jul 18 19:05:45 1972 -0500

    hello, world

    R=ken
    DELTA=7  (7 added, 0 deleted, 0 changed)

 src/pkg/debug/macho/testdata/hello.b | 7 +++++++
 1 file changed, 7 insertions(+)

commit 0bb0b61d6a85b2a1a33dcbc418089656f2754d32
Author:     Brian Kernighan <bwk>
AuthorDate: Sun Jan 20 01:02:03 1974 -0400
Commit:     Brian Kernighan <bwk>
CommitDate: Sun Jan 20 01:02:03 1974 -0400

    convert to C

    R=dmr
    DELTA=6  (0 added, 3 deleted, 3 changed)

 src/pkg/debug/macho/testdata/hello.b | 7 -------
 src/pkg/debug/macho/testdata/hello.c | 3 +++
 2 files changed, 3 insertions(+), 7 deletions(-)

commit 0744ac969119db8a0ad3253951d375eb77cfce9e
Author:     Brian Kernighan <research!bwk>
AuthorDate: Fri Apr 1 02:02:04 1988 -0500
Commit:     Brian Kernighan <research!bwk>
CommitDate: Fri Apr 1 02:02:04 1988 -0500

    convert to Draft-Proposed ANSI C

    R=dmr
    DELTA=5  (2 added, 0 deleted, 3 changed)

 src/pkg/debug/macho/testdata/hello.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

commit d82b11e4a46307f1f1415024f33263e819c222b8
Author:     Brian Kernighan <bwk@research.att.com>
AuthorDate: Fri Apr 1 02:03:04 1988 -0500
Commit:     Brian Kernighan <bwk@research.att.com>
CommitDate: Fri Apr 1 02:03:04 1988 -0500

    last-minute fix: convert to ANSI C

    R=dmr
    DELTA=3  (2 added, 0 deleted, 1 changed)

 src/pkg/debug/macho/testdata/hello.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

The July 1972 commit shows the very first “hello, world” program, copied from Brian Kernighan’s “A Tutorial Introduction to the Language B”:

main( ) {
 extrn a, b, c;
 putchar(a); putchar(b); putchar(c); putchar(’!*n’);
}

a ’hell’;
b ’o, w’;
c ’orld’;

Various online sources refer to this as a “book”, but it definitely was not. It was a printed, 17-page document that was later included as half of January 1973’s “Bell Laboratories Computing Science Technical Report #8: The Programming Language B” (still not even close to a book!). The “hello, world” program appears in section 7, preceded by the less catchy “hi!” program in section 6. As I write this blog post in 2022, I cannot find any online reference for the B tutorial being originally dated July 1972, but I believe I must have had a good reason.

The January 1974 commit converts the program to C, as found in Kernighan’s “Programming in C — A Tutorial”. The linked PDF is a retyped copy from Dennis Ritchie, without a date, but Ritchie’s “C Reference Manual” technical memo dated January 15, 1974 cites Kernighan’s tutorial as “Unpublished internal memorandum, Bell Laboratories, 1974”, implying that the tutorial must have been written in January as well. That C program was shorter than what we are used to today, but much nicer than the B program:

main( ) {
	printf("hello, world");
}

I skipped over the presentation in the first edition of The C Programming Language, which looks like:

main() {
	printf("hello, world\n");
}

The April 1988 commit shows the program from the “Draft-Proposed ANSI C” version of the second edition of The C Programming Language:

#include <stdio.h>

main()
{
	printf("hello, world\n");
}

The second April 1988 commit shows the final full ANSI C version we know today:

#include <stdio.h>

int
main(void)
{
	printf("hello, world\n");
	return 0;
}

Wikipedia says the second edition was published in April 1988. I didn’t have a day, but April 1 seemed appropriate. I didn’t have a time for either one of these, so I used 02:03:04 for the second commit and therefore 02:02:04 for the first.

The email addresses in the commits are also period-appropriate, although Mondrian’s R= and DELTA= tags clearly are not: there was no code review happening back then!

For what it’s worth, I’ve since heard from many people about how the 1972 dates have broken various presentations and analyses they’ve done on the Go repository as compared to other projects. Oops! My apologies. (I also heard from someone who was analyzing Mercurial repos for “branchiness” and decided to use the Go repo as a large test case. Their program said it had branchiness 0 and they spent a while debugging their program before realizing that the repo really was completely linear, thanks to our “rebase and merge” policy.)

Public Mercurial

We published the Google Code Mercurial repo on November 10, 2009, and to mark the occasion we added one more Easter egg. A footnote in Brian Kernighan and Rob Pike’s 1984 book The Unix Programming Environment says:

Ken Thompson was once asked what he would do differently if he were redesigning the UNIX system. His reply: “I’d spell creat with an e.”

This refers to the creat(2) system call and the O_CREAT file open flag.

Immediately once the release was public, Ken mailed me a change fixing this mistake:

commit c90d392ce3d3203e0c32b3f98d1e68c4c2b4c49b
Author:     Ken Thompson <ken@golang.org>
AuthorDate: Tue Nov 10 15:05:15 2009 -0800
Commit:     Ken Thompson <ken@golang.org>
CommitDate: Tue Nov 10 15:05:15 2009 -0800

    spell it with an "e"

    R=rsc
    http://go/go-review/1025037

 src/pkg/os/file.go | 1 +
 1 file changed, 1 insertion(+)

Sadly, we didn’t execute the joke perfectly, in that the code review went to our internal Rietveld server instead of the public one. So the very next commit updated the code review server in our configuration.

But here, for posterity, is the review, preserved in my email:

Git

So things stood from November 2009 until late 2014, when we knew that Google Code Project Hosting was going to shut down and we needed a new home. After investigating a few options, we ended up using Gerrit Code Review, which has been a fantastic choice. Many people think of Go as being hosted on GitHub, but GitHub is only primary for our issue tracker: the official primary copy of the sources is on go.googlesource.com.

You can see the transition from Mercurial to Git in the logs when the R= lines end, followed by a few completely unreviewed commits, and then Reviewed-by: lines begin:

commit 94151eb2799809ece7e44ce3212aa3cbb9520849
Author:     Russ Cox <rsc@golang.org>
AuthorDate: Fri Dec 5 21:33:07 2014 -0500
Commit:     Russ Cox <rsc@golang.org>
CommitDate: Fri Dec 5 21:33:07 2014 -0500

    encoding/xml: remove SyntaxError.Byte

    It is unused. It was introduced in the CL that added InputOffset.
    I suspect it was an editing mistake.

    LGTM=bradfitz
    R=bradfitz
    CC=golang-codereviews
    https://golang.org/cl/182580043

 src/encoding/xml/xml.go | 1 -
 1 file changed, 1 deletion(-)

commit 258f53dee33b9055ea168cb186f8c076edee5905
Author:     David Symonds <dsymonds@golang.org>
AuthorDate: Mon Dec 8 13:50:49 2014 +1100
Commit:     David Symonds <dsymonds@golang.org>
CommitDate: Mon Dec 8 13:50:49 2014 +1100

    remove .hgtags.

 .hgtags | 140 ----------------------------------------------------------------
 1 file changed, 140 deletions(-)

commit 369873c6e5d00314ae30276363f58e5af11b149c
Author:     David Symonds <dsymonds@golang.org>
AuthorDate: Mon Dec 8 13:50:49 2014 +1100
Commit:     David Symonds <dsymonds@golang.org>
CommitDate: Mon Dec 8 13:50:49 2014 +1100

    convert .hgignore to .gitignore.

 .hgignore => .gitignore | 9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)

commit f33fc0eb95be84f0a688a62e25361a117e5b995b
Author:     David Symonds <dsymonds@golang.org>
AuthorDate: Mon Dec 8 13:53:11 2014 +1100
Commit:     David Symonds <dsymonds@golang.org>
CommitDate: Mon Dec 8 13:53:11 2014 +1100

    cmd/dist: convert dist from Hg to Git.

 src/cmd/dist/build.c | 100 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 59 insertions(+), 41 deletions(-)

commit 26399948e3402d3512cb14fe5901afaef54482fa
Author:     David Symonds <dsymonds@golang.org>
AuthorDate: Mon Dec 8 11:39:11 2014 +1100
Commit:     David Symonds <dsymonds@golang.org>
CommitDate: Mon Dec 8 04:42:22 2014 +0000

    add bin/ to .gitignore.

    Change-Id: I5c788d324e56ca88366fb54b67240cebf5dced2c
    Reviewed-on: https://go-review.googlesource.com/1171
    Reviewed-by: Andrew Gerrand <adg@golang.org>

 .gitignore | 1 +
 1 file changed, 1 insertion(+)

As part of the conversion from Mercurial to Git, we did not add visible lines to the commit bodies showing the old Mercurial hashes, but we did record them in the underlying Git commit objects. For example:

% git cat-file -p 7d7c6a97f815e9279d08cfaea7d5efb5e90695a8
tree e06bd601885e16ad3d72c2a8c9b411889b2e478e
author Brian Kernighan <bwk> 80352345 -0500
committer Brian Kernighan <bwk> 80352345 -0500
golang-hg f6182e5abf5eb0c762dddbb18f8854b7e350eaeb

hello, world

R=ken
DELTA=7  (7 added, 0 deleted, 0 changed)
%

The golang-hg line records the original Mercurial commit hash.

And that’s the end of the story, until we move to a fifth version control system at some point in the future.

What NPM Should Do Today To Stop A New Colors Attack Tomorrow

2022-01-10T11:45:00-05:00

Over the weekend, a developer named Marak Squires intentionally sabotaged his popular NPM package colors and his less popular package faker. As I write this, NPM claims 18,971 direct dependents for colors and 2,751 for faker. Open Source Insights counts at least 42,000 more indirect dependents for colors. Many popular NPM packages depend on these packages.

A misfeature in NPM’s design means that as soon as the sabotaged version of colors was published, fresh installs of command-line tools depending on colors immediately started using it, with no testing that it was in any way compatible with each tool. (Spoiler alert: it wasn’t!)

The specific misfeature is that when you use NPM to install a package, including a command-line tool, NPM selects the dependency versions according to the requirements listed in package.json as well as the state of the world at that moment, preferring the newest possible allowed version of every dependency. This means that the moment Marak updated colors, installs of aws-cdk and the other tools started breaking, and the bug reports started rolling in, like this one:

And also these in apostrophe, cdk8s, compodoc, foreversd, hexo, highcharts, jest, netlify, oclif, and more.

NPM users may be upset at Marak today, but at least the change didn’t do anything worse than print garbage to the terminal. It could have been worse. A lot worse. Even ignoring this kind of intentional breakage, innocent bugs happen all the time too. Essentially every open source software license points out that the code is made available with no warranty at all. Modern package managers need to be designed to expect and mitigate this risk.

Anyone running modern production systems knows about testing followed by gradual or staged rollouts, in which changes to a running system are deployed gradually over a long period of time, to reduce the possibility of accidentally taking down everything at once. For example, the last time I needed to make a change to Google’s core DNS zone files, the change was tested against many many regression tests and then deployed to each of Google’s four name servers, one at a time, over a period of 24 hours. Regression testing checks that the change does not appear to affect answers it shouldn’t have, and then the gradual rollout gives plenty of time for both automated systems and reliability engineers to notice unexpected problems and stop the rollout.

NPM’s design choice is the exact opposite. The latest version of colors was promoted to use in all its dependents before any of them had a chance to test it and without any kind of gradual rollout. Users can disable this behavior today, by pinning the exact versions of all their dependencies. For example here is the fix to aws-cdk. That’s not a good answer, but at least it’s possible.

The right path forward for NPM and package managers like it is to stop preferring the latest possible version of all dependencies when installing a new package. Instead, they should prefer to use the dependency versions that the package was actually tested with, or versions as close as possible to those. I call that a high-fidelity build. In contrast, the people who installed aws-cdk and other packages over the weekend got low-fidelity builds: NPM inserted a new version of colors that the developers of these other packages had never tested against. Users got to test that brand new configuration themselves over the weekend, and the test failed.

High-fidelity builds solve both the testing problem and the gradual rollout problem. A new version of colors wouldn’t get picked up by an aws-cdk install until the aws-cdk authors had gotten a chance to test it and push a new version configuration in a new version of aws-cdk. At that point, all new aws-cdk installs would get the new colors, but all the other tools would still be unaffected, until they too tested and officially adopted the new version of colors.

There are many ways to produce high-fidelity builds. In Go, a package declares the minimum required version of each dependency, and that’s what the build uses, unless some other constraint in the same build graph requests a newer one. And then, it only uses that specific newer one, not the one that just appeared over the weekend and is entirely untested by anyone. For more about this approach, see “The Principles of Versioning in Go.”

Package managers don’t have to adopt Go’s approach exactly. It would be enough, for example, to record the versions that the aws-cdk developers used for their testing and then reuse those versions during the install. In fact, NPM can already record those versions, in a lock file. But npm install of a new package does not use the information in that package’s lock file to decide the versions of dependencies: lock files are not transitive.

NPM also has an npm shrinkwrap command, as well as an npm ci command, both of which appear to fix this problem in certain, limited circumstances. Most of the authors and users of commands affected by the colors sabotage should be looking carefully at those today. Kudos to NPM for providing those, but they shouldn’t be off to the side. The next step is for NPM to arrange for that kind of protection to happen by default. And then the same protection is needed when installing a new library package as a dependency, not just when installing a command. All this will require more work.

Other language package managers should take note too. Marak has done all of us a huge favor by highlighting the problems most package managers create with their policy of automatic adoption of new dependencies without the opportunity for gradual rollout or any kind of testing whatsoever. Fixing those problems is long overdue. Next time will be worse.

On “Trojan Source” Attacks

2021-11-01T23:33:00-04:00

There is a paper making the rounds, with a slick accompanying web site, in which the authors describe a software supply chain attack they call “Trojan Source: Invisible Vulnerabilities”. In short, if you use comments containing Unicode LTR and RTL code points, which control whether text is rendered left-to-right or right-to-left, you can make code look different in a standard Unicode rendering than it does to a program ignoring the comments.

The authors claim this is “a new type of attack” that “cannot be perceived directly by human code reviewers” and “pose[s] an immediate threat”, and they propose that compilers should be “upgraded to block this attack.” None of this is true.

The attack is old

First, the attacks are not new. Here is a Go example from 2017, a Rust example from 2018, a C++ example from 2019, and a Ruby example from 2020.

The change is visible

Second, it is technically true that the attack cannot be perceived directly by human code reviewers, but only in the sense that no program in a computer can be perceived directly by humans (except of course the real programmers using magnetized needles and a steady hand). Instead, we build tools that convert the electrical charges or magnetized particles that represent our programs into some more recognizable form, like a pattern of lights. And of course we have complete control over the exact conversion those programs use and therefore exactly what they enable us to perceive, a fact I will return to later.

(Also, as noted on Hacker News, any editor that syntax highlights comments will suffice to detect the examples in the paper!)

The threat is not immediate

Third, the attacks do not create an immediate threat, at least not a new one. The attack model in the paper assumes you take changes to your code from untrusted people. Not everyone does this! And the people who do take those changes are usually not reading the code carefully enough that this attack is necessary. In the event-stream incident, for example, many people focus on event-stream being hijacked by social engineering, while very few people focus on the fact that the malicious code was hidden by only including it in a “minimized” JavaScript file, a fact the Copay authors missed when upgrading their dependencies, if they looked at them at all. Perhaps most importantly, if you are letting untrusted people make arbitrary changes to your code, they can probably find far more subtle (and deniable!) ways to hide a malicious change than using LTR/RTL code points.

The compiler is the wrong place for a fix

Finally, compilers should not be “upgraded” to block the attack. Fixing compilers closes only one of many open doors. What about assemblers? What about build and configuration file parsers? What about general YAML parsers? What about every other possible program that in some way executes the content of a text file that allows comments or quoted string literals?

For example, the Rust project issued 1.56.1 today, changing rustc to disallow LTR/RTL code points in Rust source files. But as far as I can tell there has been no update to cargo, meaning that a similar attack can probably still be carried out using comments and string literals in Cargo.toml.

Considering build configuration files alone, closing all the doors would mean updating the programs associated with BUILD.bazel, CMakefile, Cargo.toml, Dockerfile, GNUmakefile, Makefile, go.mod, package.json, pom.xml, requirements.txt, and many, many more. And again, that’s just build configuration. It would be an unbounded amount of work to require every program that interprets a text file to be changed to exclude a list of certain Unicode code points.

Even excluding “bad” Unicode code is pretty complicated. The next problem is homograph attacks, using characters that look the same but aren’t.

Changing compilers is also arguably a false sense of security. It’s impossible in general for the compiler to tell whether code is good or bad, for almost any definition of good or bad. Even if the compiler rejects LTR/RTL code points, it can’t reject the many more subtle ways an attacker might introduce an unnoticed change.

The answer is proper review

Instead of changing compilers, we should take advantage of the fact that we must use tools to render our programs for us—tools like text editors and code review web sites. We should make sure we are using those tools and also make sure their renderers make suspicious Unicode use easier to see. There are far fewer of those tools than there are programs that interpret or execute content from text files: most development efforts will have just one review tool and a few common editors.

Making LTR/RTL code points visible is particularly important for review tools, and it is good that GitHub now warns about these characters in PRs. On the other hand, the blog post’s suggestion to use view UTF-8 files in VSCode as CP 437 to “see” Unicode sequences is a kludge. Hopefully VSCode will add a proper warning and visible indicators in UTF-8 mode soon too.

Summary

In summary: This is an old, already known bug. The source changes are hardly invisible: many programs can see them today, and no doubt more will be able to see them tomorrow. There is no new threat here: people who can modify the code you run can do a lot of damage already that not enough people watch for and that can be made arbitrarily subtle without Unicode tricks. Making the fix in every compiler is both a lot of work and not nearly good enough: it omits all the other programs that execute instructions from text files. Instead, the right answer to Unicode tricks is proper code review and dependency hygiene, which will handle a much broader class of problems that fully includes this one, especially using review tools that highlight suspicious Unicode, which isn’t limited to LTR/RTL attacks.

The authors of this paper have clearly done a good job promoting it. Kudos to them on that. But I am concerned that the attention and response this paper is getting is in general distracting from far more useful security efforts. We should redirect that attention and response at improving general code and dependency review instead.

The most egregious example of breathless coverage of this relatively minor issue is Brian Krebs’s headline: ‘Trojan Source’ Bug Threatens the Security of All Code. Imagine the writeup if he’d attended Ken Thompson’s Turing Award Lecture. That’s an invisible vulnerability! (For the record, back in 2013, Ken told me that the backdoored compiler did in fact exist and was deployed, but it had a subtle bug that exposed the backdoor: the reproduction code added an extra \0 to the string each time it copied itself. This made the compiler binary grow by one byte every time it rebuilt itself. Eventually someone noticed and debugged what was going on, aided by the fact that the “print assembly” compilation mode did not insert the backdoor at all, and all traces were cleaned away. Or so we believe.)

How Many Go Developers Are There?

2017-07-13T13:00:00-04:00

How many Go developers are there in the world? Around two million.

As of August 2021, my best estimate is between 1.6 and 2.5 million.

Previously:
In July 2017, I estimated between half a million and a million.
In July 2018, I estimated between 0.8 and 1.6 million.
In November 2019, I estimated between 1.15 and 1.96 million.

Approach

My approach is to compute:

Number of Go Developers = Number of Software Developers × Fraction using Go

Then we need to answer how many software developers there are in the world and what percentage of them are using Go.

Number of Software Developers

How many software developers are there in the world?

In January 2014, InfoQ reported that IDC published a report (no longer available online, it would seem) estimating that there were 11,005,000 “professional software developers” and 7,534,500 “hobbyist software developers,” giving a total estimate of 18,539,500.

In October 2016, Evans Data Corporation issued a press release advertising their “Global Developer Population and Demographic Study 2016” in which they estimated the total worldwide population of software developers to be 21 million.

Maybe the Evans estimate is too high. The details of their methodology are key to their business and therefore not revealed publicly, so we can’t easily tell how strict or loose their definition of developer is. In January 2017, PK of the DQYDJ blog posted an analysis titled “How Many Developers are There in America, and Where Do They Live?,” That post, which includes an admirably detailed methodology section, used data from the 2016 American Census Survey (ACS) and included these employment categories as “strict” software developers:

Computer Scientists and Systems Analysts / Network Systems Analysts / Web Developers
Computer Programmers
Software Developers, Applications and Systems Software
Database Administrators

Using that list, PK arrived at a total of 3,357,626 software developers in the United States. The post then added two less strict categories, which expanded the total to 4,185,114 software developers. A conservative estimate of the number of software developers worldwide would probably include only PK’s “strict” category, about 80% of the United States total. If we assume conservatively that the Evans estimate was similarly loose and that the 80% ratio holds worldwide, we can make the Evans estimate stricter by multiplying it by the same 80%, arriving at 16.8 million.

Maybe the Evans estimate is too low. In May 2017, RedMonk blogger James Governor reported that, in a recent speech, GitHub CEO Chris Wanstrath claimed GitHub has 21 million active users and GitHub’s Atom editor has 2 million active users (who haven’t turned off metrics and tracking) and concluded that the IDC and Evans estimates are therefore too low. Governor went on to give a “wild assed guess” of 35 million developers worldwide.

Based on all this (and ignoring wild-assed guesses), my estimate in July 2017 was that the number of software developers worldwide was likely to be in the range 16.8–21 million.

The 2018 Evans Data Global Developer Population and Demographic Study estimated 23 million developers worldwide, up from 21 million in the 2016 survey.

Based on the confidence range in 2017 being 16.8–21 million, my estimate in July 2018 applied the Evans Data 10% growth to arrive at 18.4–23 million developers in 2018.

The 2019 Evans Data Global Development Survey estimated 23.9 million developers worldwide in May 2019, up from 23 million in the 2018 survey.

The IDC Worldwide Developer Census, 2018 estimated 22.30 million developers worldwide, up from 21.25 million in 2017.

SlashData’s Global Developer Population 2019 estimates 14.7 million developers in Q2 2017, 15.7 million in Q4 2017, 16.9 million in Q2 2018, and 18.9 million in Q4 2018, extrapolating to “at least 21M developers by the end of 2019 and possibly upwards of 23M.” Oddly, SlashData’s Developer Economics State of the Developer Nation 17th Edition estimated “18 million active software developers in the world” as of Q2 2019. It is unclear if this was rounded down from the 18.9, if SlashData believes the number of developers decreased in the first half of 2019, or if the numbers are completely unrelated.

Based on these, my estimate in November 2019 is that the number of developers worldwide is likely to be in the range 18.9–23.9 million developers.

The Evans Data Corporation Worldwide Developer Population and Demographic Study 2020, Volume 2 estimated 24.5 million developers worldwide, with lower growth than predicted attributed to the pandemic.

The IDC Worldwide Developer Census, 2020 estimated 26.2 million developers worldwide in January 2020.

SlashData’s Developer Economics State of the Developer Nation 20th Edition estimated 24.3 million developers worldwide.

These estimates seem to be converging, but to be conservative, I'm only going to move the low end halfway from the previous 18.9 to the 24.3 here, producing 21.6 million.

Based on these, my estimate in August 2021 is that the number of developers worldwide is likely to be in the range 21.6–26.2 million developers.

Fraction using Go

What fraction of software developers use Go?

Stack Overflow has been running an annual developer survey for the past few years. In their 2017 survey, 4.2% of all respondents and 4.6% of professional developers reported using Go. Unfortunately, we cannot sanity check Go against the year before, because the 2016 survey report cut off the list of popular technologies after Objective-C (6.5%).

O’Reilly has been running annual software developer salary surveys for the past few years as well, and their survey asks about language use. The 2016 worldwide survey reports that Go is used by 3.9% of respondents, while the 2016 European survey reports Go is used by 3.3% of respondents. (I derived both these numbers by measuring the bars in the graphs.) The 2017 worldwide survey reports in commentary that 4.5% of respondents say they use Go.

Maybe the 4.2–4.6% estimate is too high. Both of these are online surveys with a danger of self-selection bias among respondents, and that developers who don’t answer online surveys use Go much less than those who do. For example, perhaps the surveys are skewed by geography or experience in a way that affects the result. Suppose, I think quite pessimistically, that the survey respondents are only representative of half of the software developer population, and that in the other half, Go is only half as popular. Then if a survey found 4.2% of developers use Go, the real percentage would be three quarters as much, or 3.15%.

Based on all this, my estimate in July 2017 was that the fraction of software developers using Go worldwide is at least 3% and possibly as high as 4.6%.

The 2018 Stack Overflow Developer Survey reports that 7.1% of all developers and 7.2% of professional developers use Go. Applying the same pessimism as last year (multiplying by three quarters) suggests a lower bound of 5.3%, but I’ll be even more conservative and use last year’s 4.6% as a lower bound. (The O’Reilly surveys seem to have stopped being run.)

Based on this, my estimate in July 2018 was that 4.6–7.1% of developers use Go.

The 2019 Stack Overflow Developer Survey reports that 8.2% of all developers and 8.8% of professional developers use Go (compared with 7.1% and 7.2% in 2017).

The HackerRank 2019 Developer Skills Report reports that 8.8% of respondents know Go at the end of 2018 (compared with 6.08% at the end of 2017).

SlashData’s Developer Economics State of the Developer Nation 17th Edition estimated 1.1 million active Go software developers, out of 18 million worldwide, or 6.15%. (That happens to match my usual “three quarters of Stack Overflow” conservative lower bound exactly.)

The JetBrains Developer Ecosystem Survey 2019 reports that 18% of developers used Go in 2018. That number seems too high, so I will discount it for now.

Evans Data Corporation’s Global Development Survey reports even higher (and harder to believe) percentages for Go usage in the non-public part of the survey.

Based on all this, my estimate in November 2019 is that 6.1–8.2% of developers use Go.

The 2020 Stack Overflow Developer Survey reports that 8.8% of all developers and 9.4% of professional developers use Go.

The 2021 Stack Overflow Developer Survey reports that 9.55% of all developers and 10.51% of professional developers use Go.

SlashData’s Developer Economics State of the Developer Nation 20th Edition estimated 2.1 million active Go software developers, out of 24.3 million worldwide, or 8.6%.

The JetBrains Developer Ecosystem Survey 2021 reports that 17% of developers used Go in 2020. That number still seems too high, so I will continue to discount it.

Evans Data Corporation’s Global Development Survey 2021 continues to report an even higher (and harder to believe) percentage for Go usage: 22.2% of developers spending at least 10% of their programming time using Go, roughly on par with Kotlin.

Like in the total developer population, the believable numbers seem to be converging, but to be conservative, I'm only going to move the low end halfway from the previous 6.1 to the current 8.6, producing 7.4%.

Based on all this, my estimate in August 2021 is that 7.4–9.5% of developers use Go.

Number of Go Developers

How many Go developers are there? Multiply the low developer count and Go percentages and the high ones.

In July 2017, 3–4.6% of 16.8–21 million yielded an estimate of 0.50–0.97 million Go developers.

In July 2018, 4.6–7.1% of 18.4–23 million yielded an estimate of 0.85–1.63 million Go developers.

In November 2019, 6.1–8.2% of 18.9–23.9 million yields an estimate of 1.15–1.96 million Go developers.

In August 2021, 7.4–9.5% of 21.6–26.2 million yields an estimate of 1.6–2.5 million Go developers.

Updating the Go Memory Model

2021-07-12T09:45:00-04:00

The current Go language memory model was written in 2009, with minor updates since. It is clear that there are at least a few details that we should add to the current memory model, among them an explicit endorsement of race detectors and a clear statement of how the APIs in sync/atomic synchronize programs.

This post restates Go's overall philosophy and the current memory model and then outlines the relatively small adjustments I believe that we should make to the Go memory model. It assumes the background presented in the earlier posts “Hardware Memory Models” and “Programming Language Memory Models.”

I have opened a GitHub discussion to collect feedback on the ideas presented here. Based on that feedback, I intend to prepare a formal Go proposal later this month. The use of GitHub discussions is itself a bit of an experiment, continuing to try to find a reasonable way to scale discussions of important changes.

Go's Design Philosophy

Go aims to be a programming environment for building practical, efficient systems. It aims to be lightweight for small projects but also scale up gracefully to large projects and large engineering teams.

Go encourages approaching concurrency at a high level, in particular through communication. The first Go proverb is “Don't communicate by sharing memory. Share memory by communicating.” Another popular proverb is that “Clear is better than clever.” In other words, Go encourages avoiding subtle bugs by avoiding subtle code.

Go aims not just for understandable programs but also for an understandable language and understandable package APIs. Complex or subtle language features or APIs contradict that goal. As Tony Hoare said in his 1980 Turing award lecture:

I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.
The first method is far more difficult. It demands the same skill, devotion, insight, and even inspiration as the discovery of the simple physical laws which underlie the complex phenomena of nature. It also requires a willingness to accept objectives which are limited by physical, logical, and technological constraints, and to accept a compromise when conflicting objectives cannot be met.

This aligns pretty well with Go's philosophy for APIs. We typically spend a long time during design to make sure an API is right, working to reduce it to its minimal, most useful essence.

Another aspect of Go being a useful programming environment is having well-defined semantics for the most common programming mistakes, which aids both understandability and debugging. This idea is hardly new. Quoting Tony Hoare again, this time from his 1972 “Quality of Software” checklist:

As well as being very simple to use, a software program must be very difficult to misuse; it must be kind to programming errors, giving clear indication of their occurrence, and never becoming unpredictable in its effects.

The common sense of having well-defined semantics for buggy programs is not as common as one might expect. In C/C++, undefined behavior has evolved into a kind of compiler writer's carte blanche to turn slightly buggy programs into very differently buggy programs, in ever more interesting ways. Go does not take this approach: there is no “undefined behavior.” In particular, bugs like null pointer dereferences, integer overflow, and unintentional infinite loops all have defined semantics in Go.

Go's Memory Model Today

Go's memory model begins with the following advice, consistent with Go's overall philosophy:

Programs that modify data being simultaneously accessed by multiple goroutines must serialize such access.
To serialize access, protect the data with channel operations or other synchronization primitives such as those in the sync and sync/atomic packages.
If you must read the rest of this document to understand the behavior of your program, you are being too clever.
Don't be clever.

This remains good advice. The advice is also consistent with other languages' encouragement of DRF-SC: synchronize to eliminate data races, and then programs will behave as if sequentially consistent, leaving no need to understand the remainder of the memory model.

After this advice, the Go memory model defines a conventional happens-before-based definition of racing reads and writes. Like in Java and JavaScript, a read in Go can observe any earlier but not yet overwritten write in the happens-before order, or any racing write; arranging to have only one such write forces a specific outcome.

The memory model then goes on to define the synchronization operations that establish cross-goroutine happens-before edges. The operations are the usual ones, with some Go-specific flavoring:

If a package p imports package q, the completion of q's init functions happens before the start of any of p's.
The start of the function main.main happens after all init functions have finished.
The go statement that starts a new goroutine happens before the goroutine's execution begins.
A send on a channel happens before the corresponding receive from that channel completes.
The closing of a channel happens before a receive that returns a zero value because the channel is closed.
A receive from an unbuffered channel happens before the send on that channel completes.
The k'th receive on a channel with capacity C happens before the k+C'th send from that channel completes.
For any sync.Mutex or sync.RWMutex variable l and n < m, call n of l.Unlock() happens before call m of l.Lock() returns.
A single call of f() from once.Do(f) happens (returns) before any call of once.Do(f) returns.

This list notably omits any mention of sync/atomic as well as newer APIs in package sync.

The memory model ends with some examples of incorrect synchronization. It contains no examples of incorrect compilation.

Changes to Go's Memory Model

In 2009, as we set out to write Go's memory model, the Java memory model was newly revised, and the C/C++11 memory model was being finalized. We were strongly encouraged by some to adopt the C/C++11 model, taking advantage of all the work that had gone into it. That seemed risky to us. Instead, we decided on a more conservative approach to what guarantees we would make, a decision confirmed by the subsequent decade of papers detailing very subtle problems in the Java/C/C++ line of memory models. Defining enough of a memory model to guide programmers and compiler writers is important, but defining one in complete formality—correctly!—seems still just beyond the grasp of the most talented researchers. It should suffice for Go to continue to say the minimum needed to be useful.

This section list the adjustments I believe we should make. As noted earlier, I have opened a GitHub discussion to collect feedback. Based on that feedback, I plan to prepare a formal Go proposal later this month.

Document Go's overall approach

The “don't be clever” advice is important and should stay, but we also need to say more about Go's overall approach before diving into the details of happens-before. I have seen multiple incorrect summaries of Go's approach, such as claiming that Go's model is C/C++'s “DRF-SC or Catch Fire.” Misreadings are understandable: the document doesn't say what the approach is, and it is so short (and the material so subtle) that people see what they expect to see rather than what is or is not there.

The text to be added would be something along the lines of:

Overview

Go approaches its memory model in much the same way as the rest of the language, aiming to keep the semantics simple, understandable, and useful.
A data race is defined as a write to a memory location happening concurrently with another read or write to that same location, unless all the accesses involved are atomic data accesses as provided by the sync/atomic package. As noted already, programmers are strongly encouraged to use appropriate synchronization to avoid data races. In the absence of data races, Go programs behave as if all the goroutines were multiplexed onto a single processor. This property is sometimes referred to as DRF-SC: data-race-free programs execute in a sequentially consistent manner.
Other programming languages typically take one of two approaches to programs containing data races. The first, exemplified by C and C++, is that programs with data races are invalid: a compiler may break them in arbitrarily surprising ways. The second, exemplified by Java and JavaScript, is that programs with data races have defined semantics, limiting the possible impact of a race and making programs more reliable and easier to debug. Go's approach sits between these two. Programs with data races are invalid in the sense that an implementation may report the race and terminate the program. But otherwise, programs with data races have defined semantics with a limited number of outcomes, making errant programs more reliable and easier to debug.

This text should make clear how Go is and is not like other languages, correcting any prior expectations on the part of the reader.

At the end of the “Happens Before” section, we should also clarify that certain races can still lead to corruption. It currently ends with:

Reads and writes of values larger than a single machine word behave as multiple machine-word-sized operations in an unspecified order.

We should add:

Note that this means that races on multiword data structures can lead to inconsistent values not corresponding to a single write. When the values depend on the consistency of internal (pointer, length) or (pointer, type) pairs, as is the case for interface values, maps, slices, and strings in most Go implementations, such races can in turn lead to arbitrary memory corruption.

This will more clearly state the limitations of the guarantees on programs with data races.

Document happens-before for sync libraries

New APIs have been added to the sync package since the memory model was written. We need to add them to the memory model (issue #7948). Thankfully, the additions seem straightforward. I believe they are as follows.

For sync.Cond: Broadcast or Signal happens before the return of any Wait call that it unblocks.
For sync.Map: Load, LoadAndDelete, and LoadOrStore are read operations. Delete, LoadAndDelete, and Store are write operations. LoadOrStore is a write operation when it returns loaded set to false. A write operation happens before any read operation that observes the effect of the write.
For sync.Pool: A call to Put(x) happens before a call to Get returning that same value x. Similarly, a call to New returning x happens before a call to Get returning that same value x.
For sync.WaitGroup: A call to Done happens before the return of any Wait call that it unblocks.

Users of these APIs need to know the guarantees in order to use them effectively. Therefore, while we should keep the text in the memory model for illustrative purposes, we should also include it in the doc comments in package sync. This will also help set an example for third-party synchronization primitives of the importance of documenting the ordering guarantees established by an API.

Document happens-before for sync/atomic

Atomic operations are missing from the memory model. We need to add them (issue #5045). I believe we should say:

The APIs in the sync/atomic package are collectively “atomic operations” that can be used to synchronize the execution of different goroutines. If the effect of an atomic operation A is observed by atomic operation B, then A happens before B. All the atomic operations executed in a program behave as though executed in some sequentially consistent order.

This is what Dmitri Vyukov suggested in 2013 and what I informally promised in 2016. It also has the same semantics as Java's volatiles and C++'s default atomics.

In terms of the C/C++ menu, there are only two choices for synchronizing atomics: sequentially consistent or acquire/release. (Relaxed atomics do not create happens-before edges and therefore have no synchronizing effect.) The decision between those comes down to, first, how important it is to be able to reason about the relative order of atomic operations on multiple locations, and, second, how much more expensive sequentially consistent atomics are compared to acquire/release atomics.

On the first consideration, reasoning about the relative order of atomic operations on multiple locations is very important. In an earlier post I gave an example of a condition variable with a lock-free fast path implemented using two atomic variables, broken by using acquire/release atomics. This pattern appears again and again. For example, a past implementation of sync.WaitGroup used a pair of atomic uint32 values, wg.counter and wg.waiters. The Go runtime implementation of semaphores also depends on two separate atomic words, namely the semaphore value *addr and the corresponding waiter count root.nwait. There are more. In the absence of sequentially consistent semantics (that is, if we instead adopt acquire/release semantics), people will still write code like this; it will just fail mysteriously, and only in certain contexts.

The fundamental problem is that using acquire/release atomics to make a program data-race-free does not result in a program that behaves in a sequentially consistent manner, because the atomics themselves don't. That is, such programs do not provide DRF-SC. This makes such programs very difficult to reason about and therefore difficult to write correctly.

On the second consideration, as noted in the earlier post, hardware designers are starting to provide direct support for sequentially consistent atomics. For example, ARMv8 adds the ldar and stlr instructions for implementing sequentially consistent atomics, and they are also the recommended implementation of acquire/release atomics. If we adopted acquire/release semantics for sync/atomic, programs written on ARMv8 would be getting sequential consistency anyway. This would undoubtedly lead to programs that rely on the stronger ordering accidentally, breaking on weaker platforms. This may even happen on a single architecture, if the difference between acquire/release and sequentially consistent atomics is difficult to observe in practice due to race windows being small.

Both considerations strongly suggest we should adopt sequentially consistent atomics over acquire/release atomics: sequentially consistent atomics are more useful, and some chips have already completely closed the gap between the two levels. Presumably others will do the same if the gap is significant.

The same considerations, along with Go's overall philosophy of having minimal, easily understood APIs, argue against providing acquire/release as an additional, parallel set of APIs. It seems best to provide only the most understandable, most useful, least misusable set of atomic operations.

Another possibility would be to provide raw barriers instead of atomic operations. (C++ provides both, of course.) Barriers have the drawback of making expectations less clear and being somewhat more architecture-specific. Hans Boehm's page “Why atomics have integrated ordering constraints” presents the arguments for providing atomics instead of barriers (he uses the term fences). Generally, the atomics are far easier to understand than fences, and since we already provide atomic operations today, we can't easily remove them. Better to have one mechanism than two.

Maybe: Add a typed API to sync/atomic

The definitions above say that when a particular piece of memory must be accessed concurrently by multiple goroutines without other synchronization, the only way to eliminate the race is to make all the accesses use atomics. It is not enough to make only some of the accesses use atomics. For example, a non-atomic write concurrent with atomic reads or writes is still a race, and so is an atomic write concurrent with non-atomic reads or writes.

Whether a particular value should be accessed with atomics is therefore a property of the value and not of a particular access. Because of this, most languages put this information in the type system, like Java's volatile int and C++'s atomic<int>. Go's current APIs do not, meaning that correct usage requires careful annotation of which fields of a struct or global variables are expected to only be accessed using atomic APIs.

To improve program correctness, I am starting to think that Go should define a set of typed atomic values, analogous to the current atomic.Value: Bool, Int, Uint, Int32, Uint32, Int64, Uint64, and Uintptr. Like Value, these would have CompareAndSwap, Load, Store, and Swap methods. For example:

type Int32 struct { v int32 }

func (i *Int32) Add(delta int32) int32 {
	return AddInt32(&i.v, delta)
}

func (i *Int32) CompareAndSwap(old, new int32) (swapped bool) {
	return CompareAndSwapInt32(&i.v, old, new)
}

func (i *Int32) Load() int32 {
	return LoadInt32(&i.v)
}

func (i *Int32) Store(v int32) {
	return StoreInt32(&i.v, v)
}

func (i *Int32) Swap(new int32) (old int32) {
	return SwapInt32(&i.v, new)
}

I've included Bool on the list because we have constructed atomic booleans out of atomic integers multiple times in the Go standard library (in unexported APIs). There is clearly a need.

We could also take advantage of upcoming generics support and define an API for atomic pointers that is typed and free of package unsafe in its API:

type Pointer[T any] struct { v *T }

func (p *Pointer[T]) CompareAndSwap(old, new *T) (swapped bool) {
	return CompareAndSwapPointer(... lots of unsafe ...)
}

(And so on.) To answer an obvious suggestion, I don't see a clean way to use generics to provide just a single atomic.Atomic[T] that would let us avoid introducing Bool, Int, and so on as separate types, at least not without special cases in the compiler. And that's okay.

Maybe: Add unsynchronized atomics

All other modern programming languages provide a way to make concurrent memory reads and writes that do not synchronize the program but also don't invalidate it (don't count as a data race). C, C++, Rust, and Swift have relaxed atomics. Java has VarHandle's “plain” mode. JavaScript has non-atomic accesses to the SharedArrayBuffer (the only shared memory). Go has no way to do this. Perhaps it should. I don't know.

If we wanted to add unsynchronized atomic reads and writes, we could add UnsyncAdd, UnsyncCompareAndSwap, UnsyncLoad, UnsyncStore, and UnsyncSwap methods to the typed atomics. Naming them “unsync” avoids a few problems with the name “relaxed.” First, some people use relaxed as a relative comparison, as in “acquire/release is a more relaxed memory order than sequential consistency.” You can argue that's not proper usage of the term, but it happens. Second, and more important, the critical detail about these operations is not the memory ordering of the operations themselves but the fact that they have no effect on the synchronization of the rest of the program. To people who are not experts in memory models, seeing UnsyncLoad should make clear that there is no synchronization, whereas RelaxedLoad probably would not. It's also nice that Unsync looks at a glance like Unsafe.

With the API out of the way, the real question is whether to add these at all. The usual argument for providing an unsynchronized atomic is that it really does matter for the performance of fast paths in certain data structures. My general impression is that it matters most on non-x86 architectures, although I don't have data to back this up. Not providing an unsynchronized atomic can be argued to penalize those architectures.

A possible argument against providing an unsynchronized atomic is that on x86, ignoring the effect of potential compiler reorderings, unsynchronized atomics are indistinguishable from acquire/release atomics. They might therefore be abused to write code that only works on x86. The counterargument is that such subterfuge would not pass muster with the race detector, which implements the actual memory model and not the x86 memory model.

With the lack of evidence we have today, we would not be justified in adding this API. If anyone feels strongly that we should add it, the way to make the case would be to gather evidence of both (1) general applicability in code that programmers need to write, and (2) significant performance improvements on widely used systems arising from using non-synchronizing atomics. (It would be fine to show this using programs in languages other than Go.)

Document disallowed compiler optimizations

The current memory model ends by giving examples of invalid programs. Since the memory model serves as a contract between the programmer and the compiler writers, we should add examples of invalid compiler optimizations. For example, we might add:

Incorrect compilation

The Go memory model restricts compiler optimizations as much as it does Go programs. Some compiler optimizations that would be valid in single-threaded programs are not valid in Go programs. In particular, a compiler must not introduce a data race in a race-free program. It must not allow a single read to observe multiple values. And it must not allow a single write to write multiple values.
Not introducing data races into race-free programs means not moving reads or writes out of conditional statements in which they appear. For example, a compiler must not invert the conditional in this program:
i := 0
if cond {
	i = *p
}
That is, the compiler must not rewrite the program into this one:
i := *p
if !cond {
	i = 0
}
If cond is false and another goroutine is writing *p, then the original program is race-free but the rewritten program contains a race.
Not introducing data races also means not assuming that loops terminate. For example, a compiler must not move the accesses to *p or *q ahead of the loop in this program:
n := 0
for e := list; e != nil; e = e.next {
	n++
}
i := *p
*q = 1
If list pointed to a cyclic list, then the original program would never access *p or *q, but the rewritten program would.
Not introducing data races also means not assuming that called functions always return or are free of synchronization operations. For example, a compiler must not move the accesses to *p or *q ahead of the function call in this program (at least not without direct knowledge of the precise behavior of f):
f()
i := *p
*q = 1
If the call never returned, then once again the original program would never access *p or *q, but the rewritten program would. And if the call contained synchronizing operations, then the original program could establish happens before edges preceding the accesses to *p and *q, but the rewritten program would not.
Not allowing a single read to observe multiple values means not reloading local variables from shared memory. For example, a compiler must not spill i and reload it a second time from *p in this program:
i := *p
if i < 0 || i >= len(funcs) {
	panic("invalid function index")
}
... complex code ...
// compiler must NOT reload i = *p here
funcs[i]()
If the complex code needs many registers, a compiler for single-threaded programs could discard i without saving a copy and then reload i = *p just before funcs[i](). A Go compiler must not, because the value of *p may have changed. (Instead, the compiler could spill i to the stack.)
Not allowing a single write to write multiple values also means not using the memory where a local variable will be written as temporary storage before the write. For example, a compiler must not use *p as temporary storage in this program:
*p = i + *p/2
That is, it must not rewrite the program into this one:
*p /= 2
*p += i
If i and *p start equal to 2, the original code does *p = 3, so a racing thread can read only 2 or 3 from *p. The rewritten code does *p = 1 and then *p = 3, allowing a racing thread to read 1 as well.
Note that all these optimizations are permitted in C/C++ compilers: a Go compiler sharing a back end with a C/C++ compiler must take care to disable optimizations that are invalid for Go.

These categories and examples cover the most common C/C++ compiler optimizations that are incompatible with defined semantics for racing data accesses. They establish clearly that Go and C/C++ have different requirements.

Conclusion

Go's general approach of being conservative in its memory model has served us well and should be continued. There are, however, a few changes that are overdue, including defining the synchronization behavior of new APIs in the sync and sync/atomic packages. The atomics in particular should be documented to provide sequentially consistent behavior that creates happens-before edges synchronizing the non-atomic code around them. This would match the default atomics provided by all other modern systems languages.

Perhaps the most unique part of the update is the idea of clearly stating that programs with data races may be stopped to report the race but otherwise have well-defined semantics. This constrains both programmers and compilers, and it prioritizes the debuggability and correctness of concurrent programs over convenience for compiler writers.

Acknowledgements

This series of posts benefited greatly from discussions with and feedback from a long list of engineers I am lucky to work with at Google. My thanks to them. I take full responsibility for any mistakes or unpopular opinions.

Programming Language Memory Models

2021-07-06T10:50:00-04:00

Programming language memory models answer the question of what behaviors parallel programs can rely on to share memory between their threads. For example, consider this program in a C-like language, where both x and done start out zeroed.

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

The program attempts to send a message in x from thread 1 to thread 2, using done as the signal that the message is ready to be received. If thread 1 and thread 2, each running on its own dedicated processor, both run to completion, is this program guaranteed to finish and print 1, as intended? The programming language memory model answers that question and others like it.

Although each programming language differs in the details, a few general answers are true of essentially all modern multithreaded languages, including C, C++, Go, Java, JavaScript, Rust, and Swift:

First, if x and done are ordinary variables, then thread 2's loop may never stop. A common compiler optimization is to load a variable into a register at its first use and then reuse that register for future accesses to the variable, for as long as possible. If thread 2 copies done into a register before thread 1 executes, it may keep using that register for the entire loop, never noticing that thread 1 later modifies done.
Second, even if thread 2's loop does stop, having observed done == 1, it may still print that x is 0. Compilers often reorder program reads and writes based on optimization heuristics or even just the way hash tables or other intermediate data structures end up being traversed while generating code. The compiled code for thread 1 may end up writing to x after done instead of before, or the compiled code for thread 2 may end up reading x before the loop.

Given how broken this program is, the obvious question is how to fix it.

Modern languages provide special functionality, in the form of atomic variables or atomic operations, to allow a program to synchronize its threads. If we make done an atomic variable (or manipulate it using atomic operations, in languages that take that approach), then our program is guaranteed to finish and to print 1. Making done atomic has many effects:

The compiled code for thread 1 must make sure that the write to x completes and is visible to other threads before the write to done becomes visible.
The compiled code for thread 2 must (re)read done on every iteration of the loop.
The compiled code for thread 2 must read from x after the reads from done.
The compiled code must do whatever is necessary to disable hardware optimizations that might reintroduce any of those problems.

The end result of making done atomic is that the program behaves as we want, successfully passing the value in x from thread 1 to thread 2.

In the original program, after the compiler's code reordering, thread 1 could be writing x at the same moment that thread 2 was reading it. This is a data race. In the revised program, the atomic variable done serves to synchronize access to x: it is now impossible for thread 1 to be writing x at the same moment that thread 2 is reading it. The program is data-race-free. In general, modern languages guarantee that data-race-free programs always execute in a sequentially consistent way, as if the operations from the different threads were interleaved, arbitrarily but without reordering, onto a single processor. This is the DRF-SC property from hardware memory models, adopted in the programming language context.

As an aside, these atomic variables or atomic operations would more properly be called “synchronizing atomics.” It's true that the operations are atomic in the database sense, allowing simultaneous reads and writes which behave as if run sequentially in some order: what would be a race on ordinary variables is not a race when using atomics. But it's even more important that the atomics synchronize the rest of the program, providing a way to eliminate races on the non-atomic data. The standard terminology is plain “atomic”, though, so that's what this post uses. Just remember to read “atomic” as “synchronizing atomic” unless noted otherwise.

The programming language memory model specifies the exact details of what is required from programmers and from compilers, serving as a contract between them. The general features sketched above are true of essentially all modern languages, but it is only recently that things have converged to this point: in the early 2000s, there was significantly more variation. Even today there is significant variation among languages on second-order questions, including:

What are the ordering guarantees for atomic variables themselves?
Can a variable be accessed by both atomic and non-atomic operations?
Are there synchronization mechanisms besides atomics?
Are there atomic operations that don't synchronize?
Do programs with races have any guarantees at all?

After some preliminaries, the rest of this post examines how different languages answer these and related questions, along with the paths they took to get there. The post also highlights the many false starts along the way, to emphasize that we are still very much learning what works and what does not.

Hardware, Litmus Tests, Happens Before, and DRF-SC

Before we get to details of any particular language, a brief summary of lessons from hardware memory models that we will need to keep in mind.

Different architectures allow different amounts of reordering of instructions, so that code running in parallel on multiple processors can have different allowed results depending on the architecture. The gold standard is sequential consistency, in which any execution must behave as if the programs executed on the different processors were simply interleaved in some order onto a single processor. That model is much easier for developers to reason about, but no significant architecture provides it today, because of the performance gains enabled by weaker guarantees.

It is difficult to make completely general statements comparing different memory models. Instead, it can help to focus on specific test cases, called litmus tests. If two memory models allow different behaviors for a given litmus test, this proves they are different and usually helps us see whether, at least for that test case, one is weaker or stronger than the other. For example, here is the litmus test form of the program we examined earlier:

Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?

// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!
In any modern compiled language using ordinary variables: yes!

As in the previous post, we assume every example starts with all shared variables set to zero. The name rN denotes private storage like a register or function-local variable; the other names like x and y are distinct, shared (global) variables. We ask whether a particular setting of registers is possible at the end of an execution. When answering the litmus test for hardware, we assume that there's no compiler to reorder what happens in the thread: the instructions in the listings are directly translated to assembly instructions given to the processor to execute.

The outcome r1 = 1, r2 = 0 corresponds to the original program's thread 2 finishing its loop (done is y) but then printing 0. This result is not possible in any sequentially consistent interleaving of the program operations. For an assembly language version, printing 0 is not possible on x86, although it is possible on more relaxed architectures like ARM and POWER due to reordering optimizations in the processors themselves. In a modern language, the reordering that can happen during compilation makes this outcome possible no matter what the underlying hardware.

Instead of guaranteeing sequential consistency, as we mentioned earlier, today's processors guarantee a property called “data-race-free sequential-consistency”, or DRF-SC (sometimes also written SC-DRF). A system guaranteeing DRF-SC must define specific instructions called synchronizing instructions, which provide a way to coordinate different processors (equivalently, threads). Programs use those instructions to create a “happens before” relationship between code running on one processor and code running on another.

For example, here is a depiction of a short execution of a program on two threads; as usual, each is assumed to be on its own dedicated processor:

We saw this program in the previous post too. Thread 1 and thread 2 execute a synchronizing instruction S(a). In this particular execution of the program, the two S(a) instructions establish a happens-before relationship from thread 1 to thread 2, so the W(x) in thread 1 happens before the R(x) in thread 2.

Two events on different processors that are not ordered by happens-before might occur at the same moment: the exact order is unclear. We say they execute concurrently. A data race is when a write to a variable executes concurrently with a read or another write of that same variable. Processors that provide DRF-SC (all of them, these days) guarantee that programs without data races behave as if they were running on a sequentially consistent architecture. This is the fundamental guarantee that makes it possible to write correct multithreaded assembly programs on modern processors.

As we saw earlier, DRF-SC is also the fundamental guarantee that modern languages have adopted to make it possible to write correct multithreaded programs in higher-level languages.

Compilers and Optimizations

We have mentioned a couple times that compilers might reorder the operations in the input program in the course of generating the final executable code. Let's take a closer look at that claim and at other optimizations that might cause problems.

It is generally accepted that a compiler can reorder ordinary reads from and writes to memory almost arbitrarily, provided the reordering cannot change the observed single-threaded execution of the code. For example, consider this program:

w = 1
x = 2
r1 = y
r2 = z

Since w, x, y, and z are all different variables, these four statements can be executed in any order deemed best by the compiler.

As we noted above, the ability to reorder reads and writes so freely makes the guarantees of ordinary compiled programs at least as weak as the ARM/POWER relaxed memory model, since compiled programs fail the message passing litmus test. In fact, the guarantees for compiled programs are weaker.

In the hardware post, we looked at coherence as an example of something that ARM/POWER architectures do guarantee:

Litmus Test: Coherence
Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1?
(Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: no.
In any modern compiled language using ordinary variables: yes!

All modern hardware guarantees coherence, which can also be viewed as sequential consistency for the operations on a single memory location. In this program, one of the writes must overwrite the other, and the entire system has to agree about which is which. It turns out that, because of program reordering during compilation, modern languages do not even provide coherence.

Suppose the compiler reorders the two reads in thread 4, and then the instructions run as if interleaved in this order:

// Thread 1    // Thread 2    // Thread 3    // Thread 4
                                             // (reordered)
(1) x = 1                     (2) r1 = x     (3) r4 = x
               (4) x = 2      (5) r2 = x     (6) r3 = x

The result is r1 = 1, r2 = 2, r3 = 2, r4 = 1, which was impossible in the assembly programs but possible in high-level languages. In this sense, programming language memory models are all weaker than the most relaxed hardware memory models.

But there are some guarantees. Everyone agrees on the need to provide DRF-SC, which disallows optimizations that introduce new reads or writes, even if those optimizations would have been valid in single-threaded code.

For example, consider this code:

if(c) {
	x++;
} else {
	... lots of code ...
}

There’s an if statement with lots of code in the else and only an x++ in the if body. It might be cheaper to have fewer branches and eliminate the if body entirely. We can do that by running the x++ before the if and then adjusting with an x-- in the big else body if we were wrong. That is, the compiler might consider rewriting that code to:

x++;
if(!c) {
	x--;
	... lots of code ...
}

Is this a safe compiler optimization? In a single-threaded program, yes. In a multithreaded program in which x is shared with another thread when c is false, no: the optimization would introduce a race on x that was not present in the original program.

This example is derived from one in Hans Boehm's 2004 paper, “Threads Cannot Be Implemented As a Library,” which makes the case that languages cannot be silent about the semantics of multithreaded execution.

The programming language memory model is an attempt to precisely answer these questions about which optimizations are allowed and which are not. By examining the history of attempts at writing these models over the past couple decades, we can learn what worked and what didn't, and get a sense of where things are headed.

Original Java Memory Model (1996)

Java was the first mainstream language to try to write down what it guaranteed to multithreaded programs. It included mutexes and defined the memory ordering requirements they implied. It also included “volatile” atomic variables: all the reads and writes of volatile variables were required to execute in program order directly in main memory, making the operations on volatile variables behave in a sequentially consistent manner. Finally, Java also specified (or at least attempted to specify) the behavior of programs with data races. One part of this was to mandate a form of coherence for ordinary variables, which we will examine more below. Unfortunately, this attempt, in the first edition of the Java Language Specification (1996), had at least two serious flaws. They are easy to explain with the benefit of hindsight and using the preliminaries we've already set down. At the time, they were far less obvious.

Atomics need to synchronize

The first flaw was that volatile atomic variables were non-synchronizing, so they did not help eliminate races in the rest of the program. The Java version of the message passing program we saw above would be:

int x;
volatile int done;

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

Because done is declared volatile, the loop is guaranteed to finish: the compiler cannot cache it in a register and cause an infinite loop. However, the program is not guaranteed to print 1. The compiler was not prohibited from reordering the accesses to x and done, nor was it required to prohibit the hardware from doing the same.

Because Java volatiles were non-synchronizing atomics, you could not use them to build new synchronization primitives. In this sense, the original Java memory model was too weak.

Coherence is incompatible with compiler optimizations

The orginal Java memory model was also too strong: mandating coherence—once a thread had read a new value of a memory location, it could not appear to later read the old value—disallowed basic compiler optimizations. Earlier we looked at how reordering reads would break coherence, but you might think, well, just don't reorder reads. Here's a more subtle way coherence might be broken by another optimization: common subexpression elimination.

Consider this Java program:

// p and q may or may not point at the same object.
int i = p.x;
// ... maybe another thread writes p.x at this point ...
int j = q.x;
int k = p.x;

In this program, common subexpression elimination would notice that p.x is computed twice and optimize the final line to k = i. But if p and q pointed to the same object and another thread wrote to p.x between the reads into i and j, then reusing the old value i for k violates coherence: the read into i saw an old value, the read into j saw a newer value, but then the read into k reusing i would once again see the old value. Not being able to optimize away redundant reads would hobble most compilers, making the generated code slower.

Coherence is easier for hardware to provide than for compilers because hardware can apply dynamic optimizations: it can adjust the optimization paths based on the exact addresses involved in a given sequence of memory reads and writes. In contrast, compilers can only apply static optimizations: they have to write out, ahead of time, an instruction sequence that will be correct no matter what addresses and values are involved. In the example, the compiler cannot easily change what happens based on whether p and q happen to point to the same object, at least not without writing out code for both possibilities, leading to significant time and space overheads. The compiler's incomplete knowledge about the possible aliasing between memory locations means that actually providing coherence would require giving up fundamental optimizations.

Bill Pugh identified this and other problems in his 1999 paper “Fixing the Java Memory Model.”

New Java Memory Model (2004)

Because of these problems, and because the original Java Memory Model was difficult even for experts to understand, Pugh and others started an effort to define a new memory model for Java. That model became JSR-133 and was adopted in Java 5.0, released in 2004. The canonical reference is “The Java Memory Model” (2005), by Jeremy Manson, Bill Pugh, and Sarita Adve, with additional details in Manson's Ph.D. thesis. The new model follows the DRF-SC approach: Java programs that are data-race-free are guaranteed to execute in a sequentially consistent manner.

Synchronizing atomics and other operations

As we saw earlier, to write a data-race-free program, programmers need synchronization operations that can establish happens-before edges to ensure that one thread does not write a non-atomic variable concurrently with another thread reading or writing it. In Java, the main synchronization operations are:

The creation of a thread happens before the first action in the thread.
An unlock of mutex m happens before any subsequent lock of m.
A write to volatile variable v happens before any subsequent read of v.

What does “subsequent” mean? Java defines that all lock, unlock, and volatile variable accesses behave as if they ocurred in some sequentially consistent interleaving, giving a total order over all those operations in the entire program. “Subsequent” means later in that total order. That is: the total order over lock, unlock, and volatile variable accesses defines the meaning of subsequent, then subsequent defines which happens-before edges are created by a particular execution, and then the happens-before edges define whether that particular execution had a data race. If there is no race, then the execution behaves in a sequentially consistent manner.

The fact that the volatile accesses must act as if in some total ordering means that in the store buffer litmus test, you can’t end up with r1 = 0 and r2 = 0:

Litmus Test: Store Buffering
Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!
On Java using volatiles: no.

In Java, for volatile variables x and y, the reads and writes cannot be reordered: one write has to come second, and the read that follows the second write must see the first write. If we didn’t have the sequentially consistent requirement—if, say, volatiles were only required to be coherent—the two reads could miss the writes.

There is an important but subtle point here: the total order over all the synchronizing operations is separate from the happens-before relationship. It is not true that there is a happens-before edge in one direction or the other between every lock, unlock, or volatile variable access in a program: you only get a happens-before edge from a write to a read that observes the write. For example, a lock and unlock of different mutexes have no happens-before edges between them, nor do volatile accesses of different variables, even though collectively these operations must behave as if following a single sequentially consistent interleaving.

Semantics for racy programs

DRF-SC only guarantees sequentially consistent behavior to programs with no data races. The new Java memory model, like the original, defined the behavior of racy programs, for a number of reasons:

To support Java’s general security and safety guarantees.
To make it easier for programmers to find mistakes.
To make it harder for attackers to exploit problems, because the damage possible due to a race is more limited.
To make it clearer to programmers what their programs do.

Instead of relying on coherence, the new model reused the happens-before relation (already used to decide whether a program had a race at all) to decide the outcome of racing reads and writes.

The specific rules for Java are that for word-sized or smaller variables, a read of a variable (or field) x must see the value stored by some single write to x. A write to x can be observed by a read r provided r does not happen before w. That means r can observe writes that happen before r (but that aren’t also overwritten before r), and it can observe writes that race with r.

Using happens-before in this way, combined with synchronizing atomics (volatiles) that could establish new happens-before edges, was a major improvement over the original Java memory model. It provided more useful guarantees to the programmer, and it made a large number of important compiler optimizations definitively allowed. This work is still the memory model for Java today. That said, it’s also still not quite right: there are problems with this use of happens-before for trying to define the semantics of racy programs.

Happens-before does not rule out incoherence

The first problem with happens-before for defining program semantics has to do with coherence (again!). (The following example is taken from Jaroslav Ševčík and David Aspinall's paper, “On the Validity of Program Transformations in the Java Memory Model” (2007).)

Here’s a program with three threads. Let’s assume that Thread 1 and Thread 2 are known to finish before Thread 3 starts.

// Thread 1           // Thread 2           // Thread 3
lock(m1)              lock(m2)
x = 1                 x = 2
unlock(m1)            unlock(m2)
                                            lock(m1)
                                            lock(m2)
                                            r1 = x
                                            r2 = x
                                            unlock(m2)
                                            unlock(m1)

Thread 1 writes x = 1 while holding mutex m1. Thread 2 writes x = 2 while holding mutex m2. Those are different mutexes, so the two writes race. However, only thread 3 reads x, and it does so after acquiring both mutexes. The read into r1 can read either write: both happen before it, and neither definitively overwrites the other. By the same argument, the read into r2 can read either write. But strictly speaking, nothing in the Java memory model says the two reads have to agree: technically, r1 and r2 can be left having read different values of x. That is, this program can end with r1 and r2 holding different values. Of course, no real implementation is going to produce different r1 and r2. Mutual exclusion means there are no writes happening between those two reads. They have to get the same value. But the fact that the memory model allows different reads shows that it is, in a certain technical way, not precisely describing real Java implementations.

The situation gets worse. What if we add one more instruction, x = r1, between the two reads:

// Thread 1           // Thread 2           // Thread 3
lock(m1)              lock(m2)
x = 1                 x = 2
unlock(m1)            unlock(m2)
                                            lock(m1)
                                            lock(m2)
                                            r1 = x
                                            x = r1   // !?
                                            r2 = x
                                            unlock(m2)
                                            unlock(m1)

Now, clearly the r2 = x read must use the value written by x = r1, so the program must get the same values in r1 and r2. The two values r1 and r2 are now guaranteed to be equal.

The difference between these two programs means we have a problem for compilers. A compiler that sees r1 = x followed by x = r1 may well want to delete the second assignment, which is “clearly” redundant. But that “optimization” changes the second program, which must see the same values in r1 and r2, into the first program, which technically can have r1 different from r2. Therefore, according to the Java Memory Model, this optimization is technically invalid: it changes the meaning of the program. To be clear, this optimization would not change the meaning of Java programs executing on any real JVM you can imagine. But somehow the Java Memory Model doesn’t allow it, suggesting there’s more that needs to be said.

For more about this example and others, see Ševčík and Aspinall's paper.

Happens-before does not rule out acausality

That last example turns out to have been the easy problem. Here’s a harder problem. Consider this litmus test, using ordinary (not volatile) Java variables:

Litmus Test: Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?

// Thread 1           // Thread 2
r1 = x                r2 = y
y = r1                x = r2

(Obviously not!)

All the variables in this program start out zeroed, as always, and then this program effectively runs y = x in one thread and x = y in the other thread. Can x and y end up being 42? In real life, obviously not. But why not? The memory model turns out not to disallow this result.

Suppose hypothetically that “r1 = x” did read 42. Then “y = r1” would write 42 to y, and then the racing “r2 = y” could read 42, causing the “x = r2” to write 42 to x, and that write races with (and is therefore observable by) the original “r1 = x,” appearing to justify the original hypothetical. In this example, 42 is called an out-of-thin-air value, because it appeared without any justification but then justified itself with circular logic. What if the memory had formerly held a 42 before its current 0, and the hardware incorrectly speculated that it was still 42? That speculation might become a self-fulfilling prophecy. (This argument seemed more far-fetched before Spectre and related attacks showed just how aggressively hardware speculates. Even so, no hardware invents out-of-thin-air values this way.)

It seems clear that this program cannot end with r1 and r2 set to 42, but happens-before doesn’t by itself explain why this can’t happen. That suggests again that there’s a certain incompleteness. The new Java Memory Model spends a lot of time addressing this incompleteness, about which more shortly.

This program has a race—the reads of x and y are racing against writes in the other threads—so we might fall back on arguing that it's an incorrect program. But here is a version that is data-race-free:

Litmus Test: Non-Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?

// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2

(Obviously not!)

Since x and y start out zero, any sequentially consistent execution is never going to execute the writes, so this program has no writes, so there are no races. Once again, though, happens-before alone does not exclude the possibility that, hypothetically, r1 = x sees the racing not-quite-write, and then following from that hypothetical, the conditions both end up true and x and y are both 42 at the end. This is another kind of out-of-thin-air value, but this time in a program with no race. Any model guaranteeing DRF-SC must guarantee that this program only sees all zeros at the end, yet happens-before doesn't explain why.

The Java memory model spends a lot of words that I won’t go into to try to exclude these kinds of acausal hypotheticals. Unfortunately, five years later, Sarita Adve and Hans Boehm had this to say about that work:

Prohibiting such causality violations in a way that does not also prohibit other desired optimizations turned out to be surprisingly difficult. … After many proposals and five years of spirited debate, the current model was approved as the best compromise. … Unfortunately, this model is very complex, was known to have some surprising behaviors, and has recently been shown to have a bug.

(Adve and Boehm, “Memory Models: A Case For Rethinking Parallel Languages and Hardware,” August 2010)

C++11 Memory Model (2011)

Let’s put Java to the side and examine C++. Inspired by the apparent success of Java's new memory model, many of the same people set out to define a similar memory model for C++, eventually adopted in C++11. Compared to Java, C++ deviated in two important ways. First, C++ makes no guarantees at all for programs with data races, which would seem to remove the need for much of the complexity of the Java model. Second, C++ provides three kinds of atomics: strong synchronization (“sequentially consistent”), weak synchronization (“acquire/release”, coherence-only), and no synchronization (“relaxed”, for hiding races). The relaxed atomics reintroduced all of Java's complexity about defining the meaning of what amount to racy programs. The result is that the C++ model is more complicated than Java's yet less helpful to programmers.

C++11 also defined atomic fences as an alternative to atomic variables, but they are not as commonly used and I'm not going to discuss them.

DRF-SC or Catch Fire

Unlike Java, C++ gives no guarantees to programs with races. Any program with a race anywhere in it falls into “undefined behavior.” A racing access in the first microseconds of program execution is allowed to cause arbitrary errant behavior hours or days later. This is often called “DRF-SC or Catch Fire”: if the program is data-race free it runs in a sequentially consistent manner, and if not, it can do anything at all, including catch fire.

For a longer presentation of the arguments for DRF-SC or Catch Fire, see Boehm, “Memory Model Rationales” (2007) and Boehm and Adve, “Foundations of the C++ Concurrency Memory Model” (2008).

Briefly, there are four common justifications for this position:

C and C++ are already rife with undefined behavior, corners of the language where compiler optimizations run wild and users had better not wander or else. What's the harm in one more?
Existing compilers and libraries were written with no regard to threads, breaking racy programs in arbitrary ways. It would be too difficult to find and fix all the problems, or so the argument goes, although it is unclear how those unfixed compilers and libraries are meant to cope with relaxed atomics.
Programmers who really know what they are doing and want to avoid undefined behavior can use the relaxed atomics.
Leaving race semantics undefined allows an implementation to detect and diagnose races and stop execution.

Personally, the last justification is the only one I find compelling, although I observe that it is possible to say “race detectors are allowed” without also saying “one race on an integer can invalidate your entire program.”

Here is an example from “Memory Model Rationales” that I think captures the essence of the C++ approach as well as its problems. Consider this program, which refers to a global variable x.

unsigned i = x;

if (i < 2) {
	foo: ...
	switch (i) {
	case 0:
		...;
		break;
	case 1:
		...;
		break;
	}
}

The claim is that a C++ compiler might be holding i in a register but then need to reuse the registers if the code at label foo is complex. Rather than spill the current value of i to the function stack, the compiler might instead decide to load i a second time from the global x upon reaching the switch statement. The result is that, halfway through the if body, i < 2 may stop being true. If the compiler did something like compiling the switch into a computed jump using a table indexed by i, that code would index off the end of the table and jump to an unexpected address, which could be arbitrarily bad.

From this example and others like it, the C++ memory model authors conclude that any racy access must be allowed to cause unbounded damage to the future execution of the program. Personally, I conclude instead that in a multithreaded program, compilers should not assume that they can reload a local variable like i by re-executing the memory read that initialized it. It may well have been impractical to expect existing C++ compilers, written for a single-threaded world, to find and fix code generation problems like this one, but in new languages, I think we should aim higher.

Digression: Undefined behavior in C and C++

As an aside, the C and C++ insistence on the compiler's ability to behave arbitrarily badly in response to bugs in programs leads to truly ridiculous results. For example, consider this program, which was a topic of discussion on Twitter in 2017:

#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
	return system("rm -rf slash");
}

void NeverCalled() {
	Do = EraseAll;
}

int main() {
	return Do();
}

If you were a modern C++ compiler like Clang, you might think about this program as follows:

In main, clearly Do is either null or EraseAll.
If Do is EraseAll, then Do() is the same as EraseAll().
If Do is null, then Do() is undefined behavior, which I can implement however I want, including as EraseAll() unconditionally.
Therefore I can optimize the indirect call Do() down to the direct call EraseAll().
I might as well inline EraseAll while I'm here.

The end result is that Clang optimizes the program down to:

int main() {
	return system("rm -rf slash");
}

You have to admit: next to this example, the possibility that the local variable i might suddenly stop being less than 2 halfway through the body of if (i < 2) does not seem out of place.

In essence, modern C and C++ compilers assume no programmer would dare attempt undefined behavior. A programmer writing a program with a bug? Inconceivable!

Like I said, in new languages I think we should aim higher.

Acquire/release atomics

C++ adopted sequentially consistent atomic variables much like (new) Java’s volatile variables (no relation to C++ volatile). In our message passing example, we can declare done as

atomic<int> done;

and then use done as if it were an ordinary variable, like in Java. Or we can declare an ordinary int done; and then use

atomic_store(&done, 1);

and

while(atomic_load(&done) == 0) { /* loop */ }

to access it. Either way, the operations on done take part in the sequentially consistent total order on atomic operations and synchronize the rest of the program.

C++ also added weaker atomics, which can be accessed using atomic_store_explicit and atomic_load_explicit with an additional memory ordering argument. Using memory_order_seq_cst makes the explicit calls equivalent to the shorter ones above.

The weaker atomics are called acquire/release atomics, in which a release observed by a later acquire creates a happens-before edge from the release to the acquire. The terminology is meant to evoke mutexes: release is like unlocking a mutex, and acquire is like locking that same mutex. The writes executed before the release must be visible to reads executed after the subsequent acquire, just as writes executed before unlocking a mutex must be visible to reads executed after later locking that same mutex.

To use the weaker atomics, we could change our message-passing example to use

atomic_store(&done, 1, memory_order_release);

and

while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ }

and it would still be correct. But not all programs would.

Recall that the sequentially consistent atomics required the behavior of all the atomics in the program to be consistent with some global interleaving—a total order—of the execution. Acquire/release atomics do not. They only require a sequentially consistent interleaving of the operations on a single memory location. That is, they only require coherence. The result is that a program using acquire/release atomics with more than one memory location may observe executions that cannot be explained by a sequentially consistent interleaving of all the acquire/release atomics in the program, arguably a violation of DRF-SC!

To show the difference, here’s the store buffer example again:

Litmus Test: Store Buffering
Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!
On Java (using volatiles): no.
On C++11 (sequentially consistent atomics): no.
On C++11 (acquire/release atomics): yes!

The C++ sequentially consistent atomics match Java's volatile. But the acquire-release atomics impose no relationship between the orderings for x and the orderings for y. In particular, it is allowed for the program to behave as if r1 = y happened before y = 1 while at the same time r2 = x happened before x = 1, allowing r1 = 0, r2 = 0 in contradiction of whole-program sequential consistency. These probably exist only because they are free on x86.

Note that, for a given set of specific reads observing specific writes, C++ sequentially consistent atomics and C++ acquire/release atomics create the same happens-before edges. The difference between them is that some sets of specific reads observing specific writes are disallowed by sequentially consistent atomics but allowed by acquire/release atomics. One such example is the set that leads to r1 = 0, r2 = 0 in the store buffering case.

A real example of the weakness of acquire/release

Acquire/release atomics are less useful in practice than atomics providing sequential consistency. Here is an example. Suppose we have a new synchronization primitive, a single-use condition variable with two methods Notify and Wait. For simplicity, only a single thread will call Notify and only a single thread will call Wait. We want to arrange for Notify to be lock-free when the other thread is not yet waiting. We can do this with a pair of atomic integers:

class Cond {
	atomic<int> done;
	atomic<int> waiting;
	...
};

void Cond::notify() {
	done = 1;
	if (!waiting)
		return;
	// ... wake up waiter ...
}

void Cond::wait() {
	waiting = 1;
	if(done)
		return;
	// ... sleep ...
}

The important part about this code is that notify sets done before checking waiting, while wait sets waiting before checking done, so that concurrent calls to notify and wait cannot result in notify returning immediately and wait sleeping. But with C++ acquire/release atomics, they can. And they probably would only some fraction of time, making the bug very hard to reproduce and diagnose. (Worse, on some architectures like 64-bit ARM, the best way to implement acquire/release atomics is as sequentially consistent atomics, so you might write code that works fine on 64-bit ARM and only discover it is incorrect when porting to other systems.)

With this understanding, “acquire/release” is an unfortunate name for these atomics, since the sequentially consistent ones do just as much acquiring and releasing. What's different about these is the loss of sequential consistency. It might have been better to call these “coherence” atomics. Too late.

Relaxed atomics

C++ did not stop with the merely coherent acquire/release atomics. It also introduced non-synchronizing atomics, called relaxed atomics (memory_order_relaxed). These atomics have no synchronizing effect at all—they create no happens-before edges—and they have no ordering guarantees at all either. In fact, there is no difference between a relaxed atomic read/write and an ordinary read/write except that a race on relaxed atomics is not considered a race and cannot catch fire.

Much of the complexity of the revised Java memory model arises from defining the behavior of programs with data races. It would be nice if C++'s adoption of DRF-SC or Catch Fire—effectively disallowing programs with data races—meant that we could throw away all those strange examples we looked at earlier, so that the C++ language spec would end up simpler than Java's. Unfortunately, including the relaxed atomics ends up preserving all those concerns, meaning the C++11 spec ended up no simpler than Java's.

Like Java's memory model, the C++11 memory model also ended up incorrect. Consider the data-race-free program from before:

Litmus Test: Non-Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?

// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2

(Obviously not!)

C++11 (ordinary variables): no.
C++11 (relaxed atomics): yes!

In their paper “Common Compiler Optimisations are Invalid in the C11 Memory Model and what we can do about it” (2015), Viktor Vafeiadis and others showed that the C++11 specification guarantees that this program must end with x and y set to zero when x and y are ordinary variables. But if x and y are relaxed atomics, then, strictly speaking, the C++11 specification does not rule out that r1 and r2 might both end up 42. (Surprise!)

See the paper for the details, but at a high level, the C++11 spec had some formal rules trying to disallow out-of-thin-air values, combined with some vague words to discourage other kinds of problematic values. Those formal rules were the problem, so C++14 dropped them and left only the vague words. Quoting the rationale for removing them, the C++11 formulation turned out to be “both insufficient, in that it leaves it largely impossible to reason about programs with memory_order_relaxed, and seriously harmful, in that it arguably disallows all reasonable implementations of memory_order_relaxed on architectures like ARM and POWER.”

To recap, Java tried to exclude all acausal executions formally and failed. Then, with the benefit of Java's hindsight, C++11 tried to exclude only some acausal executions formally and also failed. C++14 then said nothing formal at all. This is not going in the right direction.

In fact, a paper by Mark Batty and others from 2015 titled “The Problem of Programming Language Concurrency Semantics” gave this sobering assessment:

Disturbingly, 40+ years after the first relaxed-memory hardware was introduced (the IBM 370/158MP), the field still does not have a credible proposal for the concurrency semantics of any general-purpose high-level language that includes high-performance shared-memory concurrency primitives.

Even defining the semantics of weakly-ordered hardware (ignoring the complications of software and compiler optimization) is not going terribly well. A paper by Sizhuo Zhang and others in 2018 titled “Constructing a Weak Memory Model” recounted more recent events:

Sarkar et al. published an operational model for POWER in 2011, and Mador-Haim et al. published an axiomatic model that was proven to match the operational model in 2012. However, in 2014, Alglave et al. showed that the original operational model, as well as the corresponding axiomatic model, ruled out a newly observed behavior on POWER machines. For another instance, in 2016, Flur et al. gave an operational model for ARM, with no corresponding axiomatic model. One year later, ARM released a revision in their ISA manual explicitly forbidding behaviors allowed by Flur's model, and this resulted in another proposed ARM memory model. Clearly, formalizing weak memory models empirically is error-prone and challenging.

The researchers who have been working to define and formalize all of this over the past decade are incredibly smart, talented, and persistent, and I don't mean to detract from their efforts and accomplishments by pointing out inadequacies in the results. I conclude from those simply that this problem of specifying the exact behavior of threaded programs, even without races, is incredibly subtle and difficult. Today, it seems still beyond the grasp of even the best and brightest researchers. Even if it weren't, a programming language definition works best when it is understandable by everyday developers, without the requirement of spending a decade studying the semantics of concurrent programs.

C, Rust and Swift Memory Models

C11 adopted the C++11 memory model as well, making it the C/C++11 memory model.

Rust 1.0.0 in 2015 and Swift 5.3 in 2020 both adopted the C/C++ memory model in its entirety, with DRF-SC or Catch Fire and all the atomic types and atomic fences.

It is not surprising that both of these languages adopted the C/C++ model, since they are built on a C/C++ compiler toolchain (LLVM) and emphasize close integration with C/C++ code.

Hardware Digression: Efficient Sequentially Consistent Atomics

Early multiprocessor architectures had a variety of synchronization mechanisms and memory models, with varying degrees of usability. In this diversity, the efficiency of different synchronization abstractions depended on how well they mapped to what the architecture provided. To construct the abstraction of sequentially consistent atomic variables, sometimes the only choice was to use barriers that did more and were far more expensive than strictly necessary, especially on ARM and POWER.

With C, C++, and Java all providing this same abstraction of sequentially consistent synchronizing atomics, it behooves hardware designers to make that abstraction efficient. The ARMv8 architecture (both 32- and 64-bit) introduced ldar and stlr load and store instructions, providing a direct implementation. In a talk in 2017, Herb Sutter claimed that IBM had approved him saying that they intended future POWER implementations to have some kind of more efficient support for sequentially consistent atomics as well, giving programmers “less reason to use relaxed atomics.” I can't tell whether that happened, although here in 2021, POWER has turned out to be much less relevant than ARMv8.

The effect of this convergence is that sequentially consistent atomics are now well understood and can be efficiently implemented on all major hardware platforms, making them a good target for programming language memory models.

JavaScript Memory Model (2017)

You might think that JavaScript, a notoriously single-threaded language, would not need to worry about a memory model for what happens when code runs in parallel on multiple processors. I certainly did. But you and I would be wrong.

JavaScript has web workers, which allow running code in another thread. As originally conceived, workers only communicated with the main JavaScript thread by explicit message copying. With no shared writable memory, there was no need to consider issues like data races. However, ECMAScript 2017 (ES2017) added the SharedArrayBuffer object, which lets the main thread and workers share a block of writable memory. Why do this? In an early draft of the proposal, the first reason listed is compiling multithreaded C++ code to JavaScript.

Of course, having shared writable memory also requires defining atomic operations for synchronization and a memory model. JavaScript deviates from C++ in three important ways:

First, it limits the atomic operations to just sequentially consistent atomics. Other atomics can be compiled to sequentially consistent atomics with perhaps a loss in efficiency but no loss in correctness, and having only one kind simplifies the rest of the system.
Second, JavaScript does not adopt “DRF-SC or Catch Fire.” Instead, like Java, it carefully defines the possible results of racy accesses. The rationale is much the same as Java, in particular security. Allowing a racy read to return any value at all allows (arguably encourages) implementations to return unrelated data, which could lead to leaking private data at run time.
Third, in part because JavaScript provides semantics for racy programs, it defines what happens when atomic and non-atomic operations are used on the same memory location, as well as when the same memory location is accessed using different-sized accesses.

Precisely defining the behavior of racy programs leads to the usual complexities of relaxed memory semantics and how to disallow out-of-thin-air reads and the like. In addition to those challenges, which are mostly the same as elsewhere, the ES2017 definition had two interesting bugs that arose from a mismatch with the semantics of the new ARMv8 atomic instructions. These examples are adapted from Conrad Watt et al.'s 2020 paper “Repairing and Mechanising the JavaScript Relaxed Memory Model.”

As we noted in the previous section, ARMv8 added ldar and stlr instructions providing sequentially consistent atomic load and store. These were targeted to C++, which does not define the behavior of any program with a data race. Unsurprisingly, then, the behavior of these instructions in racy programs did not match the expectations of the ES2017 authors, and in particular it did not satisfy the ES2017 requirements for racy program behavior.

Litmus Test: ES2017 racy reads on ARMv8
Can this program (using atomics) see r1 = 0, r2 = 1?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                x = 2 (non-atomic)
                      r2 = x

C++: yes (data race, can do anything at all).
Java: the program cannot be written.
ARMv8 using ldar/stlr: yes.
ES2017: no! (contradicting ARMv8)

In this program, all the reads and writes are sequentially consistent atomics with the exception of x = 2: thread 1 writes x = 1 using an atomic store, but thread 2 writes x = 2 using a non-atomic store. In C++, this is a data race, so all bets are off. In Java, this program cannot be written: x must either be declared volatile or not; it can't be accessed atomically only sometimes. In ES2017, the memory model turns out to disallow r1 = 0, r2 = 1. If r1 = y reads 0, thread 1 must complete before thread 2 begins, in which case the non-atomic x = 2 would seem to happen after and overwrite the x = 1, causing the atomic r2 = x to read 2. This explanation seems entirely reasonable, but it is not the way ARMv8 processors work.

It turns out that, for the equivalent sequence of ARMv8 instructions, the non-atomic write to x can be reordered ahead of the atomic write to y, so that this program does in fact produce r1 = 0, r2 = 1. This is not a problem in C++, since the race means the program can do anything at all, but it is a problem for ES2017, which limits racy behaviors to a set of outcomes that does not include r1 = 0, r2 = 1.

Since it was an explicit goal of ES2017 to use the ARMv8 instructions to implement the sequentially consistent atomic operations, Watt et al. reported that their suggested fixes, slated to be included in the next revision of the standard, would weaken the racy behavior constraints just enough to allow this outcome. (It is unclear to me whether at the time “next revision” meant ES2020 or ES2021.)

Watt et al.'s suggested changes also included a fix to a second bug, first identified by Watt, Andreas Rossberg, and Jean Pichon-Pharabod, wherein a data-race-free program was not given sequentially consistent semantics by the ES2017 specification. That program is given by:

Litmus Test: ES2017 data-race-free program
Can this program (using atomics) see r1 = 1, r2 = 2?

// Thread 1           // Thread 2
x = 1                 x = 2
                      r1 = x
                      if (r1 == 1) {
                          r2 = x // non-atomic
                      }

On sequentially consistent hardware: no.
C++: I'm not enough of a C++ expert to say for sure.
Java: the program cannot be written.
ES2017: yes! (violating DRF-SC).

In this program, all the reads and writes are sequentially consistent atomics with the exception of r2 = x, as marked. This program is data-race-free: the non-atomic read, which would have to be involved in any data race, only executes when r1 = 1, which proves that thread 1's x = 1 happens before the r1 = x and therefore also before the r2 = x. DRF-SC means that the program must execute in a sequentially consistent manner, so that r1 = 1, r2 = 2 is impossible, but the ES2017 specification allowed it.

The ES2017 specification of program behavior was therefore simultaneously too strong (it disallowed real ARMv8 behavior for racy programs) and too weak (it allowed non-sequentially consistent behavior for race-free programs). As noted earlier, these mistakes are fixed. Even so, this is yet another reminder about how subtle it can be to specify the semantics of both data-race-free and racy programs exactly using happens-before, as well as how subtle it can be to match up language memory models with the underlying hardware memory models.

It is encouraging that at least for now JavaScript has avoided adding any other atomics besides the sequentially consistent ones and has resisted “DRF-SC or Catch Fire.” The result is a memory model valid as a C/C++ compilation target but much closer to Java.

Conclusions

Looking at C, C++, Java, JavaScript, Rust, and Swift, we can make the following observations:

They all provide sequentially consistent synchronizing atomics for coordinating the non-atomic parts of a parallel program.
They all aim to guarantee that programs made data-race-free using proper synchronization behave as if executed in a sequentially consistent manner.
Java resisted adding weak (acquire/release) synchronizing atomics until Java 9 introduced VarHandle. JavaScript has avoided adding them as of this writing.
They all provide a way for programs to execute “intentional” data races without invalidating the rest of the program. In C, C++, Rust, and Swift, that mechanism is relaxed, non-synchronizing atomics, a special form of memory access. In Java, that mechanism is either ordinary memory access or the Java 9 VarHandle “plain” access mode. In JavaScript, that mechanism is ordinary memory access.
None of the languages have found a way to formally disallow paradoxes like out-of-thin-air values, but all informally disallow them.

Meanwhile, processor manufacturers seem to have accepted that the abstraction of sequentially consistent synchronizing atomics is important to implement efficiently and are starting to do so: ARMv8 and RISC-V both provide direct support.

Finally, a truly immense amount of verification and formal analysis work has gone into understanding these systems and stating their behaviors precisely. It is particularly encouraging that Watt et al. were able in 2020 to give a formal model of a significant subset of JavaScript and use a theorem prover to prove correctness of compilation to ARM, POWER, RISC-V, and x86-TSO.

Twenty-five years after the first Java memory model, and after many person-centuries of research effort, we may be starting to be able to formalize entire memory models. Perhaps, one day, we will also fully understand them.

The next post in this series is “Updating the Go Memory Model.”

Acknowledgements

Hardware Memory Models

2021-06-29T12:49:00-04:00

Introduction: A Fairy Tale, Ending

A long time ago, when everyone wrote single-threaded programs, one of the most effective ways to make a program run faster was to sit back and do nothing. Optimizations in the next generation of hardware and the next generation of compilers would make the program run exactly as before, just faster. During this fairy-tale period, there was an easy test for whether an optimization was valid: if programmers couldn't tell the difference (except for the speedup) between the unoptimized and optimized execution of a valid program, then the optimization was valid. That is, valid optimizations do not change the behavior of valid programs.

One sad day, years ago, the hardware engineers' magic spells for making individual processors faster and faster stopped working. In response, they found a new magic spell that let them create computers with more and more processors, and operating systems exposed this hardware parallelism to programmers in the abstraction of threads. This new magic spell—multiple processors made available in the form of operating-system threads—worked much better for the hardware engineers, but it created significant problems for language designers, compiler writers and programmers.

Many hardware and compiler optimizations that were invisible (and therefore valid) in single-threaded programs produce visible changes in multithreaded programs. If valid optimizations do not change the behavior of valid programs, then either these optimizations or the existing programs must be declared invalid. Which will it be, and how can we decide?

Here is a simple example program in a C-like language. In this program and in all programs we will consider, all variables are initially set to zero.

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

If thread 1 and thread 2, each running on its own dedicated processor, both run to completion, can this program print 0?

It depends. It depends on the hardware, and it depends on the compiler. A direct line-for-line translation to assembly run on an x86 multiprocessor will always print 1. But a direct line-for-line translation to assembly run on an ARM or POWER multiprocessor can print 0. Also, no matter what the underlying hardware, standard compiler optimizations could make this program print 0 or go into an infinite loop.

“It depends” is not a happy ending. Programmers need a clear answer to whether a program will continue to work with new hardware and new compilers. And hardware designers and compiler developers need a clear answer to how precisely the hardware and compiled code are allowed to behave when executing a given program. Because the main issue here is the visibility and consistency of changes to data stored in memory, that contract is called the memory consistency model or just memory model.

Originally, the goal of a memory model was to define what hardware guaranteed to a programmer writing assembly code. In that setting, the compiler is not involved. Twenty-five years ago, people started trying to write memory models defining what a high-level programming language like Java or C++ guarantees to programmers writing code in that language. Including the compiler in the model makes the job of defining a reasonable model much more complicated.

This is the first of a pair of posts about hardware memory models and programming language memory models, respectively. My goal in writing these posts is to build up background for discussing potential changes we might want to make in Go's memory model. But to understand where Go is and where we might want to head, first we have to understand where other hardware memory models and language memory models are today and the precarious paths they took to get there.

Again, this post is about hardware. Let's assume we are writing assembly language for a multiprocessor computer. What guarantees do programmers need from the computer hardware in order to write correct programs? Computer scientists have been searching for good answers to this question for over forty years.

Sequential Consistency

Leslie Lamport's 1979 paper “How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs” introduced the concept of sequential consistency:

The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent.

Today we talk about not just computer hardware but also programming languages guaranteeing sequential consistency, when the only possible executions of a program correspond to some kind of interleaving of thread operations into a sequential execution. Sequential consistency is usually considered the ideal model, the one most natural for programmers to work with. It lets you assume programs execute in the order they appear on the page, and the executions of individual threads are simply interleaved in some order but not otherwise rearranged.

One might reasonably question whether sequential consistency should be the ideal model, but that's beyond the scope of this post. I will note only that considering all possible thread interleavings remains, today as in 1979, “the customary approach to designing and proving the correctness of multiprocess algorithms.” In the intervening four decades, nothing has replaced it.

Earlier I asked whether this program can print 0:

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

To make the program a bit easier to analyze, let's remove the loop and the print and ask about the possible results from reading the shared variables:

Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?

// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

We assume every example starts with all shared variables set to zero. Because we're trying to establish what hardware is allowed to do, we assume that each thread is executing on its own dedicated processor and that there's no compiler to reorder what happens in the thread: the instructions in the listings are the instructions the processor executes. The name rN denotes a thread-local register, not a shared variable, and we ask whether a particular setting of thread-local registers is possible at the end of an execution.

This kind of question about execution results for a sample program is called a litmus test. Because it has a binary answer—is this outcome possible or not?—a litmus test gives us a clear way to distinguish memory models: if one model allows a particular execution and another does not, the two models are clearly different. Unfortunately, as we will see later, the answer a particular model gives to a particular litmus test is often surprising.

If the execution of this litmus test is sequentially consistent, there are only six possible interleavings:

Since no interleaving ends with r1 = 1, r2 = 0, that result is disallowed. That is, on sequentially consistent hardware, the answer to the litmus test—can this program see r1 = 1, r2 = 0?—is no.

A good mental model for sequential consistency is to imagine all the processors connected directly to the same shared memory, which can serve a read or write request from one thread at a time. There are no caches involved, so every time a processor needs to read from or write to memory, that request goes to the shared memory. The single-use-at-a-time shared memory imposes a sequential order on the execution of all the memory accesses: sequential consistency.

(The three memory model hardware diagrams in this post are adapted from Maranget et al., “A Tutorial Introduction to the ARM and POWER Relaxed Memory Models.”)

This diagram is a model for a sequentially consistent machine, not the only way to build one. Indeed, it is possible to build a sequentially consistent machine using multiple shared memory modules and caches to help predict the result of memory fetches, but being sequentially consistent means that machine must behave indistinguishably from this model. If we are simply trying to understand what sequentially consistent execution means, we can ignore all of those possible implementation complications and think about this one model.

Unfortunately for us as programmers, giving up strict sequential consistency can let hardware execute programs faster, so all modern hardware deviates in various ways from sequential consistency. Defining exactly how specific hardware deviates turns out to be quite difficult. This post uses as two examples two memory models present in today's widely-used hardware: that of the x86, and that of the ARM and POWER processor families.

x86 Total Store Order (x86-TSO)

The memory model for modern x86 systems corresponds to this hardware diagram:

All the processors are still connected to a single shared memory, but each processor queues writes to that memory in a local write queue. The processor continues executing new instructions while the writes make their way out to the shared memory. A memory read on one processor consults the local write queue before consulting main memory, but it cannot see the write queues on other processors. The effect is that a processor sees its own writes before others do. But—and this is very important—all processors do agree on the (total) order in which writes (stores) reach the shared memory, giving the model its name: total store order, or TSO. At the moment that a write reaches shared memory, any future read on any processor will see it and use that value (until it is overwritten by a later write, or perhaps by a buffered write from another processor).

The write queue is a standard first-in, first-out queue: the memory writes are applied to the shared memory in the same order that they were executed by the processor. Because the write order is preserved by the write queue, and because other processors see the writes to shared memory immediately, the message passing litmus test we considered earlier has the same outcome as before: r1 = 1, r2 = 0 remains impossible.

Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?

// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.

The write queue guarantees that thread 1 writes x to memory before y, and the system-wide agreement about the order of memory writes (the total store order) guarantees that thread 2 learns of x's new value before it learns of y's new value. Therefore it is impossible for r1 = y to see the new y without r2 = x also seeing the new x. The store order is crucial here: thread 1 writes x before y, so thread 2 must not see the write to y before the write to x.

The sequential consistency and TSO models agree in this case, but they disagree about the results of other litmus tests. For example, this is the usual example distinguishing the two models:

Litmus Test: Write Queue (also called Store Buffer)
Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): yes!

In any sequentially consistent execution, either x = 1 or y = 1 must happen first, and then the read in the other thread must observe it, so r1 = 0, r2 = 0 is impossible. But on a TSO system, it can happen that Thread 1 and Thread 2 both queue their writes and then read from memory before either write makes it to memory, so that both reads see zeros.

This example may seem artificial, but using two synchronization variables does happen in well-known synchronization algorithms, such as Dekker's algorithm or Peterson's algorithm, as well as ad hoc schemes. They break if one thread isn’t seeing all the writes from another.

To fix algorithms that depend on stronger memory ordering, non-sequentially-consistent hardware supplies explicit instructions called memory barriers (or fences) that can be used to control the ordering. We can add a memory barrier to make sure that each thread flushes its previous write to memory before starting its read:

// Thread 1           // Thread 2
x = 1                 y = 1
barrier               barrier
r1 = y                r2 = x

With the addition of the barriers, r1 = 0, r2 = 0 is again impossible, and Dekker's or Peterson's algorithm would then work correctly. There are many kinds of barriers; the details vary from system to system and are beyond the scope of this post. The point is only that barriers exist and give programmers or language implementers a way to force sequentially consistent behavior at critical moments in a program.

One final example, to drive home why the model is called total store order. In the model, there are local write queues but no caches on the read path. Once a write reaches main memory, all processors not only agree that the value is there but also agree about when it arrived relative to writes from other processors. Consider this litmus test:

Litmus Test: Independent Reads of Independent Writes (IRIW)
Can this program see r1 = 1, r2 = 0, r3 = 1, r4 = 0?
(Can Threads 3 and 4 see x and y change in different orders?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          y = 1          r1 = x         r3 = y
                              r2 = y         r4 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.

If Thread 3 sees x change before y, can Thread 4 see y change before x? For x86 and other TSO machines, the answer is no: there is a total order over all stores (writes) to main memory, and all processors agree on that order, subject to the wrinkle that each processor knows about its own writes before they reach main memory.

The Path to x86-TSO

The x86-TSO model seems fairly clean, but the path there was full of roadblocks and wrong turns. In the 1990s, the manuals available for the first x86 multiprocessors said next to nothing about the memory model provided by the hardware.

As one example of the problems, Plan 9 was one of the first true multiprocessor operating systems (without a global kernel lock) to run on the x86. During the port to the multiprocessor Pentium Pro, in 1997, the developers stumbled over unexpected behavior that boiled down to the write queue litmus test. A subtle piece of synchronization code assumed that r1 = 0, r2 = 0 was impossible, and yet it was happening. Worse, the Intel manuals were vague about the memory model details.

In response to a mailing list suggestion that “it's better to be conservative with locks than to trust hardware designers to do what we expect,” one of the Plan 9 developers explained the problem well:

I certainly agree. We are going to encounter more relaxed ordering in multiprocessors. The question is, what do the hardware designers consider conservative? Forcing an interlock at both the beginning and end of a locked section seems to be pretty conservative to me, but I clearly am not imaginative enough. The Pro manuals go into excruciating detail in describing the caches and what keeps them coherent but don't seem to care to say anything detailed about execution or read ordering. The truth is that we have no way of knowing whether we're conservative enough.

During the discussion, an architect at Intel gave an informal explanation of the memory model, pointing out that in theory even multiprocessor 486 and Pentium systems could have produced the r1 = 0, r2 = 0 result, and that the Pentium Pro simply had larger pipelines and write queues that exposed the behavior more often.

The Intel architect also wrote:

Loosely speaking, this means the ordering of events originating from any one processor in the system, as observed by other processors, is always the same. However, different observers are allowed to disagree on the interleaving of events from two or more processors.
Future Intel processors will implement the same memory ordering model.

The claim that “different observers are allowed to disagree on the interleaving of events from two or more processors” is saying that the answer to the IRIW litmus test can answer “yes” on x86, even though in the previous section we saw that x86 answers “no.” How can that be?

The answer appears to be that Intel processors never actually answered “yes” to that litmus test, but at the time the Intel architects were reluctant to make any guarantee for future processors. What little text existed in the architecture manuals made almost no guarantees at all, making it very difficult to program against.

The Plan 9 discussion was not an isolated event. The Linux kernel developers spent over a hundred messages on their mailing list starting in late November 1999 in similar confusion over the guarantees provided by Intel processors.

In response to more and more people running into these difficulties over the decade that followed, a group of architects at Intel took on the task of writing down useful guarantees about processor behavior, for both current and future processors. The first result was the “Intel 64 Architecture Memory Ordering White Paper”, published in August 2007, which aimed to “provide software writers with a clear understanding of the results that different sequences of memory access instructions may produce.” AMD published a similar description later that year in the AMD64 Architecture Programmer's Manual revision 3.14. These descriptions were based on a model called “total lock order + causal consistency” (TLO+CC), intentionally weaker than TSO. In public talks, the Intel architects said that TLO+CC was “as strong as required but no stronger.” In particular, the model reserved the right for x86 processors to answer “yes” to the IRIW litmus test. Unfortunately, the definition of the memory barrier was not strong enough to reestablish sequentially-consistent memory semantics, even with a barrier after every instruction. Even worse, researchers observed actual Intel x86 hardware violating the TLO+CC model. For example:

Litmus Test: n6 (Paul Loewenstein)
Can this program end with r1 = 1, r2 = 0, x = 1?

// Thread 1    // Thread 2
x = 1          y = 1
r1 = x         x = 2
r2 = y

On sequentially consistent hardware: no.
On x86 TLO+CC model (2007): no.
On actual x86 hardware: yes!
On x86 TSO model: yes! (Example from x86-TSO paper.)

Revisions to the Intel and AMD specifications later in 2008 guaranteed a “no” to the IRIW case and strengthened the memory barriers but still permitted unexpected behaviors that seem like they could not arise on any reasonable hardware. For example:

Litmus Test: n5
Can this program end with r1 = 2, r2 = 1?

// Thread 1    // Thread 2
x = 1          x = 2
r1 = x         r2 = x

On sequentially consistent hardware: no.
On x86 specification (2008): yes!
On actual x86 hardware: no.
On x86 TSO model: no. (Example from x86-TSO paper.)

To address these problems, Owens et al. proposed the x86-TSO model, based on the earlier SPARCv8 TSO model. At the time they claimed that “To the best of our knowledge, x86-TSO is sound, is strong enough to program above, and is broadly in line with the vendors’ intentions.” A few months later Intel and AMD released new manuals broadly adopting this model.

It appears that all Intel processors did implement x86-TSO from the start, even though it took a decade for Intel to decide to commit to that. In retrospect, it is clear that the Intel and AMD architects were struggling with exactly how to write a memory model that left room for future processor optimizations while still making useful guarantees for compiler writers and assembly-language programmers. “As strong as required but no stronger” is a difficult balancing act.

ARM/POWER Relaxed Memory Model

Now let's look at an even more relaxed memory model, the one found on ARM and POWER processors. At an implementation level, these two systems are different in many ways, but the guaranteed memory consistency model turns out to be roughly similar, and quite a bit weaker than x86-TSO or even x86-TLO+CC.

The conceptual model for ARM and POWER systems is that each processor reads from and writes to its own complete copy of memory, and each write propagates to the other processors independently, with reordering allowed as the writes propagate.

Here, there is no total store order. Not depicted, each processor is also allowed to postpone a read until it needs the result: a read can be delayed until after a later write. In this relaxed model, the answer to every litmus test we’ve seen so far is “yes, that really can happen.”

For the original message passing litmus test, the reordering of writes by a single processor means that Thread 1's writes may not be observed by other threads in the same order:

Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?

// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!

In the ARM/POWER model, we can think of thread 1 and thread 2 each having their own separate copy of memory, with writes propagating between the memories in any order whatsoever. If thread 1's memory sends the update of y to thread 2 before sending the update of x, and if thread 2 executes between those two updates, it will indeed see the result r1 = 1, r2 = 0.

This result shows that the ARM/POWER memory model is weaker than TSO: it makes fewer requirements on the hardware. The ARM/POWER model still admits the kinds of reorderings that TSO does:

Litmus Test: Store Buffering
Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!

On ARM/POWER, the writes to x and y might be made to the local memories but not yet have propagated when the reads occur on the opposite threads.

Here’s the litmus test that showed what it meant for x86 to have a total store order:

Litmus Test: Independent Reads of Independent Writes (IRIW)
Can this program see r1 = 1, r2 = 0, r3 = 1, r4 = 0?
(Can Threads 3 and 4 see x and y change in different orders?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          y = 1          r1 = x         r3 = y
                              r2 = y         r4 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!

On ARM/POWER, different threads may learn about different writes in different orders. They are not guaranteed to agree about a total order of writes reaching main memory, so Thread 3 can see x change before y while Thread 4 sees y change before x.

As another example, ARM/POWER systems have visible buffering or reordering of memory reads (loads), as demonstrated by this litmus test:

Litmus Test: Load Buffering
Can this program see r1 = 1, r2 = 1?
(Can each thread's read happen after the other thread's write?)

// Thread 1    // Thread 2
r1 = x         r2 = y
y = 1          x = 1

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!

Any sequentially consistent interleaving must start with either thread 1's r1 = x or thread 2's r2 = y. That read must see a zero, making the outcome r1 = 1, r2 = 1 impossible. In the ARM/POWER memory model, however, processors are allowed to delay reads until after writes later in the instruction stream, so that y = 1 and x = 1 execute before the two reads.

Although both the ARM and POWER memory models allow this result, Maranget et al. reported (in 2012) being able to reproduce it empirically only on ARM systems, never on POWER. Here the divergence between model and reality comes into play just as it did when we examined Intel x86: hardware implementing a stronger model than technically guaranteed encourages dependence on the stronger behavior and means that future, weaker hardware will break programs, validly or not.

Like on TSO systems, ARM and POWER have barriers that we can insert into the examples above to force sequentially consistent behaviors. But the obvious question is whether ARM/POWER without barriers excludes any behavior at all. Can the answer to any litmus test ever be “no, that can’t happen?” It can, when we focus on a single memory location.

Here’s a litmus test for something that can’t happen even on ARM and POWER:

Litmus Test: Coherence
Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1?
(Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x

On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: no.

This litmus test is like the previous one, but now both threads are writing to a single variable x instead of two distinct variables x and y. Threads 1 and 2 write conflicting values 1 and 2 to x, while Thread 3 and Thread 4 both read x twice. If Thread 3 sees x = 1 overwritten by x = 2, can Thread 4 see the opposite?

The answer is no, even on ARM/POWER: threads in the system must agree about a total order for the writes to a single memory location. That is, threads must agree which writes overwrite other writes. This property is called called coherence. Without the coherence property, processors either disagree about the final result of memory or else report a memory location flip-flopping from one value to another and back to the first. It would be very difficult to program such a system.

I'm purposely leaving out a lot of subtleties in the ARM and POWER weak memory models. For more detail, see any of Peter Sewell's papers on the topic. Also, ARMv8 strengthened the memory model by making it “multicopy atomic,” but I won't take the space here to explain exactly what that means.

There are two important points to take away. First, there is an incredible amount of subtlety here, the subject of well over a decade of academic research by very persistent, very smart people. I don't claim to understand anywhere near all of it myself. This is not something we should hope to explain to ordinary programmers, not something that we can hope to keep straight while debugging ordinary programs. Second, the gap between what is allowed and what is observed makes for unfortunate future surprises. If current hardware does not exhibit the full range of allowed behaviors—especially when it is difficult to reason about what is allowed in the first place!—then inevitably programs will be written that accidentally depend on the more restricted behaviors of the actual hardware. If a new chip is less restricted in its behaviors, the fact that the new behavior breaking your program is technically allowed by the hardware memory model—that is, the bug is technically your fault—is of little consolation. This is no way to write programs.

Weak Ordering and Data-Race-Free Sequential Consistency

By now I hope you're convinced that the hardware details are complex and subtle and not something you want to work through every time you write a program. Instead, it would help to identify shortcuts of the form “if you follow these easy rules, your program will only produce results as if by some sequentially consistent interleaving.” (We're still talking about hardware, so we're still talking about interleaving individual assembly instructions.)

Sarita Adve and Mark Hill proposed exactly this approach in their 1990 paper “Weak Ordering – A New Definition”. They defined “weakly ordered” as follows.

Let a synchronization model be a set of constraints on memory accesses that specify how and when synchronization needs to be done.
Hardware is weakly ordered with respect to a synchronization model if and only if it appears sequentially consistent to all software that obey the synchronization model.

Although their paper was about capturing the hardware designs of that time (not x86, ARM, and POWER), the idea of elevating the discussion above specific designs, keeps the paper relevant today.

I said before that “valid optimizations do not change the behavior of valid programs.” The rules define what valid means, and then any hardware optimizations have to keep those programs working as they might on a sequentially consistent machine. Of course, the interesting details are the rules themselves, the constraints that define what it means for a program to be valid.

Adve and Hill propose one synchronization model, which they call data-race-free (DRF). This model assumes that hardware has memory synchronization operations separate from ordinary memory reads and writes. Ordinary memory reads and writes may be reordered between synchronization operations, but they may not be moved across them. (That is, the synchronization operations also serve as barriers to reordering.) A program is said to be data-race-free if, for all idealized sequentially consistent executions, any two ordinary memory accesses to the same location from different threads are either both reads or else separated by synchronization operations forcing one to happen before the other.

Let’s look at some examples, taken from Adve and Hill's paper (redrawn for presentation). Here is a single thread that executes a write of variable x followed by a read of the same variable.

The vertical arrow marks the order of execution within a single thread: the write happens, then the read. There is no race in this program, since everything is in a single thread.

In contrast, there is a race in this two-thread program:

Here, thread 2 writes to x without coordinating with thread 1. Thread 2's write races with both the write and the read by thread 1. If thread 2 were reading x instead of writing it, the program would have only one race, between the write in thread 1 and the read in thread 2. Every race involves at least one write: two uncoordinated reads do not race with each other.

To avoid races, we must add synchronization operations, which force an order between operations on different threads sharing a synchronization variable. If the synchronization S(a) (synchronizing on variable a, marked by the dashed arrow) forces thread 2's write to happen after thread 1 is done, the race is eliminated:

Now the write by thread 2 cannot happen at the same time as thread 1's operations.

If thread 2 were only reading, we would only need to synchronize with thread 1's write. The two reads can still proceed concurrently:

Threads can be ordered by a sequence of synchronizations, even using an intermediate thread. This program has no race:

On the other hand, the use of synchronization variables does not by itself eliminate races: it is possible to use them incorrectly. This program does have a race:

Thread 2's read is properly synchronized with the writes in the other threads—it definitely happens after both—but the two writes are not themselves synchronized. This program is not data-race-free.

Adve and Hill presented weak ordering as “a contract between software and hardware,” specifically that if software avoids data races, then hardware acts as if it is sequentially consistent, which is easier to reason about than the models we were examining in the earlier sections. But how can hardware satisfy its end of the contract?

Adve and Hill gave a proof that hardware “is weakly ordered by DRF,” meaning it executes data-race-free programs as if by a sequentially consistent ordering, provided it meets a set of certain minimum requirements. I’m not going to go through the details, but the point is that after the Adve and Hill paper, hardware designers had a cookbook recipe backed by a proof: do these things, and you can assert that your hardware will appear sequentially consistent to data-race-free programs. And in fact, most relaxed hardware did behave this way and has continued to do so, assuming appropriate implementations of the synchronization operations. Adve and Hill were concerned originally with the VAX, but certainly x86, ARM, and POWER can satisfy these constraints too. This idea that a system guarantees to data-race-free programs the appearance of sequential consistency is often abbreviated DRF-SC.

DRF-SC marked a turning point in hardware memory models, providing a clear strategy for both hardware designers and software authors, at least those writing software in assembly language. As we will see in the next post, the question of a memory model for a higher-level programming language does not have as neat and tidy an answer.

The next post in this series is about programming language memory models.

Acknowledgements

Memory Models

2021-06-29T12:48:00-04:00

These are the posts in the “Memory Models” series that began in June 2021:

“Hardware Memory Models” [PDF].
“Programming Language Memory Models” [PDF].
“Updating the Go Memory Model” [PDF].

The Principles of Versioning in Go

2019-12-03T14:00:00-05:00

This blog post is about how we added package versioning to Go, in the form of Go modules, and the reasons we made the choices we did. It is adapted and updated from a talk I gave at GopherCon Singapore in 2018.

Why Versions?

To start, let’s make sure we’re all on the same page, by taking a look at the ways the GOPATH-based go get breaks.

Suppose we have a fresh Go installation and we want to write a program that imports D. We run go get D. Remember that we are using the original GOPATH-based go get, not Go modules.

$ go get D

That looks up and downloads the latest version of D, which right now is D 1.0. It builds. We’re happy.

Now suppose a few months later we need C. We run go get C. That looks up and downloads the latest version of C, which is C 1.8.

$ go get C

C imports D, but go get finds that it has already downloaded a copy of D, so it reuses that copy. Unfortunately, that copy is still D 1.0. The latest copy of C was written using D 1.4, which contains a feature or maybe a bug fix that C needs and which was missing from D 1.0. So C is broken, because the dependency D is too old.

Since the build failed, we try again, with go get -u C.

$ go get -u C

Unfortunately, an hour ago D’s author published D 1.6. Because go get -u uses the latest version of every dependency, including D, it turns out that C is still broken. C’s author used D 1.4, which worked fine, but D 1.6 has introduced a bug that keeps C from working properly. Before, C was broken because D was too old. Now, C is broken because D is too new.

Those are the two ways that go get fails when using GOPATH. Sometimes it uses dependencies that are too old. Other times it uses dependencies that are too new. What we really want in this case is the version of D that C’s author used and tested against. But GOPATH-based go get can’t do that, because it has no awareness of package versions at all.

Go programmers started asking for better handling of package versions as soon as we published goinstall, the original name for go get. Various tools were written over many years, separate from the Go distribution, to help make installing specific versions easier. But because those tools did not agree on a single approach, they didn’t work as a base for creating other version-aware tools, such as a version-aware godoc or a version-aware vulnerability checker.

We needed to add the concept of package versions to Go for many reasons. The most pressing reason was to help go get stop using code that’s too old or too new, but having an agreed-upon meaning of versions in the vocabulary of Go developers and tools enables the entire Go ecosystem to become version-aware. The Go module mirror and checksum database, which safely speed up Go package downloads, and the new version-aware Go package discovery site are both made possible by an ecosystem-wide understanding of what a version is.

Versions for Software Engineering

Over the past two years, we have added support for package versions to Go itself, in the form of Go modules, built into the go command. Go modules introduce a new import path syntax called semantic import versioning, along with a new algorithm for selecting which versions to use, called minimal version selection.

You might wonder: Why not do what other languages do? Java has Maven, Node has NPM, Ruby has Bundler, Rust has Cargo. How is this not a solved problem?

You might also wonder: We introduced a new, experimental Go tool called Dep in early 2018 that implemented the general approach pioneered by Bundler and Cargo. Why did Go modules not reuse Dep’s design?

The answer is that we learned from Dep that the general Bundler/Cargo/Dep approach includes some decisions that make software engineering more complex and more challenging. Thanks to learning about the problems were in Dep’s design, the Go modules design made different decisions, to make software engineering simpler and easier instead.

But what is software engineering? How is software engineering different from programming? I like the following definition:

Software engineering is what happens to programming
when you add time and other programmers.

Programming means getting a program working. You have a problem to solve, you write some Go code, you run it, you get your answer, you’re done. That’s programming, and that’s difficult enough by itself.

But what if that code has to keep working, day after day? What if five other programmers need to work on the code too? What if the code must adapt gracefully as requirements change? Then you start to think about version control systems, to track how the code changes over time and to coordinate with the other programmers. You add unit tests, to make sure bugs you fix are not reintroduced over time, not by you six months from now, and not by that new team member who’s unfamiliar with the code. You think about modularity and design patterns, to divide the program into parts that team members can work on mostly independently. You use tools to help you find bugs earlier. You look for ways to make programs as clear as possible, so that bugs are less likely. You make sure that small changes can be tested quickly, even in large programs. You’re doing all of this because your programming has turned into software engineering.

(This definition and explanation of software engineering is my riff on an original theme by my Google colleague Titus Winters, whose preferred phrasing is “software engineering is programming integrated over time.” It’s worth seven minutes of your time to see his presentation of this idea at CppCon 2017, from 8:17 to 15:00 in the video.)

Nearly all of Go’s distinctive design decisions were motivated by concerns about software engineering. For example, most people think that we format Go code with gofmt to make code look nicer or to end debates among team members about program layout. And to some degree we do. But the more important reason for gofmt is that if an algorithm defines how Go source code is formatted, then programs, like goimports or gorename or go fix, can edit the source code more easily. This helps you maintain code over time.

As another example, Go import paths are URLs. If code imported "uuid", you’d have to ask which uuid package. Searching for uuid on pkg.go.dev turns up dozens of packages with that name. If instead the code imports "github.com/google/uuid", now it’s clear which package we mean. Using URLs avoids ambiguity and also reuses an existing mechanism for giving out names, making it simpler and easier to coordinate with other programmers. Continuing the example, Go import paths are written in Go source files, not in a separate build configuration file. This makes Go source files self-contained, which makes it easier to understand, modify, and copy them. These decisions were all made toward the goal of simplifying software engineering.

Principles

There are three broad principles behind the changes from Dep’s design to Go modules, all motivated by wanting to simplify software engineering. These are the principles of compatibility, repeatability, and cooperation. The rest of this post explains each principle, shows how it led us to make a different decision for Go modules than in Dep, and then responds, as fairly as I can, to objections against making that change.

Principle #1: Compatibility

The meaning of a name in a program should not change over time.

The first principle is compatibility. Compatibility—or, if you prefer, stability—is the idea that, in a program, the meaning of a name should not change over time. If a name meant one thing last year, it should mean the same thing this year and next year.

For example, programmers are sometimes confused by a detail of strings.Split. We all expect that splitting “hello world” produces two strings “hello” and “world.” But if the input has leading, trailing, or repeated spaces, the result contains empty strings too.

Example: strings.Split(x, " ")

"hello world"  => {"hello", "world"}
"hello  world" => {"hello", "", "world"}
" hello world" => {"", "hello", "world"}
"hello world " => {"hello", "world", ""}

Suppose we decide that it would be better overall to change the behavior of strings.Split to omit those empty strings. Can we do that?

No.

We’ve given strings.Split a specific meaning. The documentation and the implementation agree on that meaning. Programs depend on that meaning. Changing the meaning would break those programs. It would break the principle of compatibility.

We can implement the new meaning; we just need to give a new name too. In fact, years ago, to solve this exact problem, we introduced strings.Fields, which is tailored to space-separated fields and never returns empty strings.

Example: strings.Fields(x)

"hello world"  => {"hello", "world"}
"hello  world" => {"hello", "world"}
" hello world" => {"hello", "world"}
"hello world " => {"hello", "world"}

We didn’t redefine strings.Split, because we were concerned about compatibility.

Following the principle of compatibility simplifies software engineering, because it lets you ignore time when trying to understand programming. People don’t have to think, “well this package was written in 2015, back when strings.Split returned empty strings, but this other package was written last week, so it expects strings.Split to leave them out.” And not just people. Tools don’t have to worry about time either. For example, a refactoring tool can always move a strings.Split call from one package to another without worrying that it will change its meaning.

In fact, the most important feature of Go 1 was not a language change or a new library feature. It was the declaration of compatibility:

It is intended that programs written to the Go 1 specification will continue to compile and run correctly, unchanged, over the lifetime of that specification. Go programs that work today should continue to work even as future “point” releases of Go 1 arise (Go 1.1, Go 1.2, etc.).
— golang.org/doc/go1compat

We committed that we would stop changing the meaning of names in the standard library, so that programs working with Go 1.1 could be expected to continue working in Go 1.2, and so on. That ongoing commitment makes it easy for users to write code and keep it working even as they upgrade to newer Go versions to get faster implementations and new features.

What does compatibility have to do with versioning? It’s important to think about compatibility because the most popular approach to versioning today—semantic versioning—instead encourages incompatibility. That is, semantic versioning has the unfortunate effect of making incompatible changes seem easy.

Every semantic version takes the form vMAJOR.MINOR.PATCH. If two versions have the same major number, the later (if you like, greater) version is expected to be backwards compatible with the earlier (lesser) one. But if two versions have different major numbers, they have no expected compatibility relationship.

Semantic versioning seems to suggest, “It’s okay to make incompatible changes to your packages. Tell your users about them by incrementing the major version number. Everything will be fine.” But this is an empty promise. Incrementing the major version number isn’t enough. Everything is not fine. If strings.Split has one meaning today and a different meaning tomorrow, simply reading your code is now software engineering, not programming, because you need to think about time.

It gets worse.

Suppose B is written to expect strings.Split v1, while C is written to expect strings.Split v2. That’s fine if you build each by itself.

But what happens when your package A imports both B and C? If strings.Split has to have just one meaning, there’s no way to build a working program.

For the Go modules design, we realized that the principle of compatibility is absolutely essential to simplifying software engineering and must be supported, encouraged, and followed. The Go FAQ has encouraged compatibility since Go 1.2 in November 2013:

Packages intended for public use should try to maintain backwards compatibility as they evolve. The Go 1 compatibility guidelines are a good reference here: don’t remove exported names, encourage tagged composite literals, and so on. If different functionality is required, add a new name instead of changing an old one. If a complete break is required, create a new package with a new import path.

For Go modules, we gave this old advice a new name, the import compatibility rule:

If an old package and a new package have the same import path,
the new package must be backwards compatible with the old package.

But then what do we do about semantic versioning? If we still want to use semantic versioning, as many users expect, then the import compatibility rule requires that different semantic major versions, which by definition have no compatibility relationship, must use different import paths. The way to do that in Go modules is to put the major version in the import path. We call this semantic import versioning.

In this example, my/thing/v2 identifies semantic version 2 of a particular module. Version 1 was just my/thing, with no explicit version in the module path. But when you introduce major version 2 or larger, you have to add the version after the module name, to distinguish from version 1 and other major versions, so version 2 is my/thing/v2, version 3 is my/thing/v3, and so on.

If the strings package were its own module, and if for some reason we really needed to redefine Split instead of adding a new function Fields, then we could create strings (major version 1) and strings/v2 (major version 2), with different Split functions. Then the unbuildable program from before can be built: B says import ”strings" while C says import "strings/v2". Those are different packages, so it’s okay to build both into the program. And now B and C can each have the Split function they expect.

Because strings and strings/v2 have different import paths, people and tools automatically understand that they name different packages, just as people already understand that crypto/rand and math/rand name different packages. No one needs to learn a new disambiguation rule.

Let’s return to the unbuildable program, not using semantic import versioning. If we replace strings in this example with an arbitrary package D, then we have a classic “diamond dependency problem.” Both B and C build fine by themselves, but with different, conflicting requirements for D. If we try to use both in a build of A, then there’s no single choice of D that works.

Semantic import versioning cuts through diamond dependencies. There’s no such thing as conflicting requirements for D. D version 1.3 must be backwards compatible with D version 1.2, and D version 2.0 has a different import path, D/v2.

A program using both major versions keeps them as separate as any two package with different import paths and builds fine.

Objection: Aesthetics

The most common objection to semantic import versioning is that people don’t like seeing the major versions in the import paths. In short, they’re ugly. Of course, what this really means is only that people are not used to seeing the major version in import paths.

I can think of two examples of major aesthetic shifts in Go code that seemed ugly at the time but were adopted because they simplified software engineering and now look completely natural.

The first example is export syntax. Back in early 2009, Go used an export keyword to mark a function as exported. We knew we needed something more lightweight to mark individual struct fields, and we were casting about for ideas, considering things like “leading underscore means unexported” or “leading plus in declaration means export.” Eventually we hit on the “upper-case for export” idea. Using an upper-case letter as the export signal looked strange to us, but that was the only drawback we could find. Otherwise, the idea was sound, it satisfied our goals, and it was more appealing than the other choices we’d been considering. So we adopted it. I remember thinking that changing fmt.printf to fmt.Printf in my code was ugly, or at least jarring: to me, fmt.Printf didn’t look like Go, at least not the Go I had been writing. But I had no good argument against it, so I went along with (and implemented) the change. After a few weeks, I got used to it, and now it is fmt.printf that doesn’t look like Go to me. What’s more, I came to appreciate the precision about what is and isn’t exported when reading code. When I go back to C++ or Java code now and I see a call like x.dangerous() I miss being able to tell at a glance whether the dangerous method is a public method that anyone can call.

The second example is import paths, which I mentioned briefly earlier. In the early days of Go, before goinstall and go get, import paths were not full URLs. A developer had to manually download and install a package named uuid and then would write import "uuid". Changing to URLs for import paths (import "github.com/google/uuid") eliminated this ambiguity, and the added precision made go get possible. People did complain at first, but now the longer paths are second nature to us. We rely on and appreciate their precision, because it makes our software engineering work simpler.

Both these changes—upper-case for export and full URLs for import paths—were motivated by good software engineering arguments to which the only real objection was visual aesthetics. Over time we came to appreciate the benefits, and our aesthetic judgements adapted. I expect the same to happen with major versions in import paths. We’ll get used to them, and we’ll come to value the precision and simplicity they bring.

Objection: Updating Import Paths

Another common objection is that upgrading from (say) v2 of a module to v3 of the same module requires changing all the import paths referring to that module, even if the client code doesn’t need any other changes.

It’s true that the upgrade requires rewriting import paths, but it’s also easy to write a tool to do a global search and replace. We intend to make it possible to handle such upgrades with go fix, although we haven’t implemented that yet.

Both the previous objection and this one implicitly suggest keeping the major version information only in a separate version metadata file. If we do that, then an import path won’t be precise enough to identify semantics, like back when import "uuid" might have meant any one of dozens of different packages. All programmers and tools will have to look in the metadata file to answer the question: which major version is this? Which strings.Split am I calling? What happens when I copy a file from one module to another and forget to check the metadata file? If instead we keep import paths semantically precise, then programmers and tools don’t need to be taught a new way to keep different major versions of a package separate.

Another benefit of having the major version in the import path is that when you do update from v2 to v3 of a package, you can update your program gradually, in stages, maybe one package at a time, and it’s always clear which code has been converted and which has not.

Objection: Multiple Major Versions in a Build

Another common objection is that having D v1 and D v2 in the same build should be disallowed entirely. That way, D’s author won’t have to think about the complexities that arise from that situation. For example, maybe package D defines a command line flag or registers an HTTP handler, so that building both D v1 and D v2 into a single program would fail without explicit coordination between those versions.

Dep enforces exactly this restriction, and some people say it is simpler. But this is simplicity only for D’s author. It’s not simplicity for D’s users, and normally users outnumber authors. If D v1 and D v2 cannot coexist in a single build, then diamond dependencies are back. You can’t convert a large program from D v1 to D v2 gradually, the way I just explained. In internet-scale projects, this will fragment the Go package ecosystem into incompatible groups of packages: those that use D v1 and those that use D v2. For a detailed example, see my 2018 blog post, “Semantic Import Versioning.”

Dep was forced to disallow multiple major versions in a build because the Go build system requires each import path to name a unique package (and Dep did not consider semantic import versioning). In contrast, Cargo and other systems do allow multiple major versions in a build. As I understand it, the reason these systems allow multiple versions is the same reason that Go modules does: not allowing them makes it too hard to work on large programs.

Objection: Too Hard to Experiment

A final objection is that versions in import paths are unnecessary overhead when you’re just starting to design a package, you have no users, and you’re making frequent backwards-incompatible changes. That’s absolutely true.

Semantic versioning makes an exception for exactly that situation. In major version 0, there are no compatibility expectations at all, so that you can iterate quickly when you’re first starting out and not worry about compatibility. For example, v0.3.4 doesn’t need to be backwards compatible with anything else: not v0.3.3, not v0.0.1, not v1.0.0.

Semantic import versioning makes a similar exception: major version 0 is not mentioned in import paths.

In both cases, the rationale is that time has not entered the picture. You’re not doing software engineering yet. You’re just programming. Of course, this means that if you use v0 versions of other people’s packages, then you are accepting that new versions of those packages might include breaking API changes without a corresponding import path change, and you take on the responsibility to update your code when that happens.

Principle #2: Repeatability

The result of a build of a given version of a package should not change over time.

The second principle is repeatability for program builds. By repeatability I mean that when you are building a specific version of a package, the build should decide which dependency versions to use in a way that’s repeatable, that doesn’t change over time. My build today should match your build of my code tomorrow and any other programmer’s build next year. Most package management systems don’t make that guarantee.

We saw earlier how GOPATH-based go get doesn’t provide repeatability. First go get used a version of D that was too old:

Then go get -u used a version of D that was too new:

You might think, “of course go get makes this mistake: it doesn’t know anything about versions at all.” But most other systems make the same mistake. I’m going to use Dep as my example here, but at least Bundler and Cargo work the same way.

Dep asks every package to include a metadata file called a manifest, which lists requirements for dependency versions. When Dep downloads C, it reads C’s manifest and learns that C needs D 1.4 or later. Then Dep downloads the newest version of D satisfying that constraint. Yesterday, that meant D 1.5:

Today, that means D 1.6:

The decision is time-dependent. It changes from day to day. The build is not repeatable.

The developers of Dep (and Bundler and Cargo and ...) understood the importance of repeatability, so they introduced a second metadata file called a lock file. If C is a whole program, what Go calls package main, then the lock file lists the exact version to use for every dependency of C, and Dep lets the lock file override the decisions it would normally make. Locking in those decisions ensures that they stop changing over time and makes the build repeatable.

But lock files only apply to whole programs, to package main. What if C is a library, being built as part of a larger program? Then a lock file meant for building only C might not satisfy the additional constraints in the larger program. So Dep and the others must ignore lock files associated with libraries and fall back to the default time-based decisions. When you add C 1.8 to a larger build, the exact packages you get depends on what day it is.

In summary, Dep starts with a time-based decision about which version of D to use. Then it adds a lock file, to override that time-based decision, for repeatability, but that lock file can only be applied to whole programs.

In Go modules, the go command instead makes its decision about which version of D to use in a way that does not change over time. Then builds are repeatable all the time, without the added complexity of a lock file override, and this repeatability applies to libraries, not just whole programs.

The algorithm used for Go modules is very simple, despite the imposing name “minimal version selection.” It works like this. Each package specifies a minimum version of each dependency. For example, suppose B 1.3 requests D 1.3 or later, and C 1.8 requests D 1.4 or later. In Go modules, the go command prefers to use those exact versions, not the latest versions. If we’re building B by itself, we’ll use D 1.3. If we’re building C by itself, we’ll use D 1.4. The builds of these libraries are repeatable.

Also shown in the figure, if different parts of a build request different minimum versions, the go command uses the latest requested version. The build of A sees requests for D 1.3 and D 1.4, and 1.4 is later than 1.3, so the build chooses D 1.4. That decision does not depend on whether D 1.5 and D 1.6 exist, so it does not change over time.

I call this minimal version selection for two reasons. First, for each package it selects the minimum version satisfying the requests (equivalently, the maximum of the requests). And second, it seems to be just about the simplest approach that could possibly work.

Minimal version selection provides repeatability, for whole programs and for libraries, always, without any lock files. It removes time from consideration. Every chosen version is always one of the versions mentioned explicitly by some package already chosen for the build.

Objection: Using the Latest Version is a Feature

The usual first objection to prioritizing repeatability is to claim that preferring the latest version of a dependency is a feature, not a bug. The claim is that programmers either don’t want to or are too lazy to update their dependencies regularly, so tools like Dep should use the latest dependencies automatically. The argument is that the benefits of having the latest versions outweigh the loss of repeatability.

But this argument doesn’t hold up to scrutiny. Tools like Dep provide lock files, which then require programmers to update dependencies themselves, exactly because repeatable builds are more important than using the latest version. When you deploy a 1-line bug fix, you want to be sure that your bug fix is the only change, that you’re not also picking up different, newer versions of your dependencies.

You want to delay upgrades until you ask for them, so that you can be ready to run all your unit tests, all your integration tests, and maybe even production canaries, before you start using those upgraded dependencies in production. Everyone agrees about this. Lock files exist because everyone agrees about this: repeatability is more important than automatic upgrades.

Objection: Using the Latest Version is a Feature When Building a Library

The more nuanced argument you could make against minimal version selection would be to admit that repeatability matters for whole program builds, but then argue that, for libraries, the balance is different, and having the latest dependencies is more important than a repeatable build.

I disagree. As programming increasingly means connecting large libraries together, and those large libraries are increasingly organized as collections of smaller libraries, all the reasons to prefer repeatability of whole-program builds become just as important for library builds.

The extreme limit of this trend is the recent move in cloud computing to “serverless” hosting, like Amazon Lambda, Google Cloud Functions, or Microsoft Azure Functions. The code we upload to those systems is a library, not a whole program. We certainly want the production builds on those servers to use the same versions of dependencies as on our development machines.

Of course, no matter what, it’s important to make it easy for programmers to update their dependencies regularly. We also need tools to report which versions of a package are in a given build or a given binary, including reporting when updates are available and when there are known security problems in the versions being used.

Principle #3: Cooperation

To maintain the Go package ecosystem, we must all work together.
Tools cannot work around a lack of cooperation.

The third principle is cooperation. We often talk about “the Go community” and “the Go open source ecosystem.” The words community and ecosystem emphasize that all our work is interconnected, that we’re building on—depending on—each other’s contributions. The goal is one unified system that works as a coherent whole. The opposite, what we want to avoid, is an ecosystem that is fragmented, split into groups of packages that can’t work with each other.

The principle of cooperation recognizes that the only way to keep the ecosystem healthy and thriving is for us all to work together. If we don’t, then no matter how technically sophisticated our tools are, the Go open source ecosystem is guaranteed to fragment and eventually fail. By implication, then, it’s okay if fixing incompatibilities requires cooperation. We can’t avoid cooperation anyway.

For example, once again we have C 1.8, which requires D 1.4 or later. Thanks to repeatability, a build of C 1.8 by itself will use D 1.4. If we build C as part of a larger build that needs D 1.5, that’s okay too.

Then D 1.6 is released, and some larger build, maybe continuous integration testing, discovers that C 1.8 does not work with D 1.6.

No matter what, the solution is for C’s author and D’s author to cooperate and release a fix. The exact fix depends on what exactly went wrong.

Maybe C depends on buggy behavior fixed in D 1.6, or maybe C depends on unspecified behavior changed in D 1.6. Then the solution is for C’s author to release a new C version 1.9, cooperating with the evolution of D.

Or maybe D 1.6 simply has a bug. Then the solution is for D’s author to release a fixed D 1.7, cooperating by respecting the principle of compatibility, at which point C’s author can release C version 1.9 that specifies that it requires D 1.7.

Take a minute to look at what just happened. The latest C and the latest D didn’t work together. That introduced a small fracture in the Go package ecosystem. C’s author or D’s author worked to fix the bug, cooperating with each other and the rest of the ecosystem to repair the fracture. This cooperation is essential to keeping the ecosystem healthy. There is no adequate technical substitute.

The repeatable builds in Go modules mean that a buggy D 1.6 won’t be picked up until users explicitly ask to upgrade. That creates time for C’s author and D’s author to cooperate on a real solution. The Go modules system makes no other attempt to work around these temporary incompatibilities.

Objection: Use Declared Incompatibilities and SAT Solvers

The most common objection to this approach of depending on cooperation is that it is unreasonable to expect developers to cooperate. Developers need some way to fix problems alone. the argument goes: they can only truly depend on themselves, not others. The solution offered by package managers like Bundler, Cargo, and Dep is to allow developers to declare incompatibilities between their packages and others and then employ a SAT solver to find a package combination not ruled out by the constraints.

This argument breaks down for a few reasons.

First, the algorithm used by Go modules to select versions already gives the developer of a particular module complete control over which versions are selected for that module, more control in fact than SAT constraints. The developer can force the use of any specific version of any dependency, saying “use this exact version no matter what anyone else says.” But that power is limited to the build of that specific module, to avoid giving other developers the same control over your builds.

Second, repeatability of library builds in Go modules means that the release of a new, incompatible version of a dependency has no immediate effect on builds, as we saw in the previous section. The breakage only surfaces when someone takes some step to add that version to their own build, at which point they can step back again.

Third, if version selection is phrased as a problem for a SAT solver, there are often many possible satisfying selections: the SAT solver must choose between them, and there is no clear criteria for doing so. As we saw earlier, SAT-based package managers choose between multiple valid possible selections by preferring newer versions. In the case where using the newest version of everything satisfies the constraints, that’s the clear “most preferred” answer. But what if the two possible selections are “latest of B, older C” and “older B, latest of C”? Which should be preferred? How can the developer predict the outcome? The resulting system is difficult to understand.

Fourth, the output of a SAT solver is only as good as its inputs: if any incompatibilities have been omitted, the SAT solver may well arrive at a combination that is still broken, just not declared as such. Incompatibility information is likely to be particularly incomplete for combinations involving dependencies with a significant age difference that may well never have been put together before. Indeed, an analysis of Rust’s Cargo ecosystem in 2018 found that Cargo’s preference for the latest version was masking many missing constraints in Cargo manifests. If the latest version does not work, exploring old versions seems as likely to produce a combination that is “not yet known to be broken” as it is to produce a working one.

Overall, once you step off the happy path of selecting the newest version of every dependency, SAT solver-based package managers are not more likely to choose a working configuration than Go modules is. If anything, SAT solvers may well be less likely to find a working configuration.

Example: Go Modules versus SAT Solving

The counter-arguments given in the previous section are a bit abstract. Let’s make them concrete by continuing the example we’ve been working with and looking at what happens when using a SAT solver, like in Dep. I’m using Dep for concreteness, because it is the immediate predecessor of Go modules, but the behaviors here are not specific to Dep and I don’t mean to single it out. For the purposes of this example, Dep works the same way as many other package managers, and they all share the problems detailed here.

To set the stage, remember that C 1.8 works fine with D 1.4 and D 1.5, but the combination of C 1.8 and D 1.6 is broken.

That gets noticed, perhaps by continuous integration testing, and the question is what happens next.

When C’s author finds out that C 1.8 doesn’t work with D 1.6, Dep allows and encourages issuing a new version, C 1.9. C 1.9 documents that it needs D later than 1.4 but before 1.6. The idea is that documenting the incompatibility helps Dep avoid it in future builds.

In Dep, avoiding the incompatibility is important—even urgent!—because the lack of repeatability in library builds means that as soon as D 1.6 is released, all future fresh builds of C will use D 1.6 and break. This is a build emergency: all of C’s new users are broken. If D’s author is unavailable, or C’s author doesn’t have time to fix the actual bug, the argument is that C’s author must be able to take some step to protect users from the breakage. That step is to release C 1.9, documenting the incompatibility with D 1.6. That fixes new builds of C by preventing the use of D 1.6.

This emergency doesn’t happen when using Go modules, because of minimal version selection and repeatable builds. Using Go modules, the release of D 1.6 does not affect C’s users, because nothing is explicitly requesting D 1.6 yet. Users keep using the older versions of D they already use. There’s no need to document the incompatibility, because nothing is breaking. There’s time to cooperate on a real fix.

Looking at Dep’s approach of documenting incompatibility again, releasing C 1.9 is not a great solution. For one thing, the premise was that D’s author created a build emergency by releasing D 1.6 and then was unavailable to release a fix, so it was important to give C’s author a way to fix things, by releasing C 1.9. But if D’s author might be unavailable, what happens if C’s author is unavailable too? Then the emergency caused by automatic upgrades continues and all of C’s new users stay broken. Repeatable builds in Go modules avoid the emergency entirely.

Also, suppose that the bug is in D, and D’s author issues a fixed D 1.7. The workaround C 1.9 requires D before 1.6, so it won’t use the fixed D 1.7. C’s author has to issue C 1.10 to allow use of D 1.7.

In contrast, if we’re using Go modules, C’s author doesn’t have to issue C 1.9 and then also doesn’t have to undo it by issuing C 1.10.

In this simple example, Go modules end up working more smoothly for users than Dep. They avoid the build breakage automatically, creating time for cooperation on the real fix. Ideally, C or D gets fixed before any of C’s users even notice.

But what about more complex examples? Maybe Dep’s approach of documenting incompatibilities is better in more complicated situations, or maybe it keeps things working even when the real fix takes a long time to arrive.

Let’s take a look. To do that, let’s rewind the clock a little, to before the buggy D 1.6 is released, and compare the decisions made by Dep and Go modules. This figure shows the documented requirements for all the relevant package versions, along with the way both Dep and Go modules would build the latest C and the latest A.

Dep is using D 1.5 while the Go module system is using D 1.4, but both tools have found working builds. Everyone is happy.

But now suppose the buggy D 1.6 is released.

Dep builds pick up D 1.6 automatically and break. Go modules builds keep using D 1.4 and keep working. This is the simple situation we were just looking at.

Before we move on, though, let’s fix the Dep builds. We release C 1.9, which documents the incompatibility with D 1.6:

Now Dep builds pick up C 1.9 automatically, and builds start working again. Go modules can’t document incompatibility in this way, but Go modules builds also aren’t broken, so no fix is needed.

Now let’s create a build complex enough to break Go modules. We can do this in two steps. First, we will release a new B that requires D 1.6. Second, we will release a new A that requires the new B, at which point A’s build will use C with D 1.6 and break.

We start by releasing the new B 1.4 that requires D 1.6.

Go modules builds are unaffected so far, thanks to repeatability. But look! Dep builds of A pick up B 1.4 automatically and now they are broken again. What happened?

Dep prefers to build A using the latest B and the latest C, but that’s not possible: the latest B wants D 1.6 and the latest C wants D before 1.6. But does Dep give up? No. It looks for alternate versions of B and C that do agree on an acceptable D.

In this case, Dep decided to keep the latest B, which means using D 1.6, which means not using C 1.9. Since Dep can’t use the latest C, it tries older versions of C. C 1.8 looks good: it says it needs D 1.4 or later, and that allows D 1.6. So Dep uses C 1.8, and it breaks.

We know that C 1.8 and D 1.6 are incompatible, but Dep does not. Dep can’t know it, because C 1.8 was released before D 1.6: C’s author couldn’t have predicted that D 1.6 would be a problem. And all package management systems agree that package contents must be immutable once they are published, which means there’s no way for C’s author to retroactively document that C 1.8 doesn’t work with D 1.6. (And if there were some way to change C 1.8’s requirements retroactively, that would violate repeatability.) Releasing C 1.9 with the updated requirement was the fix.

Because Dep prefers to use the latest C, most of the time it will use C 1.9 and know to avoid D 1.6. But if Dep can’t use the latest of everything, it will start trying earlier versions of some things, including maybe C 1.8. And using C 1.8 makes it look like D 1.6 is okay—even though we know better—and the build breaks.

Or it might not break. Strictly speaking, Dep didn’t have to make that decision. When Dep realized that it couldn’t use both the latest B and the latest C, it had many options for how it might proceed. We assumed Dep kept the latest B. But if instead Dep kept the latest C, then it would need to use an older D and then an older B, producing a working build, as shown in the third column of the diagram.

So maybe Dep’s builds are broken or maybe not, depending on the arbitrary decisions it makes in its SAT-solver-based version selection. (Last I checked, given a choice between a newer version of one package versus another, Dep prioritizes the one with the alphabetically earlier import path, at least in small test cases.)

This example demonstrates another way that Dep and systems like it (nearly all package managers besides Go modules) can produce surprising results: when the one most preferred answer (use the latest of everything) does not apply, there are often many choices with no clear preferences between them. The exact answer depends on the details of the SAT solving algorithm, heuristics, and often the input order of the packages are presented to the solver. This underspecification and non-determinism in their solvers is another reason these systems need lock files.

In any event, for the sake of Dep users, let’s assume Dep lucked into the choice that keeps builds working. After all, we’re still trying to break the Go modules users’ builds.

To break Go modules builds, let’s release a new version of A, version 1.21, which requires the latest B, which in turn requires the latest D. Now, when the go command builds the latest A, it is forced to use the latest B and the latest D. In Go modules, there is no C 1.9, so the go command uses C 1.8, and the combination of C 1.8 and D 1.6 does not work. Finally, we have broken the Go modules builds!

But look! The Dep builds are using C 1.8 and D 1.6 too, so they’re also broken. Before, Dep had to make a choice between the latest B and the latest C. If it chose the latest B, the build broke. If it chose the latest C, the build worked. The new requirement in A is forcing Dep to choose the latest B and the latest D, taking away Dep’s choice of latest C. So Dep uses the older C 1.8, and the build breaks just like before.

What should we conclude from all this? First of all, documenting an incompatibility for Dep does not guarantee to avoid that incompatibility. Second, a repeatable build like in Go modules also does not guarantee to avoid the incompatibility. Both tools can end up building the incompatible pair of packages. But as we saw, it takes multiple intentional steps to lead Go modules to a broken build, steps that lead Dep to the same broken build. And along the way the Dep-based build broke two other times when the Go modules build did not.

I’ve been using Dep in these examples because it is the immediate predecessor of Go modules, but I don’t mean to single out Dep. In this respect, it works the same way as nearly every other package manager in every other language. They all have this problem. They’re not even really broken or misbehaving so much as unfortunately designed. They are designed to try to work around a lack of cooperation among the various package maintainers, and tools cannot work around a lack of cooperation.

The only real solution for the C versus D incompatibility is to release a new, fixed version of either C or D. Trying to avoid the incompatibility is useful only because it creates more time for C’s author and D’s author to cooperate on a fix. Compared to the Dep approach of preferring latest versions and documenting incompatibilities, the Go modules approach of repeatable builds with minimal version selection and no documented incompatibilities creates time for cooperation automatically, with no build emergencies, no declared incompatibilities, and no explicit work by users.

Then we can rely on cooperation for the real fix.

Conclusion

These are the three principles of versioning in Go, the reasons that the design of Go modules deviates from the design of Dep, Cargo, Bundler, and others.

Compatibility. The meaning of a name in a program should not change over time.
Repeatability. The result of a build of a given version of a package should not change over time.
Cooperation. To maintain the Go package ecosystem, we must all work together. Tools cannot work around a lack of cooperation.

These principles are motivated by concerns about software engineering, which is what happens to programming when you add time and other programmers. Compatibility eliminates the effects of time on the meaning of a program. Repeatability eliminates the effects of time on the result of a build. Cooperation is an explicit recognition that, no matter how advanced our tools are, we do have to work with the other programmers. We can’t work around them.

The three principles also reinforce each other, in a virtuous cycle.

Compatibility enables a new version selection algorithm, which provides repeatability. Repeatability makes sure that buggy, new releases are ignored until explicitly requested, which creates more time to cooperate on fixes. That cooperation in turn reestablishes compatibility. And the cycle goes around.

As of Go 1.13, Go modules are ready for production use, and many companies, including Google, have adopted them. The Go 1.14 and Go 1.15 releases will bring additional ergonomic improvements, toward eventually deprecating and removing support for GOPATH. For more about adopting modules, see the blog post series on the Go blog, starting with “Using Go Modules.”

Go Proposal Process: Representation

2019-10-03T11:45:00-04:00

[I’ve been thinking a lot recently about the Go proposal process, which is the way we propose, discuss, and decide changes to Go itself. Like nearly everything about Go, the proposal process is an experiment, so it makes sense to reflect on what we’ve learned and try to improve it. This post is the sixth in a series of posts about what works well and, more importantly, what we might want to change.]

Who is Represented?

At the contributor summit, we considered the question of who is well represented or over-represented in the Go development process and who is under-represented.

The question of who is well represented matters because diverse representation produces diverse viewpoints that can help us reach better overall decisions in the process. We cannot possibly hear from every single person with relevant input; instead we can try to hear from enough people that we still gather all the important viewpoints and observations.

On the well represented or possibly over-represented list, we have members of the Go team; GitHub users who have time to keep up with discussions; English-speaking users; people who keep up with tech social media on sites like Hacker News and Twitter; and people who attend and give talks at Go conferences. On the under-represented list, we have non-GitHub users or users who can’t keep up with GitHub discussions; non-English-speaking users; “heads down” users, meaning anyone who spends their time writing code to the exclusion of engaging on social media or attending Go conferences; business users in general; users with non-computer science backgrounds; users with non-programming language backgrounds; and non-users, people not using Go at all. As we consider ways to make the proposal process more accessible to more users and potential users, it is worth keeping these lists in mind to check whether new groups are being reached.

The proposal minutes help reach users who are on GitHub but can’t keep up with all the discussions, by providing a single issue to star and get roughly weekly updates about which proposals are under active discussion and which are close to being accepted or declined. The minutes are an improvement for the “can’t keep up with GitHub” category, but not for the other categories.

Reaching non-English-speaking users is one of the most difficult challenges. We on the Go team have attended Go conferences around the world to meet users in many countries; at many conferences there is simultaneous translation for the talks, which is wonderful. But there isn’t simultaneous translation for our proposal discussions. I don’t know whether the most significant proposals, like the latest version of the generics proposal, have been translated by users into their native languages, or if non-English-speakers muddle through with automatic translation, or something else. Twice in the past we’ve had questions about proposals that primarily affected Chinese users—specifically, whether to change case-based export for uncased languages and whether to build a separate Go distribution with different Go proxy defaults for China. In both these cases, we asked Asta Xie, the organizer of Gophercon China, to run a quick poll of users in a Chinese social media group of Go users. That was very helpful, but that doesn’t scale to all proposals.

Reaching “heads down” programmers and business users, those not attending Go conferences or engaging in Go-related social media, probably means branching out to more non-Go-specific places to publicize the most important Go changes, and possibly Go itself.

The final group is users with non-computer science or non-programming language backgrounds. Go proposals are usually written assuming significant familiarity with Go and often also familiarity with computer science or programming language concepts. In general, that’s more efficient than the alternative. But especially for large changes it would help to have alternate forms that are accessible to a larger audience. Ideas include longer tutorials or walkthroughs, short video demos, and recorded video-based Q&A sessions.

What Does Representation Mean?

Part of Go’s appeal for me as a user, and I think for many Go users, is the fact that it feels like a coherent system in which the pieces fit together and complement each other well. In my 2015 talk and blog post, “Go, Open Source Community,” I said that “one of the most important things we the original authors of Go can offer is consistency of vision, to help keep Go Go.” I still believe that consistency of vision, to keep Go itself consistent, simple, and understandable, remains critically important to Go’s success.

In an interview with IT World in 2000, Dennis Ritchie (the creator of C) was asked about control over C’s development. He said:

On the other hand, the “open evolution” idea has its own drawbacks, whether in official standards bodies or more informally, say over the Web or mailing lists. When I read commentary about suggestions for where C should go, I often think back and give thanks that it wasn’t developed under the advice of a worldwide crowd. C is peculiar in a lot of ways, but it, like many other successful things, has a certain unity of approach that stems from development in a small group.

I see much of that same unity of approach in Go’s design by a small group. The flip side is that if you have a small number of people making decisions alone, they can’t know enough about the million or more Go developers and their uses to anticipate all the important use cases and needs. That is, while a small number of ultimate designers provides consistency of vision, it can just as well result in a failure of vision, in which a design fundamentally fails to plan for or adapt to a requirement that becomes important later but was not seen or well understood at the time.

A decision can be both elegant for its time and short-sighted for the future. For example, see the recent crtique of Unix’s fork system call, “A fork() in the road,” by Andrew Baumann et al., from HotOS ’19. In fact, nearly all designs end up being short-sighted given a long enough time scale. We’d be fortunate for all our designs to last the 50 years that fork has. The most important part is to guard against short-term failures of vision, not very long-term ones.

To me, the most important place for broad representation and inclusion is in the proposals and discussions, because, as I said above, diverse representation produces diverse viewpoints that can help us reach better overall decisions in the process. It can help us avoid at least the short-term and hopefully medium-term failures of vision. At the same time, I hope we can maintain a long-term consistency of vision in the design of Go, by the continued active involvement of the original designers. It seems to me that having both the original designers and a diverse set of other voices in our proposal discussions and consistently working toward consensus decisions will lead to the best outcomes and balances the desire for a consistency of vision against the need to avoid failures of vision.

Again, this is the sixth post in a series of posts thinking and brainstorming about the Go proposal process. Everything about these posts is very rough. The point of posting this series—thinking out loud instead of thinking quietly—is so that anyone who is interested can join the thinking.

I encourage feedback, whether in the form of comments on these posts, comments on the newly filed issues, mail to rsc@golang.org, or your own blog posts (please leave links in the comments). Thanks for taking the time to read these and think with me.

The next post will be about how best to coordinate efforts across the Go community and ecosystem.

Our Software Dependency Problem

2019-01-23T11:00:00-05:00

For decades, discussion of software reuse was far more common than actual software reuse. Today, the situation is reversed: developers reuse software written by others every day, in the form of software dependencies, and the situation goes mostly unexamined.

My own background includes a decade of working with Google’s internal source code system, which treats software dependencies as a first-class concept,¹ and also developing support for dependencies in the Go programming language.²

Software dependencies carry with them serious risks that are too often overlooked. The shift to easy, fine-grained software reuse has happened so quickly that we do not yet understand the best practices for choosing and using dependencies effectively, or even for deciding when they are appropriate and when not. My purpose in writing this article is to raise awareness of the risks and encourage more investigation of solutions.

What is a dependency?

In today’s software development world, a dependency is additional code that you want to call from your program. Adding a dependency avoids repeating work already done: designing, writing, testing, debugging, and maintaining a specific unit of code. In this article we’ll call that unit of code a package; some systems use terms like library or module instead of package.

Taking on externally-written dependencies is an old practice: most programmers have at one point in their careers had to go through the steps of manually downloading and installing a required library, like C’s PCRE or zlib, or C++’s Boost or Qt, or Java’s JodaTime or JUnit. These packages contain high-quality, debugged code that required significant expertise to develop. For a program that needs the functionality provided by one of these packages, the tedious work of manually downloading, installing, and updating the package is easier than the work of redeveloping that functionality from scratch. But the high fixed costs of reuse mean that manually-reused packages tend to be big: a tiny package would be easier to reimplement.

A dependency manager (sometimes called a package manager) automates the downloading and installation of dependency packages. As dependency managers make individual packages easier to download and install, the lower fixed costs make smaller packages economical to publish and reuse.

For example, the Node.js dependency manager NPM provides access to over 750,000 packages. One of them, escape-string-regexp, provides a single function that escapes regular expression operators in its input. The entire implementation is:

var matchOperatorsRe = /[|\\{}()[\]^$+*?.]/g;

module.exports = function (str) {
	if (typeof str !== 'string') {
		throw new TypeError('Expected a string');
	}
	return str.replace(matchOperatorsRe, '\\$&');
};

Before dependency managers, publishing an eight-line code library would have been unthinkable: too much overhead for too little benefit. But NPM has driven the overhead approximately to zero, with the result that nearly-trivial functionality can be packaged and reused. In late January 2019, the escape-string-regexp package is explicitly depended upon by almost a thousand other NPM packages, not to mention all the packages developers write for their own use and don’t share.

Dependency managers now exist for essentially every programming language. Maven Central (Java), Nuget (.NET), Packagist (PHP), PyPI (Python), and RubyGems (Ruby) each host over 100,000 packages. The arrival of this kind of fine-grained, widespread software reuse is one of the most consequential shifts in software development over the past two decades. And if we’re not more careful, it will lead to serious problems.

What could go wrong?

A package, for this discussion, is code you download from the internet. Adding a package as a dependency outsources the work of developing that code—designing, writing, testing, debugging, and maintaining—to someone else on the internet, someone you often don’t know. By using that code, you are exposing your own program to all the failures and flaws in the dependency. Your program’s execution now literally depends on code downloaded from this stranger on the internet. Presented this way, it sounds incredibly unsafe. Why would anyone do this?

We do this because it’s easy, because it seems to work, because everyone else is doing it too, and, most importantly, because it seems like a natural continuation of age-old established practice. But there are important differences we’re ignoring.

Decades ago, most developers already trusted others to write software they depended on, such as operating systems and compilers. That software was bought from known sources, often with some kind of support agreement. There was still a potential for bugs or outright mischief,³ but at least we knew who we were dealing with and usually had commercial or legal recourses available.

The phenomenon of open-source software, distributed at no cost over the internet, has displaced many of those earlier software purchases. When reuse was difficult, there were fewer projects publishing reusable code packages. Even though their licenses typically disclaimed, among other things, any “implied warranties of merchantability and fitness for a particular purpose,” the projects built up well-known reputations that often factored heavily into people’s decisions about which to use. The commercial and legal support for trusting our software sources was replaced by reputational support. Many common early packages still enjoy good reputations: consider BLAS (published 1979), Netlib (1987), libjpeg (1991), LAPACK (1992), HP STL (1994), and zlib (1995).

Dependency managers have scaled this open-source code reuse model down: now, developers can share code at the granularity of individual functions of tens of lines. This is a major technical accomplishment. There are myriad available packages, and writing code can involve such a large number of them, but the commercial, legal, and reputational support mechanisms for trusting the code have not carried over. We are trusting more code with less justification for doing so.

The cost of adopting a bad dependency can be viewed as the sum, over all possible bad outcomes, of the cost of each bad outcome multiplied by its probability of happening (risk).

The context where a dependency will be used determines the cost of a bad outcome. At one end of the spectrum is a personal hobby project, where the cost of most bad outcomes is near zero: you’re just having fun, bugs have no real impact other than wasting some time, and even debugging them can be fun. So the risk probability almost doesn’t matter: it’s being multiplied by zero. At the other end of the spectrum is production software that must be maintained for years. Here, the cost of a bug in a dependency can be very high: servers may go down, sensitive data may be divulged, customers may be harmed, companies may fail. High failure costs make it much more important to estimate and then reduce any risk of a serious failure.

No matter what the expected cost, experiences with larger dependencies suggest some approaches for estimating and reducing the risks of adding a software dependency. It is likely that better tooling is needed to help reduce the costs of these approaches, much as dependency managers have focused to date on reducing the costs of download and installation.

Inspect the dependency

You would not hire a software developer you’ve never heard of and know nothing about. You would learn more about them first: check references, conduct a job interview, run background checks, and so on. Before you depend on a package you found on the internet, it is similarly prudent to learn a bit about it first.

A basic inspection can give you a sense of how likely you are to run into problems trying to use this code. If the inspection reveals likely minor problems, you can take steps to prepare for or maybe avoid them. If the inspection reveals major problems, it may be best not to use the package: maybe you’ll find a more suitable one, or maybe you need to develop one yourself. Remember that open-source packages are published by their authors in the hope that they will be useful but with no guarantee of usability or support. In the middle of a production outage, you’ll be the one debugging it. As the original GNU General Public License warned, “The entire risk as to the quality and performance of the program is with you. Should the program prove defective, you assume the cost of all necessary servicing, repair or correction.”⁴

The rest of this section outlines some considerations when inspecting a package and deciding whether to depend on it.

Design

Is package’s documentation clear? Does the API have a clear design? If the authors can explain the package’s API and its design well to you, the user, in the documentation, that increases the likelihood they have explained the implementation well to the computer, in the source code. Writing code for a clear, well-designed API is also easier, faster, and hopefully less error-prone. Have the authors documented what they expect from client code in order to make future upgrades compatible? (Examples include the C++⁵ and Go⁶ compatibility documents.)

Code Quality

Is the code well-written? Read some of it. Does it look like the authors have been careful, conscientious, and consistent? Does it look like code you’d want to debug? You may need to.

Develop your own systematic ways to check code quality. For example, something as simple as compiling a C or C++ program with important compiler warnings enabled (for example, -Wall) can give you a sense of how seriously the developers work to avoid various undefined behaviors. Recent languages like Go, Rust, and Swift use an unsafe keyword to mark code that violates the type system; look to see how much unsafe code there is. More advanced semantic tools like Infer⁷ or SpotBugs⁸ are helpful too. Linters are less helpful: you should ignore rote suggestions about topics like brace style and focus instead on semantic problems.

Keep an open mind to development practices you may not be familiar with. For example, the SQLite library ships as a single 200,000-line C source file and a single 11,000-line header, the “amalgamation.” The sheer size of these files should raise an initial red flag, but closer investigation would turn up the actual development source code, a traditional file tree with over a hundred C source files, tests, and support scripts. It turns out that the single-file distribution is built automatically from the original sources and is easier for end users, especially those without dependency managers. (The compiled code also runs faster, because the compiler can see more optimization opportunities.)

Testing

Does the code have tests? Can you run them? Do they pass? Tests establish that the code’s basic functionality is correct, and they signal that the developer is serious about keeping it correct. For example, the SQLite development tree has an incredibly thorough test suite with over 30,000 individual test cases as well as developer documentation explaining the testing strategy.⁹ On the other hand, if there are few tests or no tests, or if the tests fail, that’s a serious red flag: future changes to the package are likely to introduce regressions that could easily have been caught. If you insist on tests in code you write yourself (you do, right?), you should insist on tests in code you outsource to others.

Assuming the tests exist, run, and pass, you can gather more information by running them with run-time instrumentation like code coverage analysis, race detection,¹⁰ memory allocation checking, and memory leak detection.

Debugging

Find the package’s issue tracker. Are there many open bug reports? How long have they been open? Are there many fixed bugs? Have any bugs been fixed recently? If you see lots of open issues about what look like real bugs, especially if they have been open for a long time, that’s not a good sign. On the other hand, if the closed issues show that bugs are rarely found and promptly fixed, that’s great.

Maintenance

Look at the package’s commit history. How long has the code been actively maintained? Is it actively maintained now? Packages that have been actively maintained for an extended amount of time are more likely to continue to be maintained. How many people work on the package? Many packages are personal projects that developers create and share for fun in their spare time. Others are the result of thousands of hours of work by a group of paid developers. In general, the latter kind of package is more likely to have prompt bug fixes, steady improvements, and general upkeep.

On the other hand, some code really is “done.” For example, NPM’s escape-string-regexp, shown earlier, may never need to be modified again.

Usage

Do many other packages depend on this code? Dependency managers can often provide statistics about usage, or you can use a web search to estimate how often others write about using the package. More users should at least mean more people for whom the code works well enough, along with faster detection of new bugs. Widespread usage is also a hedge against the question of continued maintenance: if a widely-used package loses its maintainer, an interested user is likely to step forward.

For example, libraries like PCRE or Boost or JUnit are incredibly widely used. That makes it more likely—although certainly not guaranteed—that bugs you might otherwise run into have already been fixed, because others ran into them first.

Security

Will you be processing untrusted inputs with the package? If so, does it seem to be robust against malicious inputs? Does it have a history of security problems listed in the National Vulnerability Database (NVD)?¹¹

For example, when Jeff Dean and I started work on Google Code Search¹²—grep over public source code—in 2006, the popular PCRE regular expression library seemed like an obvious choice. In an early discussion with Google’s security team, however, we learned that PCRE had a history of problems like buffer overflows, especially in its parser. We could have learned the same by searching for PCRE in the NVD. That discovery didn’t immediately cause us to abandon PCRE, but it did make us think more carefully about testing and isolation.

Licensing

Is the code properly licensed? Does it have a license at all? Is the license acceptable for your project or company? A surprising fraction of projects on GitHub have no clear license. Your project or company may impose further restrictions on the allowed licenses of dependencies. For example, Google disallows the use of code licensed under AGPL-like licenses (too onerous) as well as WTFPL-like licenses (too vague).¹³

Dependencies

Does the code have dependencies of its own? Flaws in indirect dependencies are just as bad for your program as flaws in direct dependencies. Dependency managers can list all the transitive dependencies of a given package, and each of them should ideally be inspected as described in this section. A package with many dependencies incurs additional inspection work, because those same dependencies incur additional risk that needs to be evaluated.

Many developers have never looked at the full list of transitive dependencies of their code and don’t know what they depend on. For example, in March 2016 the NPM user community discovered that many popular projects—including Babel, Ember, and React—all depended indirectly on a tiny package called left-pad, consisting of a single 8-line function body. They discovered this when the author of left-pad deleted that package from NPM, inadvertently breaking most Node.js users’ builds.¹⁴ And left-pad is hardly exceptional in this regard. For example, 30% of the 750,000 packages published on NPM depend—at least indirectly—on escape-string-regexp. Adapting Leslie Lamport’s observation about distributed systems, a dependency manager can easily create a situation in which the failure of a package you didn’t even know existed can render your own code unusable.

Test the dependency

The inspection process should include running a package’s own tests. If the package passes the inspection and you decide to make your project depend on it, the next step should be to write new tests focused on the functionality needed by your application. These tests often start out as short standalone programs written to make sure you can understand the package’s API and that it does what you think it does. (If you can’t or it doesn’t, turn back now!) It is worth then taking the extra effort to turn those programs into automated tests that can be run against newer versions of the package. If you find a bug and have a potential fix, you’ll want to be able to rerun these project-specific tests easily, to make sure that the fix did not break anything else.

It is especially worth exercising the likely problem areas identified by the basic inspection. For Code Search, we knew from past experience that PCRE sometimes took a long time to execute certain regular expression searches. Our initial plan was to have separate thread pools for “simple” and “complicated” regular expression searches. One of the first tests we ran was a benchmark, comparing pcregrep with a few other grep implementations. When we found that, for one basic test case, pcregrep was 70X slower than the fastest grep available, we started to rethink our plan to use PCRE. Even though we eventually dropped PCRE entirely, that benchmark remains in our code base today.

Abstract the dependency

Depending on a package is a decision that you are likely to revisit later. Perhaps updates will take the package in a new direction. Perhaps serious security problems will be found. Perhaps a better option will come along. For all these reasons, it is worth the effort to make it easy to migrate your project to a new dependency.

If the package will be used from many places in your project’s source code, migrating to a new dependency would require making changes to all those different source locations. Worse, if the package will be exposed in your own project’s API, migrating to a new dependency would require making changes in all the code calling your API, which you might not control. To avoid these costs, it makes sense to define an interface of your own, along with a thin wrapper implementing that interface using the dependency. Note that the wrapper should include only what your project needs from the dependency, not everything the dependency offers. Ideally, that allows you to substitute a different, equally appropriate dependency later, by changing only the wrapper. Migrating your per-project tests to use the new interface tests the interface and wrapper implementation and also makes it easy to test any potential replacements for the dependency.

For Code Search, we developed an abstract Regexp class that defined the interface Code Search needed from any regular expression engine. Then we wrote a thin wrapper around PCRE implementing that interface. The indirection made it easy to test alternate libraries, and it kept us from accidentally introducing knowledge of PCRE internals into the rest of the source tree. That in turn ensured that it would be easy to switch to a different dependency if needed.

Isolate the dependency

It may also be appropriate to isolate a dependency at run-time, to limit the possible damage caused by bugs in it. For example, Google Chrome allows users to add dependencies—extension code—to the browser. When Chrome launched in 2008, it introduced the critical feature (now standard in all browsers) of isolating each extension in a sandbox running in a separate operating-system process.¹⁵ An exploitable bug in an badly-written extension therefore did not automatically have access to the entire memory of the browser itself and could be stopped from making inappropriate system calls.¹⁶ For Code Search, until we dropped PCRE entirely, our plan was to isolate at least the PCRE parser in a similar sandbox. Today, another option would be a lightweight hypervisor-based sandbox like gVisor.¹⁷ Isolating dependencies reduces the associated risks of running that code.

Even with these examples and other off-the-shelf options, run-time isolation of suspect code is still too difficult and rarely done. True isolation would require a completely memory-safe language, with no escape hatch into untyped code. That’s challenging not just in entirely unsafe languages like C and C++ but also in languages that provide restricted unsafe operations, like Java when including JNI, or like Go, Rust, and Swift when including their “unsafe” features. Even in a memory-safe language like JavaScript, code often has access to far more than it needs. In November 2018, the latest version of the NPM package event-stream, which provided a functional streaming API for JavaScript events, was discovered to contain obfuscated malicious code that had been added two and a half months earlier. The code, which harvested large Bitcoin wallets from users of the Copay mobile app, was accessing system resources entirely unrelated to processing event streams.¹⁸ One of many possible defenses to this kind of problem would be to better restrict what dependencies can access.

Avoid the dependency

If a dependency seems too risky and you can’t find a way to isolate it, the best answer may be to avoid it entirely, or at least to avoid the parts you’ve identified as most problematic.

For example, as we better understood the risks and costs associated with PCRE, our plan for Google Code Search evolved from “use PCRE directly,” to “use PCRE but sandbox the parser,” to “write a new regular expression parser but keep the PCRE execution engine,” to “write a new parser and connect it to a different, more efficient open-source execution engine.” Later we rewrote the execution engine as well, so that no dependencies were left, and we open-sourced the result: RE2.¹⁹

If you only need a tiny fraction of a dependency, it may be simplest to make a copy of what you need (preserving appropriate copyright and other legal notices, of course). You are taking on responsibility for fixing bugs, maintenance, and so on, but you’re also completely isolated from the larger risks. The Go developer community has a proverb about this: “A little copying is better than a little dependency.”²⁰

Upgrade the dependency

For a long time, the conventional wisdom about software was “if it ain’t broke, don’t fix it.” Upgrading carries a chance of introducing new bugs; without a corresponding reward—like a new feature you need—why take the risk? This analysis ignores two costs. The first is the cost of the eventual upgrade. In software, the difficulty of making code changes does not scale linearly: making ten small changes is less work and easier to get right than making one equivalent large change. The second is the cost of discovering already-fixed bugs the hard way. Especially in a security context, where known bugs are actively exploited, every day you wait is another day that attackers can break in.

For example, consider the year 2017 at Equifax, as recounted by executives in detailed congressional testimony.²¹ On March 7, a new vulnerability in Apache Struts was disclosed, and a patched version was released. On March 8, Equifax received a notice from US-CERT about the need to update any uses of Apache Struts. Equifax ran source code and network scans on March 9 and March 15, respectively; neither scan turned up a particular group of public-facing web servers. On May 13, attackers found the servers that Equifax’s security teams could not. They used the Apache Struts vulnerability to breach Equifax’s network and then steal detailed personal and financial information about 148 million people over the next two months. Equifax finally noticed the breach on July 29 and publicly disclosed it on September 4. By the end of September, Equifax’s CEO, CIO, and CSO had all resigned, and a congressional investigation was underway.

Equifax’s experience drives home the point that although dependency managers know the versions they are using at build time, you need other arrangements to track that information through your production deployment process. For the Go language, we are experimenting with automatically including a version manifest in every binary, so that deployment processes can scan binaries for dependencies that need upgrading. Go also makes that information available at run-time, so that servers can consult databases of known bugs and self-report to monitoring software when they are in need of upgrades.

Upgrading promptly is important, but upgrading means adding new code to your project, which should mean updating your evaluation of the risks of using the dependency based on the new version. As minimum, you’d want to skim the diffs showing the changes being made from the current version to the upgraded versions, or at least read the release notes, to identify the most likely areas of concern in the upgraded code. If a lot of code is changing, so that the diffs are difficult to digest, that is also information you can incorporate into your risk assessment update.

You’ll also want to re-run the tests you’ve written that are specific to your project, to make sure the upgraded package is at least as suitable for the project as the earlier version. It also makes sense to re-run the package’s own tests. If the package has its own dependencies, it is entirely possible that your project’s configuration uses different versions of those dependencies (either older or newer ones) than the package’s authors use. Running the package’s own tests can quickly identify problems specific to your configuration.

Again, upgrades should not be completely automatic. You need to verify that the upgraded versions are appropriate for your environment before deploying them.²²

If your upgrade process includes re-running the integration and qualification tests you’ve already written for the dependency, so that you are likely to identify new problems before they reach production, then, in most cases, delaying an upgrade is riskier than upgrading quickly.

The window for security-critical upgrades is especially short. In the aftermath of the Equifax breach, forensic security teams found evidence that attackers (perhaps different ones) had successfully exploited the Apache Struts vulnerability on the affected servers on March 10, only three days after it was publicly disclosed, but they’d only run a single whoami command.

Watch your dependencies

Even after all that work, you’re not done tending your dependencies. It’s important to continue to monitor them and perhaps even re-evaluate your decision to use them.

First, make sure that you keep using the specific package versions you think you are. Most dependency managers now make it easy or even automatic to record the cryptographic hash of the expected source code for a given package version and then to check that hash when re-downloading the package on another computer or in a test environment. This ensures that your build use the same dependency source code you inspected and tested. These kinds of checks prevented the event-stream attacker, described earlier, from silently inserting malicious code in the already-released version 3.3.5. Instead, the attacker had to create a new version, 3.3.6, and wait for people to upgrade (without looking closely at the changes).

It is also important to watch for new indirect dependencies creeping in: upgrades can easily introduce new packages upon which the success of your project now depends. They deserve your attention as well. In the case of event-stream, the malicious code was hidden in a different package, flatmap-stream, which the new event-stream release added as a new dependency.

Creeping dependencies can also affect the size of your project. During the development of Google’s Sawzall²³—a JIT’ed logs processing language—the authors discovered at various times that the main interpreter binary contained not just Sawzall’s JIT but also (unused) PostScript, Python, and JavaScript interpreters. Each time, the culprit turned out to be unused dependencies declared by some library Sawzall did depend on, combined with the fact that Google’s build system eliminated any manual effort needed to start using a new dependency.. This kind of error is the reason that the Go language makes importing an unused package a compile-time error.

Upgrading is a natural time to revisit the decision to use a dependency that’s changing. It’s also important to periodically revisit any dependency that isn’t changing. Does it seem plausible that there are no security problems or other bugs to fix? Has the project been abandoned? Maybe it’s time to start planning to replace that dependency.

It’s also important to recheck the security history of each dependency. For example, Apache Struts disclosed different major remote code execution vulnerabilities in 2016, 2017, and 2018. Even if you have a list of all the servers that run it and update them promptly, that track record might make you rethink using it at all.

Conclusion

Software reuse is finally here, and I don’t mean to understate its benefits: it has brought an enormously positive transformation for software developers. Even so, we’ve accepted this transformation without completely thinking through the potential consequences. The old reasons for trusting dependencies are becoming less valid at exactly the same time we have more dependencies than ever.

The kind of critical examination of specific dependencies that I outlined in this article is a significant amount of work and remains the exception rather than the rule. But I doubt there are any developers who actually make the effort to do this for every possible new dependency. I have only done a subset of them for a subset of my own dependencies. Most of the time the entirety of the decision is “let’s see what happens.” Too often, anything more than that seems like too much effort.

But the Copay and Equifax attacks are clear warnings of real problems in the way we consume software dependencies today. We should not ignore the warnings. I offer three broad recommendations.

Recognize the problem. If nothing else, I hope this article has convinced you that there is a problem here worth addressing. We need many people to focus significant effort on solving it.
Establish best practices for today. We need to establish best practices for managing dependencies using what’s available today. This means working out processes that evaluate, reduce, and track risk, from the original adoption decision through to production use. In fact, just as some engineers specialize in testing, it may be that we need engineers who specialize in managing dependencies.
Develop better dependency technology for tomorrow. Dependency managers have essentially eliminated the cost of downloading and installing a dependency. Future development effort should focus on reducing the cost of the kind of evaluation and maintenance necessary to use a dependency. For example, package discovery sites might work to find more ways to allow developers to share their findings. Build tools should, at the least, make it easy to run a package’s own tests. More aggressively, build tools and package management systems could also work together to allow package authors to test new changes against all public clients of their APIs. Languages should also provide easy ways to isolate a suspect package.

There’s a lot of good software out there. Let’s work together to find out how to reuse it safely.

References

Rachel Potvin and Josh Levenberg, “Why Google Stores Billions of Lines of Code in a Single Repository,” Communications of the ACM 59(7) (July 2016), pp. 78-87. https://doi.org/10.1145/2854146 (⇡)
Russ Cox, “Go & Versioning,” February 2018. https://research.swtch.com/vgo (⇡)
Ken Thompson, “Reflections on Trusting Trust,” Communications of the ACM 27(8) (August 1984), pp. 761–763. https://doi.org/10.1145/358198.358210 (⇡)
GNU Project, “GNU General Public License, version 1,” February 1989. https://www.gnu.org/licenses/old-licenses/gpl-1.0.html (⇡)
Titus Winters, “SD-8: Standard Library Compatibility,” C++ Standing Document, August 2018. https://isocpp.org/std/standing-documents/sd-8-standard-library-compatibility (⇡)
Go Project, “Go 1 and the Future of Go Programs,” September 2013. https://golang.org/doc/go1compat (⇡)
Facebook, “Infer: A tool to detect bugs in Java and C/C++/Objective-C code before it ships.” https://fbinfer.com/ (⇡)
“SpotBugs: Find bugs in Java Programs.” https://spotbugs.github.io/ (⇡)
D. Richard Hipp, “How SQLite is Tested.” https://www.sqlite.org/testing.html (⇡)
Alexander Potapenko, “Testing Chromium: ThreadSanitizer v2, a next-gen data race detector,” April 2014. https://blog.chromium.org/2014/04/testing-chromium-threadsanitizer-v2.html (⇡)
NIST, “National Vulnerability Database – Search and Statistics.” https://nvd.nist.gov/vuln/search (⇡)
Russ Cox, “Regular Expression Matching with a Trigram Index, or How Google Code Search Worked,” January 2012. https://swtch.com/~rsc/regexp/regexp4.html (⇡)
Google, “Google Open Source: Using Third-Party Licenses.” https://opensource.google.com/docs/thirdparty/licenses/#banned (⇡)
Nathan Willis, “A single Node of failure,” LWN, March 2016. https://lwn.net/Articles/681410/ (⇡)
Charlie Reis, “Multi-process Architecture,” September 2008. https://blog.chromium.org/2008/09/multi-process-architecture.html (⇡)
Adam Langley, “Chromium’s seccomp Sandbox,” August 2009. https://www.imperialviolet.org/2009/08/26/seccomp.html (⇡)
Nicolas Lacasse, “Open-sourcing gVisor, a sandboxed container runtime,” May 2018. https://cloud.google.com/blog/products/gcp/open-sourcing-gvisor-a-sandboxed-container-runtime (⇡)
Adam Baldwin, “Details about the event-stream incident,” November 2018. https://blog.npmjs.org/post/180565383195/details-about-the-event-stream-incident (⇡)
Russ Cox, “RE2: a principled approach to regular expression matching,” March 2010. https://opensource.googleblog.com/2010/03/re2-principled-approach-to-regular.html (⇡)
Rob Pike, “Go Proverbs,” November 2015. https://go-proverbs.github.io/ (⇡)
U.S. House of Representatives Committee on Oversight and Government Reform, “The Equifax Data Breach,” Majority Staff Report, 115th Congress, December 2018. https://republicans-oversight.house.gov/wp-content/uploads/2018/12/Equifax-Report.pdf (⇡)
Russ Cox, “The Principles of Versioning in Go,” GopherCon Singapore, May 2018. https://www.youtube.com/watch?v=F8nrpe0XWRg (⇡)
Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan, “Interpreting the Data: Parallel Analysis with Sawzall,” Scientific Programming Journal, vol. 13 (2005). https://doi.org/10.1155/2005/962135 (⇡)

Coda

A version of this post was published in ACM Queue (March-April 2019) and then Communications of the ACM (August 2019) under the title “Surviving Software Dependencies.”

What is Software Engineering?

2018-05-30T10:00:00-04:00

Nearly all of Go’s distinctive design decisions were aimed at making software engineering simpler and easier. We've said this often. The canonical reference is Rob Pike's 2012 article, “Go at Google: Language Design in the Service of Software Engineering.” But what is software engineering?

Software engineering is what happens to programming
when you add time and other programmers.

Programming means getting a program working. You have a problem to solve, you write some Go code, you run it, you get your answer, you’re done. That’s programming, and that's difficult enough by itself. But what if that code has to keep working, day after day? What if five other programmers need to work on the code too? Then you start to think about version control systems, to track how the code changes over time and to coordinate with the other programmers. You add unit tests, to make sure bugs you fix are not reintroduced over time, not by you six months from now, and not by that new team member who’s unfamiliar with the code. You think about modularity and design patterns, to divide the program into parts that team members can work on mostly independently. You use tools to help you find bugs earlier. You look for ways to make programs as clear as possible, so that bugs are less likely. You make sure that small changes can be tested quickly, even in large programs. You're doing all of this because your programming has turned into software engineering.

(This definition and explanation of software engineering is my riff on an original theme by my Google colleague Titus Winters, whose preferred phrasing is “software engineering is programming integrated over time.” It's worth seven minutes of your time to see his presentation of this idea at CppCon 2017, from 8:17 to 15:00 in the video.)

As I said earlier, nearly all of Go’s distinctive design decisions have been motivated by concerns about software engineering, by trying to accommodate time and other programmers into the daily practice of programming.

For example, most people think that we format Go code with gofmt to make code look nicer or to end debates among team members about program layout. But the most important reason for gofmt is that if an algorithm defines how Go source code is formatted, then programs, like goimports or gorename or go fix, can edit the source code more easily, without introducing spurious formatting changes when writing the code back. This helps you maintain code over time.

As another example, Go import paths are URLs. If code said import "uuid", you’d have to ask which uuid package. Searching for uuid on godoc.org turns up dozens of packages. If instead the code says import "github.com/pborman/uuid", now it’s clear which package we mean. Using URLs avoids ambiguity and also reuses an existing mechanism for giving out names, making it simpler and easier to coordinate with other programmers.

Continuing the example, Go import paths are written in Go source files, not in a separate build configuration file. This makes Go source files self-contained, which makes it easier to understand, modify, and copy them. These decisions, and more, were all made with the goal of simplifying software engineering.

In later posts I will talk specifically about why versions are important for software engineering and how software engineering concerns motivate the design changes from dep to vgo.

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.

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.

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.” 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. Links updated May 16, 2018.

Update, December 19, 2020. The original audio files disappeared along with the rest of the Bell Labs site some time ago, but I discovered a saved copy on one of my computers: [MP3 | original RealAudio]. I also added a few corrections and notes from Doug McIlroy, dated 2015 [sic].

Transcript

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

[McIlroy comments, 2015: I’m pretty sure I was wrong in saying Mealy and Hanson brought the stop book to heel. They built the OS, but I believe Dolores Leagus tamed Fortran. (Dolores was the most accurate programmer I ever knew. She’d write 2000 lines of code before testing a single line--and it would work.)]

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.

[McIlroy comments, 2015: I’m not sure what exact unintelligible words I uttered about Dick Hamming. When he predicted that half the Bell Labs budget would be related to computing in a decade, people scoffed in terms like “that’s just Dick being himelf, exaggerating for effect”.]

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

[McIlroy comments, 2015: I erred in attributing Dijkstra’s algorithm to Prim and Kruskal. That honor belongs to yet a third member of the math department: Ed Moore. (Dijkstra’s algorithm is for shortest path, not spanning tree.)]

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 lawmakers [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).