research!rsc

C and C++ Prioritize Performance over Correctness

2023-08-18T12:00:00-04:00

The original ANSI C standard, C89, introduced the concept of “undefined behavior,” which was used both to describe the effect of outright bugs like accessing memory in a freed object and also to capture the fact that existing implementations differed about handling certain aspects of the language, including use of uninitialized values, signed integer overflow, and null pointer handling.

The C89 spec defined undefined behavior (in section 1.6) as:

Undefined behavior—behavior, upon use of a nonportable or erroneous program construct, of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements. Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

Lumping both non-portable and buggy code into the same category was a mistake. As time has gone on, the way compilers treat undefined behavior has led to more and more unexpectedly broken programs, to the point where it is becoming difficult to tell whether any program will compile to the meaning in the original source. This post looks at a few examples and then tries to make some general observations. In particular, today’s C and C++ prioritize performance to the clear detriment of correctness.

Uninitialized variables

C and C++ do not require variables to be initialized on declaration (explicitly or implicitly) like Go and Java. Reading from an uninitialized variable is undefined behavior.

In a blog post, Chris Lattner (creator of LLVM and Clang) explains the rationale:

Use of an uninitialized variable: This is commonly known as source of problems in C programs and there are many tools to catch these: from compiler warnings to static and dynamic analyzers. This improves performance by not requiring that all variables be zero initialized when they come into scope (as Java does). For most scalar variables, this would cause little overhead, but stack arrays and malloc’d memory would incur a memset of the storage, which could be quite costly, particularly since the storage is usually completely overwritten.

Early C compilers were too crude to detect use of uninitialized basic variables like integers and pointers, but modern compilers are dramatically more sophisticated. They could absolutely react in these cases by “terminating a translation or execution (with the issuance of a diagnostic message),” which is to say reporting a compile error. Or, if they were worried about not rejecting old programs, they could insert a zero initialization with, as Lattner admits, little overhead. But they don’t do either of these. Instead, they just do whatever they feel like during code generation.

For example, here’s a simple C++ program with an uninitialized variable (a bug):

#include <stdio.h>

int main() {
    for(int i; i < 10; i++) {
        printf("%d\n", i);
    }
    return 0;
}

If you compile this with clang++ -O1, it deletes the loop entirely: main contains only the return 0. In effect, Clang has noticed the uninitialized variable and chosen not to report the error to the user but instead to pretend i is always initialized above 10, making the loop disappear.

It is true that if you compile with -Wall, then Clang does report the use of the uninitialized variable as a warning. This is why you should always build with and fix warnings in C and C++ programs. But not all compiler-optimized undefined behaviors are reliably reported as warnings.

Arithmetic overflow

At the time C89 was standardized, there were still legacy ones’-complement computers, so ANSI C could not assume the now-standard two’s-complement representation for negative numbers. In two’s complement, an int8 −1 is 0b11111111; in ones’ complement that’s −0, while −1 is 0b11111110. This meant that operations like signed integer overflow could not be defined, because

int8 127+1 = 0b01111111+1 = 0b10000000

is −127 in ones’ complement but −128 in two’s complement. That is, signed integer overflow was non-portable. Declaring it undefined behavior let compilers escalate the behavior from “non-portable”, with one of two clear meanings, to whatever they feel like doing. For example, a common thing programmers expect is that you can test for signed integer overflow by checking whether the result is less than one of the operands, as in this program:

#include <stdio.h>

int f(int x) {
    if(x+100 < x)
        printf("overflow\n");
    return x+100;
}

Clang optimizes away the if statement. The justification is that since signed integer overflow is undefined behavior, the compiler can assume it never happens, so x+100 must never be less than x. Ironically, this program would correctly detect overflow on both ones’-complement and two’s-complement machines if the compiler would actually emit the check.

In this case, clang++ -O1 -Wall prints no warning while it deletes the if statement, and neither does g++, although I seem to remember it used to, perhaps in subtly different situations or with different flags.

For C++20, the first version of proposal P0907 suggested standardizing that signed integer overflow wraps in two’s complement. The original draft gave a very clear statement of the history of the undefined behavior and the motivation for making a change:

[C11] Integer types allows three representations for signed integral types:

Signed magnitude
Ones’ complement
Two’s complement

See §4 C Signed Integer Wording for full wording.
C++ inherits these three signed integer representations from C. To the author’s knowledge no modern machine uses both C++ and a signed integer representation other than two’s complement (see §5 Survey of Signed Integer Representations). None of [MSVC], [GCC], and [LLVM] support other representations. This means that the C++ that is taught is effectively two’s complement, and the C++ that is written is two’s complement. It is extremely unlikely that there exist any significant code base developed for two’s complement machines that would actually work when run on a non-two’s complement machine.
The C++ that is spec’d, however, is not two’s complement. Signed integers currently allow for trap representations, extra padding bits, integral negative zero, and introduce undefined behavior and implementation-defined behavior for the sake of this extremely abstract machine.
Specifically, the current wording has the following effects:

Associativity and commutativity of integers is needlessly obtuse.
Naïve overflow checks, which are often security-critical, often get eliminated by compilers. This leads to exploitable code when the intent was clearly not to and the code, while naïve, was correctly performing security checks for two’s complement integers. Correct overflow checks are difficult to write and equally difficult to read, exponentially so in generic code.
Conversion between signed and unsigned are implementation-defined.
There is no portable way to generate an arithmetic right-shift, or to sign-extend an integer, which every modern CPU supports.
constexpr is further restrained by this extraneous undefined behavior.
Atomic integral are already two’s complement and have no undefined results, therefore even freestanding implementations already support two’s complement in C++.

Let’s stop pretending that the C++ abstract machine should represent integers as signed magnitude or ones’ complement. These theoretical implementations are a different programming language, not our real-world C++. Users of C++ who require signed magnitude or ones’ complement integers would be better served by a pure-library solution, and so would the rest of us.

In the end, the C++ standards committee put up “strong resistance against” the idea of defining signed integer overflow the way every programmer expects; the undefined behavior remains.

Infinite loops

A programmer would never accidentally cause a program to execute an infinite loop, would they? Consider this program:

#include <stdio.h>

int stop = 1;

void maybeStop() {
    if(stop)
        for(;;);
}

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

This seems like a completely reasonable program to write. Perhaps you are debugging and want the program to stop so you can attach a debugger. Changing the initializer for stop to 0 lets the program run to completion. But it turns out that, at least with the latest Clang, the program runs to completion anyway: the call to maybeStop is optimized away entirely, even when stop is 1.

The problem is that C++ defines that every side-effect-free loop may be assumed by the compiler to terminate. That is, a loop that does not terminate is therefore undefined behavior. This is purely for compiler optimizations, once again treated as more important than correctness. The rationale for this decision played out in the C standard and was more or less adopted in the C++ standard as well.

John Regehr pointed out this problem in his post “C Compilers Disprove Fermat’s Last Theorem,” which included this entry in a FAQ:

Q: Does the C standard permit/forbid the compiler to terminate infinite loops?
A: The compiler is given considerable freedom in how it implements the C program, but its output must have the same externally visible behavior that the program would have when interpreted by the “C abstract machine” that is described in the standard. Many knowledgeable people (including me) read this as saying that the termination behavior of a program must not be changed. Obviously some compiler writers disagree, or else don’t believe that it matters. The fact that reasonable people disagree on the interpretation would seem to indicate that the C standard is flawed.

A few months later, Douglas Walls wrote WG14/N1509: Optimizing away infinite loops, making the case that the standard should not allow this optimization. In response, Hans-J. Boehm wrote WG14/N1528: Why undefined behavior for infinite loops?, arguing for allowing the optimization.

Consider the potential optimization of this code:

for (p = q; p != 0; p = p->next)
    ++count;
for (p = q; p != 0; p = p->next)
    ++count2;

A sufficiently smart compiler might reduce it to this code:

for (p = q; p != 0; p = p->next) {
        ++count;
        ++count2;
}

Is that safe? Not if the first loop is an infinite loop. If the list at p is cyclic and another thread is modifying count2, then the first program has no race, while the second program does. Compilers clearly can’t turn correct, race-free programs into racy programs. But what if we declare that infinite loops are not correct programs? That is, what if infinite loops were undefined behavior? Then the compiler could optimize to its robotic heart’s content. This is exactly what the C standards committee decided to do.

The rationale, paraphrased, was:

It is very difficult to tell if a given loop is infinite.
Infinite loops are rare and typically unintentional.
There are many loop optimizations that are only valid for non-infinite loops.
The performance wins of these optimizations are deemed important.
Some compilers already apply these optimizations, making infinite loops non-portable too.
Therefore, we should declare programs with infinite loops undefined behavior, enabling the optimizations.

Null pointer usage

We’ve all seen how dereferencing a null pointer causes a crash on modern operating systems: they leave page zero unmapped by default precisely for this purpose. But not all systems where C and C++ run have hardware memory protection. For example, I wrote my first C and C++ programs using Turbo C on an MS-DOS system. Reading or writing a null pointer did not cause any kind of fault: the program just touched the memory at location zero and kept running. The correctness of my code improved dramatically when I moved to a Unix system that made those programs crash at the moment of the mistake. Because the behavior is non-portable, though, dereferencing a null pointer is undefined behavior.

At some point, the justification for keeping the undefined behavior became performance. Chris Lattner explains:

In C-based languages, NULL being undefined enables a large number of simple scalar optimizations that are exposed as a result of macro expansion and inlining.

In an earlier post, I showed this example, lifted from 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();
}

Because calling Do() is undefined behavior when Do is null, a modern C++ compiler like Clang simply assumes that can’t possibly be what’s happening in main. Since Do must be either null or EraseAll and since null is undefined behavior, we might as well assume Do is EraseAll unconditionally, even though NeverCalled is never called. So this program can be (and is) optimized to:

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

Lattner gives an equivalent example (search for FP()) and then this advice:

The upshot is that it is a fixable issue: if you suspect something weird is going on like this, try building at -O0, where the compiler is much less likely to be doing any optimizations at all.

This advice is not uncommon: if you cannot debug the correctness problems in your C++ program, disable optimizations.

Crashes out of sorts

C++’s std::sort sorts a collection of values (abstracted as a random access iterator, but almost always an array) according to a user-specified comparison function. The default function is operator<, but you can write any function. For example if you were sorting instances of class Person your comparison function might sort by the LastName field, breaking ties with the FirstName field. These comparison functions end up being subtle yet boring to write, and it’s easy to make a mistake. If you do make a mistake and pass in a comparison function that returns inconsistent results or accidentally reports that any value is less than itself, that’s undefined behavior: std::sort is now allowed to do whatever it likes, including walking off either end of the array and corrupting other memory. If you’re lucky, it will pass some of this memory to your comparison function, and since it won’t have pointers in the right places, your comparison function will crash. Then at least you have a chance of guessing the comparison function is at fault. In the worst case, memory is silently corrupted and the crash happens much later, with std::sort is nowhere to be found.

Programmers make mistakes, and when they do, std::sort corupts memory. This is not hypothetical. It happens enough in practice to be a popular question on StackOverflow.

As a final note, it turns out that operator< is not a valid comparison function on floating-point numbers if NaNs are involved, because:

1 < NaN and NaN < 1 are both false, implying NaN == 1.
2 < NaN and NaN < 2 are both false, implying NaN == 2.
Since NaN == 1 and NaN == 2, 1 == 2, yet 1 < 2 is true.

Programming with NaNs is never pleasant, but it seems particularly extreme to allow std::sort to crash when handed one.

Reflections and revealed preferences

Looking over these examples, it could not be more obvious that in modern C and C++, performance is job one and correctness is job two. To a C/C++ compiler, a programmer making a mistake and (gasp!) compiling a program containing a bug is just not a concern. Rather than have the compiler point out the bug or at least compile the code in a clear, understandable, debuggable manner, the approach over and over again is to let the compiler do whatever it likes, in the name of performance.

This may not be the wrong decision for these languages. There are undeniably power users for whom every last bit of performance translates to very large sums of money, and I don’t claim to know how to satisfy them otherwise. On the other hand, this performance comes at a significant development cost, and there are probably plenty of people and companies who spend more than their performance savings on unnecessarily difficult debugging sessions and additional testing and sanitizing. It also seems like there must be a middle ground where programmers retain most of the control they have in C and C++ but the program doesn’t crash when sorting NaNs or behave arbitrarily badly if you accidentally dereference a null pointer. Whatever the merits, it is important to see clearly the choice that C and C++ are making.

In the case of arithmetic overflow, later drafts of the proposal removed the defined behavior for wrapping, explaining:

The main change between [P0907r0] and the subsequent revision is to maintain undefined behavior when signed integer overflow occurs, instead of defining wrapping behavior. This direction was motivated by:

Performance concerns, whereby defining the behavior prevents optimizers from assuming that overflow never occurs;
Implementation leeway for tools such as sanitizers;
Data from Google suggesting that over 90% of all overflow is a bug, and defining wrapping behavior would not have solved the bug.

Again, performance concerns rank first. I find the third item in the list particularly telling. I’ve known C/C++ compiler authors who got excited about a 0.1% performance improvement, and incredibly excited about 1%. Yet here we have an idea that would change 10% of affected programs from incorrect to correct, and it is rejected, because performance is more important.

The argument about sanitizers is more nuanced. Leaving a behavior undefined allows any implementation at all, including reporting the behavior at runtime and stopping the program. True, the widespread use of undefined behavior enables sanitizers like ThreadSanitizer, MemorySanitizer, and UBSan, but so would defining the behavior as “either this specific behavior, or a sanitizer report.” If you believed correctness was job one, you could define overflow to wrap, fixing the 10% of programs outright and making the 90% behave at least more predictably, and then at the same time define that overflow is still a bug that can be reported by sanitizers. You might object that requiring wrapping in the absence of a sanitizer would hurt performance, and that’s fine: it’s just more evidence that performance trumps correctness.

One thing I find surprising, though, is that correctness gets ignored even when it clearly doesn’t hurt performance. It would certainly not hurt performance to emit a compiler warning about deleting the if statement testing for signed overflow, or about optimizing away the possible null pointer dereference in Do(). Yet I could find no way to make compilers report either one; certainly not -Wall.

The explanatory shift from non-portable to optimizable also seems revealing. As far as I can tell, C89 did not use performance as a justification for any of its undefined behaviors. They were non-portabilities, like signed overflow and null pointer dereferences, or they were outright bugs, like use-after-free. But now experts like Chris Lattner and Hans Boehm point to optimization potential, not portability, as justification for undefined behaviors. I conclude that the rationales really have shifted from the mid-1980s to today: an idea that meant to capture non-portability has been preserved for performance, trumping concerns like correctness and debuggability.

Occasionally in Go we have changed library functions to remove surprising behavior, It’s always a difficult decision, but we are willing to break existing programs depending on a mistake if correcting the mistake fixes a much larger number of programs. I find it striking that the C and C++ standards committees are willing in some cases to break existing programs if doing so merely speeds up a large number of programs. This is exactly what happened with the infinite loops.

I find the infinite loop example telling for a second reason: it shows clearly the escalation from non-portable to optimizable. In fact, it would appear that if you want to break C++ programs in service of optimization, one possible approach is to just do that in a compiler and wait for the standards committee to notice. The de facto non-portability of whatever programs you have broken can then serve as justification for undefining their behavior, leading to a future version of the standard in which your optimization is legal. In the process, programmers have been handed yet another footgun to try to avoid setting off.

(A common counterargument is that the standards committee cannot force existing implementations to change their compilers. This doesn’t hold up to scrutiny: every new feature that gets added is the standards committee forcing existing implementations to change their compilers.)

I am not claiming that anything should change about C and C++. I just want people to recognize that the current versions of these sacrifice correctness for performance. To some extent, all languages do this: there is almost always a tradeoff between performance and slower, safer implementations. Go has data races in part for performance reasons: we could have done everything by message copying or with a single global lock instead, but the performance wins of shared memory were too large to pass up. For C and C++, though, it seems no performance win is too small to trade against correctness.

As a programmer, you have a tradeoff to make too, and the language standards make it clear which side they are on. In some contexts, performance is the dominant priority and nothing else matters quite as much. If so, C or C++ may be the right tool for you. But in most contexts, the balance flips the other way. If programmer productivity, debuggability, reproducible bugs, and overall correctness and understandability are more important than squeezing every last little bit of performance, then C and C++ are not the right tools for you. I say this with some regret, as I spent many years happily writing C programs.

I have tried to avoid exaggerated, hyperbolic language in this post, instead laying out the tradeoff and the preferences revealed by the decisions being made. John Regehr wrote a less restrained series of posts about undefined behavior a decade ago, and in one of them he concluded:

It is basically evil to make certain program actions wrong, but to not give developers any way to tell whether or not their code performs these actions and, if so, where. One of C’s design points was “trust the programmer.” This is fine, but there’s trust and then there’s trust. I mean, I trust my 5 year old but I still don’t let him cross a busy street by himself. Creating a large piece of safety-critical or security-critical code in C or C++ is the programming equivalent of crossing an 8-lane freeway blindfolded.

To be fair to C and C++, if you set yourself the goal of crossing an 8-lane freeway blindfolded, it does make sense to focus on doing it as fast as you possibly can.

Coroutines for Go

2023-07-17T14:00:00-04:00

This post is about why we need a coroutine package for Go, and what it would look like. But first, what are coroutines?

Every programmer today is familiar with function calls (subroutines): F calls G, which stops F and runs G. G does its work, potentially calling and waiting for other functions, and eventually returns. When G returns, G is gone and F continues running. In this pattern, only one function is running at a time, while its callers wait, all the way up the call stack.

In contrast to subroutines, coroutines run concurrently on different stacks, but it's still true that only one is running at a time, while its caller waits. F starts G, but G does not run immediately. Instead, F must explicitly resume G, which then starts running. At any point, G may turn around and yield back to F. That pauses G and continues F from its resume operation. Eventually F calls resume again, which pauses F and continues G from its yield. On and on they go, back and forth, until G returns, which cleans up G and continues F from its most recent resume, with some signal to F that G is done and that F should no longer try to resume G. In this pattern, only one coroutine is running at a time, while its caller waits on a different stack. They take turns in a well-defined, coordinated manner.

This is a bit abstract. Let's look at real programs.

Coroutines in Lua

To use a venerable example, consider comparing two binary trees to see if they have the same value sequence, even if their structures are different. For example, here is code in Lua 5 to generate some binary trees:

function T(l, v, r)
    return {left = l, value = v, right = r}
end

e = nil
t1 = T(T(T(e, 1, e), 2, T(e, 3, e)), 4, T(e, 5, e))
t2 = T(e, 1, T(e, 2, T(e, 3, T(e, 4, T(e, 5, e)))))
t3 = T(e, 1, T(e, 2, T(e, 3, T(e, 4, T(e, 6, e)))))

The trees t1 and t2 both contain the values 1, 2, 3, 4, 5; t3 contains 1, 2, 3, 4, 6.

We can write a coroutine to walk over a tree and yield each value:

function visit(t)
    if t ~= nil then  -- note: ~= is "not equal"
        visit(t.left)
        coroutine.yield(t.value)
        visit(t.right)
    end
end

Then to compare two trees, we can create two visit coroutines and alternate between them to read and compare successive values:

function cmp(t1, t2)
    co1 = coroutine.create(visit)
    co2 = coroutine.create(visit)
    while true
    do
        ok1, v1 = coroutine.resume(co1, t1)
        ok2, v2 = coroutine.resume(co2, t2)
        if ok1 ~= ok2 or v1 ~= v2 then
            return false
        end
        if not ok1 and not ok2 then
            return true
        end
    end
end

The t1 and t2 arguments to coroutine.resume are only used on the first iteration, as the argument to visit. Subsequent resumes return that value from coroutine.yield, but the code ignores the value.

A more idiomatic Lua version would use coroutine.wrap, which returns a function that hides the coroutine object:

function cmp(t1, t2)
    next1 = coroutine.wrap(function() visit(t1) end)
    next2 = coroutine.wrap(function() visit(t2) end)
    while true
    do
        v1 = next1()
        v2 = next2()
        if v1 ~= v2 then
            return false
        end
        if v1 == nil and v2 == nil then
            return true
        end
    end
end

When the coroutine has finished, the next function returns nil (full code).

Generators in Python (Iterators in CLU)

Python provides generators that look a lot like Lua's coroutines, but they are not coroutines, so it's worth pointing out the differences. The main difference is that the “obvious” programs don't work. For example, here's a direct translation of our Lua tree and visitor to Python:

def T(l, v, r):
    return {'left': l, 'value': v, 'right': r}

def visit(t):
    if t is not None:
        visit(t['left'])
        yield t['value']
        visit(t['right'])

But this obvious translation doesn't work:

>>> e = None
>>> t1 = T(T(T(e, 1, e), 2, T(e, 3, e)), 4, T(e, 5, e))
>>> for x in visit(t1):
...     print(x)
...
4
>>>

We lost 1, 2, 3, and 5. What happened?

In Python, that def visit does not define an ordinary function. Because the body contains a yield statement, the result is a generator instead:

>>> type(visit(t1))
<class 'generator'>
>>>

The call visit(t['left']) doesn't run the code in visit at all. It only creates and returns a new generator, which is then discarded. To avoid discarding those results, you have to loop over the generator and re-yield them:


def visit(t):
    if t is not None:
        for x in visit(t['left']):
            yield x
        yield t['value']
        for x in visit(t['right'])
            yield x

Python 3.3 introduced yield from, allowing:

def visit(t):
    if t is not None:
        yield from visit(t['left']):
        yield t['value']
        yield from visit(t['right'])

The generator object contains the state of the single call to visit, meaning local variable values and which line is executing. That state is pushed onto the call stack each time the generator is resumed and then popped back into the generator object at each yield, which can only occur in the top-most call frame. In this way, the generator uses the same stack as the original program, avoiding the need for a full coroutine implementation but introducing these confusing limitations instead.

Python's generators appear to be almost exactly copied from CLU, which pioneered this abstraction (and so many other things), although CLU calls them iterators, not generators. A CLU tree iterator looks like:

visit = iter (t: cvt) yields (int):
    tagcase t
        tag empty: ;
        tag non_empty(t: node):
            for x: int
                in tree$visit(t.left) do
                    yield(x);
                    end;
            yield(t.value);
            for x: int
                in tree$visit(t.right) do
                    yield(x);
                    end;
        end;
    end visit;

The syntax is different, especially the tagcase that is examining a tagged union representation of a tree, but the basic structure, including the nested for loops, is exactly the same as our first working Python version. Also, because CLU was statically typed, visit is clearly marked as an iterator (iter) not a function (proc in CLU). Thanks to that type information, misuse of visit as an ordinary function call, like in our buggy Python example, is something that the compiler could (and I assume did) diagnose.

About CLU's implementation, the original implementers wrote, “Iterators are a form of coroutine; however, their use is sufficiently constrained that they are implemented using just the program stack. Using an iterator is therefore only slightly more expensive than using a procedure.” This sounds exactly like the explanation I gave above for the Python generators. For more, see Barbara Liskov et al.'s 1977 paper “Abstraction Mechanisms in CLU”, specifically sections 4.2, 4.3, and 6.

Coroutines, Threads, and Generators

At first glance, coroutines, threads, and generators look alike. All three provide concurrency in one form or another, but they differ in important ways.

Coroutines provide concurrency without parallelism: when one coroutine is running, the one that resumed it or yielded to it is not.
Because coroutines run one at a time and only switch at specific points in the program, the coroutines can share data among themselves without races. The explicit switches (coroutine.resume in the first Lua example or calling a next function in the second Lua example) serve as synchronization points, creating happens-before edges.
Because scheduling is explicit (without any preemption) and done entirely without the operating system, a coroutine switch takes at most around ten nanoseconds, usually even less. Startup and teardown is also much cheaper than threads.
Threads provide more power than coroutines, but with more cost. The additional power is parallelism, and the cost is the overhead of scheduling, including more expensive context switches and the need to add preemption in some form. Typically the operating system provides threads, and a thread switch takes a few microseconds.
For this taxonomy, Go's goroutines are cheap threads: a goroutine switch is closer to a few hundred nanoseconds, because the Go runtime takes on some of the scheduling work, but goroutines still provide the full parallelism and preemption of threads. (Java's new lightweight threads are basically the same as goroutines.)
Generators provide less power than coroutines, because only the top-most frame in the coroutine is allowed to yield. That frame is moved back and forth between an object and the call stack to suspend and resume it.

Coroutines are a useful building block for writing programs that want concurrency for program structuring but not for parallelism. For one detailed example of that, see my previous post, “Storing Data in Control Flow”. For other examples, see Ana Lúcia De Moura and Roberto Ierusalimschy's 2009 paper “Revisiting Coroutines”. For the original example, see Melvin Conway's 1963 paper “Design of a Separable Transition-Diagram Compiler”.

Why Coroutines in Go?

Coroutines are a concurrency pattern not directly served by existing Go concurrency libraries. Goroutines are often close enough, but as we saw, they are not the same, and sometimes that difference matters.

For example, Rob Pike's 2011 talk “Lexical Scanning in Go” presents the original lexer and parser for the text/template package. They ran in separate goroutines connected by a channel, imperfectly simulating a pair of coroutines: the lexer and parser ran in parallel, with the lexer looking ahead to the next token while the parser processed the most recent one. Generators would not have been good enough—the lexer yields values from many different functions—but full goroutines proved to be a bit too much. The parallelism provided by the goroutines caused races and eventually led to abandoning the design in favor of the lexer storing state in an object, which was a more faithful simulation of a coroutine. Proper coroutines would have avoided the races and been more efficient than goroutines.

An anticipated future use case for coroutines in Go is iteration over generic collections. We have discussed adding support to Go for ranging over functions, which would encourage authors of collections and other abstractions to provide CLU-like iterator functions. Iterators can be implemented today using function values, without any language changes. For example, a slightly simplified tree iterator in Go could be:

func (t *Tree[V]) All(yield func(v V)) {
    if t != nil {
        t.left.All(yield)
        yield(t.value)
        t.right.All(yield)
    }
}

That iterator can be invoked today as:

t.All(func(v V) {
    fmt.Println(v)
})

and perhaps a variant could be invoked in a future version of Go as:

for v := range t.All {
    fmt.Println(v)
}

Sometimes, however, we want to iterate over a collection in a way that doesn't fit a single for loop. The binary tree comparison is an example of this: the two iterations need to be interlaced somehow. As we've already seen, coroutines would provide an answer, letting us turn a function like (*Tree).All (a “push” iterator) into a function that returns a stream of values, one per call (a “pull” iterator).

How to Implement Coroutines in Go

If we are to add coroutines to Go, we should aim to do it without language changes. That means the definition of coroutines should be possible to implement and understand in terms of ordinary Go code. Later, I will argue for an optimized implementation provided directly by the runtime, but that implementation should be indistinguishable from the pure Go definition.

Let's start with a very simple version that ignores the yield operation entirely. It just runs a function in another goroutine:

package coro

func New[In, Out any](f func(In) Out) (resume func(In) Out) {
    cin := make(chan In)
    cout := make(chan Out)
    resume = func(in In) Out {
        cin <- in
        return <-cout
    }
    go func() { cout <- f(<-cin) }()
    return resume
}

New takes a function f which must have one argument and one result. New allocates channels, defines resume, creates a goroutine to run f, and returns the resume funtion. The new goroutine blocks on <-cin, so there is no opportunity for parallelism. The resume function unblocks the new goroutine by sending an in value and then blocks receiving an out value. This send-receive pair makes a coroutine switch. We can use coro.New like this (full code):

func main() {
    resume := coro.New(strings.ToUpper)
    fmt.Println(resume("hello world"))
}

So far, coro.New is just a clunky way to call a function. We need to add yield, which we can pass as an argument to f:

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) Out) {

    cin := make(chan In)
    cout := make(chan Out)
    resume = func(in In) Out {
        cin <- in
        return <-cout
    }
    yield := func(out Out) In {
        cout <- out
        return <-cin
    }
    go func() { cout <- f(<-cin, yield) }()
    return resume
}

Note that there is still no parallelism here: yield is another send-receive pair. These goroutines are constrained by the communication pattern to act indistinguishably from coroutines.

Example: String Parser

Before we build up to iterator conversion, let's look at a few simpler examples. In “Storing Data in Control Flow,” we considered the problem of taking a function

func parseQuoted(read func() byte) bool

and running it in a separate control flow so that bytes can be provided one at a time to a Write method. Instead of the ad hoc channel-based implementation in that post, we can use:

type parser struct {
    resume func(byte) Status
}

func (p *parser) Init() {
    coparse := func(_ byte, yield func(Status) byte) Status {
        read := func() byte { return yield(NeedMoreInput) }
        if !parseQuoted(read) {
            return BadInput
        }
        return Success
    }
    p.resume = coro.New(coparse)
    p.resume(0)
}

func (p *parser) Write(c byte) Status {
    return p.resume(c)
}

The Init funtion does all the work, and not much. It defines a function coparse that has the signature needed by coro.New, which means adding a throwaway input of type byte. That function defines a read that yields NeedMoreInput and then returns the byte provided by the caller. It then runs parseQuoted(read), converting the boolean result to the usual status code. Having created a coroutine for coparse using coro.New, Init calls p.resume(0) to allow coparse to advance to the first read in parseQuoted. Finally the Write method is a trivial wrapper around p.resume (full code).

This setup abstracts away the pair of channels that we maintained by hand in the previous post, allowing us to work at a higher level as we write the program.

Example: Prime Sieve

As a slightly larger example, consider Doug McIlroy's concurrent prime sieve. It consists of a pipeline of coroutines, one for each prime p, each running:

loop:
    n = get a number from left neighbor
    if (p does not divide n)
        pass n to right neighbor

A counting coroutine on the leftmost side of the pipeline feeds the numbers 2, 3, 4, ... into the left end of the pipeline. A printing coroutines on the rightmost side can read primes out, print them, and create new filtering coroutines. The first filter in the pipeline removes multiples of 2, the next removes multiples of 3, the next removes multiples of 5, and so on.

The coro.New primitive we've created lets us take a straightforward loop that yields values and convert it into a function that can be called to obtain each value one at a time. Here is the counter:

func counter() func(bool) int {
    return coro.New(func(more bool, yield func(int) bool) int {
        for i := 2; more; i++ {
            more = yield(i)
        }
        return 0
    })
}

The counter logic is the function literal passed to New. It takes a yield function of type func(int) bool. The code yields a value by passing it to yield and then receives back a boolean saying whether to continue generating more numbers. When told to stop, either because more was false on entry or because a yield call returned false, the loop ends. It returns a final, ignored value, to satisfy the function type required by New.

New turns this into loop a function that is the inverse of yield: a func(bool) int that can be called with true to obtain the next value or with false to shut down the generator. The filtering coroutine is only slightly more complex:

func filter(p int, next func(bool) int) (filtered func(bool) int) {
    return coro.New(func(more bool, yield func(int) bool) int {
        for more {
            n := next(true)
            if n%p != 0 {
                more = yield(n)
            }
        }
        return next(false)
    })
}

It takes a prime p and a next func connected to the coroutine on the left and then returns the filtered output stream to connect to the coroutine on the right.

Finally we have the printing coroutine:

func main() {
    next := counter()
    for i := 0; i < 10; i++ {
        p := next(true)
        fmt.Println(p)
        next = filter(p, next)
    }
    next(false)
}

Starting with the counter, main maintains in next the output of the pipeline constructed so far. Then it loops: read a prime p, print p, and then add a new filter on the right end of the pipeline to remove multiples of p (full code).

Notice that the calling relationship between coroutines can change over time: any coroutine C can call another coroutine D's next function and become the coroutine that D yields to. The counter's first yield goes to main, while its subsequent yields go to the 2-filter. Similarly each p-filter yields its first output (the next prime) to main while its subsequent yields go to the filter for that next prime.

Coroutines and Goroutines

In a certain sense, it is a misnomer to call these control flows coroutines. They are full goroutines, and they can do everything an ordinary goroutine can, including block waiting for mutexes, channels, system calls, and so on. What coro.New does is create goroutines with access to coroutine switch operations inside the yield and resume functions (which the sieve calls next). The ability to use those operations can even be passed to different goroutines, which is happening with main handing off each of its next streams to each successive filter goroutine. Unlike the go statement, coro.New adds new concurrency to the program without new parallelism. The goroutine that coro.New(f) creates can only run when some other goroutine explicitly loans it the ability to run using resume; that loan is repaid by yield or by f returning. If you have just one main goroutine and run 10 go statements, then all 11 goroutines can be running at once. In contrast, if you have one main goroutine and run 10 coro.New calls, there are now 11 control flows but the parallelism of the program is what it was before: only one runs at a time. Exactly which goroutines are paused in coroutine operations can vary as the program runs, but the parallelism never increases.

In short, go creates a new concurrent, parallel control flow, while coro.New creates a new concurrent, non-parallel control flow. It is convenient to continue to talk about the non-parallel control flows as coroutines, but remember that exactly which goroutines are “non-parallel” can change over the execution of a program, exactly the same way that which goroutines are receiving or sending from channels can change over the execution of a program.

Robust Resumes

There are a few improvements we can make to coro.New so that it works better in real programs. The first is to allow resume to be called after the function is done: right now it deadlocks. Let's add a bool result indicating whether resume's result came from a yield. The coro.New implementation we have so far is:

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) Out) {
    cin := make(chan In)
    cout := make(chan Out)
    resume = func(in In) Out {
        cin <- in
        return <-cout
    }
    yield := func(out Out) In {
        cout <- out
        return <-cin
    }
    go func() {
        cout <- f(<-cin, yield)
    }()
    return resume
}

To add this extra result, we need to track whether f is running and return that result from resume:

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) (Out, bool)) {
    cin := make(chan In)
    cout := make(chan Out)
    running := true
    resume = func(in In) (out Out, ok bool) {
        if !running {
            return
        }
        cin <- in
        out = <-cout
        return out, running
    }
    yield := func(out Out) In {
        cout <- out
        return <-cin
    }
    go func() {
        out := f(<-cin, yield)
        running = false
        cout <- out
    }()
    return resume
}

Note that since resume can only run when the calling goroutine is blocked, and vice versa, sharing the running variable is not a race. The two are synchronizing by taking turns executing. If resume is called after the coroutine has exited, resume returns a zero value and false.

Now we can tell when a goroutine is done (full code):

func main() {
    resume := coro.New(func(_ int, yield func(string) int) string {
        yield("hello")
        yield("world")
        return "done"
    })
    for i := 0; i < 4; i++ {
        s, ok := resume(0)
        fmt.Printf("%q %v\n", s, ok)
    }
}


$ go run cohello.go
"hello" true
"world" true
"done" false
"" false
$

Example: Iterator Conversion

The prime sieve example showed direct use of coro.New, but the more bool argument was a bit awkward and does not match the iterator functions we saw before. Let's look at converting any push iterator into a pull iterator using coro.New. We will need a way to terminate the coroutine running the push iterator if we want to stop early, so we will add a boolean result from yield indicating whether to continue, just like in the prime sieve:

push func(yield func(V) bool)

The goal of the new function coro.Pull is to turn that push function into a pull iterator. The iterator will return the next value and a boolean indicating whether the iteration is over, just like a channel receive or map lookup:

pull func() (V, bool)

If we want to stop the push iteration early, we need some way to signal that, so Pull will return not just the pull function but also a stop function:

stop func()

Putting those together, the full signature of Pull is:

func Pull[V any](push func(yield func(V) bool)) (pull func() (V, bool), stop func()) {
    ...
}

The first thing Pull needs to do is start a coroutine to run the push iterator, and to do that it needs a wrapper function with the right type, namely one that takes a more bool to match the bool result from yield, and that returns a final V. The pull function can call resume(true), while the stop function can call resume(false):

func Pull[V any](push func(yield func(V) bool)) (pull func() (V, bool), stop func()) {
    copush := func(more bool, yield func(V) bool) V {
        if more {
            push(yield)
        }
        var zero V
        return zero
    }
    resume := coro.New(copush)
    pull = func() (V, bool) {
        return resume(true)
    }
    stop = func() {
        resume(false)
    }
    return pull, stop
}

That's the complete implementation. With the power of coro.New, it took very little code and effort to build a nice iterator converter.

To use coro.Pull, we need to redefine the tree's All method to expect and use the new bool result from yield:

func (t *Tree[V]) All(yield func(v V) bool) {
    t.all(yield)
}

func (t *Tree[V]) all(yield func(v V) bool) bool {
    return t == nil ||
        t.Left.all(yield) && yield(t.Value) && t.Right.all(yield)
}

Now we have everything we need to write a tree comparison function in Go (full code):

func cmp[V comparable](t1, t2 *Tree[V]) bool {
    next1, stop1 := coro.Pull(t1.All)
    next2, stop2 := coro.Pull(t2.All)
    defer stop1()
    defer stop2()
    for {
        v1, ok1 := next1()
        v2, ok2 := next2()
        if v1 != v2 || ok1 != ok2 {
            return false
        }
        if !ok1 && !ok2 {
            return true
        }
    }
}

Propagating Panics

Another improvement is to pass panics from a coroutine back to its caller, meaning the coroutine that most recently called resume to run it (and is therefore sitting blocked in resume waiting for it). Some mechanism to inform one goroutine when another panics is a very common request, but in general that can be difficult, because we don't know which goroutine to inform and whether it is ready to hear that message. In the case of coroutines, we have the caller blocked waiting for news, so it makes sense to deliver news of the panic.

To do that, we can add a defer to catch a panic in the new coroutine and trigger it again in the resume that is waiting.

type msg[T any] struct {
    panic any
    val   T
}

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) (Out, bool)) {
    cin := make(chan In)
    cout := make(chan msg[Out])
    running := true
    resume = func(in In) (out Out, ok bool) {
        if !running {
            return
        }
        cin <- in
        m := <-cout
        if m.panic != nil {
            panic(m.panic)
        }
        return m.val, running
    }
    yield := func(out Out) In {
        cout <- msg[Out]{val: out}
        return <-cin
    }
    go func() {
        defer func() {
            if running {
                running = false
                cout <- msg[Out]{panic: recover()}
            }
        }()
        out := f(<-cin, yield)
        running = false
        cout <- msg[Out]{val: out}
    }()
    return resume
}

Let's test it out (full code):

func main() {
    defer func() {
        if e := recover(); e != nil {
            fmt.Println("main panic:", e)
            panic(e)
        }
    }()
    next, _ := coro.Pull(func(yield func(string) bool) {
        yield("hello")
        panic("world")
    })
    for {
        fmt.Println(next())
    }
}

The new coroutine yields hello and then panics world. That panic is propagated back to the main goroutine, which prints the value and repanics. We can see that the panic appears to originate in the call to resume:

% go run coro.go
hello true
main panic: world
panic: world [recovered]
    panic: world

goroutine 1 [running]:
main.main.func1()
    /tmp/coro.go:9 +0x95
panic({0x108f360?, 0x10c2cf0?})
    /go/src/runtime/panic.go:1003 +0x225
main.coro_New[...].func1()
    /tmp/coro.go.go:55 +0x91
main.Pull[...].func2()
    /tmp/coro.go.go:31 +0x1c
main.main()
    /tmp/coro.go.go:17 +0x52
exit status 2
%

Cancellation

Panic propagation takes care of telling the caller about an early coroutine exit, but what about telling a coroutine about an early caller exit? Analogous to the stop function in the pull iterator, we need some way to signal to the coroutine that it's no longer needed, perhaps because the caller is panicking, or perhaps because the caller is simply returning.

To do that, we can change coro.New to return not just resume but also a cancel func. Calling cancel will be like resume, except that yield panics instead of returning a value. If a coroutine panics in a different way during cancellation, we want cancel to propagate that panic, just as resume does. But of course we don't want cancel to propagate its own panic, so we create a unique panic value we can check for. We also have to handle a cancellation in before f begins.

var ErrCanceled = errors.New("coroutine canceled")

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) (Out, bool), cancel func()) {
    cin := make(chan msg[In])
    cout := make(chan msg[Out])
    running := true
    resume = func(in In) (out Out, ok bool) {
        if !running {
            return
        }
        cin <- msg[In]{val: in}
        m := <-cout
        if m.panic != nil {
            panic(m.panic)
        }
        return m.val, running
    }
    cancel = func() {
        e := fmt.Errorf("%w", ErrCanceled) // unique wrapper
        cin <- msg[In]{panic: e}
        m := <-cout
        if m.panic != nil && m.panic != e {
            panic(m.panic)
        }
    }
    yield := func(out Out) In {
        cout <- msg[Out]{val: out}
        m := <-cin
        if m.panic != nil {
            panic(m.panic)
        }
        return m.val
    }
    go func() {
        defer func() {
            if running {
                running = false
                cout <- msg[Out]{panic: recover()}
            }
        }()
        var out Out
        m := <-cin
        if m.panic == nil {
            out = f(m.val, yield)
        }
        running = false
        cout <- msg[Out]{val: out}
    }()
    return resume, cancel
}

We could change Pull to use panics to cancel iterators as well, but in that context the explicit bool seems clearer, especially since stopping an iterator is unexceptional.

Example: Prime Sieve Revisited

Let's look at how panic propagation and cancellation make cleanup of the prime sieve “just work”. First let's update the sieve to use the new API. The counter and filter functions are already “one-line” return coro.New(...) calls. They change signature to include the additional cancel func returned from coro.New:

func counter() (func(bool) (int, bool), func()) {
    return coro.New(...)
}

func filter(p int, next func(bool) (int, bool)) (func(bool) (int, bool), func()) {
    return coro.New(...)
}

Then let's convert the main function to be a primes function that prints n primes (full code):

func primes(n int) {
    next, cancel := counter()
    defer cancel()
    for i := 0; i < n; i++ {
        p, _ := next(true)
        fmt.Println(p)
        next, cancel = filter(p, next)
        defer cancel()
    }
}

When this function runs, after it has gotten n primes, it returns. Each of the deferred cancel calls cleans up the coroutines that were created. And what if one of the coroutines has a bug and panics? If the coroutine was resumed by a next call in primes, then the panic comes back to primes, and primes's deferred cancel calls clean up all the other coroutines. If the coroutine was resumed by a next call in a filter coroutine, then the panic will propagate up to the waiting filter coroutine and then the next waiting filter coroutine, and so on, until it gets to the p := next(true) in primes, which will again clean up the remaining coroutines.

API

The API we've arrived at is:

New creates a new, paused coroutine ready to run the function f. The new coroutine is a goroutine that never runs on its own: it only runs while some other goroutine invokes and waits for it, by calling resume or cancel.
A goroutine can pause itself and switch to the new coroutine by calling resume(in). The first call to resume starts f(in, yield). Resume blocks while f runs, until either f calls yield(out) or returns out. When f calls yield, yield blocks and resume returns out, true. When f returns, resume returns out, false. When resume has returned due to a yield, the next resume(in) switches back to f, with yield returning in.
Cancel stops the execution of f and shuts down the coroutine. If resume has not been called, then f does not run at all. Otherwise, cancel causes the blocked yield call to panic with an error satisfying errors.Is(err, ErrCanceled).
If f panics and does not recover the panic, the panic is stopped in f's coroutine and restarted in the goroutine waiting for f, by causing the blocked resume or cancel that is waiting to re-panic with the same panic value. Cancel does not re-panic when f's panic is one that cancel itself triggered.
Once f has returned or panicked, the coroutine no longer exists. Subsequent calls to resume return zero, false. Subsequent calls to cancel simply return.
The functions resume, cancel, and yield can be passed between and used by different goroutines, in effect dynamically changing which goroutine is “the coroutine.” Although New creates a new goroutine, it also establishes an invariant that one goroutine is always blocked, either in resume, cancel, yield, or (right after New) waiting for the resume that will call f. This invariant holds until f returns, at which point the new goroutine is shut down. The net result is that coro.New creates new concurrency in the program without any new parallelism.
If multiple goroutines call resume or cancel, those calls are serialized. Similarly, if multiple goroutines call yield, those calls are serialized.

func New[In, Out any](f func(in In, yield func(Out) In) Out) (resume func(In) (Out, bool), cancel func())

Efficiency

As I said at the start, while it's important to have a definition of coroutines that can be understood by reference to a pure Go implementation, I believe we should use an optimized runtime implementation. On my 2019 MacBook Pro, passing values back and forth using the channel-based coro.New in this post requires approximately 190ns per switch, or 380ns per value in coro.Pull. Remember that coro.Pull would not be the standard way to use an iterator: the standard way would be to invoke the iterator directly, which has no coroutine overhead at all. You only need coro.Pull when you want to process iterated values incrementally, not using a single for loop. Even so, we want to make coro.Pull as fast as we can.

First I tried having the compiler mark send-receive pairs and leave hints for the runtime to fuse them into a single operation. That would let the channel runtime bypass the scheduler and jump directly to the other coroutine. This implementation requires about 118ns per switch, or 236ns per pulled value (38% faster). That's better, but it's still not as fast as I would like. The full generality of channels is adding too much overhead.

Next I added a direct coroutine switch to the runtime, avoiding channels entirely. That cuts the coroutine switch to three atomic compare-and-swaps (one in the coroutine data structure, one for the scheduler status of the blocking coroutine, and one for the scheduler status of the resuming coroutine), which I believe is optimal given the safety invariants that must be maintained. That implementation takes 20ns per switch, or 40ns per pulled value. This is about 10X faster than the original channel implementation. Perhaps more importantly, 40ns per pulled value seems small enough in absolute terms not to be a bottleneck for code that needs coro.Pull.

Storing Data in Control Flow

2023-07-11T14:00:00-04:00

A decision that arises over and over when designing concurrent programs is whether to represent program state in control flow or as data. This post is about what that decision means and how to approach it. Done well, taking program state stored in data and storing it instead in control flow can make programs much clearer and more maintainable than they otherwise would be.

Before saying much more, it’s important to note that concurrency is not parallelism.:

Concurrency is about how you write programs, about being able to compose independently executing control flows, whether you call them processes or threads or goroutines, so that your program can be dealing with lots of things at once without turning into a giant mess.
On the other hand, parallelism is about how you execute programs, allowing multiple computations to run simultaneously, so that your program can be doing lots of things at once efficiently.

Concurrency lends itself naturally to parallel execution, but the focus in this post is about how to use concurrency to write cleaner programs, not faster ones.

The difference between concurrent programs and non-concurrent programs is that concurrent programs can be written as if they are executing multiple independent control flows at the same time. The name for the smaller control flows varies by language: thread, task, process, fiber, coroutine, goroutine, and so on. No matter the name, the fundamental point for this post is that writing a program in terms of multiple independently executing control flows allows you to store program state in the execution state of one or more of those control flows, specifically in the program counter (which line is executing in that piece) and on the stack. Control flow state can always be maintained as explicit data instead, but then the explicit data form is essentially simulating the control flow. Most of the time, using the control flow features built into a programming language is easier to understand, reason about, and maintain than simulating them in data structures.

The rest of this post illustrates the rather abstract claims I’ve been making about storing data in control flow by walking through some concrete examples. They happen to be written in Go, but the ideas apply to any language that supports writing concurrent programs, including essentially every modern language.

A Step-by-Step Example

Here is a seemingly trivial problem that demonstrates what it means to store program state in control flow. Suppose we are reading characters from a file and want to scan over a C-style double-quoted string. In this case, we have a non-parallel program. There is no opportunity for parallelism here, but as we will see, concurrency can still play a useful part.

If we don’t worry about checking the exact escape sequences in the string, it suffices to match the regular expression "([^"\\]|\\.)*", which matches a double quote, then a sequence of zero or more characters, and then another double quote. Between the quotes, a character is anything that’s not a quote or backslash, or else a backslash followed by anything (including a quote or backslash).

Every regular expression can be compiled into finite automaton or state machine, so we might use a tool to turn that specification into this Go code:

state := 0
for {
    c := read()
    switch state {
    case 0:
        if c != '"' {
            return false
        }
        state = 1
    case 1:
        if c == '"' {
            return true
        }
        if c == '\\' {
            state = 2
        } else {
            state = 1
        }
    case 2:
        state = 1
    }
}

The code has a single variable named state that represents the state of the automaton. The for loop reads a character and updates the state, over and over, until it finds either the end of the string or a syntax error. This is the kind of code that a program would write and that only a program could love. It’s difficult for people to read, and it will be difficult for people to maintain.

The main reason this program is so opaque is that its program state is stored as data, specifically in the variable named state. When it’s possible to store state in code instead, that often leads to a clearer program. To see this, let’s transform the program, one small step at a time, into an equivalent but much more understandable version.

We can start by duplicating the read calls into each case of the switch:

state := 0                          state := 0
for {                               for {
    c := read()                     
    switch state {                      switch state {
    case 0:                             case 0:
                                            c := read()
        if c != '"' {                       if c != '"' {
            return false                        return false
        }                                   }
        state = 1                           state = 1
    case 1:                             case 1:
                                            c := read()
        if c == '"' {                       if c == '"' {
            return true                         return true
        }                                   }
        if c == '\\' {                      if c == '\\' {
            state = 2                           state = 2
        } else {                            } else {
            state = 1                           state = 1
        }                                   }
    case 2:                             case 2:
                                            c := read()
        state = 1                           state = 1
    }                                   }
}                                   }

(In this and all the displays that follow, the old program is on the left, the new program is on the right, and lines that haven’t changed are printed in gray text.)

Now, instead of writing to state and then immediately going around the for loop again to look up what to do in that state, we can use code labels and goto statements:

state := 0                          state0:
for {                               
    switch state {                  
    case 0:                         
        c := read()                     c := read()
        if c != '"' {                   if c != '"' {
            return false                    return false
        }                               }
        state = 1                       goto state1
    case 1:                         state1:
        c := read()                     c := read()
        if c == '"' {                   if c == '"' {
            return true                     return true
        }                               }
        if c == '\\' {                  if c == '\\' {
            state = 2                       goto state2
        } else {                        } else {
            state = 1                       goto state1
        }                               }
    case 2:                         state2:
        c := read()                     read()
        state = 1                       goto state1
    }                               
}

Then we can simplify the program further. The goto state1 right before the state1 label is a no-op and can be deleted. And we can see that there’s only one way to get to state2, so we might as well replace the goto state2 with the actual code from state2:

state0:                         state0:
    c := read()                     c := read()
    if c != '"' {                   if c != '"' {
        return false                    return false
    }                               }
    goto state1                 
state1:                         state1:
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        goto state2             
    } else {                    
        goto state1             
    }                           
state2:                         
    read()                              read()
    goto state1                         goto state1
                                    } else {
                                        goto state1
                                    }

Then we can factor the “goto state1” out of both branches of the if statement.

state0:                         state0:
    c := read()                     c := read()
    if c != '"' {                   if c != '"' {
        return false                    return false
    }                               }
                                
state1:                         state1:
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        read()                          read()
        goto state1                 }
    } else {                        goto state1
        goto state1             
    }

Then we can drop the unused state0 label and replace the state1 loop with an actual loop. Now we have something that looks like a real program:

state0:                         
    c := read()                 c := read()
    if c != '"' {               if c != '"' {
        return false                return false
    }                           }
                                
state1:                         for {
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        read()                          read()
    }                               }
    goto state1                 }

We can simplify a little further, eliminating some unnecessary variables, and we can make the check for the final quote (c == "") be the loop terminator.

c := read()                     if read() != '"' {
if c != '"' {                   
    return false                    return false
}                               }
                                
for {                           var c byte
    c := read()                 for c != '"' {
    if c == '"' {                   c = read()
        return true             
    }                           
    if c == '\\' {                  if c == '\\' {
        read()                          read()
    }                               }
}                               }
                                return true

The final version is:

func parseQuoted(read func() byte) bool {
    if read() != '"' {
        return false
    }
    var c byte
    for c != '"' {
        c = read()
        if c == '\\' {
            read()
        }
    }
    return true
}

Earlier I explained the regular expression by saying it “matches a double quote, then a sequence of zero or more characters, and then another double quote. Between the quotes, a character is anything that’s not a quote or backslash, or else a backslash followed by anything.” It’s easy to see that this program does exactly that.

Hand-written programs can have opportunities to use control flow too. For example, here is a version that a person might have written by hand:

if read() != '"' {
    return false
}
inEscape := false
for {
    c := read()
    if inEscape {
        inEscape = false
        continue
    }
    if c == '"' {
        return true
    }
    if c == '\\' {
        inEscape = true
    }
}

The same kinds of small steps can be used to convert the boolean variable inEscape from data to control flow, ending at the same cleaned up version.

Either way, the state variable in the original is now implicitly represented by the program counter, meaning which part of the program is executing. The comments in this version indicate the implicit value of the original’s state (or inEscape) variables:

func parseQuoted(read func() byte) bool {
    // state == 0
    if read() != '"' {
        return false
    }

    var c byte
    for c != '"' {
        // state == 1 (inEscape = false)
        c = read()
        if c == '\\' {
            // state == 2 (inEscape = true)
            read()
        }
    }
    return true
}

The original program was, in essence, simulating this control flow using the explicit state variable as a program counter, tracking which line was executing. If a program can be converted to store explicit state in control flow instead, then that explicit state was merely an awkward simulation of the control flow.

More Threads for More State

Before widespread support for concurrency, that kind of awkward simulation was often necessary, because a different part of the program wanted to use the control flow instead.

For example, suppose the text being parsed is the result of decoding base64 input, in which sequences of four 6-bit characters (drawn from a 64-character alphabet) decode to three 8-bit bytes. The core of that decoder looks like:

for {
    c1, c2, c3, c4 := read(), read(), read(), read()
    b1, b2, b3 := decode(c1, c2, c3, c4)
    write(b1)
    write(b2)
    write(b3)
}

If we want those write calls to feed into the parser from the previous section, we need a parser that can be called with one byte at a time, not one that demands a read callback. This decode loop cannot be presented as a read callback bceause it obtains 3 input bytes at a time and uses its control flow to track which ones have been written. Because the decoder is storing its own state in its control flow, parseQuoted cannot.

In a non-concurrent program, this base64 decoder and parseQuoted would be at an impasse: one would have to give up its use of control flow state and fall back to some kind of simulated version instead.

To rewrite parseQuoted, we have to reintroduce the state variable, which we can encapsulate in a struct with a Write method:

type parser struct {
    state int
}

func (p *parser) Init() {
    p.state = 0
}

func (p *parser) Write(c byte) Status {
    switch p.state {
    case 0:
        if c != '"' {
            return BadInput
        }
        p.state = 1
    case 1:
        if c == '"' {
            return Success
        }
        if c == '\\' {
            p.state = 2
        } else {
            p.state = 1
        }
    case 2:
        p.state = 1
    }
    return NeedMoreInput
}

The Init method initializes the state, and then each Write loads the state, takes actions based on the state and the input byte, and then saves the state back to the struct.

For parseQuoted, the state machine is simple enough that this may be completely fine. But maybe the state machine is much more complex, or maybe the algorithm is best expressed recursively. In those cases, being passed an input sequence by the caller one byte at a time means making all that state explicit in a data structure simulating the original control flow.

Concurrency eliminates the contention between different parts of the program over which gets to store state in control flow, because now there can be multiple control flows.

Suppose we already have the parseQuoted function, and it’s big and complicated and tested and correct, and we don’t want to change it. We can avoid editing that code at all by writing this wrapper:

type parser struct {
    c      chan byte
    status chan Status
}

func (p *parser) Init() {
    p.c = make(chan byte)
    p.status = make(chan Status)
    go p.run()
    <-p.status // always NeedMoreInput
}

func (p *parser) run() {
    if !parseQuoted(p.read) {
        p.status <- BadSyntax
    } else {
        p.status <- Success
    }
}

func (p *parser) read() byte {
    p.status <- NeedMoreInput
    return <-p.c
}

func (p *parser) Write(c byte) Status {
    p.c <- c
    return <-p.status
}

Note the use of parseQuoted, completely unmodified, in the run method. Now the base64 decoder can use p.Write and keep its program counter and local variables.

The new goroutine that Init creates runs the p.run method, which invokes the original parseQuoted function with an appropriate implementation of read. Before starting p.run, Init allocates two channels for communicating between the p.run method, runing in its own goroutine, and whatever goroutine calls p.Write (such as the base64 decoder’s goroutine). The channel p.c carries bytes from Write to read, and the channel p.status carries status updates back. Each time parseQuoted calls read, p.read sends NeedMoreInput on p.status and waits for an input byte on p.c. Each time p.Write is called, it does the opposite: it sends the input byte c on p.c and then waits for and returns an updated status from p.status. These two calls take turns, back and forth, one executing and one waiting at any given moment.

To get this cycle going, the Init method does the initial receive from p.status, which will correspond to the first read in parseQuoted. The actual status for that first update is guaranteed to be NeedMoreInput and is discarded. To end the cycle, we assume that when Write returns BadSyntax or Success, the caller knows not to call Write again. If the caller incorrectly kept calling Write, the send on p.c would block forever, since parseQuoted is done. We would of course make that more robust in a production implementation.

By creating a new control flow (a new goroutine), we were able to keep the code-state-based implementation of parseQuoted as well as our code-state-based base64 decoder. We avoided having to understand the internals of either implementation. In this example, both are trivial enough that rewriting one would not have been a big deal, but in a larger program, it could be a huge win to be able to write this kind of adapter instead of having to make changes to existing code. As we’ll discuss later, the conversion is not entirely free – we need to make sure the extra control flow gets cleaned up, and we need to think about the cost of the context switches – but it may well still be a net win.

Store Stacks on the Stack

The base64 decoder’s control flow state included not just the program counter but also two local variables. Those would have to be pulled out into a struct if the decoder had to be changed not to use control flow state. Programs can use an arbitrary number of local variables by using their call stack. For example, suppose we have a simple binary tree data structure:

type Tree[V any] struct {
    left  *Tree[V]
    right *Tree[V]
    value V
}

If you can’t use control flow state, then to implement iteration over this tree, you have to introduce an explicit “iterator”:

type Iter[V any] struct {
    stk []*Tree[V]
}

func (t *Tree[V]) NewIter() *Iter[V] {
    it := new(Iter[V])
    for ; t != nil; t = t.left {
        it.stk = append(it.stk, t)
    }
    return it
}

func (it *Iter[V]) Next() (v V, ok bool) {
    if len(it.stk) == 0 {
        return v, false
    }
    t := it.stk[len(it.stk)-1]
    v = t.value
    it.stk = it.stk[:len(it.stk)-1]
    for t = t.right; t != nil; t = t.left {
        it.stk = append(it.stk, t)
    }
    return v, true
}

On the other hand, if you can use control flow state, confident that other parts of the program that need their own state can run in other control flows, then you can implement iteration without an explicit iterator, as a method that calls a yield function for each value:

func (t *Tree[V]) All(f func(v V)) {
    if t != nil {
        t.left.All(f)
        f(t.value)
        t.right.All(f)
    }
}

The All method is obviously correct. The correctness of the Iter version is much less obvious. The simplest explanation is that Iter is simulating All. The NewIter method’s loop that sets up stk is simulating the recursion in t.All(f) down successive t.left branches. Next pops and saves the t at the top of the stack and then simulates the recursion in t.right.All(f) down successive t.left branches, setting up for the next Next. Finally it returns the value from the top-of-stack t, simulating f(value).

We could write code like NewIter and argue its correctness by explaining that it simulates a simple function like All. I’d rather write All and stop there.

Comparing Binary Trees

One might argue that NewIter is better than All, because it does not use any control flow state, so it can be used in contexts that already use their control flows to hold other information. For example, what if we want to traverse two binary trees at the same time, checking that they hold the same values even if their internal structure differs. With NewIter, this is straighforward:

func SameValues[V any](t1, t2 *Tree[V]) bool {
    it1 := t1.NewIter()
    it2 := t2.NewIter()
    for {
        v1, ok1 := it1.Next()
        v2, ok2 := it2.Next()
        if v1 != v2 || ok1 != ok2 {
            return false
        }
        if !ok1 && !ok2 {
            return true
        }
    }
}

This program cannot be written as easily using All, the argument goes, because SameValues wants to use its own control flow (advancing two lists in lockstep) that cannot be replaced by All’s control flow (recursion over the tree). But this is a false dichotomy, the same one we saw with parseQuoted and the base64 decoder. If two different functions have different demands on control flow state, they can run in different control flows.

In our case, we can write this instead:

func SameValues[V any](t1, t2 *Tree[V]) bool {
    c1 := make(chan V)
    c2 := make(chan V)
    go gopher(c1, t1.All)
    go gopher(c2, t2.All)
    for {
        v1, ok1 := <-c1
        v2, ok2 := <-c2
        if v1 != v2 || ok1 != ok2 {
            return false
        }
        if !ok1 && !ok2 {
            return true
        }
    }
}

func gopher[V any](c chan<- V, all func(func(V))) {
    all(func(v V) { c <- v })
    close(c)
}

The function gopher uses all to walk a tree, announcing each value into a channel. After the walk, it closes the channel.

SameValues starts two concurrent gophers, each of which walks one tree and announces the values into one channel. Then SameValues does exactly the same loop as before to compare the two value streams.

Note that gopher is not specific to binary trees in any way: it applies to any iteration function. That is, the general idea of starting a goroutine to run the All method works for converting any code-state-based iteration into an incremental iterator. My next post, “Coroutines for Go,” expands on this idea.

Limitations

This approach of storing data in control flow is not a panacea. Here are a few caveats:

If the state needs to evolve in ways that don’t naturally map to control flow, then it’s usually best to leave the state as data. For example, the state maintained by a node in a distributed system is usually not best represented in control flow, because timeouts, errors, and other unexpected events tend to require adjusting the state in unpredictable ways.
If the state needs to be serialized for operations like snapshots, or sending over a network, that’s usually easier with data than code.
When you do need to create multiple control flows to hold different control flow state, the helper control flows need to be shut down. When SameValues returns false, it leaves the two concurrent gophers blocked waiting to send their next values. Instead, it should unblock them. That requires communication in the other direction to tell gopher to stop early. “Coroutines for Go” shows that.
In the multiple thread case, the switching costs can be significant. On my laptop, a C thread switch takes a few microseconds. A channel operation and goroutine switch is an order of magnitude cheaper: a couple hundred nanoseconds. An optimized coroutine system can reduce the cost to tens of nanoseconds or less.

In general, storing data in control flow is a valuable tool for writing clean, simple, maintainable programs. Like all tools, it works very well for some jobs and not as well for others.

Counterpoint: John McCarthy’s GOPHER

The idea of using concurrency to align a pair of binary trees is over 50 years old. It first appeared in Charles Prenner’s “The control structure facilities of ECL” (ACM SIGPLAN Notices, Volume 6, Issue 12, December 1971; see pages 106–109). In that presentation, titled “Tree Walks Using Coroutines”, the problem was to take two binary trees A and B with the same number of nodes and copy the value sequence from A into B despite the two having different internal structure. They present a straightforward coroutine-based variant.

Brian Smith and Carl Hewitt introduced the problem of simply comparing two Lisp-style cons trees (in which internal nodes carry no values) in their draft of “A Plasma Primer” (March 1975; see pages 61-62). For that problem, which they named “samefringe”, they used continuation-based actors to run a pair of “fringe” actors (credited to Howie Shrobe) over the two trees and report nodes back to a comparison loop.

Gerald Sussman and Guy Steele presented the samefringe problem again, in “Scheme: An Interpreter for Extended Lambda Calculus” (December 1975; see pages 8–9), with roughly equivalent code (crediting Smith, Hewitt, and Shrobe for inspiration). They refer to it as a “classic problem difficult to solve in most programming languages”.

In August 1976, ACM SIGART Bulletin published Patrick Greussay’s “An Iterative Lisp Solution to the Samefringe Problem”, This prompted a response letter by Tim Finin and Paul Rutler in the November 1976 issue (see pages 4–5) pointing out that Greussay’s solution runs in quadratic time and memory but also remarking that “the SAMEFRINGE problem has been notoriously overused as a justification for coroutines.” That discussion prompted a response letter by John McCarthy in the February 1977 issue (see page 4).

In his response, titled “Another samefringe”, McCarthy gives the following LISP solution:

(DE SAMEFRINGE (X Y)
       (OR (EQ X Y)
           (AND (NOT (ATOM X))
                (NOT (ATOM Y))
                (SAME (GOPHER X) (GOPHER Y)))))

(DE SAME (X Y)
       (AND (EQ (CAR X) (CAR Y))
            (SAMEFRINGE (CDR X) (CDR Y))))

(DE GOPHER (U)
       (COND ((ATOM (CAR U)) U)
             (T (GOPHER (CONS (CAAR U)
                              (CONS (CDAR U) (CDR U)))))))

He then explains:

gopher digs up the first atom in an S-expression, piling up the cdr parts (with its hind legs) so that indexing through the atoms can be resumed. Because of shared structure, the number of new cells in use in each argument at any time (apart from those occupied by the original expression and assuming iterative execution) is the number of cars required to go from the top to the current atom – usually a small fraction of the size of the S-expression.

In modern terms, McCarthy’s GOPHER loops applying right tree rotations until the leftmost node is at the top of the tree. SAMEFRINGE applies GOPHER to the two trees, compares the tops, and then loops to consider the remainders.

After presenting a second, more elaborate solution, McCarthy remarks:

I think all this shows that samefringe is not an example of the need for co-routines, and a new “simplest example” should be found. There is no merit in merely moving information from data structure to control structure, and it makes some kinds of modification harder.

I disagree with “no merit”. We can view McCarthy’s GOPHER-ized trees as an encoding of the same stack that NewIter maintains but in tree form. The correctness follows for the same reasons: it is simulating a simple recursive traversal. This GOPHER is clever, but it only works on trees. If you’re not John McCarthy, it’s easier to write the recursive traversal and then rely on the general, concurrency-based gopher we saw earlier to do the rest.

My experience is that when it is possible, moving information from data structure to control structure usually makes programs clearer, easier to understand, and easier to maintain. I hope you find similar results.

Opting In to Transparent Telemetry

2023-02-24T08:59:00-05:00

Earlier this month I posted “Transparent Telemetry for Open-Source Projects”, making the case that open-source software projects need to find an open-source-friendly way to collect basic usage and performance information about their software, to help maintainers understand how their software is used and prioritize their work. I invited feedback on a GitHub discussion and over email.

In general, the feedback was mostly constructive, and mostly positive. In the GitHub discussion, there were some unconstructive trolls with no connection to Go who showed up for a while, but they were the exception rather than the rule: most people seemed to be engaging in good faith. I also saw some good discussion on Twitter and Mastodon, and I received some good feedback via email.

People who read the posts seemed to agree that there's a real problem here for open-source maintainers and that transparent telemetry or something like it is an appropriately minimal amount of collection. By far the most common suggestion was to make the system opt-in (default off) instead of opt-out (default on). I have revised the design to do that.

The rest of this post discusses the reasons for the change to opt-in as well as the effects on the rest of the design.

Opt-in vs Opt-out

Many people were fine with this telemetry being on by default, precisely because it is carefully designed to be so minimal. On the other hand, multiple people told me things like “this is the first system I've seen that I'd actually opt in to, but I'd still turn it off if it was on by default.” A few people were concerned about a kind of reidentification attack on the published records: if you knew that company X was on record as being the only user of a given obscure configuration, you might be able to find their records and learn other things about which Go features they use. My imagination is not good enough to figure out how an attacker could exploit data like that, but even so it does seem not worth dismissing entirely.

Another concern I have with an opt-out system is that my goal is to find a path that works for many open source projects, not just Go. Although we've carefully architected the system not to collect sensitive data, if Go's telemetry were opt-out, that might be used to justify other opt-out systems that are not as careful about what they collect. For example, despite the blog posts discussing at length the distinction between everything .NET collects and the much more limited data I am suggesting that Go collect, too many people still seemed to equate them.

For all these reasons, I've revised the design to be opt-in (default off). Doing so does introduce at least two costs: first, we must run an ongoing campaign to educate users about opting in is a good choice for them, and second, with fewer systems reporting, the telemetry cost imposed on any particular user is higher.

The Campaign Cost of Opt-In

The first new cost in an opt-in system is the ongoing overhead of asking users to opt in, with a clear explanation of what is and is not collected. There are a few obvious times when that makes sense:

During a graphical install of Go, with two different buttons for the two choices (no click-through default).
In blog posts and release notes for new Go releases.
During our traditional user surveys.
The first time VS Code Go is invoked on Go code.

We may think of others ways too, of course, including giving talks about this topic, explaining why we designed the system as we did, and encouraging users to opt in.

One person suggested making the system opt-in and then collecting tons more information, like the details of every command invocation, geolocation, and more. I think that would be a serious mistake. I would be happy to stand in front of a crowd and explain the current system and why users should opt in. I would be embarrassed to try to do the same for the more detailed telemetry this person suggested, because it seems indefensible: we simply don't need all that information to inform our decisions.

The Privacy Cost of Opt-In

Even with an ongoing campaign to have users opt in, we should expect that fewer systems will end up with telemetry enabled than if it were opt-out. I don't have a good sense of what level of opting in we should expect from an effective opt-in campaign. In part, this is because most systems can't run such a campaign (see the previous paragraph). However, in the past I have heard some people say that typical opt-in rates can be as low as a few percent.

I think we would be happy to get 10% and thrilled to get 20%, but I don't know whether that's possible. We don't even have a precise way to measure the opt-in rate, since by definition we can't see anything about people who have opted out. We have estimated the number of Go developers at a few million, so seeing a few hundred thousand systems opted in would, I think, be a success.

Transparent telemetry uses sampling to reduce the privacy cost to any one system: we only need around 16,000 reports in a given week for 1% accuracy at a 99% confidence level. If there are a million systems reporting, which seemed plausible in the opt-out system, then any given system only needs to report 1.6% of the time, or less than once a year. On the other hand, if we'd be happy to get 100,000 systems opted in, then we need each system to report 16% of the time, or about once every month and a half. The opt-in system is fundamentally more invasive to any given installation than the opt-out system. Of course, by design it is still not terribly invasive, since uploaded reports do not contain any identifying information or any strings not already known to the collection system. But still, individual systems carry a larger burden when there are fewer, as there will be in an opt-in system.

Can We Still Make Good Decisions?

Thinking about even lower opt-in rates, will the system still able to provide data to help us making decisions? I think it will be, although the sampling rates will be higher.

A common mistake when thinking about polls and other sampled data collection is to confuse the fraction of samples (surveying, say, 1% of a population) with the accuracy of the result (making a claim with 1% accuracy). Those are different percentages. As we saw in “The Magic of Sampling, and its Limitations”, if there are a billion systems and we only sample 16,000 of them (0.0016%), we can still make claims with 1% accuracy, despite ignoring 99.9984% of the systems. Of course, there are not billions of Go installations (yet!). Assuming there are three million Go installations, as long as there is no correlation between whether a system is opted in and the value we want to measure, having even a 1% opt-in rate (30,000 systems available to report) should give us fairly accurate data. And of course as more systems opt in, each individual system will be sampled less often.

The “as long as there is no correlation” caveat deserves more scrutiny. What might be correlated with opting in to Go telemetry? Certainly the opt-in campaign methods will skew who opts in:

People using the Go graphical installers will be more likely to opt in.
People who read our blog and release notes will be more likely to opt in.
People who take our surveys will be more likely to opt in.
People who use VS Code Go will be more likely to opt in.

The next question is whether any of these would be correlated with and therefore skew metrics we are interested in, and how we would know. One obvious blind spot would be people installing Go through a package manager like apt-get or Homebrew. Perhaps the telemetry would undercount Linux and Mac. It might also overcount VS Code Go users. We can check many of these high-level machine demographics against the Go developer survey and others. These are biases to be aware of when interpreting the data, but I've been clear from the start that data is one input to the decision making process, not the determining factor. Some data is almost always better than no data: if the 10,000 systems you can see are all working properly, it's incredibly unlikely that there's a problem affecting even as many as 5% of all systems.

No Telemetry At All?

Before ending the post, I want to look at a couple other common suggestions. The first was to not have any telemetry at all: just use bug reports and surveys. Of all the people I saw make this comment, not one of them acknowledged reading the explanation of why those don't work at the start of the first post.

Some people made a “slippery slope” argument that having any telemetry at all would make it easier to add more invasive telemetry: good telemetry opens the door to bad telemetry. When you examine this argument more closely, it doesn't hold up. The process for adding “bad telemetry” to Go would be the same whether or not there's already “good telemetry”: modify the source code, get it checked in, and wait for it to go out in a new release. The defense strategy in either case is that Go is open source: anyone can inspect its source code, including recompiling it and verifying that the distributed binaries match that source code. Also, anyone can watch and participate in its development. If you are concerned about bad actors making changes, watch the development of Go, or trust others to watch it. If you don't believe enough people are watching, then you probably shouldn't use Go at all. You might reconsider other open-source software you use too.

Cryptographic Approaches

The most interesting suggestion was to use a system like Prio or Prochlo. Prio in particular is being productionized by ISRG (the same group that runs Let's Encrypt) as Divvi Up.

Those systems are not yet widely available, and perhaps it would make sense to use them in the future. Both depend on having two separate entities to run the system, with users trusting that the two will not collude to unmask their privacy. This kind of scheme provides enough privacy to allow collecting far more sensitive data, such as fine-grained location data or web page URLs. Luckily, for Go we have no need of anything that sensitive.

Another problem with these systems is that they are difficult to explain and inspect. The math behind them is solid, and if you're collecting that kind of sensitive data, you absolutely need something like them. But if, like in the Go design, you're not sending anything sensitive, then it could be better to use a simpler system that is easier to explain, so that people understand exactly what they are opting in to, and that is easier to watch, so that people can see exactly what information is being sent. People might well be more comfortable and more likely to opt in to a system they can more easily understand and verify.

Adopting a cryptographic schemes would therefore require significantly more effort and explanation for a relatively small privacy improvement; For now, it doesn't seem worth using one of those. If in the future one of those systems became a standard, widely accepted mechanism for open source telemetry, it would make sense to reexamine that decision.

Another possibility would be for operating system vendors to serve the role of collectors in one of these systems, taking care of collection from many programs running on the system instead. If done right, this could ensure greater privacy (provided users trust their operating system vendors!) instead of each system inventing a new wheel. If privacy-respecting telemetry collection became a standard operating system functionality, then it would absolutely make sense for Go to use that. Some day, perhaps.

Next Steps

Next week I intend to submit an actual Go proposal to add opt-in transparent telemetry to the Go toolchain. I have also added notes to the original blog posts mentioning the design change and pointing to this one.

It probably makes sense to prototype the system in gopls, the LSP server used by VS Code Go and other editors, to allow faster iteration. Once we are happy with the system, then it would make sense to add it to the standard Go toolchain as well, to enable the many use cases in the earlier post.

Thanks to everyone who took the time to write constructive, helpful feedback. Those discussions are open source at its best.

Use Cases for Transparent Telemetry

2023-02-08T08:00:03-05:00

I believe open-source software projects need to find an open-source-friendly way to do telemetry. This post is part of a short series of posts describing transparent telemetry, one possible answer to that challenge. For more about the rationale and background, see the introductory post. For details about the design, see the previous post.

For many years I believed we could make good enough decisions for Go without collecting any telemetry, by focusing on testing, benchmarks, and surveys. Over that time, however, I have collected many examples of decisions that can’t be made in a principled way without better data, as well as performance problems that would go unnoticed. This post presents some of those examples.

What fraction of `go` command invocations still use GOPATH mode (as compared to Go modules)? What fraction of Go installations do?

Understanding how often GOPATH mode (non-module mode) is used is important for understanding how important it is to keep running, and for which use cases. Like many of these questions, knowing the basic usage statistics would help us decide whether or not to ask more specific questions on a Go survey or in research meetings with Go users. We are also considering changes like fine-grained compatibility (#56986 and #57001) and per-iteration loop scoping (#56010) that depend heavily on version information available only in module mode. Understanding how often GOPATH mode is used would help us understand how many users those changes would leave behind.

To answer these questions, we would need two counters: P, the number of times the go command is invoked in GOPATH mode, and N, the the number of times the go command is invoked at all. The answer to the first question is P divided by N. When collected across all sampled systems, it wouldn’t make sense to present the total P divided by the total N. Instead, we’d want to present the distribution of P/N in sampled reports, plotting the cumulative distribution of P/N over all systems. The answer to the second question is the number of reports with P > 0 divided by the total number of reports. This can also be read off the cumulative distribution graph by looking for P/N > 0.

What fraction of `go` command invocations use Go workspaces (a `go.work` file)? What fraction of Go installations do?

We added Go workspaces in Go 1.18. Most of the time, go.work files will be most appropriate in modules that are not dependencies of other modules, such as closed-source projects. Understanding how often workspaces are used in practice would help us prioritize work on them as well as understand whether they are as useful as we expected. That knowledge would again inform future survey questions and research interviews.

Answering these questions requires the N counter from above as well as a new counter for the number of times the go command is invoked in a Go workspace.

What fraction of `go` command invocations or Go installations use `-buildmode=shared`? What fraction of Go installations do?

As mentioned in the introductory post, -buildmode=shared has never worked particularly well, and its current design is essentially incompatible with Go modules. We have a rough design for how we might make it work, but that’s a lot of work, and it’s unclear whether it should be a high priority. Our guess is that there are essentially no users of this flag, and that therefore it shouldn’t be prioritized. But that’s just a guess; data would be better.

Answering these questions requires the N counter as well as a new counter for the number of times the go command is invoked with -buildmode=shared. In general we would probably want to define a counter for the usage of every command flag. When the set of flag values is limited to a fixed set, as it is for -buildmode, we would also include the flag value, to distinguish, for example, -buildmode=c-shared (which is working and easy to support) from -buildmode=shared (which is not). As noted in the discussion of this example in the main text, it is possible that only certain build machines using -buildmode=shared and those all also have telemetry disabled. If so, we won’t see them. This is a fundamental limitation of telemetry: it serves as an additional input into decisions, not as the only deciding factor.

What fraction of `go` command invocations use a specific GOOS, GOARCH, or subarchitecture setting? What fraction of Go installations do?

Go has a porting policy that distinguishes between first-class and secondary ports. The first-class ports are the ones that the Go team at Google supports directly and that are important enough to stop a release if a serious bug is encountered. We do not have a principled, data-driven way to decide which ports are first-class and which are secondary. Instead, we make guesses based on prior knowledge and other non-Go usage statistics. Today the first-class ports are Linux, macOS, and Windows running on 386, amd64, arm, and arm64. Should we add FreeBSD to the list? (Maybe?) What about RISC-V? (Probably not yet?) At the subarchitecture level, is it time to retire support for GOARM=5 (ARMv5), which does not have support for atomic memory operations in hardware and must rely on the operating system kernel to provide them? (I have no idea.) Data would be helpful in making those decisions.

Answering these questions requires the N counter as well as a new counter for the number of times each of the Go-specific environment variables takes one of their known values. For example, there would be different counters for the go command running with GOARCH=amd64, GOARCH=arm, GOOS=linux, GOOS=windows, GOARM=5, GO386=sse2, and so on.

What fraction of Go installations run on a particular major version of an operating system such as Windows 7, Windows 8, or WSL?

As operating systems get older, they often become harder to support. It gets harder to run them in modern virtual machines for testing, kernel bugs affecting Go are left unfixed, and so on. One of the considerations when deciding to end support for a port is the amount of usage it gets, yet we have no reliable way to measure that. Recently we decided to end support for Windows 7 (#57003) and Windows 8 (#57004). We were able to rely on other considerations, namely Microsoft’s own support policy, as well as operating system statistics collected by companies deploying Go binaries. It would be helpful to have our own direct statistics as well. More recently, we announced that Go 1.20 will be the last release to support macOS High Sierra and were promptly asked to keep it around (#57125).

Answering these questions would require counters for each major operating system version like Windows 7, Windows 8, Debian Buster, Linux 3.2.x, and so on. There would be no need to collect fine-grained information like specific patch releases, unless some specific release was important for some reason (for example, we might want more resolution on Linux 2.6.x, to inform advancing the minimum Linux kernel version beyond 2.6.32).

What fraction of builds cross-compile, and what are the most common cross-compilation targets?

Go has always been portable and supported cross-compilation. That’s clearly important and won’t be removed, but what are the host/target pairs that are most important to make work well? For example, Go 1.20 will improve compiling macOS binaries from a Linux system: the binaries will now use the host DNS resolver, same as native macOS builds. After I made this change, multiple users reached out privately to thank me for solving a major pain point for them. This was a surprise to me: I was unaware that cross-compiling macOS binaries from Linux was so common. Are there other common cross-compilation targets that merit special attention?

Answering these questions uses the same counters as in the last section, along with information about the native default GOOS and GOARCH settings.

What is the overall cache miss rate in the Go build cache?

The Go build cache is a critical part of the user experience, but we don’t know how well it works in practice. The original build cache heuristics were decided in 2017 based on a tracing facility that we asked users to run for a few weeks and submit traces. Since then, many things about Go builds have changed, and we have no idea how well things are working.

Answering this question requires a counter for build cache misses and another for build cache hits or accesses.

What is the typical cache miss rate in the Go build cache for a given build?

A more detailed question would be what a typical cache miss rate is for a given build. We hope it would be very low, and if it went up, we’d want to investigate why. This is something that users are unlikely to notice and report directly, but it would still indicate a serious problem worth fixing.

Answering this question would require keeping an in-memory total of cache misses and hits, and then at the end of the build computing the overall rate and incrementing a counter corresponding to one column of a histogram, as described in the introductory post.

What fraction of `go` command invocations recompile the standard library?

The cache hit rate for standard library packages should be very high, since users are not editing those packages. Before Go 1.20, distributions shipped with pre-compiled .a files that should have served as cache hits for default builds. Only cross-compilation or changing build tags or compiler flags should have caused a rebuild, and then those would have been cached too. The cache hit rate in the standard library can therefore serve as a good indicator that the build cache is working properly. Especially if the overall hit rate is low, checking the standard library hit rate should help distinguish a few possible failure modes. As noted at the introductory post, this metric would have detected a bug invalidating the pre-compiled macOS .a files that lingered for six releases instead.

Answering this question would require keeping a counter of the number of go command invocations that recompile any standard library package, along with the total number of invocations N.

What is the typical cache hit age in the Go build cache?

Another important question is how big the cache needs to be. Today the build cache has a fixed policy of keeping entries for 5 days after last use and then deleting them, based on the traces we collected in 2017. Some users have reported the build cache being far too large for their machines (#29561). One possible change would be to reduce the maximum time since last use. Perhaps 1 day or 3 days would be almost as effective, at a fraction of the cost.

Answering this question would require making another histogram of counters, this time for a cache hit in an entry with a given age range.

Would a generational build cache work effectively?

Another possible change to the build cache would be to adopt a collection policy inspired by generational garbage collection: an entry is deleted after a few hours, unless it is used a second time, in which case it is kept until it hasn’t been used again for a few days. Would this work?

Answering this question would require a second histogram counting the age distribution of cache entries at their first reuse, as well as a counter of the number of cache entries deleted without any reuse at all.

How many modules are listed in a typical Go workspace?

Go 1.18 workspaces allow working in multiple work modules simultaneously. How many work modules are in a typical workspace? We don’t know, so we don’t know how important per-module overheads are.

Answering this question would require a histogram of workspace size.

How many `go.mod` files are loaded in a typical `go` command invocation?

In addition to the one or more modules making up the workspace, every time the go command starts up it needs to load information about all the dependency modules. In many projects, the number of direct module requirements appears small but indirect requirements add many more modules. What is a typical number of modules the go command must load?

Go 1.17 introduced module graph pruning, which lists all used transitive dependencies in the top-level go.mod file for a project and then avoids reading go.mod files from unused indirect dependencies. That is reduces the number of go.mod files loaded. We know it works on our test cases and a few real repositories like Kubernetes, but we don’t know how well it works across a variety of Go installations. If we’d had telemetry before the change, we should have seen a significant drop in this statistic. If not, that would be a bug to investigate.

Answering this question would require a histogram of the number of modules loaded.

What is the distribution of time spent downloading modules in a given build?

Even with module graph pruning, the go command still spends time downloading go.mod files and module content into the cache as needed. How much time is spent on downloads? If it’s a lot, then maybe we should work on reducing that number, such as by parallelizing downloads or improving download speed.

Answering this question would require a histogram of time spent in the module download phase of the go command.

What is the latency distribution of a Go workspace load?

Most go command invocations will not need to download anything. Those are bottlenecked by the overall workspace load, which spends its time reading the go.mod files and scanning all the Go packages to understand the import graph and relevant source files. How long does that typically take?

We found out from discussions with users that the number was significantly higher in module mode than in GOPATH mode in a real system, so in Go 1.19 we introduced module cache indexing, which lets the go command avoid reading the top of every Go source file in every dependency at startup to learn the import graph. If we’d had telemetry before the change, we should have seen a significant drop in this statistic. If not, that would be a bug to investigate.

Answering this question would require a histogram of time spent in the workspace load phase of the go command.

What is the module cache index miss rate?

The module cache index should have a very low miss rate, because changes to the module’s dependency graph are much less common than changes to source files. Is that true on real systems? If not, there’s a bug to find.

Answering this question would require computing the overall module cache index miss rate during a build and then keeping a histogram of rates observed, just like for the build cache miss rate.

What fraction of builds encounter corrupt Go source files in the module cache? Does this percentage correlate with host operating system?

We have some reports of corrupted Go source files when using the module index (#54651). This corruption seems very uncommon, and it seems to manifest only when using GOOS=linux under the Windows Linux subsystem WSL2, suggesting that the problem may not be Go’s fault at all. There is not an obvious path forward for that issue, and we don’t understand the severity, although it appears to be low. If we could change the Go toolchain to work around observed corruption but also self-report its occurrence, then we could get a better sense of the impact of this bug and how important it is to fix. For a bug like this, we would typically reason that it is not happening very often so it would be better to leave it open and learn more about what causes it than to add a workaround and lose that signal. Telemetry lets us both add the workaround and watch to see that the bug is not a sign of a larger problem.

Answering this question would require having a counter for encountering invalid Go source files in the module cache. That should be a rare event, and if we saw an uptick we could look at correlation with other information like the default GOOS and the operating system major versions, provided WSL2 was reported as something other than Linux.

How much CPU and RAM does a typical invocation of the compiler or linker take?

We have invested significant effort into reducing the CPU and RAM requirements of both the compiler and the linker. The linker in particular was almost completely reengineered in Go 1.15 and Go 1.16. We have some benchmarks to exercise them, but we don’t know how that translates into real-world performance. The linker work was motivated by performance limits in Google’s build environment compiling Google’s Go source code. Other environments may have significantly different performance characteristics. If so, that would be good to know.

Answering this question would require a CPU histogram for the compiler, a RAM histogram for the compiler, and then CPU and RAM histograms for the linker as well.

What is the relative usage of different versions of the Go toolchain?

The current Go release support policy is that each release is supported until there are two newer major releases. With work like the Go compatibility policy, we aim to make it easy to update to newer releases, so that users do not get stuck on unsupported releases. How well is that working? We don’t know. The fine-grained compatibility work (#56986 and #57001) aims to make it easier to update to a newer toolchain, which should mean usage of older versions falls off quicker. It would be helpful to confirm that with data. Also, once there is a baseline for how quickly new versions are adopted, seeing one lag would indicate a problem worth investigating. For example, I recently learned about a Windows timer problem (#44343) that is keeping some Windows users on Go 1.15. If we saw that in the data, we could look for what is holding users back.

Answering this question would not require any direct counters. The reports are already annotated with which version of Go was running, so the percentage can be calculated as number of reports from a specific version of Go divided by total reports.

What is the relative distribution of Go versions in `go` lines in the work module during a build?

Today the go line indicates roughly (but not exactly) the maximum version of Go that a module targets. Part of proposal #57001 is to change it to be the exact minimum permitted version of Go. It would be good to know how often modules set that line to the latest version of Go as compared to the previous version of Go or an unsupported earlier version, for much the same reasons as the previous question.

Answering this question requires a counter for each released go version, incremented for each build using a go line with that version. Another way to answer this question would be to scan open-source Go modules, but conventions in the open-source Go library ecosystem may well be different from conventions in the production systems that use those packages. We don’t want to overfit our decisions to what happens in open-source code.

What fraction of builds encounter `//go:debug` lines? What is the relative usage of each setting?

The fine-grained compatibility work (#56986) proposes to add a new //go:debug line used in main packages to set default GODEBUG settings. Those settings would be guaranteed to be provided for two years, but after that we would be able to retire settings as needed. Knowing how much each one is used would let us make informed decisions about whether to retire specific settings.

Answering these questions requires a counter for each GODEBUG setting, incremented for each build using a //go:debug line with that setting. As before, another possibility would be to scan open-source Go modules, but the vast majority of open source is libraries, not main packages, so there would be very little signal, and the signal we do get could be very different from the reality of production usage.

What fraction of builds use C code via cgo? What about C++, Objective-C, Fortran, or SWIG?

Cgo is another area where the open-source Go library ecosystem is almost certainly not aligned with actual production usage: cgo tends to be discouraged in most public Go libraries but is a critical part of interoperation with existing code in many production systems. We don’t know how many though, nor what the cgo use looks like. Go added support for C++ and SWIG early on, due to usage at Google. Objective-C and Fortran were added at user request. Objective-C probably gets lots of use now on macOS and iOS, but what about Fortran? Is anyone using it at all? Do we need to prioritize testing it or fixing bugs in it?

Answering these questions requires a counter for each go build of a package using cgo, and then additional counters for when the cgo code includes each of the languages of interest. Again we could scan open-source Go modules, but production usage is likely to be different from open-source libraries.

What fraction of builds with cgo code explicitly disable cgo? What fraction implicitly disable it? What fraction of builds implicitly disable cgo because there is no host C compiler?

Many builds insist on not using cgo by setting CGO_ENABLED=0. Cgo is also disabled by default when cross-compiling. Starting in Go 1.20, cgo is disabled by default when there is no host C compiler. It would be helpful to know how often these cases happen. If lots of builds explicitly disable cgo, that would be something to ask about in surveys and research interviews. If lots of builds implicitly disable cgo due to cross-compiling, we might want to look into improving support for cgo when cross-compiling. If lots of builds implicitly disable cgo for not having a host C compiler, we might want to talk to users to understand how it happens and then update documentation appropriately.

Answering these questions requires counters for builds with cgo code, builds with an explicit CGO_ENABLED=0, builds with implicit disabling due to cross-compilation, and builds with implicit disabling due to lack of host C compiler.

What fraction of Go installations use a particular version of a Go toolchain dependency such as Clang, GCC, Git, or SWIG?

The Go toolchain contains many workarounds for old versions of tools that it invokes, like Clang, GCC, Git, and SWIG. For example, Clang 3.8’s -g flag is incompatible with .note.GNU-stack sections, so the go command has to look for a specific error and retry without the flag. The go command also invokes various git commands to understand the repository it is working inside, and it is difficult to tell whether a new command will be safe. For example, go uses the global git -c option, which was added in Git 1.7.2. Is that old enough to depend on? We decided yes in 2018, but that broke CentOS 6. Even today we have not resolved what versions we should require for version control dependencies (#26746). Data would help us make the decision.

Answering these questions requires counters for builds that invoke each of these tools along with per-tool-version counters, giving a version histogram for each tool.

What fraction of builds use `GOEXPERIMENT=boringcrypto`?

Go published a fork using BoringCrypto years ago; in Go 1.19 the code moved into the main tree, accessible with GOEXPERIMENT=boringcrypto. The code is unsupported today, but if there was substantial usage, that might make us think more about whether to start supporting it.

Answering this question requires a counter for builds with GOEXPERIMENT=boringcrypto.

What are the observed internal compiler errors in practice?

Because compilers try to keep processing a program even after finding the first error, it is common to see index out of bounds or nil reference panics happen in code that has already been diagnosed as invalid. Instead of crashing in this situation, the Go compiler has a panic handler that checks whether any errors have already been printed. If so, then the compiler silently exits early (unsuccessfully), leaving the user to fix the reported errors and try again. After the reported errors are fixed, the next run is likely to work just fine. Hiding these panics provides a much better experience to users, but each such panic is still a bug we would like to fix. Since the panics are successfully masked, users will never file bug reports for them. It would be helpful to collect stack traces for these panics, even when the compiler exits gracefully.

Answering this question would require a crash counter (corresponding to the current call stack) to be incremented in the panic handler even when the panic is otherwise silenced.

What is the relative distribution of compiler errors printed during development?

The errors printed by the compiler for invalid programs are a critical part of the overall Go user experience. In the early days of Go, I spent a lot of time making sure that the errors printed for my own buggy programs were clear. But different Go users make different mistakes: helping new Go users with their own programs was an important way I found out about other errors that needed to be clearer, Today, Go usage has grown far beyond anything we can understand from personal experience. Understanding which errors people hit the most would help us decide which ones to focus on in research interviews and make clearer or more specific. Commonly encountered errors might also prompt ideas about language changes. For example, we made unused imports and variables errors before go vet existed. If users hit those frequently enough to be bothersome, we might consider making them no longer compiler errors and instead leave them to be go vet errors.

It would also be interesting to compare the error distribution from the compiler against the error distribution from gopls for users who work in an IDE. Does the IDE make certain errors less (or more) likely? Does it keep code with certain errors from ever reaching the compiler?

Answering these questions would require a counter for each distinct error message printed. One option would be to have each error-reporting call site in the compiler also declare a counter passed to the error-reporting function. Another option would be to treat a call to the error-reporting function itself as a crash, incrementing a crash counter corresponding to the current call stack, perhaps truncated to just a few frames.

What is the relative distribution of `go` `vet`-reported errors printed during development?

The errors printed by go vet are its entire user experience. They have to be good. Just like with the compiler, we don’t know which ones are printed the most and might need more attention. If there are vet errors that are never or rarely printed, that would also be good to know. Perhaps the checks are broken, or perhaps they are no longer necessary and can be removed. As a concrete example, we noticed recently that the vet shift check has unfortunate false positives (#58030). Data about how often the check triggers would be a useful input to the decision about what to do about it.

Answering this question would use the same approach as in the compiler, either explicit counters or short-stack crash counters.

What fraction of Go installations invoke `go` `vet` explicitly, as opposed to the automatic run during `go` `test`?

I suspect that the majority of Go users never run go vet themselves, that they only run it implicitly as part of go test. Am I right? If so, we should probably spend more time improving the analyses that were deemed too noisy for go test, because those aren’t running and therefore aren’t helping find bugs.

Answering this question would require a counter for go vet invocations and a counter for go test-initiated vet invocations.

What is the relative distribution of specific analyses run using `go` `vet`?

When go vet is run explicitly, passing no command-line flags runs all analyses. Adding command-line flags runs only specific analyses. Do most runs use all analyses or only specific ones? If the latter, which ones? If we found that some analyses were being avoided, we might want to do further research to understand why. If we found that some analyses were being run very frequently, we might want to look into adding it to the go test set.

Answering this question would require a counter for go vet invocations and a counter for each analysis mode.

What is the relative usage of different versions of `gopls`?

Gopls is the only widely-used Go tool maintained by the Go team that ships separate from the Go distribution. As with Go releases, knowing which versions are still commonly used would help us understand which still need to be supported. Knowing how frequently versions are updated would help us tell when the upgrade process needs to be easier or more well documented.

Answering this question would require a counter incremented at gopls startup, since reports already separate counter sets by the version of the program being run.

What fraction of `gopls` installations connect to specific editors?

Gopls is an LSP server that can connect to any editor with LSP support. Different editors speak LSP differently, though, and editor-specific bugs are common. If we knew which editors are most commonly used, we could prioritize those in testing.

Answering this question would require a counter for gopls being invoked from each known editor (Emacs, Vim, VS Code, and so on), along with a counter for “Other”, since we cannot collect counters with arbitrary values. If “Other” became a significant percentage, a survey or user research interview would help us identify a new, more specific counter to add.

Which settings is `gopls` configured with?

Gopls has many settings, some of which are deprecated or obsolete. We don’t know which ones can be removed without disrupting users, or how many users would be disrupted by each (#52897, #54180, #55268, #57329). We guess as best we can, but real data would be better.

Answering this question would require a counter for each setting, incremented at gopls startup or after each setting change. Like with the LSP editors and the compiler flags, only a fixed collection of settings can be collected. For settings that take arbitrary user-defined values, there can only be a counter for the setting being used at all.

What fraction of `gopls` installations make use of a given code lens?

Gopls provides quite a few code lenses that users can invoke using their editor UI. Which ones actually get used? If one isn’t being used, we would want to use a survey or user research interview to understand why and either improve or remove it.

Answering this question would require a counter for each code lens setting being enabled, incremented at gopls startup or after each configuration change.

What fraction of `gopls` installations disable or enable a given analyzer?

Gopls provides quite a few analyzers as well. These run while a program is being edited and show warnings or other information about the code. If many users turn off an analyzer that is on by default, that’s a useful signal that the analyzer has too many false positives or is too noisy in some other way. And if many users enable an analyzer that is off by default, that’s a useful signal that we should consider turning it on by default instead.

Answering this question would require a counter for each analyzer being enabled, incremented at gopls startup or after each configuration change.

What fraction of `gopls` code completion suggestions are accepted?

One core feature of gopls is making code completion suggestions. Are they any good? We only know what we see from our own usage and from limited user research studies, which are time-consuming to collect, cannot be repeated frequently, and may not be representative of Go users overall. If instead we knew what fraction of suggestions were accepted, we could tell whether suggestions need more work and whether they are getting better or worse.

Answering this question would require a counter for the number of suggestions made as well as the number of times the first suggestion was accepted, the number of times the second suggestion was accepted, and so on.

What is the latency distribution for important `gopls` editor operations, like saving a file, suggesting a completion, or finding a definition?

We believe that performance greatly influences overall user happiness with gopls: when we spent a few months in 2022 working on performance improvements, user-reported happiness in VS Code Go surveys noticeably increased. We can run synthetic performance benchmarks, but there is no substitute for actual real-world performance measurements.

Answering this question would require a histogram for each key operation.

How often does `gopls` crash? Why?

Gopls is a long-running server that can, over time, find its way into a bad state and crash. We spent a few months in 2022 on overall gopls stability improvements, and we believe the crash rate is much lower now, but we have no real-world data to back that up.

Answering this question would require counters for each time gopls starts and each time it crashes. Each crash should also increment a crash counter to record the stack.

How often does `gopls` get manually restarted?

Sometimes gopls hasn’t crashed but also isn’t behaving as it should, so users manually restart it. It is difficult to know why gopls is being restarted each time, but at the least we can track how often that happens and then follow up in sureys or user research interviews to understand the root cause.

Answering this question would require counters for each time gopls starts and each time it is manually restarted.

Is the body of this `if` statement ever reached?

In general, when refactoring or cleaning up code it is common to see a workaround or special case and wonder if it ever happens anymore and how.

Answering this question would require a stack counter incremented at the start of the body of the if statement in question. The reports would then include not just the fact that the body is reached but also a few frames of context explaining the call stack to it to help understand how it is reached.

And so on ...

I could keep going, but I will stop here. It should be clear that knowing the answers to these questions really would help developers working on Go to make better, more informed decisions about feature work and identify performance bugs and other latent problems in Go itself. It should also be clear from the breadth of examples that there is no way to ask all these questions on a survey, at least not one that users will finish. Many of them, including all the histograms, are completely impractical as survey questions anyway.

I hope it is also clear that the basic primitive of counters for predefined events is powerful enough to answer all these questions, while at the same time not exposing any user data, path names, project names, identifiers, or anything of that sort.

Finally, I hope it is clear that none of this is terribly specific to Go. Any open source project with more than a few users has the problem of understanding how the software is used and how well it’s working.

For more background about telemetry and why it is important, see the introductory post. For details about the design, see the previous post.

The Design of Transparent Telemetry

2023-02-08T08:00:02-05:00

I believe open-source software projects need to find an open-source-friendly way to do telemetry. This post is part of a short series of posts describing transparent telemetry, one possible answer to that challenge. For more about the rationale and background, see the previous post. For additional use cases, see the next post.

Transparent telemetry is made up of five parts:

Counting: Go toolchain programs store counter values in per-week files maintained locally.
Configuration: There is a reviewed public process for defining a new graph or metric to track and publish on the Go web site. The exact counters that need to be collected, along with the sampling rate needed for high accuracy results, are derived from this configuration.
Reporting: Once a week, an automated reporting program randomly decides whether to fetch the current configuration and then whether to be one of the sampled systems that week. If so, it reports the counters listed in the configuration to a server run by the Go team at Google. In typical usage, we expect a particular Go installation to report each week with under 2% probability, meaning less than once per year on average. [Update, 2023-02-24: The design has been changed to be opt-in, which raises the expected reporting probabilities.]
Publishing: The server publishes each day’s reports in full (in a compressed form) as well as publishing the tabular and graphical summaries defined in the configuration.
Opt-out: The system is enabled by default, but opting out is as straightforward, simple, and complete as possible. [Update, 2023-02-24: The design has been changed to be opt-in.]

This post details each of these parts in turn. I wrote an implementation of local counter collection to convince myself it could be made cheap enough, but as of the publication of this post, no other part of the system exists today in any form. I hope that the system can be built for Go over the course of 2023, and I hope that other open-source projects will be interested to adopt this approach or inspired to explore others.

Counting

Go toolchain programs (go and the other programs that ship in the Go distribution, like go tool compile and go tool vet, along with other Go team-maintained programs like gopls and govulncheck) collect counter values in local files using a simple API:

package counter

func New(name string) *Counter
func (c *Counter) Inc()

func NewStack(name string, frames int) *Stack
func (s *Stack) Inc()

Basic named counters are created with counter.New, typically assigned to a global variable (this has no init-time overhead), and then incremented as the program runs by using the Inc method.

For example, suppose we want to monitor the typical build cache miss rate for a go build command. Each go command invocation can track the miss rate during its run and then increment one bucket of a histogram with exponentially-spaced buckets: 0%, <0.1%, <0.2%, <0.5%, <1%, <2%, <5%, <10%, <20%, <50%, and <100%. After a week, those 11 counters record the distribution of build cache miss rate experienced on that system.

Stack counters are similar, but the constructor also takes the maximum number of frames to record. Each frame is represented by an import path, function name, and line number relative to the start of the function, such as cmd/compile/internal/base.Errorf+10. The counter name is the concatenation of the the name passed to the constructor and the given number of frames. For example, the counter name for one increment of the result of NewStack("missing-std-import", 5) might be

missing-std-import
cmd/compile/internal/types2.(*Checker).importPackage+39
cmd/compile/internal/types2.(*Checker).collectObjects+54
cmd/compile/internal/types2.(*Checker).checkFiles+18
cmd/compile/internal/types2.(*Checker).Files+0
cmd/compile/internal/types2.(*Config).Check+2

A line number relative to the start of the function is fairly stable across unrelated edits in the source code, making it possible to identify the same stack trace even across different versions of a program.

One of the key properties of transparent telemetry is that uploaded reports only contain strings that are already known to the collection server. Using an import path instead of the full file path allows aggregation across different systems and more importantly avoids exposing details like the full path to a directory where the Go compiler source code was stored when it was built. Another important consideration is that function names in modified copies of Go tools might contain unexpected strings: we don’t want to know about a modified copy that adds types2.checkWithChatGPT to the call stack. This problem is handled by only saving stack traces from specific unmodified, released versions of tools. The version information and the presence of any modifications can be identified using the build information embedded in the binary. (In contrast, .NET reports full file system paths and then documents that it is the developer’s responsibility to “avoid inadvertent disclosure of information” by not building the software in “directories whose path names expose personal or sensitive information”. The burden of not exposing private data in a telemetry system should never be placed on users.)

The counter files are stored in the directory <user>/go/telemetry/local/, where <user> is the user configuration directory, as reported by os.UserConfigDir. Each file is named by the program’s name, version, build toolchain version, GOOS, and GOARCH, along with the date of the start of the week. For example:

/Users/rsc/Library/Application Support/go/telemetry/local/
    compile-go1.21.1-darwin-arm64-2023-01-04.v1.count
    gopls@v0.11.0-go1.21.1-linux-386-2023-01-04.v1.count
    ...

The version and build toolchain version are recorded only as devel for unversioned tools, such as when developing Go itself.

Aggregating counters by week has two important purposes. First, it should help reduce privacy concerns by making clear that there is no way to reconstruct any kind of fine-grained trace of user behavior. Second, reporting counters by week reduces statistical noise caused by persistent usage variations such as weekends. Every long-term monitoring dashboard I have ever seen begins by computing 7- or 28-day averages of the data to remove this high-frequency noise. Removing it client-side gives both more privacy and cleaner reports.

When Go telemetry first creates the local directory, it randomly selects the start of that system’s week. The system in our example has chosen weeks beginning on Wednesday. The random choice of week start spreads the server load over the week and also provides prompt reporting of new problems: if a new Go distribution is published on Tuesday, one seventh of the systems that install it immediately will include Tuesday’s operation in the Wednesday uploads.

These files use a custom binary format that starts with a simple key-value header repeating the information that went into the file name:

Week: 2023-01-04
Program: compile
GoVersion: go1.21.1
GOOS: darwin
GOARCH: arm64

After the header come the counters, in an on-disk hash table suitable for memory mapping into each running instance of the program. Those instances use lock-free atomic operations to increment counters and maintain the file, keeping the overhead associated with telemetry very low. The design also avoids any possibility of deadlock or unbounded latency when a counter is incremented, even if one instance of the program is hung or otherwise misbehaving. A tool, perhaps called go tool telemetry, will convert one of these binary files to JSON for processing by other interested programs.

Note that the raw data stored on disk is only names of counters and their associated 64-bit totals. There is no event log or any more detailed kind of trace. The decision to maintain the counters directly, instead of deriving them from a more detailed trace, is motivated mainly by concerns about disk space and update latency. However, never having any kind of event log or trace also reduces the privacy impact of the local collection.

A local web server (perhaps go tool telemetry -http) will display the local counters and be able to graph counter data over time for user inspection (at only 1-week granularity, of course).

Configuration

Data collection in transparent telemetry starts with the reason the data is being collected: a specific graph that is going to be computed, along with the specific margin of error desired for that graph. From that graphing configuration, the transparent telemetry server can compute the reporting configuration, declaring which counters to report at what sampling rate in order to produce that graph.

For example, a graphing configuration for the Go build cache miss rate graph we considered in the previous section might look like:

title: Go build cache miss rate
type: histogram
error: 1%
counter: go/buildcache/miss:{0,0.1,0.2,0.5,1,2,5,10,20,50,100}

For a margin of error of 1% at a 99% confidence level, we need about 16,000 samples. The server would keep track of an estimate of the number of reporting systems and adjust the sampling rate each week to produce the right number of samples. If there are one million reporting systems, then the sampling rate to get 16,000 samples is 1.6%, so the corresponding reporting configuration would sample each counter with that probability.

Changing what is collected can have privacy implications, so we have to ensure changes are properly reviewed. As an example of a privacy mistake, suppose a developer mistakenly decided it was important to understand which standard library packages are most imported and created a histogram of import paths using counter.New("import:"+path).Inc(). I don’t think that would be a useful histogram anyway, but the privacy mistake is that the histogram would include private user import paths as well as standard library paths. However, the impact of the mistake would be limited to local collection, because the graphing and reporting configurations would not mention counters like import:my.company/private/package, so they would never be reported.

Developers of the Go toolchain will probably want to add counters to the toolchain purely for local use, to understand whether they would be helpful to report. That decision should not be overburdened with process, because the stakes are relatively low. Probably our standard code review process suffices, paired with clear documentation about what kinds of counters are and are not appropriate to introduce.

Changes to the server’s graphing configuration merit more attention, since as we saw it is the graphing configuration that determines which counters are reported. It probably makes sense to require such changes to go through a review by a small group charged with ownership and maintenance of the configuration, either on the issue tracker or on the Gerrit server.

Finally, note the lack of any kind of wildcards in the graphing configuration. It is impossible to ask for all the counters beginning with import:, which means import:my.company/private/package will never be reported, because the graphing configuration will never list that counter explicitly by name. (Any attempt to do so would be caught by the public configuration review process.)

Reporting

When a counter file’s week is over, toolchain programs (even long-running ones) automatically start writing counters to the next week’s file. Remember that “week” refers to a 7-day period that starts on a weekday chosen randomly for each Go installation: on some machines weeks are Sunday to Saturday, others use Tuesday to Monday, and so on. At some point after the week ends, a reporting program (probably the go command, perhaps also gopls) will notice the completed week of counters and begin the reporting process.

The reporting program uses a reporting configuration to find out which counters should be reported. It would be served as a Go module (perhaps telemetry.go.dev/config). Visiting that same page in a browser would print a nice HTML page listing all the counters that have ever been collected, annotating each with the date ranges when it was collected and the justification for collection. In the event that some counter is deemed no longer necessary or somehow problematic to collect, it can be removed from the configuration, and programs will immediately stop reporting it. Similarly, if the system must be shut down for some reason, serving an empty configuration would stop all reporting.

The reporting configuration would be JSON corresponding to the Go type ReportConfig defined as:

type ReportConfig struct {
    GOOS      []string
    GOARCH    []string
    GoVersion []string
    Programs  []ProgramConfig
}

type ProgramConfig struct {
    Name     string
    Versions []string
    Counters []CounterConfig
    Stacks   []CounterConfig
}

type CounterConfig struct {
    Name string
    Rate float64
}

The ReportConfig lists the known GOOS, GOARCH, and Go versions that can be reported. This ensures that programs testing with an experimental, as-yet-unknown operating system, architecture, or Go version are not accidentally collected. Similarly, the ProgramConfig lists the programs that should be collected from and their specific versions, if they are separate from the main Go toolchain (like gopls and govulncheck). The CounterConfig lists the specific counters being collected and their individual sample rates.

The reporter starts by picking a random floating point number X between 0 and 1. If X ≥ 0.1, then the reporter stops without even downloading the configuration. For example, if the reporter picks X = 0.2, it stops immediately. This step imposes a hard limit of 10% sampling rate for any counter or stack, and it arranges that a particular Go installation won’t even download the collection configuration more than once every couple of months on average.

Assuming X < 0.1, the reporter downloads and reads the collection configuration. It then reads all the per-program counter files and filters them to include only the ones with matching GOOS, GOARCH, Go version, program name, and program version. It further filters the selected reports to drop any counters for which the configured rate is less than X. For example, if the reporter picks X = 0.05, it will report counters configured with rate 0.1 but not counters configured with rate 0.01. If a particular program has no sampled counters, that program is dropped from the report. If the report has no programs, no report is sent at all.

In a large deployment such as Go’s, a typical reporting rate will be under 0.02 (2%), with the effect that each system will average around one weekly report per year, or fewer. One nice property of transparent telemetry is that as more and more systems run with it enabled, each system reports less and less data.

[Update, 2023-02-24: The hard limit of 10% and the expected reporting rate of 2% were based on opt-out telemetry with millions of installations. The design has changed to be opt-in, which will raise those probabilities.]

When there is a report to send, the reporting program prepares JSON corresponding to the Go type Report defined as:

type Report struct {
    Config   string
    Week     string
    LastWeek string
    X        float64
    Programs []Program
}

type ProgramReport struct {
    Program   string
    Version   string
    GoVersion string
    GOOS      string
    GOARCH    string
    Counters  []Counter
    Stacks    []Counter
}

type Counter struct {
    Name  string
    Count int64
    Stack []string
}

The Report’s Config field lists the configuration version used for generating the report, so analysis can determine the sampling rates applied.

On a system that uses Go only intermittently, a reporting program might not run for a few days or more after the week ends. The Report’s Week field identifies the week this report covers, by giving its first day in yyyy-mm-dd format. If it has been more than seven days since the last use of Go, the now-weeks-old local report will not be uploaded. This lets the server “close the books” on a given week’s telemetry after seven days.

In any data collection system it is important to quantify how much data is being discarded. (This is why, for example, pprof attributes missed profile events to synthesized functions like _LostExternalCode.) In transparent telemetry, if a system is used one week but then not used at all the next week, the system will have no opportunity to (randomly decide to) report the first week’s data. The number of systems being used so intermittently is probably low enough not to worry about having a statistically significant effect on the results, but it would be good to measure that rather than guess. The LastWeek field reports the week prior to the one being reported when the reporting system last gathered any counters at all. On a frequently used system, LastWeek will always be seven days earlier than Week. After a long pause in Go usage, LastWeek will be two or more weeks earlier than Week, indicating that this system never even considered reporting counters from LastWeek. If a substantial number of reports have a mutiweek gap, we can conclude that the earlier week’s data may be less accurate than previously estimated. Again, this is generally unlikely, but perhaps it would happen after vacations such as end-of-year holidays. It would be good to have an explicit signal that those numbers are not as trustworthy rather than puzzle through why they look different. The LastWeek field also makes it possible to estimate the number of active users over longer time periods, such as 4 weeks or 52 weeks, which may be useful for understanding overall usage.

Note that the different programs’ counter sets are all uploaded together, so that for example if the go command is taking a surprisingly long time to run a build, the associated counters from the compile and link program are in the same record. Note also that there is no persistent identifier in the records that would allow linking one week’s upload with a different week’s upload.

The server would necessarily observe the source IP address in the TCP session uploading the report, but the server would not record that address with the data, a fact that can be confirmed by inspecting the reporting server source code (the server would be open source like the rest of Go) or by reference to a stated privacy policy like the one for the Go module mirror, depending on whether you lean more toward trusting software engineers or lawyers. A company could also run their own HTTP proxy to shield individual system’s IP addresses and arrange for employee systems to set GOTELEMETRY to the address of that proxy. It may also make sense to allow Go module proxies to proxy uploads, so that the existing GOPROXY setting also works for redirecting the upload and shielding the system’s IP address.

Recall from above that the local, binary counter files are stored in <user>/go/telemetry/local/. When a report is uploaded, the exact JSON that was uploaded is written to <user>/go/telemetry/uploaded/, named for the day of the upload (2006-01-02.json). The aim of both these directories (including their naming) is to make the system’s overall operation as transparent as possible. The expectation is that a typical report will be under 1,000 counters, requiring about 50 kB in JSON format. Assuming twice as many counters are counted locally than are uploaded, that’s 2,000 counters in binary format, which is another 100 kB. The storage cost of keeping the local forms indefinitely is then under 100 kB/week or 5 MB/year. An upload once or twice a year adds only another 100 kB/year. A command like go clean -telemetry would delete all of these.

The privacy feature of waiting at least a week before uploading anything at all (to give people plenty of time to opt out before any data is sent) means that ephemeral machines such as build containers will never be counted. The tradeoff of better privacy seems worth the loss of visiblity into these machines.

Publishing

Every day, the upload server takes the previous 24 hours’ worth of uploads and updates the published graphs defined in the graph configuration.

It also publishes the full, raw JSON for the previous 24 hours worth of uploads, in seven distinct data sets corresponding to the seven different possible weeks (starting Sunday, Monday, Tuesday, ...) that could have been reported that day. For example, the files published on 2023-01-18 would be:

week-2023-01-04-uploaded-2023-01-17.v1.reports
week-2023-01-05-uploaded-2023-01-17.v1.reports
week-2023-01-06-uploaded-2023-01-17.v1.reports
week-2023-01-07-uploaded-2023-01-17.v1.reports
week-2023-01-08-uploaded-2023-01-17.v1.reports
week-2023-01-09-uploaded-2023-01-17.v1.reports
week-2023-01-10-uploaded-2023-01-17.v1.reports

Thanks to sampling, the collected uploads will be fairly small and will not grow even as the number of active installations does. Estimating 50 kB per uploaded report and a target of about 16,000 reports per week, each week’s reports total only 800 MB (split across the seven different starting days in that week). Compression with Brotli should reduce the footprint by at least a factor of 10, making each week at most 80 MB, or at most 4 GB for an entire year’s worth of uploads.

Opt-Out

[Update, 2023-02-24: The design has been changed to be opt-in. This section is unmodified from the original for historical purposes.]

An explicit goal of this design is to build a system that is reasonable to have enabled by default, for two reasons. First, the vast majority of users do not change any default settings. In systems that have collection off by default, opt-in rates tend to be very low, skewing the results toward power users who understand the system well. Second, the existence of an opt-in checkbox is in my opinion too often used as justification for collecting far more data than is necessary. Aiming for an opt-out system with as few reasons as possible to opt out led to this minimal design instead. Also, because the design collects a fixed number of samples, more systems being opted in means collecting less from any given system, reducing the privacy impact to each individual system.

Enabling the system by default requires proper notice to users who are installing the system. As we did with the on-by-default module proxy and checksum database, notices would be posted in the release notes for the first Go distribution that enables telemetry as well as displayed next to the download links on go.dev and go.dev/dl.

Some users will want to opt out on general principle, no matter how minimal the system is, and that should be as easy as possible, something like:

go env -w GOTELEMETRY=off

Like all go env -w commands, this would configure a per-user setting that applies to all installed Go toolchains, present and future: a new Go toolchain installed tomorrow would respect the setting too.

In addition, some Linux distributions may want to prompt users during installation or disable telemetry unconditionally. We should make that easy to do too. Proposal #57179 introduced a go.env file in the root of the Go toolchain that configures per-toolchain settings. This will ship in Go 1.21. Linux distributions that want to disable telemetry could include a go.env file containing GOTELEMETRY=off.

Another dark pattern in opt-out systems is reporting information before the user has a chance to opt out. For example, I was once told about a popular developer tool that showed a telemetry checkbox, pre-checked, during the installation process, giving users the opportunity to uncheck the box. But at this point, a few screens into the installation, telemetry had already been sent, allowing the company behind the tool to track installation counts and opt-out rate by the fact that telemetry suddenly stopped, as well as tracking details like the IP and MAC addresses of systems that have opted out. In that system, to avoid sending any telemetry at all, you had to set an environment variable and then invoke the installer from the command line. I can’t find concrete evidence anywhere for this story, so I am not sure if the system in question still behaves this way or ever did. Either way, I strongly disagree with this kind of trick as violating the entire spirit of an opt-out decision.

Transparent telemetry waits at least a week after installation before sending any report or even fetching the collection configuration. This should give plenty of time to run go env -w to opt out.

Summary

Repeating the summary from the introductory post, transparent telemetry has the following key properties:

The decisions about what metrics to collect are made in an open, public process.
The collection configuration is automatically generated from the actively tracked metrics: no data is collected that isn’t needed for the metrics.
The collection configuration is served using a tamper-evident transparent log, making it very difficult to serve different collection configurations to different systems.
The collection configuration is a cacheable, proxied Go module, so any privacy-enhancing local Go proxy already in use for ordinary modules will automatically be used for collection configuration. To further ameliorate concerns about tracking systems by the downloading of the collection configuration, each installation only bothers downloading the configuration each week with probability 10%, so that each installation only asks for the configuration about five times per year. [Update, 2023-02-24: The design has changed to be opt-in, which requires raising these probabilities.]
Uploaded reports only include total event counts over a full week, not any kind of time-ordered event trace.
Uploaded reports do not include user IDs, machine IDs, or any other kind of ID.
Uploaded reports only contain strings that are already known to the collection server: counter names, program names, and version strings repeated from the collection configuration, along with the names of functions in specific, unmodified Go toolchain programs for stack traces. The only types of non-string data in the reports are event counts, dates, and line numbers.
IP addresses exposed by the HTTP session that uploads the report are not recorded with the reports.
Thanks to sampling, only a constant number of uploaded reports are needed to achieve a specific accuracy target, no matter how many installations exist. Specifically, only about 16,000 reports are needed for 1% accuracy at a 99% confidence level. This means that as new systems are added to the system, each system reports less often. With a conservative estimate of two million Go installations, about 16,000 reporting each week corresponds to an overall reporting rate of well under 2% per week, meaning each installation would upload a report on average less than once per year. [Update, 2023-02-24: The design has changed to be opt-in, which requires raising these probabilities.]
The aggregate computed metrics are made public in graphical and tabular form.
The full raw data as collected is made public, so that project maintainers have no proprietary advantage or insights in their role as the direct data collector.
The system is on by default, but opting out is easy, effective, and persistent. [Update, 2023-02-24: The design has been changed to be opt-in.]

Next Steps

For more background about telemetry and why it is important, see the introductory post. For more use cases, see the next post.

I am posting these to start a discussion about how the Go toolchain can adopt telemetry in some form to help the Go toolchain developers make better decisions about the development and maintenance of Go. I have written an implementation of local counter collection to convince myself it could be made cheap enough, but no other part of the system exists today in any form. I hope that the system can be built over the course of 2023.

Transparent Telemetry for Open-Source Projects

2023-02-08T08:00:01-05:00

How do software developers understand which parts of their software are being used and whether they are performing as expected? The modern answer is telemetry, which means software sending data to answer those questions back to a collection server. This post is about why I believe telemetry is important for open-source projects, and what it might look like to approach telemetry in an open-source-friendly way. That leads to a new design I call transparent telemetry. If you are impatient, skip to the summary at the end. Other posts in the series detail the design and present various uses.

Why Telemetry?

Without telemetry, developers rely on bug reports and surveys to find out when their software isn’t working or how it is being used. Both of these techniques are too limited in their effectiveness. Let’s look at each in turn.

Bug reports are not enough. Users only file bug reports when they think something is broken. If a function is not behaving as documented, that’s a clear bug to report. But if a program is misbehaving in a way that doesn’t affect correctness, users are much less likely to notice. Statistics gathered by transparent telemetry make it possible for developers to notice that something is going wrong even when users do not.

For example, during the Go 1.14 release process in early 2020 we made a change to the way macOS Go distributions are built, as part of keeping them acceptable to Apple’s signing tools. Unfortunately, the way we made the change also made all the pre-compiled .a files shipped in the distribution appear stale to builds. The effect was that the go command rebuilt and cached the standard library on first run, which meant that compiling any program using package net (which uses cgo) required Xcode to be installed. So Go 1.14 and later unintentionally required Xcode to compile even trivial demo Go programs like a basic HTTP server. This is not the way we want Go to work on macOS. On systems without Xcode, when go tried to invoke clang, macOS popped up a box explaining how to install it. Users simply accepted that this was necessary, perhaps even thinking go had displayed the popup. No one reported the bug over three years of Go releases. We didn’t notice and fix the problem until late 2022 while investigating something else. With telemetry for the miss rate in the cache of pre-compiled standard library packages, the impact would have been obvious: all Macs running Go 1.14 or later would have a pre-installed package miss rate of 100%. This bug wasn’t caught by our unit tests because it was caused by the distribution build machines having a modified environment different from actual user machines. The unit tests ran in the same modified environment as the build and worked fine. These kinds of unexpected differences between developer machines and user machines are inevitable at scale. Instrumenting the software on user machines is the most reliable way to understand how well it is working.

Surveys are not enough. Surveys help us understand what users want to do with Go, but they are only a small sample and have limited resolution. Asking about usage of infrequently-used features on a survey wastes time for a majority of respondents, and it requires large response counts to get an accurate measurement.

For example, we announced in the Go 1.13 release notes that future releases would drop support for Native Client (GOOS=nacl). Similarly, we announced in the Go 1.15 release notes that future releases would drop support for hardware floating point on 32-bit Intel CPUs without SSE2 instructions (GO386=387). Both of those removals went off okay, retroactively proving that our instincts about how few people would be affected were correct. On the other hand, we drafted an announcement for Go 1.18 removing -buildmode=shared, because it had essentially been broken since the introduction of modules, but when we issued Go 1.18 beta 1 we got feedback from at least a few people who were using it in some form. We still don’t know how many people are using it or whether it is worth the maintenance costs, so it lingers on. Another question is how long to keep supporting ARMv5 (GOARM=5), which doesn’t have modern atomic instructions. More recently, we announced that Go 1.20 will be the last release to support macOS High Sierra and were promptly asked to keep it around. Usage information would help us make more informed decisions. It’s important to note the limitations of this usage information: if telemetry is disabled on all the machines that use the feature in question, or if it is only used in machines that don’t stay up long enough to report anything, then we won’t observe the usage. Telemetry is never perfect, but it’s a useful input to the decision and much better than guessing. A survey is not any better and usually worse: there is a limit to how many questions we can reasonably ask in a survey, and asking a question where 99% of people answer “no I don’t use that” is a waste of most people’s time.

Why Telemetry For Open Source?

When you hear the word telemetry, if you’re like me, you may have a visceral negative reaction to a mental image of intrusive, detailed traces of your every keystroke and mouse click headed back to the developers of the software you’re using. And for good reason! That mental image sounds like it must be an exaggeration but turns out to be fairly accurate. (Citations: Kindle tracking individual page turns, VS Code telemetry logs, and .NET telemetry events.)

Open-source software projects have tended to avoid this kind of telemetry, for two reasons. The first is the significant privacy cost to users of collecting and storing detailed activity traces. The second is the fact that access to this data must be restricted, which would make the project less open than most strive to be. When the choice is between this kind of invasive tracking or doing nothing, doing nothing seems like an easy call. Still, doing nothing has real disadvantages. It means open-source developers like me tend not to understand as well how our software is used or how it performs. Then, because we lack that knowledge, we end up wasting time by maintaining features that aren’t used, hurting users by removing features that are still being used, and delivering a poorer user experience by failing to notice when our software is underperforming in real-world usage.

Some open-source projects have adopted traditional telemetry, with mixed success and varying levels of user pushback. For example: Audacity, GitLab, and Homebrew. Homebrew’s telemetry seems to be generally accepted by users, and VS Code’s detailed telemetry has not stopped it from being used by 74% of developers, as reported by the 2022 StackOverflow survey. It could even be that the benefits from telemetry are part of how VS Code’s developers have been able to build a tool that users like so much. Even so, the vast majority of projects, even large ones that would benefit, stay away from telemetry.

I believe that the choice between invasive tracking and doing nothing at all is a false dichotomy, and it’s harming open source. Not having basic information about how their software is used and how well it is performing puts open-source developers at a disadvantage compared to commercial software developers. Not having this information makes it more difficult to understand what’s important and what isn’t working, making prioritization that much harder. Not having clear prioritization in turn exacerbates the pre-existing problems with maintainer burnout.

Eric Raymond famously declared that “given enough eyeballs, all bugs are shallow,” which he explained as meaning that “[g]iven a large enough beta-tester and co-developer base, almost every problem will be characterized quickly and the fix obvious to someone.” Perhaps this was true in 1997 (perhaps not), but it’s certainly not true today, as the Go macOS cache bug shows. A quarter century later, software is much larger, and open-source software is used by far more people who didn’t develop it and aren’t familiar with how it should and should not behave. Eyeballs don’t scale.

I believe that open-source software projects need to explore new telemetry designs that help developers get the information they need to work efficiently and effectively, without collecting invasive traces of detailed user activity.

Transparent Telemetry

This series of blog posts presents one such design, which I call transparent telemetry, because it collects as little as possible (kilobytes per year from each installation) and then publishes every bit that it collects, for public inspection and analysis.

I’d like to explore using this system, or one like it, in the Go toolchain, which I hope will help Go project developers and users alike. To be clear, I am only suggesting that the instrumentation be added to the Go command-line tools written and distributed by the Go team, such as the go command, the Go compiler, gopls, and govulncheck. I am not suggesting that instrumentation be added by the Go compiler to all Go programs in the world: that’s clearly inappropriate. Also, throughout these posts, “developer” refers to the authors of a given piece of software, while “user” refers to the users of that software. From the point of view of the Go toolchain, “developer” means a Go toolchain developers like me, while “user” means one of the millions of Go programmers using that toolchain.

With transparent telemetry, as programs from the Go toolchain run, they would increment counters for various events of interest (for example: cache hit, use of a given feature, measured latency in a given range) in a per-week on-disk file. These files hold only counter values, not user data nor user identifiers. Some counter names include a short stack trace (function names and line offsets only, no argument data).

The Go team at Google would run a collection server. Each week, with 10% probability (averaging ~5 times per year) the user’s Go installation would download a “collection configuration” to find out which counter values are of interest to the server and at what sample rate. The collection configuration would be served in a Go module validated using the Go checksum database, for added confidence that all clients are being served the same configuration. Based on the sample rates, the Go installation might send a report containing the counter values of interest. Typical sample rates would be around 2% (averaging ~1 report per installation per year), but very rare events could be sampled at a higher rate, up to the 10% limit. As more systems take part in transparent telemetry, the overall sample rate on any given system will decrease, because only a fixed number of samples is necessary.

The report would contain no ID of any form – no user login, no machine ID, no MAC address, no IP address, no IP address prefix, no geolocation information, no randomly-generated pseudo-ID, no other kind of identifiers. The report would contain basic information about the toolchain, such as its version and what operating system and architecture it was built for. The report could also contain coarse-grained information about the version of the host operating system (for example, “Windows 8”) and other tools the Go toolchain uses, such as the local C compiler (“gcc 2.95”).

The server would collect each day’s uploaded reports, update telemetry graphs served publicly on go.dev, and post the full set of uploaded reports for public download, inspection, and analysis.

Although the report would not include any identifiers, the TCP connection uploading the report would expose the system’s public IP address to the server if a proxy is not being used. This IP address would not be associated with the uploaded reports in any way. Standard system maintenance, including DoS prevention, might require logs that include the IP address, but uploaded reports will be kept separate from those logs. The privacy policy would be similar to the one used by the Go module mirror and checksum database.

The Go home page and download page already include a notice about the default use of the Go module mirror and a link to more information. That notice and link would be updated to disclose on-by-default telemetry. To opt out, users would set GOTELEMETRY=off in their environment or run a simple command like go env -w GOTELEMETRY=off; The first telemetry report is not sent until at least one week after installation, giving ample time to opt out. Opting out stops all collection and reporting: no “opt out” event is sent. It is simply impossible to see systems that install Go and then opt out in the next seven days.

Summary

Transparent telemetry has the following key properties:

The decisions about what metrics to collect are made in an open, public process.
The collection configuration is automatically generated from the actively tracked metrics: no data is collected that isn’t needed for the metrics.
The collection configuration is served using a tamper-evident transparent log, making it very difficult to serve different collection configurations to different systems.
The collection configuration is a cacheable, proxied Go module, so any privacy-enhancing local Go proxy already in use for ordinary modules will automatically be used for collection configuration. To further ameliorate concerns about tracking systems by the downloading of the collection configuration, each installation only bothers downloading the configuration each week with probability 10%, so that each installation only asks for the configuration about five times per year. [Update, 2023-02-24: The design has changed to be opt-in, which requires raising these probabilities.]
Uploaded reports only include total event counts over a full week, not any kind of time-ordered event trace.
Uploaded reports do not include user IDs, machine IDs, or any other kind of ID.
Uploaded reports only contain strings that are already known to the collection server: counter names, program names, and version strings repeated from the collection configuration, along with the names of functions in specific, unmodified Go toolchain programs for stack traces. The only types of non-string data in the reports are event counts, dates, and line numbers.
IP addresses exposed by the HTTP session that uploads the report are not recorded with the reports.
Thanks to sampling, only a constant number of uploaded reports are needed to achieve a specific accuracy target, no matter how many installations exist. Specifically, only about 16,000 reports are needed for 1% accuracy at a 99% confidence level. This means that as new systems are added to the system, each system reports less often. With a conservative estimate of two million Go installations, about 16,000 reporting each week corresponds to an overall reporting rate of well under 2% per week, meaning each installation would upload a report on average less than once per year. [Update, 2023-02-24: The design has changed to be opt-in, which requires raising these probabilities.]
The aggregate computed metrics are made public in graphical and tabular form.
The full raw data as collected is made public, so that project maintainers have no proprietary advantage or insights in their role as the direct data collector.
The system is on by default, but opting out is easy, effective, and persistent. [Update, 2023-02-24: The design has been changed to be opt-in.]

Next Steps

For more detail about the design, see the next post. For more use cases, see the post after that.

Although these posts use Go as the example system using transparent telemetry, I hope that the ideas apply and can be adopted by other open-source projects too, in their own, separate collection systems. For example, even though VS Code collects high-resolution event traces (sometimes tens or hundreds of events per minute), a close reading of those traces shows hardly anything is new in each event. That is, VS Code suffers the reputational hit of collecting lots of data but appears to gather relatively little actual information. Perhaps using transparent telemetry in VS Code or a similar editor could offer the editor’s developers roughly equivalent insights and development velocity at a much lower privacy cost to users.

Transparent Telemetry

2023-02-08T08:00:00-05:00

These are the posts in the February 2023 “Transparent Telemetry” series:

“Transparent Telemetry for Open-Source Projects” [PDF].
“The Design of Transparent Telemetry” [PDF].
“Use Cases for Transparent Telemetry” [PDF].

A (now closed) GitHub discussion about adding transparent telemetry to Go is at https://go.dev/s/telemetry-discussion.

There is one followup post:

“Opting In to Transparent Telemetry” [PDF].

The Magic of Sampling, and its Limitations

2023-02-04T12:00:00-05:00

Suppose I have a large number of M&Ms and want to estimate what fraction of them have Peter’s face on them. As one does.

If I am too lazy to count them all, I can estimate the true fraction using sampling: pick N at random, count how many P have Peter’s face, and then estimate the fraction to be P/N.

I can write a Go program to pick 10 of the 37 M&Ms for me: 27 30 1 13 36 5 33 7 10 19. (Yes, I am too lazy to count them, but I was not too lazy to number the M&Ms in order to use the Go program.)

Based on this estimate, we can estimate that 3/10 = 30% of my M&Ms have Peter’s face. We can do it a few more times:

And we get a few new estimates: 30%, 40%, 20%. The actual fraction turns out to be 9/37 = 24.3%. These estimates are perhaps not that impressive, but we are only using 10 samples. With not too many more samples, we can get far more accurate estimates, even for much larger data sets. Suppose we had many more M&Ms, again 24.3% Peter faces, and we sample 100 of them, or 1,000, or 10,000. Since we’re lazy, let’s write a program to simulate the process.

$ go run sample.go
   10: 40.0% 20.0% 30.0%  0.0% 10.0% 30.0% 10.0% 20.0% 20.0%  0.0%
  100: 25.0% 26.0% 21.0% 26.0% 15.0% 25.0% 30.0% 30.0% 29.0% 20.0%
 1000: 24.7% 23.8% 21.0% 25.4% 25.1% 24.2% 25.7% 22.9% 24.0% 23.8%
10000: 23.4% 24.6% 24.3% 24.3% 24.7% 24.6% 24.6% 24.7% 24.1% 25.0%
$

Accuracy improves fairly quickly:

With 10 samples, our estimates are accurate to within about 15%.
With 100 samples, our estimates are accurate to within about 5%.
With 1,000 samples, our estimates are accurate to within about 3%.
With 10,000 samples, our estimates are accurate to within about 1%.

Because we are estimating only the percentage of Peter faces, not the total number, the accuracy (also measured in percentages) does not depend on the total number of M&Ms, only on the number of samples. So 10,000 samples is enough to get roughly 1% accuracy whether we have 100,000 M&Ms, 1 million M&Ms, or even 100 billion M&Ms! In the last scenario, we have 1% accuracy despite only sampling 0.00001% of the M&Ms.

The magic of sampling is that we can derive accurate estimates about a very large population using a relatively small number of samples.

Sampling turns many one-off estimations into jobs that are feasible to do by hand. For example, suppose we are considering revising an error-prone API and want to estimate how often that API is used incorrectly. If we have a way to randomly sample uses of the API (maybe grep -Rn pkg.Func . | shuffle -m 100), then manually checking 100 of them will give us an estimate that’s accurate to within 5% or so. And checking 1,000 of them, which may not take more than an hour or so if they’re easy to eyeball, improves the accuracy to 1.5% or so. Real data to decide an important question is usually well worth a small amount of manual effort.

For the kinds of decisions I look at related to Go, this approach comes up all the time: What fraction of for loops in real code have a loop scoping bug? What fraction of warnings by a new go vet check are false positives? What fraction of modules have no dependencies? These are drawn from my experience, and so they may seem specific to Go or to language development, but once you realize that sampling makes accurate estimates so easy to come by, all kind of uses present themselves. Any time you have a large data set,

select * from data order by random() limit 1000;

is a very effective way to get a data set you can analyze by hand and still derive many useful conclusions from.

Accuracy

Let’s work out what accuracy we should expect from these estimates. The brute force approach would be to run many samples of a given size and calculate the accuracy for each. This program runs 1,000 trials of 100 samples each, calculating the observed error for each estimate and then printing them all in sorted order. If we plot those points one after the other along the x axis, we get a picture like this:

The data viewer I’m using in this screenshot has scaled the x-axis labels by a factor of 1,000 (“x in thousands”). Eyeballing the scatterplot, we can see that half the time the error is under 3%, and 80% of the time the error is under 5½%.

We might wonder at this point whether the error depends on the actual answer (24.3% in our programs so far). It does: the error will be lower when the population is lopsided. Obviously, if the M&Ms are 0% or 100% Peter faces, our estimates will have no error at all. In a slightly less degenerate case, if the M&Ms are 1% or 99% Peter faces, the most likely estimate from just a few samples is 0% or 100%, which has only 1% error. It turns out that, in general, the error is maximized when the actual fraction is 50%, so we’ll use that for the rest of the analysis.

With an actual fraction of 50%, 1,000 sorted errors from estimating by sampling 100 values look like:

The errors are a bit larger. Now the half the time the error is 4% and 80% of the time the error is 6%. Zooming in on the tail end of the plot produces:

We can see that 90% of the trials have error 8% or less, 95% of the trials have error 10% or less, and 99% of the trials have error 12% or less. The statistical way to phrase those statements is that “a sample of size N = 100 produces a margin of error of 8% with 90% confidence, 10% with 95% confidence, and 12% with 99% confidence.”

Instead of eyeballing the graphs, we can update the program to compute these numbers directly.

$ go run sample.go
N =    10: 90%: 30.00% 95%: 30.00% 99%: 40.00%
N =   100: 90%:  9.00% 95%: 11.00% 99%: 13.00%
N =  1000: 90%:  2.70% 95%:  3.20% 99%:  4.30%
N = 10000: 90%:  0.82% 95%:  0.98% 99%:  1.24%
$

There is something meta about using sampling (of trials) to estimate the errors introduced by sampling of an actual distribution. What about the error being introduced by sampling the errors? We could instead write a program to count all possible outcomes and calculate the exact error distribution, but counting won’t work for larger sample sizes. Luckily, others have done the math for us and even implemented the relevant functions in Go’s standard math package. The margin of error for a given confidence level and sample size is:

func moe(confidence float64, N int) float64 {
    return math.Erfinv(confidence) / math.Sqrt(2 * float64(N))
}

That lets us compute the table more directly.

$ go run sample.go
N =     10: 90%: 26.01% 95%: 30.99% 99%: 40.73%
N =     20: 90%: 18.39% 95%: 21.91% 99%: 28.80%
N =     50: 90%: 11.63% 95%: 13.86% 99%: 18.21%
N =    100: 90%:  8.22% 95%:  9.80% 99%: 12.88%
N =    200: 90%:  5.82% 95%:  6.93% 99%:  9.11%
N =    500: 90%:  3.68% 95%:  4.38% 99%:  5.76%
N =   1000: 90%:  2.60% 95%:  3.10% 99%:  4.07%
N =   2000: 90%:  1.84% 95%:  2.19% 99%:  2.88%
N =   5000: 90%:  1.16% 95%:  1.39% 99%:  1.82%
N =  10000: 90%:  0.82% 95%:  0.98% 99%:  1.29%
N =  20000: 90%:  0.58% 95%:  0.69% 99%:  0.91%
N =  50000: 90%:  0.37% 95%:  0.44% 99%:  0.58%
N = 100000: 90%:  0.26% 95%:  0.31% 99%:  0.41%
$

We can also reverse the equation to compute the necessary sample size from a given confidence level and margin of error:

func N(confidence, moe float64) int {
    return int(math.Ceil(0.5 * math.Pow(math.Erfinv(confidence)/moe, 2)))
}

That lets us compute this table.

$ go run sample.go
moe = 5%:  90%:   271  95%:   385  99%:   664
moe = 2%:  90%:  1691  95%:  2401  99%:  4147
moe = 1%:  90%:  6764  95%:  9604  99%: 16588
$

Limitations

To accurately estimate the fraction of items with a given property, like M&Ms with Peter faces, each item must have the same chance of being selected, as each M&M did. Suppose instead that we had ten bags of M&Ms: nine one-pound bags with 500 M&Ms each, and a small bag containing the 37 M&Ms we used before. If we want to estimate the fraction of M&Ms with Peter faces, it would not work to sample by first picking a bag at random and then picking an M&M at random from the bag. The chance of picking any specific M&M from a one-pound bag would be 1/10 × 1/500 = 1/5,000, while the chance of picking any specific M&M from the small bag would be 1/10 × 1/37 = 1/370. We would end up with an estimate of around 9/370 = 2.4% Peter faces, even though the actual answer is 9/(9×500+37) = 0.2% Peter faces.

The problem here is not the kind of random sampling error that we computed in the previous section. Instead it is a systematic error caused by a sampling mechanism that does not align with the statistic being estimated. We could recover an accurate estimate by weighting an M&M found in the small bag as only w = 37/500 of an M&M in both the numerator and denominator of any estimate. For example, if we picked 100 M&Ms with replacement from each bag and found 24 Peter faces in the small bag, then instead of 24/1000 = 2.4% we would compute 24w/(900+100w) = 0.2%.

As a less contrived example, Go’s memory profiler aims to sample approximately one allocation per half-megabyte allocated and then derive statistics about where programs allocate memory. Roughly speaking, to do this the profiler maintains a sampling trigger, initialized to a random number between 0 and one million. Each time a new object is allocated, the profiler decrements the trigger by the size of the object. When an allocation decrements the trigger below zero, the profiler samples that allocation and then resets the trigger to a new random number between 0 and one million.

This byte-based sampling means that to estimate the fraction of bytes allocated in a given function, the profiler can divide the total sampled bytes allocated in that function divided by the total sampled bytes allocated in the entire program. Using the same approach to estimate the fraction of objects allocated in a given function would be inaccurate: it would overcount large objects and undercount small ones, because large objects are more likely to be sampled. In order to recover accurate statistics about allocation counts, the profiler applies a size-based weighting function during the calcuation, just as in the M&M example. (This is the reverse of the situation with the M&Ms: we are randomly sampling individual bytes of allocated memory but now want statistics about their “bags”.)

It is not always possible to undo skewed sampling, and the skew makes margin of error calculation more difficult too. It is almost always better to make sure that the sampling is aligned with the statistic you want to compute.

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.

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