It Works, and It's Too Slow

The tower works, and now you put it under load. Mira’s Courtyard server is popular. It runs on a machine with a fast card, and the wire can carry a gigabit a second, which is more than enough for a great deal of chat. Yet the server tops out while serving a small fraction of that, with the processor pinned at full and most of the wire idle. Nothing is broken. Every message is delivered correctly. The machine cannot keep up, and the wire it is attached to is mostly empty while it fails to.

To see why, you have to open the box you have been leaving shut since Chapter 7, which is the operating system, and look at what it does between a frame arriving and your program’s read returning. Follow one frame in, in full, the naive way, which is the way that is correct and slow.

The card receives the bits and assembles a frame in a little memory of its own. Now it has to tell the operating system, and the only means it has of getting the processor’s attention is an interrupt, a hardware signal that stops whatever the processor was doing, mid-instruction, and forces it to run a special handler. So the card interrupts. The processor drops its work, saves where it was, and runs the card’s handler. The handler copies the frame out of the card’s memory into the operating system’s memory. Then it hands control back, and the processor restores what it was doing and resumes, until the next frame arrives a few microseconds later and it is interrupted all over again.

Then the operating system walks the frame up the tower. It checks the frame (Chapter 3). It strips the frame header and reads the location header (Chapter 5). It strips that and reads the port header, and searches its socket tables for the four-tuple (Chapters 7 and 8). It places the bytes into that socket’s buffer, updates the sequence tracking, and decides whether to acknowledge (Chapter 11). Every one of these steps reads the frame’s bytes again where they sit in the operating system’s memory.

Finally your program calls read. The bytes are in the operating system’s memory, and your program lives in its own memory, which the operating system keeps strictly separate, for safety, so that one program cannot read another’s. So it copies the bytes across the boundary, from its memory into your program’s, and only then does read return.

Count the costs, because each one is about to become a fix. There is an interrupt per frame, which throws the processor off its work twice for every single frame. There are two copies of every payload, one from card to operating system and one from operating system to program. And there is the walk up the tower, some of which is repetitive per-frame arithmetic. At a few hundred bytes a frame on a gigabit wire, that is hundreds of thousands of frames a second, each paying all of it. The processor spends its life being interrupted and copying, and never gets to the actual work. That is the pinned processor and the idle wire.

Now descend the tower a second time, not to add correctness, which is done, but to remove cost. This is the first time in the book you are optimising anything, and it is allowed only because the correct version already exists, and you are not going to change what it means, only what it costs.

Start with the interrupts. An interrupt is expensive, since it throws the processor off its work and makes it save and restore state, and under load you are paying for one hundreds of thousands of times a second. But under load there is a fresh frame waiting almost always. The interrupt is telling you something you already know. So turn it off while the card is busy. The first frame interrupts. The handler, instead of processing one frame and re-enabling the interrupt, leaves the interrupt off and starts polling: it processes that frame, checks whether another has arrived, processes that too, and keeps going as long as frames keep coming. Only when the card runs dry does it turn the interrupt back on and go idle. Under load, that is one interrupt to enter a busy stretch and then pure polling through thousands of frames. When things are quiet, it is back to one interrupt per frame, which is fine, because when things are quiet you can afford it.

The machine now pays for interrupts in proportion to how bursty the traffic is, not how much of it there is. It is the idea of Chapter 14’s zero-window probe and Chapter 13’s heartbeat turned upside down. There, you added messages so that silence would carry information; here, you drop signals because their information is redundant. The technique is called interrupt coalescing, and the polling arrangement is the heart of what Linux calls NAPI.

Next, the first copy, in which the card’s handler lifts the frame out of the card’s memory into the operating system’s. This is pure waste, because the card can reach the machine’s main memory directly. So let it. Give the card, in advance, a set of empty memory buffers arranged in a ring, and let it write each arriving frame straight into the next one, itself, without the processor lifting anything. Now the processor’s handler does not copy. It looks at the ring and finds the frame already sitting in main memory, put there by the card while the processor was doing something else. A card writing to memory on its own is doing direct memory access, DMA for short, and the arrangement of pre-provided buffers is a ring buffer: the card fills a ring of waiting memory slots on its own, and the processor collects them at its leisure. One of the two copies is gone, and the processor was never involved in it.

The second copy, from operating system to your program, exists for a real reason, which is the memory boundary that keeps programs from reading each other. You cannot abolish it. But you can avoid it in the cases that matter most. The trick is to stop moving the bytes and start sharing them. If your program and the operating system can be made to point at the same physical memory, with the operating system arranging the protections so that this is safe, then the bytes the card wrote into the ring can be handed to your program without being copied at all. Your program reads them where they already are. Techniques with names like zero-copy do this, and the classic example is a server sending a file. Instead of reading the file into the program and then writing it to the socket, which is two copies through the program for bytes the program never even looks at, a single call tells the operating system to send the file to the socket directly, and the payload never enters the program’s memory at all. Zero-copy is neither free nor universal. It needs the bytes to be things the program does not have to touch, and it complicates the safety arrangements. But for the heavy flows, the video and the file transfers, it removes the last copy from the hot path.

That leaves the walk up the tower. Some of it is per-message logic that has to happen on the processor. But some of it is bulk, repetitive arithmetic: computing and checking the Chapter 3 checksums over every byte, and cutting a large outgoing message into frame-sized pieces (Chapter 10) and stamping each with its headers. Cards can do this, so hand it to them. Let the card verify checksums on the way in and compute them on the way out, and let the card take one large buffer and segment it into properly framed pieces itself. The processor hands the card a big chunk and a template, and the card emits the frames. This is offloading, and modern cards do a surprising amount of the lower tower in hardware.

There is a limit to all of this. Even a perfect version still walks each message through the operating system, across the protected boundary, once. For almost everything, that is fine. The operating system’s involvement is what gives you the safety and the sharing between programs, and it is cheap once the copies and interrupts are gone. But for a very small number of extreme cases, a machine whose entire job is to move packets at the absolute limit of the hardware, even that one crossing is too much, and the answer is to take the operating system out of the path altogether. A single dedicated program owns the card directly and runs its own tiny tower in user space, giving up the safety and the sharing in exchange for raw speed. This is called kernel bypass, and you should know that it exists and know that it is almost never what you want. It is mentioned here to mark the far end of the spectrum, not to recommend it. If you ever need it, you will know, and it will be someone else’s whole job.

Consider what none of this did. It did not change a single agreement. Messages are still framed, checked, addressed, numbered, acknowledged, and delivered in order. Your program still calls read and gets its bytes. Mira’s client cannot tell whether the machine it is talking to coalesces interrupts or uses DMA or offloads its checksums. The behaviour is identical; only the speed has changed.

That is what an optimisation is, and it is why this book made you wait twenty-two chapters for one. An optimisation is a change to cost that leaves meaning untouched, and you cannot tell whether meaning is untouched unless you first built the meaning and can see it clearly. Every optimisation in Part III, the caches, the spreading of load, the extra copies of data, will have this same shape and demand this same discipline. Build the correct thing. Confirm that it is correct. Then, and only then, make it faster, and check that you did not change what it does. Petzold, in Code, built the adder before complaining about how long the carry took, and the order is the same every time.

Mira’s server now serves the whole wire, because the machine spends its cycles on messages instead of on interrupts and copies. Part I is finished: a complete, correct, secure, and fast path from any program on one machine to any program on another, across a wire you can see, built as a tower of agreements you invented one at a time and can name and trace end to end.

And now the wire disappears. Mira is moving across the city. There will be no wire between your machines; there will be something, a vast something you do not own and cannot see into, made of other people’s boxes with their own interests. Everything you built assumed a path you controlled, or at least a path that was there. Part II is about what happens when the path becomes a stranger, and the first thing you will do is stop trying to understand it and ask instead what, precisely, it owes you.