DHO is Mostly Confused

Wait-free Monitors for Concurrent Batching Workloads

Sun, 22 Apr 2018 00:40:00 +0000

Monitors are hard to use. Per Wikipedia’s entry on the topic, “a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.” The use case for such a construct is often to signal other threads that new work may be completed. Unfortunately, they’re really easy to use incorrectly, largely because many APIs for them are terrible.

In POSIX, monitors are provided through the API for condition variables. A new condition variable is created with pthread_cond_init(3); conditions are waited on and signalled using pthread_cond_wait(3) / pthread_cond_timedwait(3) and pthread_cond_signal(3) / pthread_cond_broadcast(3), respectively. To use the pthread_cond_wait(3) interface, you also need a mutex (because what you really have is a monitor); this mutex must be held before calling pthread_cond_wait(3), which will unlock the mutex before waiting on the condition, and return with the mutex still held. If this doesn’t sound subtle enough, consider the really crappy bit: the pthread_cond_signal(3) API does not accept a mutex as an argument at all! What you get from this is a ton of confusion about lost signals when people call pthread_cond_signal(3) without holding the mutex around signalling the condition.

And what happens in this scenario? You lose messages: notifications on a condition are not persistent. This API assumes that the only time the mutex will be unlocked is when a thread is waiting on a condition, and that signals will only occur with that mutex held. The problem is that, although the API had an opportunity to enforce this, it did not do so.

Apologists for the API say that one should “just know” how to use it correctly: these requirements are common knowledge. But misuse appears even in popular software, written by experienced individuals. One such example can be found in the source code of the widely popular Varnish Cache: the condvar is waited on with the lock held, but notifications are sent without the lock held. In fact, even though the condvar is waited on with the lock held, that lock is also released for portions of the loop that waits on the condition, so it’s still possible for the mutex to be acquired when the condition isn’t being waited upon. And it’s done this way because that mutex is conflated between the condition and shared mutable state in the structure it lives in. This misuse of condvars has existed in Varnish for over a decade.

Let’s take a step back and consider a couple use-cases for monitors.

First, let’s consider a log producer where many worker threads are producing log messages, and a consumer thread is persisting those to some kind of storage in batches. When no work is being done, we don’t want the consumer thread to spin waiting for logs to write. So our producers acquire a lock and signal a condition that the consumer waits on. This is problematic in high-volume services, because there’s significant contention on the monitor’s mutex. Additionally, if we have misused the API, it’s possible that a low-volume service with a burst of traffic will have logs delayed until the next log item occurs – which may be a while, since the service doesn’t have much volume.

Consider a sharded worker pool where one or more producers may generate work items, and a pool of workers must each do something different with these work items. In this scenario, every worker thread must see every message. You might be tempted to use pthread_cond_broadcast(3), but this turns out to be an anti-pattern. First of all, each waiter on the condvar must have acquired the mutex to return from pthread_cond_wait(3), so this means that your worker jobs actually execute serially. And if you’ve decided to solve this by unlocking the mutex while you perform your work, another producer may decide to broadcast while no workers are waiting. In reality, you have two options if you want to maintain correctness while also parallelizing your work: either you use N condition variables and N mutexes to signal N workers, or you need to wait on a semaphore (that is also protected by the monitor’s lock!) to ensure all your workers are waiting before you broadcast. Neither of these solutions are particularly elegant.

My final gripe with monitors is that they require lock-based synchronization. Lock-based synchronization is nearly the canonical way to protect shared mutable state from concurrent access, but this approach has several drawbacks.

Locks are not composable. When we talk about composability with regard to an API, we really mean a couple of things. First, a composable interface is self-contained: it does not have dependencies on external state for its correctness. Mutexes are not self-contained: their correct use depends on consuming the mutex API at every appropriate place in code, and the API is also sensitive to ordering. Ordering issues don’t sound bad when all you have to consider are lock and unlock operations, but sometimes mutable state must be protected by multiple mutexes. At this point, the ordering of which mutex is locked first is important, as is the ordering of unlock operations – again, at every point that these mutexes have to operate. Apologists will say that it’s easier to use locks than anything else; I have yet to see or work on a large, multi-threaded codebase that hasn’t run into issues directly related to lack of composability.

Another issue with locks is effectively how they work. If you ask folks what a lock does, they’ll typically say something like, “A lock protects concurrent access to shared memory within its critical section.” But this isn’t really what locks do. Locks are a construct that serialize execution through their critical section such that only a single process may execute that code at a time. This has the side-effect of achieving the goal of protecting concurrent access to shared mutable state, but unless you consider how it achieves that, you’re missing numerous downsides. While a lock is held, no other concurrent task may acquire the lock. This means that resources dedicated to running code are effectively stalled waiting for the critical section to finish. Maybe this doesn’t seem so bad; critical sections are typically pretty short. The problem is that modern schedulers only allow tasks to run for so long. Once you’ve used your timeshare, it’s going to want to run something else. If you’ve lost your timeshare in the middle of a critical section, literally every other process waiting on that lock is also not runnable, and your system makes no progress.

These issues are fundamental to the monitor API provided by pthreads. (Other monitor implementations may address the composability problem a bit better, but the issue with progress guarantees remains by virtue of mutual exclusion.) The pthread monitor interface introduces additional dependencies between a mutex and data, imposes additional requirements on both lock ordering and critical section size, and does nothing to solve the problem of system progress (which is ostensibly one reason you’d want to use threads at all).

Can we do better? At my previous job, I had a few situations similar to the log producer situation I mentioned above: multiple threads producing work items, and a single thread acting upon that work in batches. I wanted to use some lock-free datastructures from Concurrency Kit to create a queue of work that the consumer could easily batch, but there were some problems. With monitors, I’d be blocking work producers while the batch work was being completed, and in some cases that could have taken a non-trivial amount of time. In other cases, the consumer was able to operate quickly, but the production was high-volume, and I didn’t want to have producers blocking each other in their fast path. So I made a wait-free monitor for MPSC workloads.

I had wanted to write about this monitor while I worked there, but never got around to it. Now that I don’t work there anymore, I don’t have the code. And I didn’t remember what clever tricks I had used. So I decided to reïnvent it. My new version is portable to any POSIX system with support for Concurrency Kit’s atomic primitives; I seem to recall that what I’d done in the original code was Linux-specific. I may implement system-specific versions later; POSIX’s lack of an interface like eventfd(2) in Linux, and its lack of ability to report time slept in poll(2) on EINTR make the POSIX implementation a bit more heavyweight than it really needs to be. The remainder of this article will be a discussion of my new implementation.

The notification system can exist in one of three states.

enum monitor_state {
    STATE_WORKING,
    STATE_PENDING,
    STATE_BLOCKED,
};

STATE_WORKING is the initial state of the system, and is the state of the monitor when it is created. This state indicates that no waiters are currently listening to the monitor. The second state of the monitor is STATE_PENDING, which indicates that work is pending. The final state is STATE_BLOCKED, which indicates that the consumer wanted to do some work, but none was available.

The structure itself is relatively simple: it contains some file descriptors for a pipe (to block when no work is pending), the state of the monitor, and an unfortunate flag as to whether the pipe needs draining (this is a side-effect of POSIX lacking anything eventfd(2)-like). It also contains a generation counter that is used to avoid having multiple producers write to the pipe to unblock a consumer. This turns out to be rather important, for reasons discussed below.

struct monitor {
    union {
        struct {
            int r;
            int w;
        } pipe;
        int fds[2];
    };
    uint8_t state;
    uint8_t drain;
    uint64_t gen;
};

Creating a monitor is as you would expect:

struct monitor *
monitor_create(void)
{
    struct monitor *m = malloc(sizeof *m);

    if (m == NULL) {
        return NULL;
    }

    m->state = STATE_WORKING;
    if (pipe(m->fds) == -1) {
        perror("pipe");
        free(m);
        return NULL;
    }

    return m;
}

Destroying a monitor is a bit of a hassle because I wanted to actually handle errors with close(2). I had hoped this would make things idempotent such that you could retry destroying the thing when close(2) failed, but I’m not sure what the caller would do here anyway. I might just ignore these errors anyway; I’m not sure whether it’s really feasible to get EIO, and I’m not sure I care about any realistic ways to get EBADF.

bool
monitor_destroy(struct monitor *m)
{
    bool fail = false;

    int r;
    if (m->pipe.r != -1) {
        do {
            r = close(m->pipe.r);
        } while (r == -1 && errno == EINTR);

        if (r == -1) {
            return false;
        }
    }

    m->pipe.r = -1;

    if (m->pipe.w != -1) {
        do {
            r = close(m->pipe.w);
        } while (r == -1 && errno == EINTR);

        if (r == -1) {
            return false;
        }
    }

    m->pipe.w = -1;

    free(m);
    return true;
}

The actual cool stuff happens when we start thinking about how a waiter should behave when there’s no mutex involved. First, some function boilerplate:

bool
monitor_wait(struct monitor *n, int timeout_ms)
{
    enum monitor_state cur;
    bool rv = true;

    assert(n != NULL);

When we enter this function, the first question we’re trying to answer is whether any work was produced while the worker wasn’t listening. Since we start out in STATE_WORKING, this means that if we enter the function in that state, no work is pending for us to do, and so we should block. Alternatively, if we enter in STATE_PENDING, that means work does exist, and we shouldn’t bother blocking. If we guarantee that this function is the only function that can move the state to STATE_BLOCKED and that it always exits in STATE_WORKING, we can achieve this by doing a simple atomic compare-and-swap to move our state from STATE_WORKING to STATE_BLOCKED. If the CAS operation fails, we know that work is pending.

    if (!ck_pr_cas_8(&m->state, STATE_WORKING, STATE_BLOCKED)) {
        ck_pr_store_8(&m->state, STATE_WORKING);
        ck_pr_fence_store();
        goto drain;
    }

Alternatively, when the CAS operation succeeds, that means no work was available for us to complete. In this case, we need to wait for a notification; we’ll receive this over the read side of our pipe(2). Because we may not want to wait forever, we allow the user to specify a timeout that we pass to poll(2).

    struct pollfd pfd[1] = {{
        .fd = m->pipe.r,
        .events = POLLIN|POLLPRI,
    }};

    errno = 0;
    int p = poll(pfd, 1, timeout);
    if (p == -1 && errno == EINTR) {
        errno = EAGAIN;
        rv = false;
        goto drain;
    } else if (p == -1) {
        perror("poll");
        rv = false;
        goto drain;
    } else if (p == 0 || (pfd[0].revents & (POLLHUP|POLLERR)) != 0) {
        rv = false;
        goto drain;
    }

You’ve noticed that we’re doing goto drain; instead of ever returning anything so far. Some errors returned by syscalls we call can’t easily be dealt with inside this code, so it’s possible that we exit without any work to do anyway. However, this does mean that it’s possible that someone had to write to the pipe to wake us, and there’s data stuck there. We detect this condition and try to drain the pipe when it has been written to, even when we didn’t need to block for work. This does mean that there are cases where we might do syscalls when we didn’t need to, but this is only really likely to occur when there’s a timeout. If poll(2) is told to block forever, this is only likely to happen on EINTR, or for (probably catastrophic) errors. If everything goes well here, we clear our draining flag, which will only be set again if we block.

drain:
    if (ck_pr_load_8(&m->drain) == 1) {
        ssize_t r; 
        uint8_t buf;
        do {
            p = poll(pfd, 1, 0);
            if (p == 0) {
                break;
            } else if (p == -1 && errno == EINTR) {
                continue;
            } else if (p == -1) {
                perror("drain poll");
                rv = false;
                goto ret;
            } else if ((pfd[0].revents & (POLLHUP|POLLERR)) != 0) {
                rv = false;
                goto ret;
            }

            do {
                r = read(m->pipe.r, &buf, sizeof buf)
            } while (r == -1 && errno == EINTR);

            if (r == -1) {
                perror("read");
                goto ret;
            }
        } while (p == 1);
    }

    ck_pr_store_8(&m->drain, 0);

Whenever we leave this function, we have to leave in STATE_WORKING. However, we do return to the caller whether we left because work was available (in which case rv is true). At some point, I’d like to add an error API so the caller can figure out exactly what failed when this function returns false – so that’ll probably happen before this makes it to GitHub. In any case, transitioning to STATE_WORKING whenever we return is really the big trick to making this wait-free.

ret:
    ck_pr_store_8(&m->state, STATE_WORKING);
    ck_pr_fence_store();

    return rv;
}

Waking up a waiter is pretty simple. First, our function prologue…

bool
monitor_wake(struct monitor *m)
{
    enum monitor_state cur;

    assert(m != NULL);

Whenever we enter this function, it is always OK to set the state to STATE_PENDING. We set this state using an atomic fetch-and-set operation, which allows us to move the state forward while also knowing what the previous state was. If the consumer is working, the state will either have already been set to STATE_PENDING by another producer, or it will still be in STATE_WORKING. In either case, we can be assured that when the consumer is ready, it will notice that we’ve produced work.

    cur = ck_pr_fas_8(&m->state, STATE_PENDING);
    if (cur == STATE_PENDING || cur == STATE_WORKING) {
        ck_pr_fence_store();
        return true;
    }

When the consumer is blocked, however, the state we read will be STATE_BLOCKED, and we will have set that to STATE_PENDING. This turns out to be just fine. If the consumer is blocked indefinitely, it doesn’t care about what the value is until its woken up again via its pipe. If it’s blocked on a timeout, one of a few benign scenarios can happen:

The timeout occurs, and the consumer re-enters without any new work having been produced. The state will remain STATE_WORKING, and the consumer will block again.
The timeout occurs, and a producer sets the state to STATE_PENDING above after the consumer sets the state to STATE_WORKING. The consumer re-enters and notices the new work. Nothing is written to the pipe, and nothing is read from the pipe.
The timeout occurs, and several producers set the state to STATE_PENDING above before the consumer sets the state to STATE_WORKING. The producers race on updating the generation count below; the winner will write to the pipe. The consumer sets the state to STATE_WORKING and returns. No new work is produced. When it re-enters, it will set its state to STATE_BLOCKING and immediately read the value written by the producer, picking up that work.
The same as above, but new work is produced before the consumer re-enters. The consumer enters and sees the state as STATE_PENDING. It also notices that the drain flag is set, and drains the pipe. It will have picked up the work that was produced by the subsequent producers as well as the one that wrote to the pipe. Even if there is a race on the drain flag being set, the consumer will eventually notice the drain and clean it up.

None of these cases are terrible: in all cases, the consumer is eventually notified of the work. When an error occurs in a syscall, the producer is free to try again.

    uint64_t gen = ck_pr_load_64(&m->gen);
    if (!ck_pr_cas_8(&m->gen, gen, gen + 1)) {
        ck_pr_fence_store();
        return true;
    }

    ssize_t r;
    do {
        uint8_t buf = 0;
        r = write(m->pipe.w, &buf, sizeof buf);
    } while (r == -1 && errno == EINTR);

    if (r == -1) {
        return false;
    }

    ck_pr_store_8(&m->drain, 1);
    ck_pr_fence_store();

    return true;
}

The system described above is wait-free when work is available, which is really the only situation in which non-blocking behavior is helpful for a monitor, since the goal is to block when no work can be done. This is ideal for concurrent batching workloads of nearly any volume. The composability of the interface means that, even for low volume systems, there’s no chance that forgetting about implementation subtleties will result in missed notifications. And the wait-free nature means that with high-volume workloads, your producer’s fast-path only takes the hit of a single atomic operation on average, and you will almost never incur the penalty of a syscall.

This is a stepping stone for additional work. The system presented here is really only appropriate for single-consumer workloads. In particular, multiple consumers sharing the same monitor would notice the monitor in STATE_BLOCKED upon entry to the monitor_wait function. This would cause them to erroneously think work was available, and result in spinning. Before I put this code on Github, I’d really like to solve the multiple-consumer problem. In particular, I’d like to have interfaces for signalling any consumer, signalling a specific consumer, and broadcasting to all consumers. I believe that this is all possible to do wait-free, assuming that the multiple-consumer versions simply slap an interface around managing N different monitors.

As a final note, I haven’t tested this code yet at all; it’s entirely possible that it’s broken. I’m not writing any C in my new job, which is a bit of a bummer. This also means that I don’t really have any use-cases for this code at the moment, making it a bit more difficult to test. I’ll of course spend a bit more time on this before publishing anything to Github.

A Malloc Idiom in Go

Thu, 22 Feb 2018 19:45:00 +0000

I’m finally writing Go. Although I was very active in contributing to the project for the first two-and-a-bit years, I’ve been pretty absent since 2012. Initially, I contributed because I am a fan of Plan 9 from Bell Labs and of FreeBSD. I loved the idea of having a usable, CSP-inspired language, but the initial release of Go only ran on Linux and OS X. I only had a FreeBSD system at the time, so I ported the compiler toolchain, runtime, and standard library to FreeBSD (with a good bit of education on debugging from Russ Cox).

However, most of my work has been on low-latency systems software – mostly written in C – and FreeBSD has not been supported by any of my employers since 2007. Since I wasn’t really getting a chance to write new software in Go, and I eventually was no longer interested in the overhead of maintaining knowledge of an OS I was only using for fun, my use of and contributions to Go fell by the wayside.

Now that I work at Google, I’ve finally had some opportunities to write code in Go. While I still enjoy the language, there are a few experience report-style things that ended up keeping me from using the language for the last 5-6 years, and things I currently find a little cumbersome. At the suggestion of some colleagues, I thought I’d document at least one of them.

One thing I miss is something like C’s malloc idiom. In C, allocated memory generally comes from calls to malloc-family functions, which give you at least enough memory to fit at least one of the thing you want, or none at all. The idiom for doing this looks like:

T *p = malloc(sizeof *p);

Notice how the type of p (T *) only appears once. This line of code exploits how sizeof behaves when its operand appears to dereference a pointer – which isn’t what happens, because the result of sizeof must Kate Flavel reminds me that this is not true for VLA types, which are so useless, I always forget. Such a type has its expression evaluated. always be discernable at compile-time. What the language defines instead for this syntax is that sizeof yields the size of the pointed-to object; it doesn’t turn into some runtime thing. The nice thing about the C idiom is that if I change the type represented by T, I only change the type in the declaration or definition. No changes need to be made in the site(s) the pointer object is assigned to the result of the allocation. While the example above is trivial, consider a more complicated case where a structure member points to some type:

struct set {
    size_t cap;
    size_t nmemb;
    int members[];
}

struct set *
set_create(size_t sz)
{
    struct set *n = malloc(sizeof *n + (sz * sizeof *n->members));
    if (n == NULL) {
        return NULL;
    }

    n->cap = sz;
    n->nmemb = 0;

    return n;
}

If, later, we want to change struct set to support members with other than int, we might change members to a union, and add some enum specifying the fields we wanted to add. And we can do this without changing any of our code in set_create.

This has bitten me in Go literally every time I’ve created some struct type that embeds a thing that must be allocated, like a slice or a map. In Go, we are forced to repeat ourselves in expressing the type of thing we’d like to allocate, despite that type being well known to the compiler, and type inference is so idiomatic (consider expressions like a := b), I sometimes have to dig to figure out what the type of a thing is. Let’s look at what’s involved in creating a struct with a map embedded:

type NamedMap struct {
    name string
    m    map[string]string
}

func NewNamedMap(name string) *NamedMap {
    return &NamedMap{name: name, m: map[string]string{}}
}

We could alternatively use make in NewNamedMap, but we’re still left with return &NamedMap{name: name, m: make(map[string]string)} – again, repeating the type. With well-thought-out code, there should be only one (additional) place where we need to specify the type to allocate it, but this still requires touching multiple points of code when types change. This bites me when I’m prototyping and haven’t thought fully about the amount of state I need to keep in a map. I’ve found myself needing to change map[string]string to map[string]T on several occasions, and it bugs me every time I have to change more than one line.

One could argue I should think more about what I need before writing code, and that’d be fair. I’d still counter that it’s not uncommon for additional state requirements to develop within a project’s lifetime, like in my set example above. It’s also possible that constraints of a system change over time such that a type that was perfectly fine initially eventually becomes unusable. In Go, the set structure might look like this:

type Set struct {
    nmemb   int
    cap     int
    members []int
}

func NewSet(sz int) *Set {
    return &Set{cap: sz, members: []int{}}
}

You might ask why I’m not just using a slice, and the answer is that this is a short example for demonstrating the problem. Anyway, we may later want to support a slice of different types, and we run into the same problem we had previously. With a slice, we might be able to ignore the initialization, assuming we only ever read from the slice after appending to it. With e.g. maps and channels, the situation is more complicated because we really must allocate before use. So it’s not that uncommon to repeat type information somewhere.

I’m not entirely sure how to go about solving this. For compound literals, it perhaps it would be possible to add a syntax like:

return &Set{cap: sz, members: Set.members{}}

If you had a pointer to a slice for whatever reason:

return &Set{cap: sz, members: &Set.members{}}

I don’t know if I like these compound literal syntaxes. Fixing make to support the sizeof behavior in C feels more expressive and obvious:

return &Set{cap: sz, members: make(Set.members)}

But maybe this is just me programming in C for too long.

I don’t know that it is useful or valuable to change new to have similar behavior; I suspect its use is uncommon enough that it is not. In any case, it does seem clear to me that this would reduce the overhead of refactoring software, and of writing new software.

This particular issue isn’t so bad, but fixing it would definitely make my life better. Go is already much more expressive than C in many cases, and than C++ (which I still can’t stand to learn). I think if support for type inference in allocation was added to the language, it’d become more appealing to C systems programmers who are still holding out for reasons other than GC. (Personally, I’d also like to see a better story around support for system-level concurrency, but that’s best left for a separate post.)

I’ve edited this article to fix an error in the C example. When I originally wrote the example, the struct set did not make use of flexible array members. Anmol Sethi wrote to ask about this feature, and pointed out that I was erroneously allocating and assigning to the FAM again. I had forgotten to remove that code. Oops.

Rote Learning in CS

Sun, 20 Aug 2017 00:59:00 +0000

Does rote learning have a place in computer science education? In my talk at QCon, I stated:

[Learning through discovery] is so much better than this typical, learn-by-rote method of teaching that we all sort of think of as teaching…

I just read a blog post by Zed Shaw suggesting that rote learning is basically required to become skillful in the field. I came into the article wholly skeptical – I haven’t always been a fan of what Zed writes, and my own research seemed to contradict what I thought the thesis would be. After reading it, I maintain that rote learning is useless as a teaching strategy. So I was surprised to find that I actually agreed with large parts of Zed’s post. What gives?

Consider for instance this sentence from Zed:

The problem with [the fear of rote learning] is that nearly every creative thing you do requires rote practice.

Now, let’s compare that sentence to what I said:

To gain skill, we have to practice at the edge of our ability.

Zed and I agree on this idea that practice is required to gain skill – although if you bring in some context, it might not appear that we do. We coincidentally both contextualize this around learning guitar. Zed writes, “The idea that I’m going to learn the major scale on a guitar by just learning the concept of a major scale is laughable.” I think it’s entirely possible for someone to conclude I disagree based on what I said:

[F]or example, I’ve played guitar for twenty-five years. And I suck.

And fundamentally, this is because I rarely challenge myself. I learn some song or – the coolest thing I ever learned was some sweep picking pattern, and I can’t even do it very fast. But I rarely challenge myself to do something new. We don’t get better at guitar by playing one chord or plucking one string time after time after time. In fact, I don’t think that would even help us master that chord because you’ve got to do transitions in and out of it, et cetera.

While it sounds like we’re saying very different things here, I don’t think we are. Undoubtedly, mastery of guitar requires repetition. You’re going to play scales a lot. I mean, a lot. I’ve played them a lot, and I’m still terrible. I’m so bad, I have exactly 0 positions memorized. I could probably noodle out major/minor/blues scales given some time, but it wouldn’t be pretty. Why? Part of this is that my practice is inconsistent; I’ll speak more about what kinds of practice are effective in the closing paragraphs.

In my own context, I seem to be saying that practice doesn’t help you learn guitar at all. But this isn’t at all what I meant – I really failed to communicate clearly. I meant that playing guitar isn’t really a single skill. You aren’t good at guitar simply when you can play a single chord or a single song. If you practice one single thing until your death, playing that one thing absolutely perfectly every time, you’ve mastered exactly 0% of guitar. The greats in guitar have skills outside the realm of guitar playing as well as a mastery of the instrument. They can improvise. They can play many different styles of music. They’re fundamentally diverse in their skillset.

Zed goes on to tie his ideas into CS education. He writes:

If you’re imagining yourself at 12 trying to learn to code, then I’m betting you had either a book or website with code that you copied and made work. This should just be how we start people in programming, and not the current method of conceptual “weed out” classes.

I identify closely with this hypothetical. As a kid, I remember copying programs out of books on QBasic and making simple changes to try to understand how things worked. I do think we need to be careful about making an assumption this is the only way people could successfully learn to program – most of the people I know who learned this way were white, middle-class boys. I would also note that I was a pretty terrible programmer for a really long time until I had people mentoring me, and I thought I was a much better programmer than I actually was until years after I had people who were mentoring me. I’m not entirely sure that I agree this is an effective way to start. It took me about 10 years of professional programming to get anywhere close to being something that most folks would call good, and I’m positive that a more formal grounding in computer science would have helped.

I suggest this caution specifically because I’m not a fan of Zed’s LCTHW book for many reasons. The book no longer appears to be freely available, but in a previous iteration, it contained a section called “Make is your new Python.” While factually incorrect, this section title is an example of Meaningful Learning, the idea that we gain new knowledge by building and expanding upon things we already know. I generally think this is a good idea; it’s why I suggest using mail as a metaphor when discussing indirection in C.

But Tim also points out, “What if the reader has no experience with Python at all, and doesn’t even know what it is? The author is making an assumption here that not only is the reader a novice in terms of C, but Python also.” I think this is a fair criticism. This assumption of knowledge is why, although I identify with the hypothetical scenario of learning to program at age 12, I think we should be careful in assuming its validity for the purposes of teaching others. If that knowledge is not foundational (and is potentially exclusive), we may continue with the shitty status quo in diversity in our field. This is why I also said we need to operate from curiosity: we have to figure out where it is to start teaching folks.

That all said, I agree that the “weed out” classes are problematic: they challenge people without promoting an incremental self-theory. They’re basically designed to be anti-diversity machines. They’re designed to be this sort of pedagogical manifestation of laziness by instructors who don’t actually want to help people learn.

Anyway, this bit from Zed’s post is what really spurred me to write this post:

I think the main reason why this is ignored or vilified in CS is the same reason that most programmers simply can’t teach: They are so far removed from their beginner experience that they forget that they actually learned to code via rote learning.

Compare again this statement to what I said about the pedagogy of debugging:

As we gain experience, we forget what it was like to learn a thing, and we forget even more the more experience we gain.

Zed doesn’t appear to be stating that repetitive practice should be the only way that CS education happens, but rather that it should be explored as part of it.

Is repeated practice entirely absent in CS education? Programs that are heavy on lab projects effectively promote such practice by having students use their new knowledge to solve multiple different problems. I think this effectively merges the repetitive practice aspect with the creative learning aspect. So I don’t agree entirely that practice is globally “ignored or vilified,” we just need to look at how it actually manifests in some curricula.

And how does it manifest? I was talking to a high school programming class earlier this year. As part of my presentation, I illustrated how problems that don’t at all look similar actually end up being the same problem. The example I gave started with Scrabble: we need some kind of dictionary structure to look up words. It turns out this is exactly the same problem that you face if you want to implement key-based purging in a content delivery network. By understanding how to handle a Scrabble dictionary, I was able to implement the Surrogate Keys feature at Fastly.

So we find repetition in solving lots of related problems; this is why programs heavy in lab work can be successful. And we make that less boring (which is the main complaint against this pedagogical practice of rote learning, outside of its total lack of efficacy) by being creative in the tasks that we have folks solve. This seems similar to Zed’s suggestion to engage in “…training that involves a mixture of rote (scales, chords, ear training) followed by copying and modifying (learn a song and try to improvise).”

Was I off-base in my talk? Do I agree with Zed? I wasn’t off-base, and I think I agree with Zed, but the reason is because of semantics. You may’ve noticed that I keep saying “repetitive practice” and not “rote.” The word “rote” means a form of mechanical, habitual, unthinking practice. This isn’t what I’m talking about. It doesn’t seem to be what Zed is talking about. I really don’t agree that rote learning works, and I don’t think he actually does either. It doesn’t jive with his own examples of learning guitar and painting: skills he is motivated to practice deliberately.

When I say “learn-by-rote,” I really do mean “rote” in this mechanical, mindless context. This is not at all effective; there’s significant, neurological evidence to support the idea that it is ineffectual. As a quick aside, a fantastic segment earlier this year on KQED’s Forum program explored the problems with lecture-based education, in an interview with Nobel laureate Carl Wieman. (Shameless self-promotion: I called into this program at 16:49.) I think it’s relevant because lectures are basically unengaging, mechanical, habitual, unthinking ways of throwing entirely too much information at a person and having them remember none of it.

Finally, it’s not just repetition in practice that is required to gain skill in a craft. Peter Norvig’s Teach Yourself Programming in Ten Years cites numerous papers in explaining that deliberation is also required:

The key is deliberative practice: not just doing it again and again, but challenging yourself with a task that is just beyond your current ability, trying it, analyzing your performance while and after doing it, and correcting any mistakes. Then repeat. And repeat again. There appear to be no real shortcuts…

Based on his post, I don’t think Zed actually believes that repetitive, undirected, automatic practice builds skill. Past experience reading Zed’s responses to people who argue with him about semantics haven’t been pleasant, so I don’t really want to engage in a semantic argument. However, I do wonder whether this incorrect terminology is the reason he thinks that “rote learning” is such a taboo in education. Ultimately, I think we’re both talking about the same thing, and I agree that it works.

Edit: I somewhat tongue-in-cheek tagged Zed when posting this article on Twitter. He replied and, far from a flame war, we had a pretty interesting discussion. Zed does mean “mindless” when he says “rote” – but it’s more of a Buddhist, meditative interpretation of the word. I think I know what he means; I can understand how a sort of culturally different view on “mindlessness” might be beneficial in learning. Western culture has a romance with the idea of smart, and smart means thinking. As such, learning is often stressful. This makes the sort of meditative version of “mindlessness” difficult to attain, if at all attainable given the stress on children to perform academically. This was definitely an area of unconscious bias for me, and I’m happy to have learned.

Go Go Gadget Co-Ro

Mon, 05 Jun 2017 16:00:00 +0000

I like coroutines. The other day on my team’s Slack channel, someone introduced Adam Dunkels’ protothreads. Either I hadn’t seen these before or had forgotten them, but it looked cool. A short conversation ensued, and at some point a colleague offered:

i can’t ever decide if i like [coroutines] or not. so ignoring that, i think there’s a decent heuristic: something like tatham’s coroutines will provoke a conversation every time you use it. i figure if something produces so much discussion, it’s certainly non-obvious to understand

This colleague is an excellent software engineer and computer scientist. She’s definitely familiar enough with threads, and so this comment struck me as odd. Programs implemented using threads are, in my view, much more difficult to understand than those implemented atop coroutines. If you can understand how threads work, you can understand coroutines. In this post, I’d like to describe what threads and coroutines actually are, the similarities and differences between them, and why I think coroutines provoke so much discussion.

We’ll start out with some definitions. What are threads; what are coroutines? The easiest way I find to introduce concepts is to present definitions based on the properties of the things the word describes. So we’ll start at a low level, and work our way up.

A computer is some hardware that provides state, and can execute at least one program. A program is simply a specification for how state is changed over time. A program executed by a computer is called a process. The context in which the program is executed is called a “thread,” and every process contains at least one thread. Processes containing multiple threads may see those threads execute in parallel. The state provided by the computer may or may not be shared between processes, but within a process, this state is shared. Threads are also typically given some “protected” state: state intended for use by the thread, but not expressly prohibited from sharing between threads.

As a program executes, state changes, and time progresses. These tuples of (execution unit, computer state) may be arranged over the vector of time to describe what is called an “execution history.” Each thread is a container of an independent ⊕ There may be dependencies in state between threads, but the execution histories exist indepentedly of eachother. execution history vector. This independence allows threads to be run either serially or in parallel. Multiplexing threads within a process is indistinguishable from a hardware platform that provides no meaningful abstraction for a process, and multiplexes threads directly.

So we have this hierarchy of “computer” and “process” and “thread” – but all of these things are just containers of independent execution histories. The computer has one or more processors that execute instructions to modify state over time. It executes processes that are comprised of one or more execution histories, which also describes what a thread is. If these are all the same thing, why in the world do we have different words for them?

Each word describes the same thing, but at a different level of abstraction. This abstraction is great, because it provides us a means to approximate a new Turing machine, which means we get a little extra state to do something useful each time we abstract. So although we usually say that a computer doesn’t contain another computer, we have VMs! Processes don’t contain other processes, but they do contain threads – which are effectively little processes. And threads don’t contain threads. But a thread comprising Turing-complete execution units running on an abstraction of a Turing machine can obviously implement another Turing machine. Therefore, a thread may contain another thread, just not at the same abstraction level!

Our computer is our base-level abstraction for a Turing machine (we don’t actually have one of these because nobody has infinite tape). Our process is another abstraction that allows us to pretend our computer runs multiple Turing machines at once: this is useful because we don’t want the computation of one of them to influence the computation of another. And threads exist for effectively the same reason – they’re useful for multiplexing the same kind of computation on discrete bits of state.

Coroutines are what we get when we define an abstraction on top of threads. In a novel way, coroutines are threads, in the same way that threads are processes and processes are computers – all abstractions for a Turing machine. Coroutines recognize that the fundamental unit of execution is this tuple of (execution unit, computer state), that multiple vectors of these can execute independently with an almost arbitrary interleaving. Furthermore, since they exist at an abstraction above threads, that abstraction should be providing something that makes them easier to understand.

To understand why we might like this abstraction, let’s take a deeper look at some of the problems with writing purely threaded software.

Threads provide an abstraction above the machine or process level, representing multiple independent execution histories. This abstraction became popular in recent years as multicore and manycore systems became ubiquitous. Threads existed even before such systems were terribly common, so what is it about the abstraction that makes them useful?

Many tasks we solve with software are repetitive. We rarely try to solve tasks that involve taking a single specific input and producing a single specific output. Such a transformation only needs to occur once, and we only write software for something this specific when the input and / or output sets are large. In network servers, for example, requests from a client arrive that direct the software to do some work. These requests will all be very similar, and so it makes sense for us to use the same codepath to process each request. Additionally, network requests tend to take time to satisfy, and request arrival often follows a Poisson distribution which (practically) means that requests will usually occur in clusters.

Let’s say we’re serving requests for image thumbnails. This means we’re serving a lot of small content across a potentially large library. For simplicitly, let’s assume a each request can only result in a single thumbnail, and every thumbnail is equally likely to be requested. A random disk seek on a fast spinning disk takes about 10 milliseconds. This seek time dominates the time we spend on the request, so we can approximate the request time as 10ms + ε. The simplest solution, to serve each request from a single thread of execution as it arrives, has two consequences:

The oldest request accumulates the latency of every request in front of it.
We are maximally able to serve 100 requests per second.

Because request arrival rate tends to follow a Poisson distribution, it’s likely that a large number of requests experience the negative of the first point. And if we receive over 100 requests within the same 10 milliseconds, the folks with the latest requests will wait over a second for their thumbnail. In fact, even if we add more disks in a RAID configuration, we can never beat this problem, if we insist on serving requests serially.

The abstraction of the thread allows us to take advantage of parallelism in hardware. Let’s now assume we have a RAID1+0 configuration (mirrored and striped), and so our objects are stored twice, and distributed across many disks. Adding threads allows us to amortize the cost of disk seeks over multiple disks, reducing the probable latency for any individual request. Because the time for processing the request (compared to the disk seek) is ε, our mental model now says that the probability of any two requests requiring the same disk is proportional to the number of disks. Let’s say that we have 10 disks. Now with 100 clustered requests, it’s entirely possible we can serve all of them within 100ms instead of 1s.

This is fantastic for read-only and read-mostly workloads. However, when requests require us to mutate state, things go downhill quickly. As an abstraction on top of some state (either a machine or a process), threads have access to everything in the parent’s state. Traditionally, this has meant that threads are able to share stateful things like memory that tend to be protected between instances of their parent abstraction. This is problematic when the shared state is mutable. Because multiple threads of execution may occur in parallel, some actions may occur at the same time. It’s well known that conflicts occur when multiple threads attempt to access some shared mutable state, and one of those accesses is a write. Consider the following code:

#include <threads.h>
#include <stdint.h>
#include <stdio.h>

static volatile uint64_t counter;
#define NTHRD 2

thrd_start_t
thread(void *arg)
{
        (void) arg;
        for (int i = 0; i < 1000000; i++) {
            counter++;
        }
        return NULL;
}

int
main(void)
{
        thrd_t tds[NTHRD];
        for (int i = 0; i < NTHRD; i++) {
                if (thrd_create(&tds[i], thread, NULL) != thrd_success) {
                        return -1;
                }
        }
        for (int i = 0; i < NTHRD; i++) {
                if (thrd_join(tds[i], NULL) != thrd_success) {
                        return -1;
                }
        }
        printf("counter: %" PRIu64 "\n", counter);
}

In this example, the resulting value of counter is unclear. Strictly speaking, in C11, this program invokes undefined behavior; it’s fair to say that the program as a whole has no meaning. It is entirely possible that the value output at the end of the program is any number from 1,000,000 to 2,000,000. The issue here is that code is designed to implement a protocol. In the case above, that protocol is the “increment a counter” protocol, which is actually broken down into three steps:

Read the value of the counter from memory.
Modify the value of the counter by adding one to the value read.
Write the value of the counter back to memory.

Even though this read-modify-write operation is expressed in C (and possibly at the hardware level) as a single “increment” instruction, it actually decomposes into these three operations. And each of them could happen interleaved with similar operations executed by other threads. If our first and second threads consistently execute each operation in lock-step with each other (112233), each loop only increments the counter by one despite having run twice.

The reason that this can happen has to do partially with how computer hardware handles memory accesses, and partially due to how threads are scheduled (by the machine or an OS scheduler). Because reads from and writes to memory are expensive (when compared to the cost of performing some operations in registers), processors tend to cache these reads and writes. On a system with multiple processors, with each thread simultaneously executing on a different processor, the threads will be operating on cached copies of the memory (despite our use of volatile). If a processor did not provide an increment instruction, the assembly for counter++ might look like:

load    %reg, (counter) ; load counter from memory into register
add     %reg, 1         ; add 1 to value in register
store   (counter), %reg ; store register back into memory

One property of threads is that they’re often pre-emptable. This means that whatever is running the threads (whether the machine or an OS scheduler) may stop the process from executing while it is in-between instructions. In the case where our increment is implemented as three separate instructions, the thread could be paused between any of them. This pre-emption further exacerbates the problem of the data race.

Typically, we solve this problem by using synchronization constructs. In this case, the hardware might provide us an instruction to do a synchronized increment. In other cases, we might need to use a mutex (or other serializing construct) to ensure the correctness of our implementation of the “increment a counter” protocol. This has its own issues (many of which are presented well in Samy Al Bahra’s article on non-blocking synchronization) that I might cover in a separate blog post.

For now, let’s go back to our thumbnail serving example. Implemented in somewhat pseudocode, we might have the following.

thrd_start_t
serve_thumbnails(void *arg)
{
        while (true) {
                struct request_state *state = get_actionable_request();

                if (read_request(state) ||
                    get_thumbnail(state) ||
                    send_response(state)) {
                        handle_error(state);
                }
        }
        cleanup(state);
}

Ignoring caching, pre-emption is the primary effect that allows a threaded implementation of our thumbnail service to operate efficiently. However, if we take a deeper look, read_request and send_response are also potentially latency-intensive. Our 10ms + ε estimate wasn’t exactly correct because although get_thumbnail is approximately bounded at 10ms, it could take us dozens or hundreds of milliseconds to read the request and send the response. During that time, the thread is consuming resources (every abstraction requires some amount of state to represent), while not providing any computational benefit. Schedulers recognize this and run something else during the time the thread is blocked waiting on input, or waiting for the output side to become ready for more data.

Unfortunately, a thread consumes resources (at least memory) even when it is not being executed. Even with threads being lighter-weight than processes, their mere existence isn’t necessarily cheap when you have a lot of them. Additionally, the cost to “context switch” between threads of execution is usually somewhat expensive. Context switches are pretty awful because during that time, the machine isn’t doing anything particularly useful. It is just changing the environment around a bit to switch to a different Turing machine abstraction. When we’re doing I/O intensive operations, these operations might occur while we still have time to run on the scheduler (that is, we would not have been pre-empted if we had not done some I/O task).

To address this problem, we can make our I/O operations asynchronous. In the example above, we’ve already created an abstraction for our request state. We can use that to create a finite state machine to know what to execute at any point.

thrd_start_t
serve_thumbnails(void *arg)
{
        while (true) {
next_state:
                struct request_state *state = get_actionable_request();

                switch (state->fsm_state) {
                case STATE_READ_REQUEST:
                        switch (read_request(state)) {
                        case BLOCKED:
                                queue_for_input(state);
                                goto next_state;
                        case ERROR:
                                state->fsm_state = STATE_ERROR;
                                break;
                        case SUCCESS:
                                state->fsm_state = STATE_GET_THUMBNAIL;
                                break;
                        }
                        break;

                case STATE_GET_THUMBNAIL:
                        switch (get_thumbnail(state)) {
                        case BLOCKED:
                                queue_for_input(state);
                                goto next_state;
                        case ERROR:
                                state->fsm_state = STATE_ERROR;
                                break;
                        case SUCCESS:
                                state->fsm_state = STATE_SEND_RESPONSE;
                                break;
                        }
                        break;

                case STATE_SEND_RESPONSE:
                        switch (send_response(state)) {
                        case BLOCKED:
                                queue_for_output(state);
                                goto next_state;
                        case ERROR:
                                state->fsm_state = STATE_ERROR;
                                break;
                        case SUCCESS:
                                state->fsm_state = STATE_DONE;
                                break;
                        }
                        break;

                case STATE_ERROR:
                        handle_error(state);
                        break;

                case STATE_DONE:
                        cleanup(state);
                        break;
                }
        }

        return NULL;
}

This works, but it’s not particularly easy to read. We no longer have a linear flow of code. There’s tons of branching, and we have to be very careful to advance our state correctly to avoid cases where we might cause a loop in our state graph, fail to handle a state, or something else bad. There are a couple of opportunities to avoid repetition in this code, but that won’t drastically improve its readability. The property we have lost here is called “composability.”

Composability is a property of a system or API that describes how easy it is to implement, consume, and understand that system or interface. Examples of composable interfaces include functions for working with common data structures like queues, hash tables, and graphs of various shapes. These structures tend to have add, remove, and find interfaces. We can “compose” these interfaces with relative ease to get correct structures that efficiently manage and represent our data sets or program flow.

In our example above, we see that C isn’t the best language we could possibly use to compose a finite state automaton. When a language, system, or interface becomes too difficult to put together, too difficult to read, or too difficult to understand, we say that it is not composable. We generally solve this by introducing additional layer of abstraction. For example, the wonderful library and tools provided by libfsm give us several pleasant means to compose finite state automata through languages, tools, and libraries.

Let’s look at our original example again:

thrd_start_t
serve_thumbnails(void *arg)
{
        while (true) {
                struct request_state *state = get_actionable_request();

                if (read_request(state) ||
                    get_thumbnail(state) ||
                    send_response(state)) {
                        handle_error(state);
                }
        }
        cleanup(state);
}

In an ideal world, this would be expressive enough to encode our state transitions. If read_request would block, it would be nice if it could simply stop its execution and retry exactly where it left off, instead of us having to design an entire machine to do that. The finite state machine we created does exactly this, but it isn’t a very nice way to abstract the problem.

This is precisely where coroutines help. The point of the abstraction of coroutines is to offload much of this complexity into the scheduler. Unlike threads, coroutines are not pre-empted; they are instead “cooperatively” scheduled. That is to say, a coroutine (unlike a thread) runs until it explicitly yields its runtime to another coroutine. Like any abstraction, it requires some additional state, but this state is relatively small. Of course, we still have to “context switch” between coroutines, but this is a much simpler and faster operation than having the OS context switch between threads.

A coroutine doesn’t typically have a “protected” state like a thread does. When this is useful, this protected state is usually much smaller than that of a thread. On many machine implementations, coroutines only require a subset of machine registers to be saved and restored. Coroutines exist in a very small number of different states: running, runnable, or blocked on a resource. Because of this, multiple coroutines may execute concurrently on a single thread.

Concurrency and parallelism are often confused to mean the same thing. Parallelism describes a system in which multiple independent execution histories may occur at literally the same time. This is the case with threads, where (for example) parallel independent execution histories may be executed simultaneously on multiple processors. Concurrency is weaker: it simply states that multiple independent execution histories may be interleaved such that they appear to be occurring at the same time. This is roughly the same feature operating system schedulers provide to give the illusion of multitasking many processes on the same system.

Using coroutines, our original example still works just fine. We might have multiple threads of execution (so that we can utilize our hardware in parallel) with each thread multiplexing several coroutines. In this world, the complexity moves around, but it is tightly contained in a few spots. This lends itself nicely to composability. As an example, our read_request function might look like this:

int
read_request(struct request_state *state)
{
        ssize_t r;

        do {
                r = read(state->fd, state->buf, state->bufsiz);
                if (r == -1) {
                        if (errno == EAGAIN) {
                                yield_on_read(state);
                        } else {
                                return 1;
                        }
                }
        } while (request_not_complete(state));

        return 0;
}

The special function yield_on_read is provided by the coroutine implementation. It snapshots the current machine state of the coroutine, updates the coroutine’s state to become runnable when more data exists on the file descriptor, and returns to the scheduler with a lightweight “context switch.” Later on, when data arrives (or possibly when a timeout occurs) on that file descriptor, the scheduler returns directly into the coroutine where it left off (again with this lightweight “context switch”). The coroutine continues by testing request_not_complete (which will be true because the request wasn’t completed the previous time), and will re-execute the read system call, this time guaranteed to get at least some data. In the time between this, some other coroutines may have executed. Similar things could be implemented for get_thumbnail and send_response. Indeed, we could abstract out all blocking I/O operations into a single API such that other coroutines don’t need to implement their own state handling in a loop like we’ve done here.

How do coroutines snapshot the machine state? This is usually done using functions like makecontext and swapcontext, or getcontext and setcontext. As previously mentioned, some machines do not require all execution context to be saved. In such cases, some assembly code to read or restore the minimal required machine state is written.

Why aren’t coroutines more widely used? Although the resulting code often ends up being more composable, and although highly concurrent workloads like network servers tend to benefit from such an expression, there’s a fair amount of overhead involved in implementing the underlying API and scheduling. Threads are already relatively lightweight (at least compared to processes) and already have a scheduler to run them. Much of the time, the overhead of implementing APIs and scheduling is not seen as justification for the resulting composability and scalability win.

In my opinion, this is the reason that coroutines provoke a discussion. It looks like a difficult technical discussion about how complicated writing a scheduler is, but really it boils down to a discussion about where and how to hide complexity. It seems clear to me that the bulk of code written using coroutines is less complicated, and the composability benefits are huge.

But in some cases, coroutines have significant drawbacks. When part of a cooperatively scheduled task has high computational overhead, do we yield before performing the computation? All other coroutines are blocked while one is executing, so we need to be aware of this tradeoff. If we want to take advantage of parallelism with coroutines, we also face more challenges. If several coroutines are working with some shared state and those coroutines can yield in the middle of something that should logically be a critical section, we still need locking. Problematically, if we also have added multiple threads on which to execute coroutines, this means that we need to introduce some kind of locking protocol. Several more corner cases like these exist, and none are particularly trivial to solve. All add complexity to the scheduler and have runtime overhead.

It’s frequently safer and easier to go with the devil you know. And so we have long conversations (and blog posts) about coroutines instead of actually using them.

That all said, the popularity and reasonably good performance of the Go programming language in the systems and network programming space shows that it is possible to get coroutines right.

If you’re interested in implementations or adopting coroutines into your work, there are several great resources. My two favorites (apart from homegrown implementations) are libmill, which is a library that provides Go-style concurrency for C, and libtask provides coroutines as well as appropriate non-blocking file and network I/O interfaces as a portable version of Plan 9’s concurrent programming interface.

I’ve avoided covering numerous related topics. In particular, message passing in a threaded environment combines the simplicity of existing pre-empted thread scheduling with the composability of data structure operations. In fact, message passing is a fantastic way to implement notification queues for systems built on either threads or coroutines (or both). Like any abstraction, the devil is in the details. Message passing in threaded environments moves the complexity away from the scheduler and the threading code, but into the algorithms and data structures used to pass messages. In environments with extremely high thread counts, this can be a non-starter when using an unmanaged language like C. Anyway – it’s an idea for another blog post!

Discovering Undefined Behavior

Mon, 17 Apr 2017 17:00:00 +0000

The C language is infamous for undefined behavior. Fantastic, multi-part articles by Chris Lattner and John Regehr have made their rounds over the years, describing several instances of undefined behavior. In particular, they describe how compilers are allowed to assume it does not occur in correct C programs, and therefore make optimizations that seem to remove correctness from programs. The intent of these posts seems to be to educate people that they should be aware of what consitutes undefined behavior.

But this isn’t always so easy.

When does undefined behavior occur? The C11 draft formalizes this in §4p2:

If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of a constraint or runtime-constraint is violated, the behavior is undefined. Undefined behavior is otherwise indicated in this International Standard by the words ‘‘undefined behavior’’ or by the omission of any explicit definition of behavior. There is no difference in emphasis among these three; they all describe ‘‘behavior that is undefined’’.

Of note should be the text stating that undefined behavior occurs when “any explicit definition of behavior” is omitted. What happens if you try to run a C compiler on cheese? This is undefined by omission, and therefore this implicit undefined behavior becomes explicit.

Maybe that doesn’t sound so bad, but it results in tons of confusion amongst programmers and compiler implementors. For example, did you know that printf("%p", (void *)NULL); yields undefined behavior? This is because §7.1.4p1 states, “If an argument to a function has … a null pointer, … the behavior is undefined.” Later on, in the specification of the printf family, no such exception appears.

This might seem innocuous, but it’s maybe more obviously problematic if you consider a case like printf("%s\n", s);, where s is NULL. Printf functions have relatively high overhead: they’re variadic functions, which tend to be more expensive to call. They also contain format strings, which must be parsed at runtime. Some compilers therefore optimize calls like printf("%s\n", s); to puts(s);, which are functionally equivalent. This is allowed because of the statement in §7.1.4p1, but pisses folks off because most printf implementations will output something like (nil) if s is NULL. Puts, on the other hand, probably crashes trying to dereference a null pointer.

You might think all cases of undefined behavior have been discovered. I’d be surprised if this was true. The “undefined by omission” case allows for all sorts of things that are so circuitous to understand, it makes you wonder how the language works at all. For example, after a somewhat long discussion in ##C on Freenode, we came to the conclusion that there’s undefined behavior hidden in bit-fields. To get here, you have to jump through several hoops:

First of all, §6.7.2p5 states that an implementation may choose whether a bit-field of type int is represented as signed int or unsigned int. Given the following code,

struct ex {
    int bf : 1;
};

we might expect to be able to represent the values -1 and 0. Or maybe 0 and 1. Or maybe -0 and 0. But none of these are actually possible, because §6.2.6.2p2 defines signed integers as “containing exactly one sign bit,” the purpose of which is to modify the value of the variable with either sign and magnitude, two’s complement, or ones’ complement semantics. However, in the above example, ex.bf clearly has no value bits to modify if it is represented as a signed integer: there is only enough space to represent the sign bit.

The spec could clear this up by specifying in §6.7.2.1 that bit-fields of signed type must include enough space for at least one value bit. Or specifying something similar at or around §6.2.6.2, where the representation of signed integers is discussed. As it stands, this is the kind of thing you end up running into on accident.

I don’t think it’s great that programmers should be left to “discover” undefined behavior. To that end, I think it’d be great if things like this were spelled out more completely in the standard, or if Annex J.2 was considered normative. However, it seems the standard committee is fine leaving such behavior undefined by omission.

What undefined behavior have you discovered? I’d love to hear about it!

This post was edited to fix a statement about printf and puts equivalency. In particular, I had stated that printf("%s", s); was functionally equivalent to puts(s);. It is not, but printf("%s\n", s); is. Thanks to lemonade\` on Freenode for pointing this out.

Help Vampires Aren't

Fri, 14 Apr 2017 23:20:00 +0000

Help vampires. It’s an idea apparently coined by Amy Hoy in an article she wrote over ten years ago. The “vampires” described are common in open source communities. They’re also prevalent in online chat communities like IRC, especially in channels ostensibly for help purposes. The blog post describes a real problem that people experience. Some people in these communities (usually neophytes) engage in maladaptive learning behaviors that drain the energy out of those who might be able to help them (hence the term “help vampire”).

But I have a real problem with this terminology, the presentation of information in the article, and many of its suggestions for solving the problem.

The tone of the first half of the article is glib, but inflammatory. The article claims to be a resource one might share with a so-called “help vampire,” but it spends the entire first half basically lambasting these individuals. This could be solved relatively easy by reversing the order of the article, such that the helpful information is placed first and the backstory comes at the end. If this were the case, the article would read to be more genuine about wanting to help.

Though the article claims that it can help people change their ways (and help others help those people change their ways), it subverts this goal entirely by first offending the person looking for help, and by training educators to recognize these people as malicious. For example, this appears in the fourth paragraph of the article: “[T]hese vampires suck the very life and energy out of people.”

Read that several times. If you were just called a “help vampire” – this is the first suggestion of how to deal with such individuals – would you feel good about yourself? Would you suddenly be open to changing? Or would you be confused why someone is trying to stop you from learning something? Would you feel offended? Would you become defensive? Would you shut down? Would you feel like this community is for you? Here, at the very beginning of an article that is supposed to be helpful to people of this classification, such individuals are already vilified. This is not an effective strategy for educating people, nor is it an effective strategy for convincing people to change their behaviors. In fact, it engages in the same kinds of “life sucking” activities it accuses the “vampire” of possessing!

The problem is that the whole idea of a “help vampire” (as specified) assumes malevolence. It completely disregards the popular aphorism of Hanlon’s razor Hanlon’s razor is usually expressed as “never attribute to malice that which is adequately explained by stupidity.” I prefer “never attribute to malice that which is adequately explained by ignorance.” This version is less inflammatory; folks often interpret stupidity as uncorrectable. – the idea that people are more likely to be ignorant than malicious. The “help vampire” likely engages in their maladaptive learning strategy for one or more of the following reasons:

It has worked for them in the past.
They possess an entity self-theory as defined by Carol Dweck.
They’re under a time crunch and a quick answer is more useful than expanding their knowledge.
They simply don’t have enough context to know what to ask, how to ask it, or where to start learning.

None of these reasons include malice, so interpreting them as malicious is incorrect. It even ends up being destructive when, for example, a person under a time crunch may intend to learn more about the problem after it is mitigated to a sufficient degree. But this person need help mitigating the problem now. They might have a deadline attached to an angry boss. If you don’t offer help, you’ll never know. The point is really that if the person asking for help is assumed to have a malicious intent, someone equipped to help is less likely to do so. It presents the person as an immediate enemy. This isn’t conducive to education.

These statements about being “out to stop” people for sucking “life and energy” isn’t the only example of where malice is trained. Hoy claimed that the “vampire” has intent:

First, to identify a victim foolish enough to attempt to answer the impossible question. Second, to distract the victim long enough to separate him from his fellows; and [l]astly, to befuddle the victim’s brain while their soul is being removed through the abdominal cavity by way of a standard-issue Bendy Straw.

This is destructive, and a direct example of assuming malice.

An argument is made that the trait of “help vampire” is somehow correlated to gender. This is a sensitive subject for many, especially in computer science, where we have such an unfortunate gender disparity. This is a polarizing issue in our field. As such, needlessly labeling any gender as having some undesirable traits is likely to continue polarization of the field.

Most problematically, Hoy cited no research to back up this claim. She surmised (probably in jest) that this must somehow be related to some evolutionary trait, but provided no rationale for this. As such, there’s no way to address her statement other than to suggest it is purely experiential. As such, it would be more reflective of the gender disparity in computer science than it is some undiscovered evolutionary trait. And the research backs this view up.

The maladaptive learning strategies attributed to the “vampire” are exactly those associated with individuals with an entity self-theory. Defined by Stanford’s Carol Dweck in her book “Self-theories: Their Role in Motivation, Personality, and Development.” Furthermore, Dweck has also conducted research showing that girls are more likely to have an entity self-theory than men, and that this is developed early in life. Is Math a Gift? Beliefs That Put Females at Risk. Dweck, Carol S.; Ceci, Stephen J. (Ed); Williams, Wendy M. (Ed). (2007). Why aren’t more women in science?: Top researchers debate the evidence, (pp. 47-55). Washington, DC, US: American Psychological Association, xx, 254 pp. http://dx.doi.org/10.1037/11546-004 Women begin learning and experience the psychological effects of shitty, sexist, pseudo-aphorisms like “women should be pretty and not smart” at a very young age. The ideas represented by this sexism are culturally reinforced, and such statements actively promote an entity self-theory. Dweck discusses this in some depth in chapter sixteen of her book, where she states directly “we find that [bright girls] are the group with the greatest vulnerability to helplessness.”

Therefore, I don’t believe this claim that men are somehow more likely to be “help vampires” is true. In fact, I believe the evidence shows that women are more likely to engage in “help vampirism.”

And this is what really frustrates me about bringing gender into this at all. It turns out that you can move people from an entity self-theory to an incremental self-theory, and you can do so with the same strategies, regardless of gender. Calling anyone a “help vampire” is a shitty thing to do, and bringing gender into it is pointless because it has no bearing on the solution.

I don’t mean to suggest that Hoy’s article is entirely without merit. Good suggestions are provided as to how individuals can reduce the burden of “help vampires” on their communities. Many of her suggestions directly reflect suggestions I might provide. Others are variations on things like engaging in Socratic exercises, or engaging in the creation of educational material. (One must be careful here: for example, “tutorials” that are poorly written end up encouraging copycat behaviors, and may actually prohibit learning.) The majority of the suggestions are good, and in many cases, a well-intentioned effort is better than none at all.

Really the only suggestion I take issue with is the suggestion to meet “vampires head-on.” First of all, the help vampire doesn’t know that they are, and probably hasn’t heard the term before. So they’re sent to Hoy’s article, where they immediately learn that they are not respected and not appreciated. They become depressed, defensive, angry, and frustrated. This comes from the same portion of the article that refers to itself as a “good resource” for someone to become enlightened to their own “vampy ways.”

Techniques for teaching positive learning strategies exist that don’t require one convey offense (intentionally or otherwise). In many cases, simply asking the person to reframe their question and directly engaging in a Socratic exercise works wonderfully. I’ve written previously on productive ways to engage in Socratic exercises without being patronizing or putting the student on the defensive. My talk on debugging and mindsets, while focused on debugging, contains general-purpose approaches for helping oneself and others learn effectively. (I created a transcript in case watching a video isn’t your thing.)

Self-awareness is also needed. Are you too tired to help? Do you need to leave in a few minutes, and you just don’t have the time to educate the person on all the knowledge that they clearly need to solve their problem? Don’t help. Seriously, just don’t do it. It’s remarkably easy to not engage with people. All you have to do is stop typing. You’ll avoid being drained, and the person will either get the help they need or not. And that was never really your problem, was it?

The article also suggests “weeding out the hopeless cases.” I disagree that any case in particular is hopeless. I also don’t think the set of people who understand the article includes the same set of people who know how to discern between a hopeless case, and a seriously frustrated individual. Certainly it’s possible to identify toxic individuals, but not everyone is in the position to eject someone from the community (and as just mentioned, those who are in that position may not be able to discern between hopeless cases). This should really be a last-ditch effort. Removal from the community is also the most obvious solution to dealing with a problem if you’re in a position of authority, so I’d have preferred it be left out entirely.

Hoy’s article finishes on a high note:

I felt the need to write this because I think that people are basically good, and basically self-sufficient in the right circumstances.

I agree with this in general.

I felt the need to write this because I keep seeing folks being called “help vampires” by others who have clearly misunderstood what (I think) Hoy intended. I believe that she is basically good, and that the article is well-intentioned. I think most of the suggestions in the article are basically good.

As far as I can tell, “help vampires” are as mythological as the real thing; experiencing someone as such is as much a reflection of the mentor as the mentee.

Today, Hoy’s article is misinterpreted and misapplied – at least in my corners of the Internet. Folks are attacked with this inflammatory label after asking a simple question once or twice. They get it applied to them for not understanding how to follow logic from A to B, when they have no knowledge of A or B. It targets neophytes by definition (as they are the most likely to ask the most basic of questions about any given topic). It discourages people who suffer from impostor syndrome by reinforcing the idea that they are somehow wasting the time of those they feel they are imposing upon. A literal interpretation of what (I hope) was intended as hyperbole throughout the article puts individuals trying to learn on the defensive, and teaches would-be mentors to identify and expect malicious intent where clearly none is intended.

I read the article shortly after it was written. I remember quite enjoying it when I first read it. I took the content as hyperbole, but I know that I irrationally called numerous people “help vampires.” And I know it colored my perception of neophytes; I had this implicit platform of knowledge that put me above these vampy creatures. Reflecting on this article after ten years, still being involved in several help and discussion communities on IRC, I feel that it might be time to take another stab at the topic of “help vampires.” And I’m curious what Hoy thinks of her article ten years on.

Because “help vampires” simply aren’t. They’re just people.

Pointers on Pointers

Thu, 13 Apr 2017 16:00:00 +0000

I’ve been hanging around in the ##c channel on Freenode (a channel for discussions about the C programming language) off-and-on for something like ten or fifteen years. One constant over that time (whatever my skill level) has been questions about pointers. They seem a topic that’s thoroughly confusing to many, especially neophyte hobbyists and autodidacts. Recently, I witnessed an explanation of pointers that involved people in small rooms, a man with a sign that points, and a magical great uncle named Merlin.

(I shit you not. No, I didn’t get it either.)

Once the person who was trying to learn was thoroughly confused, I said (tongue firmly in cheek), “Too much indirection.” Speaking indirectly about anything is confusing, especially when the thing you are trying to explain is indirection.

Much of the material I’ve seen on the Internet isn’t particularly great at teaching anything about pointers to anybody. People are already asking questions after having read their books. If 45 years of existence hasn’t yielded any obviously good methods for learning to use pointers, perhaps it’s not surprising that folks find them difficult to teach.

I’m intending for this to be part one of several posts on education about pointers. Here, I’ll discuss some (hopefully) best practices for teaching folks about them. Future posts will attempt to actually teach them.

Programming is based on abstractions. We use abstractions in an attempt to simplify, to avoid repetition, and to reuse code. This is great because we end up with reusable, generalized code – as long as we don’t overdo it. Comfort with indirection is a key differentiator between novice and expert programmers (indeed, so is overuse of indirection). Indirection is about representing something very complicated in a generic fashion, and this is a skill that is developed with experience.

Indirection is arguably the most powerful tool in software engineering. It is the engine that powers reusability, that drives well-designed software, that allows us to find patterns in complicated data, and then to derive a general solution for processing those data. This might be hyperbole, but there are few things more crucial to writing good software than a core understanding and appropriate use of abstraction.

The need for generality also isn’t immediately apparent to novices; they’ve little to no foundational knowledge upon which to build new knowledge. Thinking about abstraction in the way that skilled programmers do is not very obvious (though I believe most people do it in other ways). We need to start teaching people about indirection by first illustrating why generalization, abstraction, and reuse are important concepts when writing software.

But this isn’t always easy.

Indirection is difficult to talk about. First of all, it’s abstract. It’s difficult to discuss abstractions concretely. It’s difficult to discuss indirection directly. So we’ve invented tons of jargon to help us communicate effectively about it. Learning jargon is hard because definitions often seem circular, or at least as indirect and abstract as the concept they’re describing. For example, I’ve seen definitions of indirection that describe “going through” a variable to find a value. It makes sense once you know the thing, but it isn’t enlightening when you don’t.

Secondly, even if we did figure out some really good definitions, it’s unclear to me whether that would be helpful. We’d need to define numerous terms, and the person learning would have to learn them all individually before they stuck. Rote memorization is an outmoded, unhelpful teaching technique. And I believe it’s actually harmful here because it’s the critical thinking bit that’s important for appropriately using indirection and abstraction in software. Memorization neither reinforces nor encourages critical thinking. Far better would be for us to teach these concepts while also encouraging such problem-solving skills.

Even doing that, we’re faced with some additional problems.

Indirection in C is a shit show. There’s too much crammed into a tight spot. If you learn variables first from a very correct resource, you know that a variable is a name for storage. But then you get to pointers, and it’s not clear why there’s any difference between a pointer and a variable (because the reason is hidden behind at least one level of indirection). You have the * operator, which has three distinct meanings and has some special (possibly ambiguous-looking) behavior with the sizeof operator.

If you learn about pointers, you’ve already learned about arrays. And the first thing you learn about pointers is that they’re actually quite similar to arrays. But then you get lost because you can’t spot what that similarity is other than some arithmetic that is somehow not regular. So you try to get some answers in ##c. Bad decision. Now four people are explaining it to you differently (and at length), and it’s not long until the explanation devolves into a lengthy and pointed argument about the word “decay” and whether it implies permanence.

It’s no wonder folks tear their hair out trying to learn this. How can we as educators and mentors do a better job teaching this subject to students?

Begin at their level. Knowledge is gained, stored, and retrieved by relating new information to past experience. Be curious about what your students and mentees already know. Don’t start off by correcting invalid assumptions, either. Try to ask “discovery questions.” These are questions intended to help you to discover where the student’s knowledge comes from (and where it starts to be incorrect) so you can start teaching from the most correct level.

When you start teaching pointers, begin by teaching their motivating uses. Why would we ever want pointers? They’re a tool for indirection, and abstraction is one of the most important things in software. But since the student is unlikely to be familiar with this either, we need to provide relevant examples of where generalization is helpful.

To do this, familiarize yourself with the individual’s current expertise. For example, if your student is comfortable with math, bring up addition. What are we actually doing when we add two numbers? How difficult would it be if the rules for obtaining a result changed for each set of numbers we had to add. If your student is comfortable with languages, bring up verb conjugation. How difficult would language be if every verb was irregular? Indirection and abstraction provide us a means to think about different things and create general rules for dealing with them.

Once you’ve established a motivation for pointers, indirection, and abstraction, make sure the student really understands variables. You’ll likely need to start at this level. Make sure the student understands what variables are, and all the information they describe. You can present it as a simple hierarchical set of definitions if you like:

a variable is a convenient name for an object,
an object is storage which may contain a value and has a lifetime,
a value is information with a type,
and a type is a way to understand how to interpret the information in the value.

In my experience, much of the confusion around pointers has to do with a poor understanding of how variables, storage, values, and types work. The above list is short enough to fit on a slide, and easy enough to memorize without being tedious.

Avoid using similies. Similies are indirect comparisons. When explaining abstraction and indirection, being indirect is about the worst way to do it. Use metaphor instead. If, for example, you were relating indirection in C to mail (because you first figured out your student understood mail relatively well), a pointer is not like an address, it is an address.

In the same vein, avoid using allegory unless you’ve given your story significant thought and the premise is already one your student understands. A poor story featuring magical men holding signs elucidates nothing.

I quite like using mail. Most people understand relatively well how mail works (snail or e), at least at a high level. We already have a shared term between pointers and mail: “address.” And it’s also very much true that writing a value to a pointer is analogous to sending a message to the address. Reading a value is very much analogous to receiving a message. I think this analogy ends up working well for other fields like concurrency, networking, and distributed systems, and the fundamental reason is because it describes a method of communication which is (if you squint a little) what we are doing when we write software. It’s nice to have a single thing to use to teach multiple concepts, both for you and the student.

One would think this would go without saying, but don’t berate the student. In ##C, we have a contributor who is very technically correct, and offers a lot of good advice. Unfortunately, this person has a habit of doing so in a sometimes cryptic fasion. This person also frequently assumes knowledge. The result is that whenever a newbie is unable to follow this person’s train of thought, they’re told in colorful ways what kind of idiot they must be.

Never do this; it is never helpful. If you don’t have the time, energy, or patience to help someone learn – which must necessarily start with figuring out where you should begin teaching – don’t do it. You will be frustrated, your student will be frustrated, and your student may lose interest in learning. Of course there is the class of person who only wants the solution book… but even here, the same applies. If you don’t want to help someone for any reason, just don’t.

Similarly, don’t assume that just because a student has a book, they should be able to learn from it. I’ve seen numerous people ask, “Where’s your book?” If it’s not the right book (how were they supposed to know beforehand?), they have to get another one. This isn’t great because most books on C aren’t particularly cheap, and this assumes an ability or desire to spend a possibly non-trivial amount of money. Secondly, even with the “right” book, it’s not guaranteed that everybody will come to the same understanding from the same material. Operating under the false assumption that they should be able to do this is likely to make your student feel stupid, which will close them to wanting to learn.

Learning is the process of forming new understanding. New understanding is, very fundamentally, the relation of new information to past experience. For any given static article, book, or tutorial about pointers, there will be some set of people who can not derive the indended meaning from that work, because it has no contextual relationship to their past experience. This is precisely what makes the real-time experience so exciting! As an educator, you have the ability (and the responsibility) to figure out where to start teaching. You get to be the material that is finally successful in helping this person learn something crucial. If this is not an exciting prospect to you, it might be worth reconsidering whether you are actually interested in helping folks learn.

If you’re not interested in putting in the effort, just don’t. You’re ruining the experience for the people who want to do it, and you’re ruining the experience for people who want to learn. You may even drive people away from learning, which is just an awful thing to do. And you are making it more difficult for people in the future to help your own student.

Through exercises in patience, curiosity, discovery, and compassion, we can help people learn (and be excited to learn) even the most complicated topics. Pointers are so difficult for so many people to learn that we as educators must engage in these exercises. We need to be patient in our explanation: knowledge can’t be rushed. We need to be curious about where our students are coming from, and discover where their gaps in understanding are. In doing this, we provide them personalized context for the new information, which allows them to engage in real learning. And in being compassionate, we recognize that we also don’t know everything, we didn’t always have our own knowledge, and we show our students that with just a little effort, they can be like us.

CasTTY: Screencast your Terminal

Fri, 10 Mar 2017 00:30:00 +0000

An internet-friend has been encouraging me to put together some material to help teach people stuff about software engineering in C and POSIX environments. I’ve been wanting to do this sort of thing for some time, but the tools are always really obtuse. You have some application that captures a window and makes a video, but then nobody can really interact with the text.

But then I remembered that ttyrec was a thing. I’ve used it before (mostly to watch NetHack games), but hadn’t thought much of using it as a tool for education. A few hours of work pulling together a bunch of other peoples’ hard work, and I ended up with CasTTY.

CasTTY is a stripped-down version of ttyrec (in particular, it doesn’t care so much about portability) that aims to make creating educational “videos” easy. It comes with code to “record” a TTY and simultaneously records audio. Where ttyrec just spits out some 32 bit integers with time offsets and terminal sequences, CasTTY spits out some Javascript containing basically the same information. Audio is recorded using PortAudio.

The player combines xterm.js, rangeslider.js, jQuery, and all the new-fangled HTML5 audio stuff to make an immutable (but copy-buffer-friendly) player. I’m hoping to use this in the near term to make some slightly-interactive tutorials on programming and debugging.

Putting this together was a snap, but I’d like to give another hat-tip to the developers of all the software I cobbled together for this project. Without their software, I probably wouldn’t have done this at all.

There are still bugs and numerous features I’d like to implement, but I want to get some experience using it first. I was thinking of doing a dive into the CasTTY code as a first example of how it works – but other suggestions are welcomed!

Finally, if you’d like to contribute, there are plenty of ideas for ways to take the code. I’d especially appreciate help with the UI-side of things. I’m not very good at making things look very good.

Enjoy!

Some Updates

Tue, 07 Mar 2017 01:22:00 +0000

I’ve been avoiding updating this site for some time because I really wanted to use Tufte CSS for this site. I switched my theme to the Hugo-Tufte theme for numerous reasons. For one, I really like they layout and readability. But I’m also finding that I really want to use things like sidenotes. I’m not super happy with how those are exposed in Hugo-Tufte, but I will grin and bear it until I spend some more time formalizing a Markdown-derivative that supports such things.

After several long months, my presentation at QConSF 2016 is available to watch! I’ve also written an article for the ACM Queue on the topic in the Jan/Feb 2017 issue. It isn’t currently available without a subscription, but will be available at the issue page once it is released for public viewership.

Some new blog material is in the works. In particular, I’ve been doing a fair amount of work on searching data using finite state automata using my wonderful colleague Kate’s library, libfsm. As usual, my inputs are relatively large, so I’ve put a fair amount of work into improving the performance of the tools, and I’m pretty excited by what we’re going to use them for. A quick example of a FSM for IPv4 network space:

I’ll also be wrapping up a blog post shortly regarding pointers in C. It remains a topic confusing to many, and I figured I should try my hand at it. I’m looking forward to wrapping that up soon and hopefully writing more in the near future.

Practicing Socratic Exercises Without Patronizing

Wed, 16 Nov 2016 00:23:00 +0000

At my QConSF talk, I got a really great question:

So when you were talking about the Socratic method, how do you engage in the Socratic method without sliding into a patronizing tone, if you know what I mean?

Off the top of my head, the answer I gave focused on fostering trust. But I think this is a really important question, and I ended up ruminating on it for some time afterwards. I don’t think this was the best answer, and I think it’s worth talking about some more.

Regardless of what Socrates actually believed about knowledge, the methodology he used to help educate others stays with us today because it’s useful and it works. Briefly, it is a methodology by which one or more people intending to learn are asked leading questions about a premise. The idea is that when the “right questions” are asked, the student is able to solve the problem without actually having been spoon-fed a solution. This is fantastic for the individual(s) learning, because they get a feeling of ownership of knowledge, and the new knowledge they own is solidly based on things they already understand.

The problem encoded in this question is that it is very easy to come across as patronizing in exercises like this. And the trick here is really in asking the right questions. Start from something that is plainly obvious, and your mentee feels patronized. Start from something that isn’t at all obvious, and you risk frustrating your mentee. Figuring out what questions to ask and how to ask them is hard. To engage in a successful Socratic exercise, we really have to get this right.

Difficulties of Socratic Dialogue

Consider an online forum, or any other medium where folks are temporally present, but may not have much context into who you are, your motivations, or your expertise. If someone raises a question and is immediately met with a question in response, this discussion is unlikely to be successful. Why should anybody entertain your question?

There are multiple reasons folks may be hostile, skeptical, or otherwise adverse in engaging in such a discussion. In a sort of context-free environment, you’re operating without credentials and it’s likely folks simply don’t know who you are. If you’re an authority on the subject, this is not necessarily obvious. The people in most need of help are going to be new to the subject. This by definition means they are likely unfamiliar with who the experts of a particular field actually are, and wouldn’t be able to recognize you as one anyway.

This can be exacerbated by the fact that we implicitly categorize people asking questions as fellow learners, rather than mentors. Socratic dialogue, as old as it is, isn’t a hugely popular form of teaching. So the technique remains unfamiliar to many. If I’ve asked a question, and I’m met with a question in response, it may feel natural for me to doubt whether this person is trying to help, or whether they’re in the same boat as I am. My primary motivator is gaining knowledge to solve my problem, not to help someone else who is stuck with possibly less information than I have. Even experienced folks are likely to be similarly conditioned.

Finally, in the age of the Internet, there’s plenty of misinformation and most folks are clued in to this. Especially in the area of programming languages and technology, moderately experienced folks tend to look out for blatantly incorrect information. People who are experienced may just be looking for a quick refresher as opposed to a long-winded discussion about what they already know. These folks may be more hostile towards engaging in a Socratic dialogue for this reason as well.

Building Trust

I think building and fostering trust is the first step we need to take when communicating with anybody in any form, but it especially holds here. When engaging in Socratic exercises, we can’t just start with asking questions. We have to have some lead-in by which we engage in the discussion. One frequent pitfall I’ve observed in practicing Socratic dialogues has been the lack of lead-in.

We can start with something like, “Hey, I think I can help you with your problem, would you mind me asking you a few questions about what you’ve found out first?” This solves nearly all of the difficulties mentioned in the previous section:

You’ve established yourself as an authority by stating you think you can help with the problem.
You’ve established your willingness to help with the problem, so it’s unlikely you will be misidentified as someone with a similar problem.
You’re setting up the individual to expect questions. This allows them to see your questions as a tool for their learning as opposed to a tool for you.
You’ve provided an opportunity for someone unwilling to engage in a Socratic exercise to reply with something like, “Hey, I appreciate that, I know what I’m doing, but I’m having a brain fart right now and I really just need the name of this function so I can look at the manpage.”

If the person responds positively, it’s time to engage in a Socratic dialogue. (Although, surprise surprise, this first question already started that process!) If they’re cautious, they’ve also a chance to ask you why you think you can help.

Some people only recognize “help” as being spoon-fed answers. It’s up to you whether you want to do this or not, but either engage or disengage. There’s little point in complaining about whether a person is learning in a “proper” fashion. In fact, doing so will discredit your authority and will engender distrust from the person aiming to learn. That’s antithetical to the goal here: to build trust.

If someone is on the fence, or really wants to be spoon-fed information, continue to build trust. “Ok, well it would help me to have all of the information about where you are so that I can provide you an accurate answer. You said the problem is X. How did you reach that conclusion?”

Stay calm and collected. Apologize if offense is taken and reassure none was intended. Your goal is to educate, and being a trusted person is going to reduce the likelihood people see you as an elitist or authority figure (and therefore more likely to take offense at your help), while increasing the likelihood you are a helpful peer. Which is really what you are if you cared enough to read this article.

Avoiding Patronizing

Once we start the meat of the process, we need to be very careful to ask questions that are not just leading, they’re guiding. Unfortunately, this is also very descriptive of patronizing questions. Let’s be clear about what constitutes patronizing.

OED defines patronizing as treating another “with an apparent kindness which betrays a feeling of superiority.” (Kind of like their definition of that word.) Merriam-Webster says it is “talk[ing] to (someone) in a way that shows that you believe you are more intelligent or better than other people.”

There are two difficulties:

This is a subjective experience. With no malintent on your behalf, someone may read superiority into your tone, expression, cadence, delivery, vocabulary, or anything else you’re using to communicate.
We’re conditioned to see teachers as authority figures. This means that there’s an increased likelihood that folks will interpret superiority where none was intended, and it also means that we’re conditioned to act with superiority when attempting to mentor others.

As it is a purely subjective experience, we might be tempted to gauge another’s reactions to our questions to detect whether we’re being experienced as patronizing. But I’d recommend against that. First of all, it might require reading between the lines, which is counterproductive because it tends to add non-present information; it’s the behavior that was likely to have made you seem patronizing in the first place. Additionally, in text-only communication platforms, there are no non-verbal cues to interpret. This makes it highly likely you will misinterpret something like “hold on a sec” as an indicator of exasperation instead of as “I really need to pee” (for example). Finally, even with trust, we are likely not qualified to determine whether they can even understand the social cues and behaviors that might result in this assessment.

We’re most likely to be misunderstood for patronizing if we ask questions that have obvious answers. If we think we might be asking such a question, the onus is on us to preface it with, “I’m sorry if this is obvious; …” But this doesn’t really help if we genuinely don’t know. If a response comes back that seems exasperated, we can apologize: “I’m sorry, I’m trying to understand the problem from your perspective. I didn’t intend any condescention.” The goal here again is to reinforce trust.

Avoiding Frustration

Sometimes these exercises can go on for a long time. Learning can be an arduous and time-consuming process. This is likely to result in one or both of you becoming tired and frustrated.

If you notice your mentee repeating previous mistakes or becoming frustrated (and especially if you notice yourself becoming frustrated), take a time-boxed break. Neurologically, we are not wired to learn by spending more than a few hours on a task (which is why methods like spaced practice / segmented study work really well). Negotiate a break and a time when you can both get back to solving the problem.

Commonalities

In both cases, curiosity is crucial. We ostensibly have knowledge our mentee lacks, which is why we are in a position to help. Yet we cannot offer this knowledge in a Socratic dialogue, where we are primarily asking questions. Somehow, we need to use this knowledge to ask the right questions, and this is why we need curiosity.

In my QConSF talk, I said that curiosity “is really about understanding where your mentee or your colleagues are coming from.” Only when we are able to truly empathize with folks can we successfully employ the Socratic Method. The basis of employing Socratic methodologies should always be to understand the mentee. We likely already know the problem and the solution, but the goal of a Socratic exercise is to allow an individual to independently discover the solution (a far more rewarding experience than the “learn-by-rote” method of teaching to which we are all accustomed).

To this end, really try to put yourself in your mentee’s shoes. Don’t ask questions that are clearly within the mentee’s knowledge: this is blatantly patronizing. Don’t ask questions that are clearly outside the mentee’s knowledge: this is both patronizing and frustrating. The goal with each question should be to ask from the edge of the mentee’s ability such that new knowledge is formed with the answer to each question. Understanding your mentee’s existing knowledge, perspectives, and favorite learning methods is crucial for effectively employing Socratic exercises.

In Closing

We may be avoiding employing Socratic exercises as a learning tool in our work and education environments because we don’t wish to be condescending. Yet it is only by practicing such exercises that we can really identify how to best use this method without patronizing or frustrating others. Like nearly everything in life, Socratic learning methods are a skill, and we only get better with practice. I hope that this post can serve to help others engage more effectively in this amazing teaching tool we have to help others in their own lifelong journies of learning.

Building a Debugging Mindset

Sun, 13 Nov 2016 05:39:00 +0000

I spoke at QConSF last week about debugging. The content is largely similar to my previous blog posts on the topic, but I think more refined. I’m unsure as to when the video of the talk will be made available on InfoQ’s website. If you attended QConSF, you have early access to watch the video. However, since that may be some time yet, I figured I’d put the slides here with a rough transcript.

I love speaking and sharing knowledge. Every time I do it, I get a bit nervous in the minutes before I present. I opened this one up with a favorite joke of mine to break the ice:

An ion walks into a bar. It goes up to the bartender and says, “Hey, excuse me, I think I left an electron here last night.” The bartender asks, “Are you sure?” And the ion replies, “I’m positive!”

Today, I’m really excited to share with you a learning journey I undertook. I wanted to know why some people seem better than others at debugging, which sort of lead me to the fundamental question of why debugging is hard. What makes it hard? And the underlying motivation here was that I wanted to see how this thing that we spend so much of our time doing, that seems so difficult, how we could make that process easier.

I’m actually going to front-roll some credits for this talk, so I want to thank Inés Sombra, Elaine Greenberg, Nathan Taylor, Erran Berger, and my wife Crystal O’Dell for sitting through this over multiple iterations. And also thank you for coming. There are some really awesome presentations that I know are going on during this time, so thanks for being here.

A bit about me. I’m Devon O’Dell, it’s really great to meet all of you!

I work at Fastly; I’ve been there for about 4 years. We’re a content delivery network focused on near-real-time features like instant cache invalidation, streaming logs, live metrics, and instant configuration changes. We also provide web security and performance-related solutions for our customers.

Professionally, I started doing web development in 2000. I started mixing in systems programming (down at the kernel / hardware level) in about 2004. At Fastly, I work on our edge caching layer. I lead a team that works on performance and features. I also collaborate with other teams that build on top of the infrastructure I work on.

Now, performance and features are always really hard to get right the first time. So, inevitably, I spend a large amount of my time on debugging-related tasks.

And since I spend a lot of time debugging, I also spend a lot of time being confused. Debugging is hard because it’s confusing. And that’s really the thesis of this talk: debugging is hard.

This talk is roughly split into two acts. In the first act, I’m going to speak about why debugging is hard, and sort of finish off with what are some of the qualities that make some people inherently better at the task than others. And in the second, I’m going to discuss what things we can do to make everybody successful at debugging.

So: Act 1: Debugging is hard.

Over the years, I’ve asked folks what they think, why they think debugging is difficult, and there’s a real wide range of answers, right? Confusing interfaces, incomplete knowledge of systems, state space explosion, experience, just to name a few.

So let’s look at some of these, let’s take experience. Debugging is hard because it’s a skill, and experience ranges widely. But I know ridiculously senior engineers who seem basically “okay” at debugging. They’re not great, but they’re not bad. But I’ve also worked with novices who just seem to have a knack for it that’s sort of beyond their skill level, or what you would expect from their experience. And research shows, by the way, that there is a wide range of skill, even amongst experts, so this isn’t just me telling you an anecdote.

Experience really can’t be the only factor, so let’s look at another one.

Let’s look at confusing interfaces. I work primarily on systems stuff in C and POSIX environments these days. And for me, the mmap syscall is a really, really great example of a confusing interface. It has 6 arguments; I can never remember the order – because it’s not really logical, none of them sort of follow from the other. I don’t actually know any syscalls that have more arguments that I can think of off the top of my head.

One of the arguments is a bitmap of flags. Now POSIX specifies three or four, but on Linux, you have like twelve. Other systems have more or fewer.

Mmap can return at least seven different kinds of errors, and one those errors can happen for four completely separate reasons.

So mmap is hard because I can really never remember how to use it, how it fails, and this really means that I’m constantly referring to the manpage every time I need to use this interface. And when I have to debug it, you got it: back at the manpage.

So these aren’t really satisfying answers: experience or confusing interfaces. They don’t really give us the whole picture. And it seems like there’s something more fundamental going on about the difficulty. So to figure out what to do about the difficulty, I thought I needed to understand why it was difficult, fundamentally. So I kept looking, and I thought that some of the answer would lie in the history of software engineering.

So I went way, way, way, way back. In “Memoirs of a Computer Pioneer,” Maurice Wilkes talks about his experience programming the EDSAC (at Cambridge, I believe) in June of 1949. And now, at this time, nearly nothing about software development was obvious. And at one point, Wilkes relayed this powerful realization he had that he was going to spend a large portion of the remainder of his life finding errors in his own programs.

Now, debugging is hard because it’s not obvious. If we think back to when we first started programming, it wasn’t ever obvious that it was going to be hard to figure out what went wrong, or even that things would go wrong in the first place. Programs were just these sort of magical things that mostly worked. And when they didn’t, we thought it was our fault.

Bugs also have a connotation of failure. And Wilkes, in the full context of his quote, sort of gives a hat tip to this. I think this connotation has sort of led us to a culture of half-joking about how we make terrible decisions about the design and implementation of systems and interfaces.

Debugging is hard because we’ve created a self-deprecating culture around it. So nobody actually wants to do it. And I think that’s tragic, because as other people in this track before me have said, we learn from failure. So every failure is at least a partial success.

Ok, so let’s fast-forward twenty-five years. In 1974, Brian Kernighan and P.J. Plauger publish the book “The Elements of Programming Style.”

And in this book, Kernighan introduces this quote that I think many of you may be familiar with:

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?

Now taken at face value, this is pure rhetoric. All it says is that debugging is hard and we’re not clever enough to debug our cleverest solutions. And this is actually how I see this quote used most often in context: as a joke, in jest. Again with the self-deprecation.

But I think it says something more. What if we looked at this question as a challenge?

This leads me to much more fundamental questions about the conjecture and the premise. Is debugging really twice as hard as programming? If so, why? And how will we ever debug these programs?

Let’s just take as a given that debugging is twice as hard as programming. Where might we learn more information about how to apply that practically?

One place I found answers is an area of positive psychology pioneered by Mihaly Csikszentmihalyi; the concept of Flow. We all intuitively know what Flow is, it’s this feeling of being “in the zone.” Everything else is shut out and you just get stuff done. You look up at the clock, hours have passed. You just feel good. We feel our most accomplished, our most productive, and our most fulfilled in our jobs or the activities we’re engaging in when we’re operating in this Flow state.

Now, “Flow” is actually the technical term for this, even though it sounds a little “watery.”

I do want to say that tying Flow to debugging isn’t an original idea of mine. I got the idea from Linus Åkesson, who wrote a blog post specifically tying it to Kernighan’s quote.

But basically, let’s say we’re debugging a problem. We can plot that task on this graph based on the bug’s difficulty versus our debugging skill. There’s this area in the middle that represents our Flow state, and this is where we’re going to be our most effective and most engaged in solving the problem.

However, if the bug falls below that Flow state, what happens is we feel bored or apathetic. Maybe in some cases relaxed, but we’re never really engaged in solving the problem. Now, if some task is too hard, it’s above our Flow state, and we might get frustrated or worried or anxious solving the problem. You might not be able to hit a deadline or something.

Practically, this actually gives us a choice. We can a priori optimize our experience either for debugging or for implementation.

So if we implement below our Flow state and debugging is twice as hard, we’re optimizing to be able to debug in Flow. However, this means we’re going to be bored writing our code, because we’re not that engaged.

If, on the other hand, we implement in Flow state, we get frustrated and anxious debugging outside of our skill.

So what choice do we make here? Most studies I’ve read seem to find 50% of the time spent in the software development lifecycle is on debugging-related tasks. I’ve actually seen studies that state as high as 80%. So if we’re spending an absolute minimum of half of our time debugging, you might think we should optimize for debugging in Flow. Implementing below Flow.

But I want to challenge that here; I want to encourage implementation in Flow. And one simple, but absolutely crucial reason for this is that to gain skill in an activity, we have to practice at the edge of our ability.

So for example, I’ve played guitar for twenty-five years. And I suck.

And fundamentally, this is because I rarely challenge myself. I learn some song or – the coolest thing I ever learned was some sweep picking pattern, and I can’t even do it very fast. But I rarely challenge myself to do something new. We don’t get better at guitar by playing one chord or plucking one string time after time after time. In fact, I don’t think that would even help us master that chord because you’ve got to do transitions in and out of it, et cetera.

So to gain skill, we really have to practice at the edge of our ability.

For debugging, what this means is that we have to learn something new. And since learning involves teaching to some extent, I thought I might find some answers to my questions in the area of the pedagogical aspects of debugging.

Debugging actually turns out to be hard because we don’t teach it. There are lectures embedded into some courseware that I’ve seen, but as far as I’m aware, no universities are actually teaching full courses on the subject. I think that needs to change. I think industry is actually in a place to ask for that change from academia.

Even so, there’s been plenty of research into teaching it. My hands-down favorite paper in this area is a 2008 literature review from Renée McCauley and like six other folks. And what it does is survey fifty-two papers from 1967 to 2008 and its trying to gather – sort of collate – all the information on how debugging is taught, what’s working, and what’s not.

Most of these papers end up being about the classification. So the who, the what, the when, the where, the why of bugs. And what I was really interested in, the how. Right? How do we solve it?

Unfortunately, after reading tens of papers, nothing I read actually had conclusive, positive results that we can help people get better at debugging through teaching it. So. Back to asking questions.

And why not go to the root cause? Why do bugs happen? We know specific reasons: off-by-one errors, race conditions, buffer overflows, whatever. But these are actually just classifications of related types of failure. They’re not explanatory. And the key reason that I love this paper is that it goes through the literature and gives us a single, generalized, and I really think correct answer about why bugs occur.

It says that bugs occur due to “chains of cognitive breakdowns that are formed over the course of programming activity.” That sounds ominous, right? But what does it actually mean?

So it means that debugging is hard because we don’t know, and we can’t possibly know everything. For any moderately complex system, we can’t possibly know all of it. So we create mental models about how the system behaves. And these are effectively assumptions and the goal is to provide a foundation to us to accurately reason about the behavior of these systems as we execute them, as we make changes, and as we debug them.

We actually need to do this even for the simplest software. We take it for granted because of experience, I think, but really think. Just take a second to really think about everything that has to happen under the hood for “Hello, World!” to work in any environment.

Our gaps in knowledge can lie anywhere from our editor, our compiler, our runtime environment. Our filesystem. Kernel. Hardware. Physics, if we’re dealing with latency-sensitive applications. Debugging is hard because we have so many opportunities to lack knowledge, even for very fundamentally simple problems.

And I think this answer, that we necessarily lack knowledge really gets to the core of why debugging is hard. I think it actually shows that Kernighan is right, that it is actually harder than programming.

If you don’t agree, think of it this way: writing software requires us to use existing knowledge to solve a problem. If we’re writing new software, we may have to learn something new, but we typically front-load this into our process with technical design, reviewing API documentation, et cetera. That happens before we really engage in writing full systems in code.

Debugging on the other hand requires us to gain new knowledge to solve a problem that we already thought was solved correctly. And this is harder because we by definition don’t know where we went wrong. And so, I think this roughly proves Kernighan’s conjecture.

Now, I mentioned none of the research had conclusively positive results in how we teach debugging in order to help people get better at it. And maybe that’s why we don’t teach it: we don’t know how. But in that 2008 paper, it was recommended that future studies into teaching debugging look into some work from Carol Dweck. She published a book called “Self-Theories” in 1999, there’s also a sort of pop-psych version called “Mindsets” that some people may be more familiar with.

Anyway, this 2008 paper suggests we might find some promising results there. And I do want to note that a later paper – or some later papers – have actually seen successes in teaching debugging, incorporating this stuff, which is why I got interested in it.

So Dweck’s work includes over 40 years of what I think is just absolutely fascinating scientific research that unfortunately I don’t have time to cover in detail. But if this sort of hooks you a little bit, I will talk about it for years. If you read one reference from this talk, and at the end I have reference slides in case you’re interested, I do recommend reading this book. It’s not that long.

In a nutshell, her work says that an individual’s view of intelligence falls on a spectrum – somewhere on a spectrum – of intelligence being an inherent trait versus a developed skill. And actually where a person’s view falls on this spectrum says quite a lot about how they solve problems and their motivations for solving problems.

So what does intelligence have to do with debugging?

Debugging at its core is all about solving problems. Since this research addresses how and why folks are actually doing that, I think it turns out to be a really great proxy for talking about debugging.

People who have an idea that intelligence is an inherent trait, you can’t do much to change it, you’re sort of born with it have a fixed mindset. And people who think it’s a skill, it can be developed, it’s malleable, you can grow in your intelligence, are said to have a growth mindset.

And it’s specifically the traits and the motivations and the behaviors of people operating on one or the other side of this spectrum that makes this relevant to debugging.

Debugging is hard in a fixed mindset. If you can’t change much about your skill at debugging, why try? So fixed-mindset individuals don’t tend to take on challenging problems. And this also means that fixed-mindset individuals stagnate in their skill. If you remember from earlier when we were learning about Flow and debugging, to get better at a skill, we have to practice at the edge of our ability, and fixed mindset individuals avoid this, because they don’t take on the challenging problems.

People operating in a fixed mindset are also more likely to cheat. Now, that sounds very academic, how do you cheat writing software? Well, think for example of folks who cargo-cult some code off of StackOverflow and put it in because it answered some question they were asking about how to do a thing in their software. They paste it in without understanding the code, the edge conditions, how it’s designed to work within a system, and maybe they don’t even give attribution. So now when there’s a gap in their understanding (which is I would assert a complete gap because otherwise they would have just written the code themselves), they can’t even figure out where that solution came from.

So why would anybody do any of this? The fixed-mindset individual is motivated primarily by appearing smart. This means they tend to compete with others in collaborative situations, like pair programming. This makes debugging more difficult because they don’t do this collaboration, they don’t ask questions, they’re trying to outperform. Because appearing smart is a motivator for them, they see failure as a failure. They don’t see it as an opportunity to learn. And to make matters even worse, failure will actually negatively their future performance when they’re working on problems that fall within their concrete, foundational skill level.

The growth mindset is basically the opposite of all of this. Growth-oriented individuals are fundamentally motivated by hard work and tackling challenging problems. And this is because they see it as a way to gain skill.

They work well with others in collaborative situations; they’re likely to ask questions therefore. They’re usually enthusiastic to impart their knowledge and help mentor others because they also learn through teaching.

Debugging is hard, but all of these traits make the task easier for the growth-oriented individual. And this gives us some insight as to why some people seem to be better at it than others. It’s as simple and fundamental as their motivations for solving problems.

So that’s a lot of information.

When I got to this point in my research I had a ton of questions. I still hadn’t learned anything about how we get folks interested in practicing at the edge of their ability. Can we move people from fixed to growth mindsets? How can we effectively develop our teams to solve the problems that they’re always facing?

So now we’re in act 2, and we’re gonna explore some techniques we can use as mentors and as individuals to improve our skill and to make the technique of debugging – the experience of debugging – less painful for everybody. I want to note that while I’m going to tie these techniques specifically to debugging, I think they all generalize very nicely; we can use them in other areas of our lives as well.

Creating growth-oriented teams starts at hiring.

When we’re looking at resumes, provide some additional screening for people who are clearly touting credentials. Who focus on individual achievements without trying to tie this to the global benefit of the solutions they provided. These folks are more likely to operate in a fixed mindset.

People who like to explain in detail how they worked hard to solve a problem, what’s challenging them right now, what they’re learning: these are folks who are more likely to have growth-oriented thoughts towards work and debugging.

And so in interviews now, I ask, “What are you working on or learning right now that’s really challinging you, that you’re finding difficult?” Fixed-mindset people don’t tend to have a compelling answer! They don’t want to admit there’s something that they don’t know. Now, growth folks will answer this question forever, so you need to time-box it.

I do really, really, really, really specifically want to note that we shouldn’t exclude fixed-mindset individuals from hire. There are a number of super-compelling reasons around diversity and what types of folks are more likely to develop a fixed mindset (specifically women and minorities). This is sort of culturally enforced, but I don’t want to get too much into that so I’ll talk about that more afterwards. But just as good a reason is that we can actually promote folks into a growth mindset.

This can be as simple as changing the words we use when communicating with people. Dweck’s research actually repeatedly shows that praising people for being smart results – reinforces a fixed mindset and all the negative that comes with it. Praising hard work, on the other hand, reinforces the motivation to work hard. It recognizes the effort put into work, and it promotes a shift to a growth mindset for someone who’s not there already.

When we praise folks for being smart, we’re actually robbing them of the recognition of the time and effort they spent solving problems. So the next time your team member solves a particularly hairy bug, praise them for their hard work. For their effort. And if someone calls you a genius for doing the same, deflect that assessment. Because they way you respond can help move that person away from their fixed view of your ability into a growth-oriented view. So you can reply with something like, “Thanks for the compliment! I’ve actually just done this kind of thing a lot.” Or, “I have a lot of experience in this area.”

Once we’ve created and promoted growth-oriented teams, we need to nurture and support their success. And one way to do this is by encouraging curiosity. Encouraging learning. When mentoring folks, we also need to be curious. What does a mentor have to be curious about?

So for example, I was explaining issues of debugging concurrent systems to a team member recently and used some metaphor (it doesn’t really matter what) to describe how concurrent processes interact with shared mutable state. My colleague reflected a completely different metaphor back at me. My first hunch was to toss it aside, because it didn’t immediately make sense to me. It wasn’t how I was internalizing the view of this system. So I wanted to correct this person.

But after some further thought, I realized that the new metaphor was perfectly fine, it just wasn’t what I was using. And this is what I mean by being curious: be open to new ideas, to new solutions, to new methods of actually thinking about things.

Because there’s many paths to get to knowledge. Our own intrinsic views aren’t the best for everybody. People want to base new knowledge on existing knowledge. It provides them an already-understood foundation on which to build. So being curious is really about understanding where your mentee or your colleagues are coming from.

If we’re encouraging curiosity, we should expect to answer questions; we should ask questions. Asking questions about someone’s past experiences and solutions to problems is a really effective way to learn. And when I was first learning to debug, I didn’t even know what to ask. So I started with, “How do you debug?”

And one frequent answer I’d get was, “Oh, well, debugging’s more of an art than a science.” Is that true?

Uh… debugging is part of computer science, which is science, and computer art is something very different. So I think this is a B.S. answer.

I think the reason that we think debugging is an art is actually a privilege of experience. As we gain experience, we forget what it was like to learn a thing, and we forget even more the more experience we gain. Giving this answer tacitly allows us to avoid remembering. It acts as a scapegoat for not actually having to teach anything to anybody. Finally, this answer also reinforces the idea that debugging is not actually a science.

And that’s not great because the scientific method is a collection of techniques specifically designed for the acquisition of new knowledge. Which is exactly what we need for a task that requires us to gain new knowledge.

As a quick review: we observe a problem, we develop a general theory about the problem. We ask some questions, gather some data about that theory. We form a hypothesis, we test the hypothesis. Now science is in this sort of regard a Bloom filter. Because if our tests succeed, we might be right, and if they fail, we’re definitely wrong about something.

But in practice, I notice that we skip steps.

So for example, let’s say our software crashed, and we look at memory, and it’s garbage. And we say, “Ah-ha-ha-ha! This obvious memory corruption.” And we start looking for and testing that.

But that’s not a hypothesis, it’s a general theory. And because it’s a general theory, it’s also wrong sometimes. And so we end up calling it a heisenbug because we’re uncertain when it happens, even though the actual problem is that we don’t understand why it happens.

The root cause here is that we skipped some of the steps. We skipped the steps of creating and testing a hypothesis.

Furthermore, memory corruption is usually a symptom of something else, at least in my area. Something like wrong buffer sizes, off-by-one bugs, wild pointers, use-after-free, race conditions, any number of other things could actually be a cause for corrupted memory.

So we end up debugging symptoms instead of causes. And if we were looking for something specific, like uninialized variable or an off-by-one instead of “obvious memory corruption,” the heisenbug effectively ceases to be so uncertain.

We can avoid all of this simply by creating and testing against a real hypothesis. Now, a hypothesis is a testable and falsifiable statement like, “An uninitialized variable causes us to write past the end of some object, corrupting adjacent memory under some very specific conditions.”

Reproducing the problem with tests is a crucial part of the scientific method as applied to debugging. This is how we test our hypothesis; we need to reproduce issues. Following this process not only makes debugging less frustrating, it actually makes it easier the next time around because all of a sudden, you can intuit causes from your new experience.

That’s all well and good. But sometimes we don’t actually have enough information to ask intelligent questions about the data that we see to help us form a hypothesis. So what do we do then? We might not even know the causes for memory corruption.

The Socratic method is a fantastic way to build understanding in a collaborative fashion. It works hand-in-hand with the scientific method because its goal is to identify and eliminate hypotheses that lead to contradictions. And it’s based on the idea that people build new knowledge from existing knowledge, so it explicitly promotes curiosity.

The circular flowchart I’ve drawn here is an illustration of how a group process called “the Socratic circle” is designed to work. Starting from some existing knowledge, a premise is introduced by the person who is aiming to learn. A mentor then asks questions about this premise, and a discussion ensues. The mentor is guiding the discussion through questions, not through providing answers. The mentee is the one providing answers and making statements about the questions.

This can lead to new questions, at which point we repeat the process, but it’s repeated until some new knowledge is formed… at which point that becomes existing knowledge, and we can repeat with new premises.

A really key benefit here is it allows a mentee to discover knowledge, to really own it. Isn’t it really great to feel like you’ve discovered something new?

It’s so much better than this typical, learn-by-rote method of teaching that we all sort of think of as teaching, where all glory belongs to the teacher, to the mentor. Owning new knowledge feels really great for the person who is learning, and it absolutely helps to build and solidify strong teams.

The next two techniques I’d like to share with you, I learned from Allison Kaptur. Active recall – I think she calls it something different, I don’t remember what she calls it; I call it active recall – it’s the process of actively trying to remember the answer to a thing that you don’t think you know. Flash cards. We all think they suck, but maybe we’re just not using them properly.

For example, as applied to something real, remember at the very beginning of this talk, I was ranting about how mmap is confusing and I’m always looking at the manpage? Well, instead of looking at the manpage, I can use active recall. And what this means is that I try my hardest to write the line of code to consume the interface and its errors. (Or lines, if I’m consuming the errors as well.) I just do that to the best of my ability. As I think it works.

And then regardless of whether I’m right or wrong, I can check my answer, because I have a manpage that tells me. So I can actively work on trying to remember what the answer to a thing is before I do the checking. It’s completely harmless. I wouldn’t necessarily recommend doing this in production, but it’s harmless like 99% of the time or more.

In addition to being a really excellent personal exercise, we can also practice this with others on our teams. It fits in really nicely with the Socratic method. So for example, the next time somebody comes up with a bug and they say, “Hey, how did this happen,” you can say, “Well, what’s your understanding of the bug right now?” This engages in a Socratic dialogue and forces them to recall their knowledge of the system and the conditions of this bug and what they think.

Another technique I learned from Allison is spaced practice. The idea here is that when we learn new information, our brains need time to process it, or sort it, or whatever makes sense for you to visualize how we retain information. If we spend too much time adding new, related information (like in a 40 minute talk), our brains don’t have time to do the background processing they need to really let that information sink in. I’m not a neuroscientist, so apologies, that hand-wavy thing is about as good as I’m going to get here.

But spaced practice is the idea of switching between different tasks to allow this processing to occur. Different unrelated tasks.

So for example, think of the last time you spent and entire afternoon staring at a debugger. It’s really easy for us to get engaged in these sort of sunk-cost fallacies about our work, where we spend additional time – more and more and more time – debugging despite diminishing returns for our effort.

If we put the problem away for a few hours or overnight, frequently we have a workable solution the next time we come back to it; I think we all identify with this.

What we can do about this is to have one or two additional items to switch to through the course of the day. Do go eat lunch. Do take breaks. Go home. Go to sleep. Give yourself the personal resources that you need to finish the challenge, and really encourage your team members to do the same thing.

Especially if you’re in a managerial role: it’s extremely important because most people won’t ask for something from you. It’s extremely important for you to explicitly allow people to just let something go for a little while. Especially when they’ve worked really hard for a really long time and they have basically nothing to show for it.

What spaced practice doesn’t mean is putting problems to the side and giving up when you encounter a challenging problem. Persevere through difficulties. Challenges are opportunities to learn something new, to gain skill. If you need help, ask for it and be available to others who need your help. Help them persevere by giving them effort-based encouragement. By engaging in Socratic exercises to solve their issue. And when appropriate, by givin them space to let something go for a while, give them something else to work on.

And maybe even something easier. That’s not really promoting a fixed mindset, because what it does is it gives them a win. And after a really big failure, even a small win makes a huge difference psychologically to people.

So I think we’ve seen that debugging is fundamentally more difficult than programming. There are things we can do to make it less awful. And I think if we go down to it, the change needs to start in our culture.

Engineering culture has this sort of romance with the idea of “smart.” It starts with our language, we praise people for their “genius” or their “intelligence” instead of their effort, or the outcome. But our jobs are all fundamentally effort-driven.

We engage in fixed-mindset assessments of our peers. We engage in activities like hero worship: “Linus Torvalds is a god” (regardless of how you feel about him). Despite that we do this, our heroes are actually pretty similar to us. And if they have a skill that we don’t, we can get to be like them with just a little bit of effort and education.

Our culture doesn’t sometimes promote the tools we need to stay in our Flow state. Or to develop a growth mindset. We convince ourselves and others that deadlines mean that we need to discard processes like the scientific and Socratic methods, despite the fact that the time you spend using them actually saves you time in the long run.

We interrupt people with pop-up notifications in Slack, with trivial things that could have been solved better in email. Our culture doesn’t do a lot to promote the soft skills that are required to really be effective at debugging, and as I would also argue, anything to do with actually programming.

So let’s change this.

Regardless of whether you’re a manager, a mentor, a lead, an architect, an individual contributor, recognize and praise people for their effort. Congratulate hard work, not genius. Recognize and promote the idea that failure is not negative, it’s part of the learning process.

Be curious, be scientific in your work. Encourage learning and skill development, whether that’s through the Socratic method or curiosity. Through active recall. Or through sending folks, sending your employees, to conferences like this one where they can learn something new.

Give yourself time to digest information by taking breaks. Don’t interrupt people, don’t interrupt yourself with trivialities. Teach folks from what they know, not from what you know.

In closing, I want to re-assess Kernighan’s conjecture and his question.

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?

We’ve learned today that there’s no absolute, objective difficulty to debugging. We also now know that Kernighan is correct: debugging the most difficult problems – the hardest problems – is always going to be harder than writing our cleverest code. But by adopting these processes, by adopting and promoting a growth mindset – the debugging mindset – we can now definitively answer his question of how we will do it.

Thank you.

Here are my references for those of you who care. I have 12 minutes for questions if anyone has any.

Hey. Great talk, you mentioned this earlier in your talk and I was curious to know why you think minorities, in particular females, would fit more into a fixed mindset, and what is encouraging that behavior.

Yep! So this actually comes from another – the first paper I read trying to tie Dweck’s stuff to computer science. And at least in the United States this is true, but I think our culture is similar enough to other Western European cultures – and just sort of patriarchal, right?

And so what’s actually true is that high IQ girls in elementary school – so up through grade five – outperform every other group. But because of sort of socially and culturally imposed ideas like “women should be pretty, not smart” or “best to be seen and not heard,” these things are reinforced. And these things actively promote a fixed mindset.

And so, because of these cultural pressures, women are more likely to develop a fixed mindset. What you see is these high performing girls in fifth grade, all of a sudden they get to middle school and their grades go down a cliff.

The idea behind what they were saying in this paper was that this even goes as far as to explain why in computer science (and maybe STEM in general) you even see the discrepancy in gender balance in the enrollment level. Women don’t enroll in C.S. as much as men. And they tie that back to this because everything about computer science, and especially debugging, requires a growth oriented view.

So if you don’t have that, and you think you can’t solve these problems, and you’re engaging in a field that’s constantly asking you to solve something hard and outside of your skill level, you just don’t. You switch to something else.

So that’s where that comes from. I don’t think there’s anything inherently true that says it has to be that way. And this is where I’m coming from with starting the change in our culture.

So when you were talking about the Socratic method, how do you engage in the Socratic method without sliding into a patronizing tone, if you know what I mean?

Yeah, that’s really hard. So, to be honest, most of my experience with this is on IRC and so people are just going to take things how they take them. So in like help channels like ##c on Freenode, or #freebsd, or other channels that I’m involved in or have been.

I think it gets back to what some other folks in this track have said which is that it requires trust. If you have a good relationship with the person you’re involved with in this methond – or the people you’re involved with in this method, you end up having this trust. Trust that your questions are genuinely curiosity-driven.

Also one thing I didn’t really touch on is that it can feel patronizing, but it isn’t necessarily experienced that way. And one of the reasons we might be concerned about that is that these aren’t really behaviors we’re engaging in frequently with our colleagues or even with ourselves. But, getting again back to neuroscience, there’s neuroplasticity. The more frequently you engage in some behavior, the less weird it becomes.

And so I would suggest if you’re engaging in this exercise and you’re concerned about that, be up-front about what you’re doing, at the head. Say, “I’d like to try this activity with you… it might come across…” – and we can all sort of tell if we’re sounding like an ass, so just don’t sound like an ass, but, “I’m not trying to be condescending and I’m not trying to be patronizing, but I’d like to try this method with you, would you engage in it with me?”

And from there, I think you’ve kind of gotten rid of that sort of stigma, maybe.

Hi, so you talked about a couple of methods like taking breaks, working on a couple of different things to kind of give people that space to grow. What I’m curious about is in a very time-critical scenario – servers are going down, you’re hemmoraging value – what other approaches would you take, or how can we apply that in a way that sort of tightens that loop and keeps people focused.

That’s a really good question that I would have suggested you went to my colleague Lisa Phillips’ talk this morning on how we run our incident command. And actually, fundamentally, it follows a lot of these same principles. So she’s actually VP of our ops department and she’d be able to explain – I’m just a lowly engineer slash tech lead – whatever I am.

Provide support for people outside the context of what they’re doing. So we have incident commanders who delegate tasks, specific tasks, who consume information from folks, who ask people if they need bathroom breaks or rest breaks or food breaks – who will order food for them. It really gets back again to some of the bits of spaced practice where you need to really give yourself the personal space to honor your body and your mind. I mean, without sounding too granola, I hope.

But these are things that you physiologically need, and when you don’t get them, your performance diminishes. So it is always better, in fact I would argue you should be doing all of these things especially in those activities, because if you’re not, you’re more likely to F-up if you don’t have your needs met.

I have seen, and you can see, some developers are really good at attacking a problem in some way, and others may take a while. Is that aligned with because they are fixed mindset versus growth, or is it something just because of experience and an individual’s expertise?

The mindset research doesn’t say anything about actual skill at any point in time. It just talks about motivations and approaches. So I don’t think you could derive mindset from that. But there are questions you could ask about a person and about their view.

So fixed-mindset people will say things like, “I just…” and, “I can’t” and stuff like that, and so you can observe that through the way they communicate with you. I don’t think you can observe it through how they do their work, or how long it takes them.

You might be able to observe it in how they approach problems. Do they try the same thing frequently expecting a different result? That maybe gives a better idea.

VarnishCon Video and QConSF

Sun, 21 Aug 2016 05:39:00 +0000

I wrote earlier about my talk at VarnishCon 2016. A video is now available of the talk.

Unfortunately, I think I did a particularly poor job of conveying irony (especially at the end: “I did you all a huge solid”), which I regret. Also, time constraints meant that I had to skip some of the points in applying the information, which I think made some of the talk less than useful for folks who didn’t chat with me afterwards.

I hope folks can look past that, and I’d be happy to answer any lingering questions about my talk via email or whatever medium.

In the same vein, I’ll be speaking at QConSF this year on a similar topic! I’m hoping to make this talk a little more actionable, while focusing more on Dweck’s research, the scientific method, teams, mentorship, learning, and even neuroplasticity.

If folks have thoughts / opinions (as if anybody actually reads this) on what I could do better from my previous talk, I’d love to hear it!

Debugging: Psychology, Theory, and Application

Thu, 23 Jun 2016 00:23:00 +0000

I spoke at VarnishCon 2016 on debugging. A small portion of the content was related to Varnish, but about half of the talk focuses on research into debugging. Though I have made my slides available, they’re not very useful without speaker notes (and I ended up ad-libbing a fair bit more than intended). This post is an attempt to provide a reference material for the ideas in the talk as well as to expand on some points I didn’t have time to cover.

Theory

Debugging, if we’re honest about it, is simply another word for problem solving. We’ve all been doing this since seeing word problems in our basic school math education. “If Levar has 3 apples and Melissa has 2 apples, how many apples do both Levar and Melissa have?” Debugging isn’t that dissimilar: the only thing missing here is that formulating the question we have to solve isn’t actually part of our education. Given the word problem above, debugging would be like showing kids a picture of Levar and Melissa and their apples. They’d be asked to create a word problem that could be solved to determine the total number of apples, and then to solve that problem. It’s easier said than done, but there are things we can do to make debugging easier for ourselves and for others.

Impetus

Why does any of this matter? Certainly we spend time debugging our software, but eventually this just becomes part of the process.

Personally, information in this area is currently extra interesting. I have a new role as “Tech Lead” at Fastly, where my primary objective is to help other members of my team succeed. Without a good idea of what success looks like or how to get people there, I can’t succeed in this. It would follow here that either they succeed and my role is obviated, or they simply don’t succeed. I’d prefer for success all around.

But there are reasons that everyone should care regardless of their role in an organization.

A 2013 study (PDF) conducted by the University of Cambridge Judge School of Business concluded that the estimated total cost of debugging globally reaches $312 billion. Their study also finds that 49.9% of programming time was spent on debugging activities (“fixing bugs” and “making code work”). Other studies find that the proportion of debugging to coding time is as high as 80%.

This implies that if we can reduce the time it takes to “fix bugs” and “make code work”, we can save our employers money. If that doesn’t sound rewarding for some reason, we can also spend more of our time working on new code, which is quite often a more rewarding exercise than staring at that damn bug for 8 hours a day.

The Root of the Problem

As soon as we started programming, we found to our surprise that it wasn’t as easy to get programs right as we had thought. We had to discover debugging. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs. —Maurice Wilkes, 1949

I think we’re all sympathetic to Wilkes’ discovery. Indeed, we all individually “find out” that it’s not as easy to write software as it first appears to be. “Just tell the computer to copy this thing there,” we naïvely speculate. “How hard can that possibly be?”

25 years later, we have an indicator for how hard it is. In The Elements of Programming Style, Brian Kernighan famously states:

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?

First, we should understand that in context, this quote is illustrating that we really shouldn’t be trying to outsmart compilers in the name of optimization. Expressing our problem as simply as possible is beneficial to others reading the code. And as it turns out, it is usually beneficial to compilers.

That said, there’s still a strong, unsupported conjecture here: that debugging is twice as hard as programming. Is this really true? Should it be true?

I don’t have a good feeling for the order of magnitude of difference, but I feel that debugging is necessarily more difficult than programming. The rationale here is that a bug is generally indicative of a piece of software behaving in an unexpected way. This lack of expectation translates directly to some unhandled case in the software. When software is sufficiently well designed, we can deduce that such unhandled cases were unhandled because they were not understood (as opposed to being understood but forgotten).

Certainly, some bugs are indicative of forgetfulness. But these cases of misunderstandings and ignorance are fundamentally more insidious when dealing with software bugs. If we work on well-designed software, and we encounter a bug in it, we are operating without the tool of knowledge, which is a thing we did have when we were writing the software.

Whether this makes debugging exactly twice as hard as writing software remains ambiguous, and would be worth a quantitative study. But we can probably safely say that it is harder. From this, it is clear that if we are operating at the limits of our knowledge and ability, to debug code, we must extend the limits of our knowledge and ability.

There are other interesting things we can read into this quote. One is that when we’re debugging software, it’s usually not software we wrote ourselves. The software industry is overwhelmingly collaborative, and very few popular projects or professional endeavors receive contributions from only a single source. This means that to debug most code, we actually have to extend our abilities and knowledge past those of our colleagues and peers.

Intuitively, we know that this is a solveable problem. Whether you’ve been in a computer science course for a semester, gone through a code bootcamp for a few months, or practiced professionally for more than twenty years, you’re better at writing code than you were when you started. You’re more clever. And you’re better at debugging than when you started.

So how will we ever debug this clever code? How will we extend the limits of our knowledge and ability? Simple: we have to learn more.

Flowing Along

Clearly there’s another way to interpret this quote. Instead of seeing it as a conjecture preventing us from debugging complicated systems, we can look at it as a platform we can use to raise our ability.

Linus Åkesson calls this platform “Kernighan’s lever”. Linus notes:

By putting in a small amount of motivation towards the short-term goal of implementing some functionality, you suddenly end up with a much larger amount of motivation towards a long term investment in your own personal growth as a programmer.

Linus then builds on top of Mihaly Csikszentmihalyi’s work on the psychological concept called Flow. The whole book summarized is that “flow” is the name of the state you get into when you are fully immersed in a task such that you find it difficult to be distracted, lose track of time, and gather great enjoyment from the process. Furthermore, this state only occurs when you’re taking on a task that matches the limits of your abilities. The book goes on to talk about practicing achieving Flow state, mostly by repeating the thesis. Csikszentmihalyi’s TED talk on Flow is more digestable.

Anyway, Linus observes that when this concept is applied to Kernighan’s quote, there are two consequences. If we want to optimize our experience for debugging, we have to implement code below our ability — but this is tedious and boring. If we want to optimize our experience for writing code, we have to debug above our ability, but then debugging is frustrating. Making a decision between tedium and frustration seems counter-productive as well.

So in this model of learning more by implementing outside of our ability, we are necessarily frustrated at least part of the time. If we make the tradeoff to never do this, we don’t learn more. I wanted to see if there was any academic research on debugging, how it’s taught, and how we learn to get better at it.

Reading Papers

It turns out that there’s been a fair amount of research into many areas of debugging not directly related to tools and automation. Debugging: a review of the literature from an educational perspective (PDF) from Renée McCauley, Sue Fitzgerald, Gary Lewandowski, Laurie Murphy, Beth Simon, Lynda Thomas, and Carol Zander provides an excellent overview of the research on the pedagogical aspects of debugging, reviewing materials from as early as 1967 through to 2008. I’d like to stress to researchers that this sort of literature review is extremely useful to practitioners and to other researchers who aren’t quite sure where to start.

In the literature, much of the research from 1980 to 2008 focuses on classification of programmers based on skill level. Nearly all of this classification research relies on the Dreyfus model of skill acquisition (PDF) or a simplified form of it. In particular, this research tends to compare programmers of “novice” and “expert” skill levels and figure out what abilities the expert has that the novice lacks.

The pedagogical research here then looks at whether it is possible to teach these skills to novices. Though several papers claim success (notably Chmiel & Loui in 2004), I find the success criteria dubious. For example, Chmiel & Loui write:

From these observations, it appears that the improvement in debugging time shown by the treatment group over the control group is directly related to their completion of the debugging exercises rather than differences in aptitude or in program design skills. Students who completed the debugging exercises spent significantly less time debugging their programs than those who did not complete the exercises.

However, some of the previous observations include:

Although the treatment group spent a smaller percentage of time on debugging than the control group, this statistic does not show whether the treatment group also spent less actual time on debugging the programming assignments.

And

Students in each group were not consistently spending the same amount of time on each assignment.

And

We analyzed the exam scores of students in each group to determine whether there was a difference in aptitude between the groups. …[T]here was no noticeable difference in the aptitude of the two groups.

This sort of thing seemed common in the papers I read (I had to choose one of them to pick on). Fundamentally, it remains unclear whether this actually reduced the amount of time it took for students to debug issues, and it is clear that none of these studies were able to increase student test scores by any statistically significant amount. This would suggest that specific strategies were taught and tested with problems that looked similar.

Applying this research to the idea of “Kernighan’s lever” almost invalidates the idea of the lever. If folks were able to increase the edge of their knowledge and debug in flow, we’d expect a more complete understanding, which should translate to better test scores. To that end, students who were not given specific debugging instruction should have been operating more outside their skill level and should have therefore increased test scores with some significance, and that’s just not what we see:

On the first midterm, the treatment group averaged 70.7% while the control group averaged 72.0%. On the final exam, the treatment group averaged 78.6% while the control group averaged 74.0%. T-tests showed neither of these differences to be statistically significant.

Furthermore, the Dreyfus model seems particularly useless for classifying programmer capability if you want to perform research to figure out how to move people from one end to the other. In Chmiel & Loui, they note that “[n]ovices make observations … with no attention to the overall situation.” This is a behavior that is almost entirely contradictory to the approach of the expert, who is “able to act on intuition” and is “not limited by the rules.” The focus then should be on changing behaviors instead of whether debugging time was reduced.

All of this together makes it seem like education has a limit, and there is some sort of self-limiting factor on the part of students.

McCauley et. al. seem to be aware of this, and in their section on future research directions, they note:

The relationships between debugging success and individual factors such as goal orientation, motivation, and other self theories (Dweck, 1999) have not been researched. … Given that debugging presents challenges for many novices, exploring the influence of self theories on student approaches to debugging appears worthwhile.

Later in 2008, they got their wish.

Dweck and Self-Theory

In 1999, Carol Dweck published a book called Self-theories: Their role in motivation, personality and development. This work covers over two decades of research conducted by Dweck and others, and presents an interesting thesis: an individual’s own perception of intelligence and how it is obtained directly affects the way they solve problems and interact with others. This perception is called a self-theory.

An individual’s self-theory falls somewhere within a range of mindsets. At one extreme, we have the fixed mindset; at the other end, we find the growth mindset.

The fixed mindset person has a view that intelligence is a fixed resource. Internally, this means that when a fixed-mindset person approaches a difficult problem, they give up quickly under the assumption that the solution lies outside of their ability. This view is projected onto others: someone else who can solve the problem has an inherently larger capacity for intelligence. When required to solve difficult problems, the fixed mindset person may find a way to evade the issue. They may even become visibly agitated.

On the other end of the spectrum, we have growth mindset people, who believe that intelligence is malleable. They recognize problems as opportunities for learning and growth, and solving problems as the only way to capitalize on that opportunity.

The practices of both programming and debugging can be compartmentalized into a single field, a field of problem solving. Some problems are inherently challenging. When viewed from this perspective, an individual with a growth mindset is necessarily more capable and productive than an individual with a fixed mindset. The reasoning here is that the person with a fixed mindset is more concerned with keeping up appearances of a particular level of intelligence: they want to appear smart. The easiest way to do this is to only solve problems at or below their skill level. The growth-minded person is also concerned with keeping up appearances, but the appearance they want recognition for is hard work. And it turns out the only way to really give the appearance of working hard is to actually work hard.

I admit that this sounds a little wishy-washy, but the research and experimentation holds up. I’m still digesting it, but I definitely recommend a talk Allison Kaptur gave as a keynote speech at Kiwi PyCon 2015. (She also provides a blog post serving as a rough transcript of the talk.)

The talk is titled Effective Learning Strategies for Programmers, and I highly recommend reading / watching for more information on Dweck’s research and how it can be practically applied.

Self-Theory and Debugging

In 2008, Laurie Murphy and Lynda Thomas released a paper Dangers of a Fixed Mindset: Implications of Self-theories Research for Computer Science Education (PDF). This work is (as far as I can find) the first to apply Dweck’s research to the practice of problem solving in computer science. It considers numerous factors of how self-theory affects the field of computer science, including:

Learning to write programs

[M]ost CS students … face many challenges and a barrage of negative feedback … While students with a growth mindset view errors and obstacles as opportunities for learning, those with a fixed mindset are likely to interpret excessive negative feedback a as a challenge to their intelligence and to avoid similar situations in the future.

The extremely unfortunate situation of gender disparity in CS

Research has also shown that, although high-IQ girls tend to out perform all other groups in elementary school, they are also more likely to have a fixed mindset. As a consequence, they are less inclined to seek out challenges.

Why collaborative programming practices don’t always work

Pair-programming has been shown to boost confidence, improve retention, increase program quality and heighten students’ enjoyment. Students with a growth mindset “feel good about their abilities when they help their peers learn.” However, because those with a fixed mindset feel smartest when they out perform others, they are less likely to value collaborative learning.

Defensive classroom climates

Those who believe intelligence is fixed seek validation and judge and label others. Such practices are exhibited in CS by students who ask “pseudo-questions” so they can demonstrate their programming knowledge, and by instructors who accord special status to students with previous experience.

Psychological success factors like self-efficacy and self-handicapping

A study by Bergin and Reilly looked at both self-efficacy and motivation and observed that intrinsic motivation had a strong correlation with programming performance, as did self-efficacy. They did not, however, establish the nature of this link. Self-theories research, which has linked theories of intelligence to motivation and self-esteem, may shed light on results from CS education.

The paper then goes on to provide suggestions for how teachers may better utilize this information to help student retention, handle classrooms where students have diverse backgrounds, and more. It sets recommendations for future research about what teachers can do to influence growth mindsets in students.

In 2010, Manipulating Mindset to Positively Influence Introductory Programming Performance (PDF) was published by Quintin Cutts, Emily Cutts, Stephen Draper, Patrick O’Donnel, and Peter Saffrey. Though this study admits some faults, it does show that with some particular “interventions”, students can both improve mindset and grades. These interventions included first teaching all students about self-theory research and its implications in learning; this was called “mindset training intervention”.

Some students received a crib-sheet that explained various ways in which they could solve various types of problems generally. When tutors were assisting students, they were required to assist from the crib-sheet only. The idea was to remind students at every struggle that general solutions to problems exist and to take them through the process of figuring out how to apply a general solution to a specific problem, every time there was a problem. This was called the “crib-sheet intervention”.

Finally, when feedback was received on worksheets / problem sets, some students received “rubric intervention”. For these students, feedback sheets all included at the top:

Remember, learning to program can take a surprising amount of time & effort – students may get there at different rates, but almost all students who put in the time & effort get there eventually. Making good use of the feedback on this sheet is an essential part of this process.

This intervention was designed to remind students to enter the growth mindset when they received feedback, which is ostensibly when they would be in a position to learn the most.

The study was done in a 2x2x2 matrix form. While the crib-sheet intervention was ineffective alone, only students who received all three interventions were shown to improve test scores. The ineffectiveness of the crib-sheet intervention applied alone backs up other research studying the “saying is believing” theory and finding that it isn’t necessarily true.

So… what?

This research fundamentally shows that it is possible to both improve mindset in students and improve their scores. By being aware of self-theory and its impleications, approaching problems methodologically and with an open mind, we can improve our abilities in problem solving. And debugging is just a fancy word for problem solving.

Finally we have a path forward both for educating students and continuing to educate ourselves. By approaching problems with a growth mindset, we are much more likely to learn and grow our skills. If we approach our problems with a fixed mindset, we stunt our growth.

Practice

Once we reject the fixed-mindset view that programming is an innate talent (and Jacob Kaplan-Moss discusses several reasons we might want to do that which have nothing to do with personal growth), we are ready to continue our journey to becoming an expert. How do we do this? What general steps do we take to debug software?

Mental Models

When we think about or discuss software, we are usually simplifying its behavior in order to better comprehend it. In a talk at ACM’s Applicative conference in 2016, Andi Kleen discussed mental models as they relate to performance tuning. One of the foundational points of this talk was that it is actually impossible to fully understand any sufficiently complex software. Why should this be?

Software and hardware becomes more complex by handling additional states. The number of states and state transitions handled scales with the number of logical components of a piece of software, including subsystems, classes, threads, consumed libraries, and even the number of source lines. As all these variables increase, so does the amount of state carried by the system as it runs, and we necessarily observe the combinatorial explosion problem. Trying to reason exactly about such systems is akin to the problem of trying to understand infinity (PDF).

So we must necessarily create mental models of how software should work to simplify the process of understanding it. In software engineering, we even do this as an up-front exercise when designing new software: from product requirements documents to “architectural” design to technical design documents, the process begins and completes by following predefined models of what the software should do.

A bug is effectively defined as a disconnect between the expectation of a piece of software to behave in some particular way versus how the software actually behaved. It follows that one critical component of why bugs occur is an incorrect mental model. And the research (PDF) supports this.

Importantly, this means that mental models do not help us when debugging software. The first step of approaching a software bug is to be critical of our own understanding of the buggy code and the code it interacts with. In other words, we must accept our knowledge of the system is flawed and discard it as faulty. (This is, as you might imagine, more difficult for a fixed-mindset individual.)

The Scientific Method

Software engineering is synonymous with applied computer science. When attempting to diagnose and troubleshoot bugs in a system, it is proper to follow the scientific method. As a refresher:

Form a hypothesis.
Rigorously test the hypothesis and gather data.
If the data do not support the hypothesis, goto 1.

Experience leads me to believe that many engineers (myself sometimes included) follow this process backwards. We are so caught up in trying to fix the underlying problem that we forget about the process of first figuring out what the underlying problem actually is.

To that end, the mistake we often make is treating our investigation as if the hypothesis was “I think there is a bug in the software.” As the presence of a bug is usually self-evident, such a hypothesis is already proven. As engineers, we need to come up with a hypothesis of why the bug happens, not that the bug exists.

To this end, a better initial hypothesis might be something to the effect of, “I think the bug is on source line 42.” This is somewhat better than, “I think there is a bug in the software” as it provides some specificity to the situation. Sometimes we can test whether line 42 is buggy simply by commenting it out! A better hypothesis describes the situation in detail, which means we usually need to gather data to form a hypothesis, not just to test it.

“An off-by-one condition on line 42 causes us to fail to log the bytes received from the last read call” is a fantastic hypothesis. We can test that the issue is on line 42. We can test that the bug is solved by looking at our logs.

Investigation

Sometimes we have a good intuition of what the issue is with our code. This could be because some compiler or tool gave us a hint as to the issue; it could be because the bug misbehaved in a very particular way, giving us a clue to its nature. This intuition gives us an initial hypothesis (and sometimes coming up with the hypothesis is the hardest part). In this case, we quickly identify a possibly buggy section of code and begin to analyze it for a bug.

Intent versus Syntax

When forming a hypothesis, we should begin by reading code for semantics — what it means — versus syntax — what it says.

Let’s take a simple, buggy VCL snippet as an example:

    sub vcl_fetch {
        if (beresp.http.authenticated) {
            set beresp.http.cacheable = "false";
            return (pass);
        }

        return (deliver);
    }

First, notice there is nothing obviously wrong with this code. We may have an intuition that something is wrong here specifically because we found some object cached that we expected this code to avoid caching. So we focus our efforts here.

If we read this code for what it says, we are literally pronouncing the syntax of the code out loud, substituting some syntactic elements with words while stripping others. “If the backend response header ‘authenticated’ is set, set the backend response header ‘cacheable’ to ‘false’ and return ‘pass’. Otherwise, return deliver.” This tells us nothing new about the nature of the bug.

If we instead read the code for its intent, we get “responses for resources that required authentication must not be cached.” In addition to being shorter to say (and therefore easier to communicate about with others, should you need external input), it tells us something else: what the code is supposed to do. When we do not yet have a hypothesis, this can be crucial for figuring out which areas of the code may be responsible for a bug.

Once intent is understood, we can begin to gather data. We might look at the responses for authenticated resources and realize that such resources are actually identified by a header called authed instead of one called authenticated. It is only at this point that we have data about the state of the system that we should actually begin to do any syntactic analysis of the code.

Discard Comments

When a bug occurs in heavily commented code, ignore the comments. While they may be useful for forming a mental model of what some code is supposed to do, reading comments while debugging can subtly reinforce the correctness of incorrect code. Consider:

    /* Print all the elements */
    for (int i = 0; i <= n; i++) {
        printf("%s\n", elems[i]);
    }

You may already see that this is intended to illustrate an off-by-one error. The point here is really that the comment can tend to make us paper over this code. We may think, “Yep, this prints all the elements.” It does. It also “prints” more than that. Just because a comment is correct in describing the code it annotates does not mean that the code is correct in solving the problem.

Understand Which Bugs Occur

The McCauley et. al. literature review finds many different (and some conflicting) papers on bug classification. I’m not of the opinion that any particular set of classifications is better or worse than any other (assuming both are relatively complete). That said, agreeing on a standard terminology within a team is important so that we can efficiently and effectively communicate with others about problems.

I’ll cover a few classifications I find useful.

Syntax / Semantic Bugs

Some of the most obvious bugs have to do with not following the syntax or semantics defined by the programming language we’re using. Because our tools can already assist us a great deal here, we tend to think of these problems as trivial. This is a mistake.

Although syntax errors are nearly always caught at compile time, languages (like PHP) which do not necessarily distinguish between compile time and run time may confuse this a bit. (This is one reason a robust testing environment is important, regardless of your preferred testing strategy.) Weakly typed languages may be unable to perform type conversions at run time. In some cases, static and dynamic analysis tools for our platform can help.

A good awareness of our environment always includes an understanding of the capabilities of our language and tools. When these issues hit at run time, they can be very hard to spot because we heavily rely on our tools to figure these sorts of issues out for us. Be prepared to learn more about your environment when you encounter new issues like this.

Logic Bugs

This is a broad set of bugs with many sub-classifications. Off-by-one errors, overflows and underflows, and control flow errors (like early returns, incorrect conditionals, using logical or when you meant logical and — or vice versa) are all examples.

It may be unfortunate to group all of these different bugs into a single category, but I prefer to do this because they are all related to a bug in our expression of logic in a program form. Furthermore, they all tend to behave differently enough from each other that they’re unlikely to be mistaken for each other.

Race Conditions

Though these are arguably logic bugs, I call out race conditions separately for a few reasons:

They’re frequently not reproducible with synthetic workloads.
A race condition is not necessarily indicative of a bug.
The absense of race conditions is not necessarily indicative of correct software.
Race conditions can appear as a result of logic bugs elsewhere.
Race conditions can mask other bugs.

Especially because of the facts that race conditions can be more symptomatic than original in nature, and because this has the effect of masking other more fundamental bugs, I find it useful to think about them as a separate category.

Performance Bugs

Premature optimization may be bad, but not performing to SLA or capacity is worse. Performance problems tend to be particularly insidious because they’re typically very hard to work around. This is likely because such issues tend to be deeply seeded in software design and highly dependent on the problem space. In addition to this, performance gains in existing systems are frequently found by changing assumptions of the complexity of the problem being solved.

To avoid being bitten by unsolvable performance problems, try to make sure your interfaces are composable. Design systems that can be independently tested and validated such that you can capacity plan. Avoid sharing state through memory. When this is not possible, use mutexes only when they are unlikely to have high contention. In highly contended workloads, attempt to make use of wait- and lock-free solutions where possible.

…and many more

When we accept that “debugging” is a domain-specific term for problem solving, it follows that a “bug” is a domain-specific term for a problem. Unexpected behaviors in software may also be caused by (or at least attributed to) a number of areas outside of the code itself:

Protocol bugs: the software you are implementing is specified incorrectly such that an implementation to the specification cannot possibly fulfill the stated goals of the specification.
Process bugs: a failure to incorporate accepted best-practices into an individual or organizational project. This includes lack of version control, not performing code reviews, absence and aversion to testing, etc.
Environmental bugs: problems with the tools we use when designing, building, and running our software may end up affecting how our software runs. From compiler bugs to kernel issues, library bugs to hardware bugs, any number of issues in our environment may affect the run-time behavior of our software. These issues tend to be insidious; we usually assume our operating platform to be infallible. It’s not, and this is why actual full-stack understanding is necessary.

Behavioral Patterns

It turns out that these classifications are more than just a taxonomy. Though the above classifications seem to be solely based on how a bug was introduced into the system, it turns out that nearly all of these classifications have run-time signatures as well. In other words, we can observe patterns of behavior from a single sort of bug.

For example, an off-by-one bug is always going to do something one fewer or one more time than expected (whether that “something” is “scan a string” or “count references”). Once we understand the reason for this bug, we can generalize: maybe there are special cases where we could have off-by-N. And indeed, in C this is usually a thing that happens iterating over an array of structs.

But first we have to be able to observe these patterns.

Tooling

Tools and introspection are crucial to the debugging process. As both the processes of forming and testing a hypothesis require analyzing data, we need tools to collect, analyze, and understand the data. Relevant tools differ for nearly every project, but include things like:

Software to read statistics counters from the buggy application (like varnishstat).
Graphing / plotting statistics over time (using something like Ganglia or Graphite).
Debuggers like gdb, lldb, or any other language / platform-specific debugger.
Profiling utilities like perf or hwpmc.
Tracing facilities like dtrace or lttng.

I can’t stress enough the importance of recording metrics over time. At Fastly we use Ganglia, DataDog, and other tools to gather data over time and track changes. As far as recognizing patterns go, visualizations really can’t be beat.

The useful tools vary by project, so it’s not super useful to discuss them in any real detail. What is important is to understand that you will need to gather data for both forming and testing your hypothesis, and understanding the tools available in your domain gets you halfway there.

Importantly, not every tool fits the task. Be prepared to extend your software to provide additional information, as well as to write your own tools to gather and analyze this information.

Application

What does this look like in the real world? In practice, we encounter cases where we’re looking at problems extending far past our experience. Bugs, as Kernighan might say, we are not yet clever enough to debug. In some cases, we may be extremely time-constrained in how long we have to solve an issue. In yet other cases, the tools we have may not even be useful.

Our workload at Fastly is unique. Our Varnish runs at a thread load between 40000-60000 threads; it consumes in some of our busier POPs over 300GB RAM. This comes with all sorts of problems:

The Maps Debacle

Many debugging tools on Linux rely on the /proc/[pid]/maps file to gather information about mapped memory regions in the executable. In releases of the Linux kernel from 3.2 to 4.5, some code to annotate which maps belonged to thread stacks actually resulted in O(n^2) complexity, iterating over maps. A good analysis of this problem is available on the backtrace.io blog. Reading this file on our systems took minutes.

Fundamentally, this meant rolling releases of libraries like libunwind and perf to use /proc/<pid>/task/<pid>/maps (which does not suffer from this issue). It also resulted in sending patches upstream to jemalloc.

The GDB Fiasco

Both GDB and LLDB have a similar polynomial-time issue when attaching to processes with large numbers of threads. This is largely due to how both utilities have decided to structure contexts about threads they are attached to. The last time I tried to attach GDB to one of our Varnish instances, it took over 4 hours and still hadn’t finished attaching. I tried to cancel this operation and panicked the kernel.

To this end, we’re using other tools for runtime introspection that I will talk about later. And you might ask why not just grab a core of the process and analyze it offline…

The Core Dump Disappointment

Our cache nodes have 768GB RAM. Varnish uses several hundred gigabytes of this memory, and most of it is actually not at all related to object storage, but instead to thread stacks, various memory pools, and metadata. Our root filesystems generally have about 150GB free space. This means we do not have enough disk space to store core dumps if Varnish crashes. We could, of course, offline one of our SSDs, but it is not economically sensible for us to waste 500GB-2TB of space to leave room for core dumps.

Besides, it actually takes a ridiculously long time for the kernel to dump a couple hundred gigs of memory into a file. And even then, it would take over an hour to copy the dump off of the machine at 10Gbit speed, compressed.

Here, we are using some software from backtrace.io to solve the problem. I highly recommend using their utilities if you’re working on systems software, regardless of your software architecture and memory usage.

Carrying On…

Modifying existing utilities to work around system bottlenecks is a little frustrating, but being fundamentally unable to do any runtime debugging is maddening. To that end, we’ve come up with creative ways to gather information from our system at low operational overhead. Our strategy here is frequently to have these features be things we can leave “always on” as turning them on during an outage situation may lose valuable originating context. To this end, the solutions must be low-overhead.

I have blogged about librip this year, detailing the software and the problems it solves. To summarize, librip is a “minimal-overhead API for instruction-level tracing in highly concurrent software” and it enables us to get execution histories of threads at runtime. This granularity isn’t quite to the level of providing a backtrace, but it gets close. And it has helped us solve deadlocks, livelocks, stalls, and performance issues.

Tracing is another point where custom tooling can be extremely useful. Several great existing technologies exist on this front, including DTrace and LTTng. Tools like DTrace are fantastic as they operate without any overhead when disabled. However, the dynamic nature of DTrace makes its runtime overhead considerable when generating high-frequency traces, which is where instrumentation-oriented tools like LTTng become useful. (DTrace can do this too, but then you’re responsible for writing the instrumentation hooks as well as dealing with the overhead of instrumenting.)

In any case, tracing information can be a firehose: it spits out a ton of potentially useful information, but figuring out which bits of the information are actually useful can be difficult. Usually we’re looking for a couple different things:

Long tail trace information. 99th percentile trace events are common in systems handling tens of thousands of events per second. Figuring out the 99.999th percentile is more difficult, as described by Dan Luu.
Correlating events. When we notice some long tail traces, what other traces are responsible? For example, if we spent a long time waiting to acquire a mutex, we may be interested to correlate this time with the original holder of the mutex.

I’m working on some tracing tools that use local trace buffers to scribble information into, and logging entire trace buffers at a time. The idea is that it is easier to determine whether any individual trace chain is interesting than it is to determine whether any individual trace is interesting in terms of data retention. It’s my hope that this will be successful, and I will surely blog about it if so.

Wrapping it Up

This has been a ridiculously long post. To summarize:

Recent research provides us evidence that the way we think about problems directly effects our ability to learn and how we interact with others about these problems.
There are ways that we can improve our mindset (and influence the mindsets of those around us) such that we optimize our experience for learning, problem solving, and success.
Debugging is a special case of problem solving, and benefits hugely from shifts in mindset.
Through classifying bugs, recognizing patterns, and using tools, we are able to come up with a general strategy for solving problems in our code, based on the scientific method.
Understanding this methodology prepares us to ask better questions about what data we need to solve problems. This allows us to extend existing and author new tools to help us in our journey.

I’m extremely interested in this subject in general. Look for more posts related to debugging and pedagogical topics in the (hopefully near) future!

Ripping Rings

Wed, 16 Mar 2016 15:07:35 +0000

TL;DR, I’ve released a “library” called librip: a “minimal-overhead API for instruction-level tracing in highly concurrent software”. The rest of this post is about the “why” of the software, followed by a slightly a little bit of the “what” and only a smidge of the “how”.

Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?

I’ve previously included this Brian Kernighan quote from The Elements of Programming Style before in my writing (I likely will again) – it’s as true today as it was over forty years ago when it was published. However, it is not all despair. The quote ends with a question, and questions beg for answers. And fundamentally, that’s what I do in my capacity as a software engineer. The answer to this particular question is to always be learning – you have to level-up your clever.

But I’m also not always debugging my own code. I suppose this means that I have to be twice as clever as the original author was when writing the code to debug the code. In my experience, this usually results in code deletion and simplification – which is the underlying point of the context surrounding the quoted passage above.

In my work at Fastly, there’s rarely a shortage of things to debug. Whether the Internet-at-large has managed to trigger some pathological edge case or I’m working on new features, debugging is always in the picture. And I can’t always be twice as clever. In such cases, I’m usually aided by the trusty debugging toolset: gdb, perf, strace, lsof, etc. But here’s the catch: sometimes these tools are entirely unusable.

Tens of Thousands of Threads

It’s no secret that we at Fastly use a modified Varnish Cache to facilitate our content delivery. What’s less well known is how it works. When Varnish was originally implemented, the idea was that threads were cheap, and that operating systems were going to do a better job scheduling them than you were. This is (to a large degree) true today, but it comes at a cost.

On our caches, our Varnish processes run with tens of thousands of threads in the normal case. And it turns out that the kernel does a reasonably good job with this workload. When most of your time is spent writing data over a network, the kernel does a pretty reasonable job of keeping everyone running within acceptable latency bounds. But as with Biggie’s money, with more threads, we do get some more problems.

Composability

Lock-based synchronization is nearly the canonical solution to sharing memory in concurrent software today. But there are significant drawbacks, especially in heavily threaded environments.

In a 2008 ACM Queue article, Real-world Concurrency, Bryan Cantrill points out that it is possible to write composable software built on top of mutexes. (I do find it funny that one of the suggested ways of doing this is to not use mutexes.)

Anyway, composability is a desirable property because such systems are easier to build, consume, and verify (and there is plenty of literature about this for nearly any language). While it may be possible to write composable software that consumes locks, this isn’t actually the problem. The problem is that locks themselves do not compose. Why not?

Locks are not self-contained. Although lock and unlock functions work on discrete structures, they are relatively tightly coupled both to logic described in code as well as to the data they are meant to protect. This means that programmers are required to understand implementation details of APIs surrounding code which may or may not need protection, and may or may not result in locks being held on return.

Secondly, lock operations can’t be recombined in any order to produce valid execution histories. Lock operations must precede unlocks. Locks cannot recurse. (If they can, are they unlocked once or many times?) Locks cannot be acquired and released in arbitrary orders. Nothing about their API or implementation provides guidance on what order and where locks must be acquired.

So while it is possible to hide locks behind a composable API, the code in the API itself isn’t guaranteed to be composable. Indeed, at the lowest level, it’s clear that implementing correct, composable APIs which consume locks (sorry Bryan, I had to) is at best non-trivial.

Contention

Let’s assume we have some API that isn’t at all OpenSSL. (Just kidding, it is.) But let’s assume it isn’t, because I need a strawman API that has a correct implementation that uses locks and is composable.

Even when implemented correctly, this API may cause the software (and in some cases the whole system) to enter a state known as livelock.

In livelock, your software is spending so much time negotiating lock transfer that it doesn’t actually get any work done. Your system continues to run, but appears to do nothing. I have recently encountered a livelock where the average lock hold time was something like 10 minutes because the processes owning the lock couldn’t get any time on the scheduler. (And once they did, other processes suddenly needed those locks as well.)

Concurrency

Given these problems, we might care to use a different approach to sharing memory. We may want to explore lock-free and wait-free algorithms as an alternative to lock-based approaches. So we dust off Concurrency Kit and go hacking.

Problematically, nearly all of our problems are multiple producer, multiple consumer (MPMC) problems. And in unmanaged languages like C, many (all?) MP and MC problems require some form of safe memory reclamation (SMR). Many SMR schemes have an approach that goes something like this:

Stash pointers in a thread local area.
Mark unused stashed pointers as such.
Wait for the system to enter a quiescent state.
Free any unused pointers.

The actual approach for stashing, marking, and detecting quiescent states varies, but this is the gist. When you have tens of thousands of threads, detecting a quiescent state is very difficult. Even in schemes that make it easier, the O(mn) complexity of scanning pointers in thread local areas makes many of these nearly unusable in environments with such high thread counts.

“But dho!”, you say. “Just use reference counts!” Ignoring entirely the cache unfriendliness of reference counting schemes (and therefore poor throughput with high numbers of objects), when we require non-global, per-object references (such that the reference is embedded into the memory of the protected item), we’re back to locking.

So we put Concurrency Kit back on the shelf and hope it doesn’t collect too much dust before the next time we can use it.

Debugging

Have you ever tried to attach gdb to a process with more than 40,000 threads and 500GB resident memory usage? I’ll wait. Actually, I won’t, because it’s going to take you somewhere between 45 minutes and 3 hours. (Don’t bother with lldb, it’s the same problem.) I’ve theorized that this is due to a combination of /proc/<pid>/maps suckage and something between linear and polynomial time complexity of attaching to threads in the debugger itself. (It walks a linked list of threads multiple times for each thread it attaches to.)

Backtrace.io crash dumps help for some cases, but the overhead of tracing this many threads is fundamentally non-trivial, so we can’t (yet) use their tools for tracing live processes. That said, when our software does crash, theirs is the only tool that works for us.

So now we have lock-based software with tens of thousands of threads that we can’t debug. Twice as hard as writing the code, indeed. In the absence of crash dumps, determining cause of bugs can be excruciatingly difficult. And in such highly threaded software, the likelihood that a bug is related to composability, contention, or concurrency is actually rather high.

Outside of contention, many concurrency bugs are the result of a bad execution history. Deadlocks occur when locks are acquired and / or released out of order. Race conditions occur when execution histories happen out of order with respect to a protocol defining a required ordering. If we could somehow observe execution histories, that would be pretty close to ideal for debugging numerous issues.

But how do we get this without a debugger? We sort of write our own.

Ripping Rings

I’ve released a new “library”, librip: a “minimal-overhead API for instruction-level tracing in highly concurrent software”. This code was (when I wrote it) originally baked into our Varnish implementation, where it was known as “rip_ring”. Rip because %rip is the name of the 64-bit program counter (PC) on x86-64 machines, ring because snapshots of this value are stored into a shared memory ring buffer exposed through Linux tmpfs. (Although it is currently extremely platform-specific, ports to other architectures and systems are welcomed.)

The software is comprised of two components. One is an API for actually sampling the PC into this shared memory ring buffer. The other is a script that can process the file and resolve addresses to symbols in the binary.

And how does it work?

Pretty goddamn well, to be perfectly honest. The overhead is pretty low: there are a few bitwise operations performed on some thread-local variables, and then stuff is written to memory.

Since the shared memory is backed by a tmpfs, if it is mapped with MAP_SHARED, it survives crashes. This means we get the recent execution history of every thread active in the system (plus exited threads) on a crash. It’s not quite a backtrace, but it’s close.

PC samples are littered strategically through the code. For example, our locking function interface is modified:

#define Lck_Lock(l)                                            \
        do {                                                   \
                rip_snap();                                    \
                Lck__Lock((l), __func__, __FILE__, __LINE__);  \
                rip_snap();                                    \
        } while (0)

#define Lck_Unlock(l)                                          \
        do {                                                   \
                Lck__Unlock((l), __func__, __FILE__, __LINE__);\
                rip_snap();                                    \
        } while (0)

At any particular time, this gives us all threads contending on a mutex, tells us which thread is the mutex owner, and gives us all threads that have recently released the mutex.

What does this look like? Depends what’s wrong. A livelock is exposed in the default condensed output of the read_rip utility (written by a colleague of mine):

locking_function : 19126 threads, 2 locations: ssl.c:220 (10); ssl.c:210 (19116)

Also remember, this is hanging out in shared memory. So you can use this tool to immediately rule out livelock as a runtime performance problem without pausing your software to attach a debugger or using tools that add system-wide trace-time overhead.

Lock order reversals and deadlocks are trickier. The nice thing is that the debugging information puts both rip_snap() calls on the same source line, but they (of course) get different addresses. So we can get per-thread output like:

[35283]: {82}source_a.c:124<0x442bae>, {83}source_a.c:129, {84}source_b.c:2670,
    {85}source_b.c:217, {86}source_b.c:662, {87}source_a.c:124<0x442af7>,
    {88}source_a.c:124<0x442bae>, {89}source_a.c:129, {90}source_b.c:767,
    {91}source_c.c:132, {92}source_c.c:134<0x477f12>, {93}source_c.c:144<0x477fa3>,
    {94}source_b.c:110, {95}source_b.c:3873, {96}source_b.c:3405,
    {97}source_d.c:339<0x45f617>, {98}source_d.c:339<0x45f6a3>, {99}source_d.c:341,
    {100}source_c.c:238<0x479f52>, {101}source_c.c:238<0x479fe0>,
    {102}source_c.c:240, {103}source_b.c:3405, {104}source_b.c:2773,
    {105}source_a.c:124<0x442af7>, {106}source_a.c:124<0x442bae>, {107}source_a.c:129,
    {108}source_a.c:124<0x442af7>, {109}source_a.c:124<0x442bae>, {110}source_a.c:129,
    {111}source_e.c:573<0x43be8f>, {112}source_e.c:573<0x43bf1b>,
    {113}source_a.c:124<0x442af7>

And this works quite well. Given our lock and unlock interfaces are the only ones with multiple rip_snap() calls mapping to the same source line, we can create neat little scripts, like this one that a colleague of mine whipped up in a couple of minutes. It scrapes output to help find deadlocks by providing a list of threads that have acquired locks, but not released them.

#!/usr/bin/perl

use strict;
use warnings;

my $sf = shift; # source file with lock

while (my $l = <>) {
  next unless $l =~ /\Q$sf\E/;
  next unless $l =~ /\{\d+\}\Q$sf\E:(\d+)<0x[0-9a-f]+>, \{\d+\}\Q$sf\E:\1<0x[0-9a-f]+>/;
  next if $l =~
      /\{\d+\}\Q$sf\E:(\d+)<0x[0-9a-f]+>, \{\d+\}\Q$sf\E:\1<0x[0-9a-f]+>, .*\{\d+\}\Q$sf\E/;
  print $l;
}

Super cool.

The implementation details aren’t that interesting. We do some pointer packing such that event order can be reconstructed linearly. Ring buffers wrap around, but they are also FIFO, so with counters, we can reconstruct the correct event ordering. I expect this framework to be useful in any highly-concurrent scenario. Whether using native threads or coroutines, livelocks and deadlocks are real problems as long as you employ lock-based synchronization plans to solve the problem of sharing memory.

Other than that, the utility of this thing is all in how you use it. I’d appreciate any feedback, and especially code to make this useful on other architectures (especially ones with weaker memory models than x86-TSO).

On Window TinyLFU

Wed, 09 Mar 2016 18:06:34 +0000

I was first introduced to the Window TinyLFU algorithm through a wiki entry for the caffeine project.

The graphs looked neat, but it took actually reading the Einziger and Friedman paper, TinyLFU: A Highly Efficient Cache Admission Policy to understand just how interesting and simple the algorithm actually is. Unlike many papers in computer science, this one is extremely consumable for those (like myself) lacking a strong math background.

I’ve been studying this algorithm with interest, since it is quite relevant to my work at Fastly. I’ve a few ideas for possible extensions, as well as some for efficient lock-free implementations. But first, let’s talk about cache eviction and how TinyLFU works.

LRU?

Why not just use LRU and be done with it? There are a few practical problems with LRU:

LRU is not scan resistant. What this means is that, given a cache of N items, an attacker can send N+1 requests in sequence. Once an initial scan is completed, all subsequent scans will result in cache misses.
Every hit requires moving objects in the queue. When queues are dynamically allocated, this results in high cache miss overhead, TLB thrashing, and memory writes.
With high request loads comes high lock contention.

Because of these problems, LRU implementations frequently employ clever tricks to reduce lock contention. This can be achieved with a few strategies:

Don’t promote items that were recently promoted. (They’re probably still near the front of the LRU.)
Don’t promote items in the face of lock contention.

Under high load, these strategies (coupled with the lack of scan resistance) combine in a way that results in dropping items that have some regular access frequency. These are items that we always want to have cached – so shouldn’t we consider usage frequency as part of our caching strategy?

LFU Background

Access frequency seems like a good thing to use as a cache eviction strategy. It even seems like a pretty close approximation to the clairvoyant algorithm: cache every item that is frequently used.

Easier said than done.

Aging

The first problem is one of aging. Frequency isn’t a useful absolute metric in terms of knowing which objects are worth keeping. This is especially true for sites like Imgur, where front-page images will see many impressions on one day, and then effectively never be accessed again. To address this, we need some method of aging hit counts. This means that over time, the weight of a hit decreases by some factor.

How do we determine how often to age? How do we determine a good weight to use?

The Squid proxy provides links to a couple papers at their cache_replacement_policy documentation that describe two approaches used for aging when using frequency as a cache metric.

Memory Overhead

Keeping an access frequency on cached objects is common. To effectively use a frequency-based caching strategy, we also have to remember the access frequency of objects we no longer have in cache. In a system that sees and forgets about billions of distinct objects per day, the memory overhead of maintaining counters is not tenable.

Some approaches to solving this include the use of saturating counters. (A saturating counter is a counter that increments up to, but not past, some maximum value.) If we assume that any object with a frequency larger than X is an object that we want to cache, we might be able to reduce our counter space. But by how much? 1 byte only gives us 256 values (assuming CHAR_BIT is 8). What about 2 bytes? If we see 2 billion distinct objects per day, we end up using 28GB of memory just to hold counters after a week of uptime. This is memory that we cannot use to actually cache objects.

Admission

LFU is sometimes implemented as a cache admission policy, not an eviction policy. What this means is that when a cache lookup results in a miss, and the resolution of the miss results in storing a cacheable item, that item does not become cached until it surpasses some access frequency. For example, if every cached item has a access frequency of (say) at least 100 per aging period, this new item will effectively result in a miss every time until its access frequency meets or exceeds this threshold.

We typically solve this problem by creating a “window” cache in front of the LFU that caches low frequency items using some simpler approach, like an LRU. When items from the window cache are evicted, their access frequency during their time in the windowed cache is compared to their LFU frequency count to determine whether or not these items should be inserted into the main cache.

TinyLFU

These problems are hard to address, but given the promise of LFU, much research has gone into solving them. Enter TinyLFU. TinyLFU provides means for solving the problems of aging and memory overhead. In a subsequent paper, Ben Manes introduces Window-TinyLFU, which solves what it terms the “sparse burst” problem where repeated access to a new object results in many cache misses.

Dealing with Aging

First, we should consider the novel way TinyLFU handles aging. To keep frequencies “fresh”, a counter is maintained that attempts to target the sample size. The sample size is effectively the period at which we age. This period is not duration based, but is instead measured on incoming requests. The paper refers to this as W. (The paper tries very hard not to confuse the reader about the term window, but I was too dense to not be confused for a period of months.)

When this counter reaches the sample size (W), both the counter and all frequency sketches are divided by two. The paper goes on to prove that the error bounds resulting from integer divisions are reasonable and maintain a level of correctness desired from such a structure.

This division operation surprisingly simple (at least moreso than sliding window-based strategies), and usually rather efficient on modern processors.

Solving Memory Overhead

As we explored in the previous section, simply reducing counter size is not sufficient to reduce memory overhead to a usable amount. TinyLFU makes a novel observation about cache frequency patterns that not only allows us to drastically reduce counter size to under one byte, but also employs probabilistic algorithms to reduce the total number of counters we must store.

Reducing the Number of Counters

The first novel suggestion made by the paper is to reduce the number of counters by using probabilistic algorithms. This can be done by using an approximate count; section 2.2 of the paper details a number of possible schemes for this, but in this post, I will focus on discussing what is called a “minimal increment counting Bloom filter”.

Minimal Increment Counting Bloom Filters

Bloom filters are probabilistic data structures that can be used to determine whether some item is a member of some set. Instead of storing the entire set of items, a Bloom filter relies on computing several hashes of the items in a set. The result of this hash is used as an index into a bit set – if the bit is set, the item is probably in the set. If it is not set, the item is definitely not in the set. By increasing the number of distinct hash functions calculated on the elements, and increasing the total bit space, we can increase our certainty of whether the item is actually a member of the set on a hit.

For instance, using N hash functions, this lookup means the item is probably in the set:

This lookup means the item is definitely not in the set:

But Bloom filters can say more than just “probably” and “definitely not”. A “counting Bloom filter” can keep track of counts (in fact, the standard Bloom filter could be considered a 1-bit counting Bloom filter). In this case, each element in the Bloom filter space represents a (possibly saturating) counter.

The problem with this is that multiple items share counters. To keep our counters small, we need a means of making sure counters shared between objects with wildly different access frequencies do not skew each other too much. This is where the “minimal increment” counters come into play. Effectively, this structure only increments the smallest counters by one.

Let’s visualize this. All counts start off at zero. And let’s assume we have two items for which to track access frequency. At the beginning we have a set of distinct, zeroed counters {0, 0, 0, 0, 0, 0}:

After we record a hit on item A, we increment its smallest counters by one. Since all counters are zero, the counters for item A become {1, 1, 1}, and the total set becomes {1, 0, 1, 0, 0, 1}:

Once we record a hit on item B, we increment only its smallest counters – but note that it shares a counter with item A. Therefore, we only increment the two non-shared counters. Item B’s counters also become {1, 1, 1}, and the total set becomes {1, 1, 1, 0, 1, 1}:

If we had initially had three hits on A, its counters would be {3, 3, 3}; the total state would be {3, 0, 3, 0, 0, 3}. The counters for B would be {0, 0, 3}. Because we only ever increment or use the least of the counters, item B still has a hit rate of 0!

Using a probabilistic data structure (like a Bloom filter) for this purpose is ideal; it has predictable bounds of error, and it significantly reduces the total number of counters we need. (For more on probabilistic algorithms and data structures, I highly recommend Tyler McMullen’s talk, It Probably Works.)

Reducing Size of Counters

We already saw how reducing counters to even 1 byte can be cost prohibitive. With our Bloom filter, we significantly reduce the total number of counters we need. But we can still save more. Citing my favorite observation from the paper:

…a frequency histogram only needs to know whether a potential cache replacement victim that is already in the cache is more popular than the item currently being accessed. However, the frequency histogram need not determine the exact ordering between all items in the cache.

Because the aging policy of TinyLFU resets all counters simultaneously (instead of using e.g. a sliding window), and because of this observation that we only care about the popularity of an individual item with respect to the popularity of all cached items (irrespective of their ordering), we get another nice space savings win.

Using this information, the draws two conclusions:

[Given] a cache of size C, all items whose access frequency is above 1/C belong in the cache (under the reasonable assumption that the total number of items being accessed is larger than C).

This statement took me months to understand.

We have a cache sized to C, but this size is (potentially much) smaller than the total set of items S that could be accessed through it (as is true for many applications of a cache). So C is smaller than S.

Let’s assume that we have N requests for M distinct objects over some time period. It doesn’t matter what the time period is. Any distinct item I requested within our N requests, may have been requested more than once. D is what we’ll call the number of times I was requested during this sample. What this statement says is when D/N is larger than 1/C, the item I should be cached.

But it turns out that our aging factor gives us a time period in terms of number of requests already! We sample our frequency counts based on this number W. So now we get this really great caching rule:

Cache I when D/W is larger than 1/C.

But wait! This means that we don’t actually care about D, just the relationship between the ratios. This means that we can cap our counters at W/C. Since W is somewhat arbitrarily defined (a larger sample size increases accuracy of the frequency histogram with respect to the frequency of any individual cacheable item), this also means we get to say how much space we want to waste. The paper elightens us to the space savings:

To get a feel for counter sizes, when W/C = 8, the counters require only 3 bits each, as the sample is 8 times larger than the cache itself. For comparison, if we consider a small 2K items cache with a sample size of 16K items and we do not employ the small counters optimization, then the required counter size is 14 bits.

This choice also affects the number of counters we need to keep track of. In particular: if you define W as 8C, you only need to keep enough counters to represent the number of distinct object accesses you have across 8C requests. If your cache size is something around 100 million objects, you only need to care about the average uniqueness of 800 million requests. This is usually something you can measure.

The Doorkeeper

Especially in HTTP caches, long-tail objects account for a large portion of cacheable content. These are objects that are usually pretty low frequency, but live forever. Furthermore, such items will usually only get a single hit (if any) within the sample time. Why should we keep around “fat” counters for items that rarely see hits?

The Doorkeeper solves this problem: it is a single-bit minimum-increment counting Bloom filter. Any incoming requests for items must pass the Doorkeeper before being promoted to fat counters, effectively allowing us to use fewer fat counters than we would otherwise need: a double savings.

Once we have all these bits in place, we can simply couple this algorithm to whichever cache we choose – be it LRU, ARC, SLRU, 2Q, or whatever else floats your fancy.

Wrapping Up

We’ve looked at the components of TinyLFU, and discussed how Window TinyLFU solves a number of issues that have prevented practical use of LFU strategies for large caches.

I’ll be following this post up in the next couple months with some implementation approaches. I have an interesting (but maybe obvious) idea to do with promoting items from the window cache to the main cache, which I’d like to explore. I also have some ideas on how this can be implemented in a lock-free fashion, which is critical for caches with highly concurrent workloads. There are also a few optimizations that can be made around things like the Doorkeeper.

After that, we’ll take a look at some experimental results. The paper presents some results, but I’d like to take a look at how this works on gigantic data sets.