Chapter 20: Designing for Performance

Core Idea

Clean design and high performance are compatible. Know which operations are fundamentally expensive and choose “naturally efficient” designs that are also simple. When something is still too slow, measure first, prefer a fundamental fix, and as a last resort redesign the code around its critical path with special cases moved off it.

Frameworks Introduced

• How much to worry about performance: between two extremes.
  • Optimizing every statement slows development and adds complexity, and many “optimizations” don’t help.
  • Ignoring performance entirely spreads inefficiencies everywhere, making a system easily 5–10x slower than necessary. This is “death by a thousand cuts,” and no single later fix helps much.
  • The middle: use basic performance knowledge to choose alternatives that are “naturally efficient” yet clean and simple.
• Know what’s expensive (the book’s 2018 figures):
  • Network round trip: 10–50 µs within a datacenter (tens of thousands of instruction times); 10–100 ms over a wide area.
  • Secondary storage I/O: disk 5–10 ms (millions of instruction times); flash 10–100 µs; emerging nonvolatile memory perhaps 1 µs (about 2000 instruction times).
  • Dynamic memory allocation (malloc, new): significant overhead for allocating, freeing, and garbage collection.
  • Cache misses: a few hundred instruction times to fetch from DRAM; often as important as computation.
  • Learn costs with micro-benchmarks. RAMCloud spent a few days on a framework that lets someone add a new micro-benchmark in five or ten minutes.
• When efficiency costs complexity:
  • A small amount of hidden complexity that doesn’t affect interfaces may be worth it (“but beware: complexity is incremental”).
  • A lot of implementation complexity, or more complicated interfaces: start simple and optimize later if needed.
  • Clear evidence that performance will matter: build the faster approach now. RAMCloud bypassed the kernel for networking because earlier measurements showed kernel networking would be too slow; getting that one big issue right made the rest easier to keep simple.
• Measure before modifying: “Programmers’ intuitions about performance are unreliable,” even for experienced developers.
  • Measure deeply enough to find a small number of very specific places where time goes and where you have ideas for improvement.
  • Keep the measurements as a baseline. If a change doesn’t make a measurable difference, back it out, unless it made the system simpler.
• Fix in this order:
  1. A fundamental fix: a cache, a different algorithm (balanced tree versus list), or a different mechanism (kernel bypass). Implement it with the book’s normal design techniques.
  2. Design around the critical path (last resort):
     • Ask what is the smallest amount of code that must run for the common case. Ignore the existing structure, special cases, and method boundaries. Imagine one method and the most convenient data structures, perhaps combining several variables into one value. This is “the ideal.”
     • Find a clean design that comes as close as possible to the ideal. A little extra code for clean abstractions is fine, such as a call to a general-purpose hash table class.
     • Remove special cases from the critical path. Ideally a single if at the start detects all special cases; the normal path then runs with no more tests, and special cases branch off to code structured for simplicity.

Key Concepts

• Naturally efficient design: as simple as the slow alternative but faster. Examples: use a hash table rather than an ordered map unless you need ordering (hash tables can easily be 5–10x faster); store structs directly in a C/C++ array rather than an array of pointers, so one allocation covers everything.
• Critical path: “the minimum amount of code that must be executed in the the most common case.”
• Fundamental fix: a change in approach rather than in code details.
• Simpler code is faster: defined-away special cases need no checks; deep classes do more work per call, while shallow ones add layer crossings, each with overhead.

Mental Models

• “Complicated code tends to be slow because it does extraneous or redundant work.”
• Think of performance problems as usually concentrated in a few specific places, which only measurement reveals.
• If you write clean, simple code, your system will probably be fast enough that you rarely need to optimize.

Anti-patterns

• Tweaking by intuition: wastes time and adds complexity without speedup.
• Measuring only top-level performance: it tells you the system is slow, not why.
• Keeping complexity that didn’t measurably help.
• Many shallow layers with the same signature on a hot path (see worked example).

Code Examples

char* Buffer::alloc(int numBytes)
{
    if (this->extraAppendBytes >= numBytes) {
        // There is extra space at the end of the current
        // last chunk, so we can just allocate the new
        // region there.
        Buffer::Chunk* chunk = this->lastChunk;
        char* result = chunk->data + chunk->length;
        chunk->length += numBytes;
        this->extraAppendBytes -= numBytes;
        this->totalLength += numBytes;
        return result;
    }

    // We're going to have to create a new chunk.
    ...
}

• What it demonstrates: the redesigned critical path (Figure 20.3). One method, one test that rules out every special case, then straight-line code.

Worked Example

Speeding up RAMCloud’s Buffer class by about 2x.

1. What a Buffer is (Figure 20.1). It looks like one linear array of bytes but is stored as discontiguous chunks. Internal chunks live in the Buffer’s own storage (a small built-in allocation plus extra allocations freed with the Buffer); external chunks refer to the caller’s memory. The Buffer itself was a fundamental fix: a response with a short header and a large object uses an internal chunk for the header and an external chunk for the object, so the object is never copied.
2. Why optimize. Buffers spread until at least four were created per remote procedure call, so their speed began to matter.
3. Pick the critical path. The most common operation is allocating a little space in an internal chunk, for example for message headers. The ideal: one check that the last chunk is internal and has room, then grow it.
4. The original code (Figure 20.2). Buffer::alloc called Buffer::allocateAppend, which called Buffer::Allocation::allocateAppend. It tested 6 distinct conditions on the fast path: whether any allocations existed, whether there was room (checked twice), whether allocation succeeded (checked again), and then whether the new space happened to be adjacent to the last chunk so it could be merged. All three methods had nearly identical signatures and abstractions, a red flag (ch07), and Buffer::allocateAppend was nearly a pass-through method.
5. The redesign. The team redesigned the class around its critical paths, including others such as getting the total byte count. They added an instance variable, extraAppendBytes: the unused space right after the last chunk, which is zero if there’s no space, if the last chunk isn’t internal, or if there are no chunks. Now one test covers every special case. They kept a running totalLength, a small cost in alloc, because recomputing it from many chunks would be expensive and reading the total length is another common operation.
6. Results. Appending a 1-byte string with internal storage dropped from 8.8 ns to 4.75 ns. Constructing a Buffer, appending a small internal chunk, and destroying it dropped from 24 ns to 12 ns. The class shrank by 20%, from 1886 to 1476 lines, and became easier to read.

Key Takeaways

1. Learn the rough costs of network calls, storage I/O, allocation, and cache misses, and use micro-benchmarks.
2. Choose naturally efficient designs whenever they are just as simple.
3. Accept extra complexity for speed only when it is hidden or when you have clear evidence it is needed.
4. Measure before and after every optimization, and back out changes that don’t help.
5. Look for a fundamental fix before rewriting code.
6. When rewriting, design around the critical path with a single test for all special cases.

Connects To

• Ch 4: deep classes are faster as well as simpler.
• Ch 7: same-signature layers on the critical path are a red flag.
• Ch 10: defining away special cases removes checks.
• Ch 11: the critical-path “ideal” is another design alternative to compare against.
• Ch 18: the Buffer::allocAux example of blank lines and block comments.