C

I appreciate beautiful, readable code. And if someone were to ask me for an example of beautiful code, I’ve always had the answer ready: the linked list implementation in the Linux kernel.

The code is gorgeous in its simplicity, clarity, and amazing flexibility. If there’s ever a museum for code, this belongs there. It is a masterpiece of the craft.

I was just telling a friend about it while we talked about beautiful code and he found this piece that I share here: Linux Kernel Linked List Explained.

Kernel code contains algorithms that look unnecessarily peculiar until the constraints are visible. Population count, the number of set bits in a machine word, is a good example.

The obvious C version examines every bit:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                n += word & 1;
                word >>= 1;
        }
        return n;
}

This performs one iteration for every bit position up to the highest set bit. A sparse bitmap still pays for all the zeros in between.

Brian Kernighan’s familiar operation removes the lowest set bit at each iteration:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                word &= word - 1;
                n++;
        }
        return n;
}

Subtracting one flips the lowest set bit to zero and turns lower zeros into ones. The & keeps everything above that bit and clears the changed suffix. The loop therefore runs once per set bit.

That is excellent for sparse words and less impressive for dense ones. Kernels also use table lookups and architecture-specific instructions where available. A byte table has predictable work but adds memory access; a processor instruction can win decisively but needs dispatch or compile-time selection. There is no universally fastest source fragment independent of data and machine.

Word width matters too. Kernel types and helpers make that choice explicit, while a casual userspace benchmark can accidentally compare different widths and announce a victory produced by less work.

I benchmarked the two loops over generated sparse and dense arrays, keeping generation outside the timed section. As expected, the clear-lowest-bit version dominated sparse input. Dense input narrowed the gap considerably. Repeating one constant word produced lovely numbers and measured the compiler more than the routine, so I stopped doing that.

The broader lesson from kernel work is to understand the representation before admiring the trick. Bitmaps pack state compactly and permit word-at-a-time operations, but contention, cache placement, and scan direction can matter more than shaving an instruction from population count.

I like this algorithm because its mechanism fits in one sentence and its performance caveat requires another. Most optimization stories should have both sentences. The ones with only the first usually end in a benchmark that accidentally proves the author’s laptop exists.

The language can make a brute-force search faster, but eliminating unnecessary work is better. Substituting $c = 1000 - a - b$ into the Pythagorean equation and solving for $b$ leaves only one variable to search:

#include <stdio.h>

int main(void)
{
    const int sum = 1000;

    for (int a = 1; a < sum / 3; ++a) {
        const int numerator = sum * (sum - 2 * a);
        const int denominator = 2 * (sum - a);

        if (numerator % denominator != 0)
            continue;

        const int b = numerator / denominator;
        const int c = sum - a - b;

        if (a < b && b < c) {
            printf("%d %d %d = %d\n", a, b, c, a * b * c);
            return 0;
        }
    }

    fputs("no solution\n", stderr);
    return 1;
}

The divisibility check ensures that b is an integer. This searches fewer than sum / 3 candidates in constant space and prints $200 \times 375 \times 425 = 31\,875\,000$.

I have too much useful C code to pretend a new language arrives on an empty disk. My first serious Go experiment therefore needed an old image-processing library. That led directly to cgo, then to several hours learning that a foreign-function interface is a border crossing, not a transparent bridge.

The smallest call is almost suspiciously simple. In the snapshot I used, a preamble before import "C" declares the C side:

package scale

/*
#include <stdint.h>

static uint32_t clamp(uint32_t v, uint32_t limit) {
    return v < limit ? v : limit;
}
*/
import "C"

func clamp(v, limit uint32) uint32 {
    return uint32(C.clamp(C.uint32_t(v), C.uint32_t(limit)))
}

The exact generated names and build steps are tied to this weekly release. cgo is changing quickly, so this is a field note rather than a durable manual. I run cgo as part of the package build, compile its generated C, then let the normal architecture-specific tools finish the package.

Scalar conversion is the easy part. Buffers force the real questions: who owns the memory, how long does an address remain valid, and may either runtime retain it after the call? I settled on a strict rule for this experiment: Go calls C synchronously, C consumes the supplied bytes before returning, and C stores no pointer into Go-managed memory.

For output allocated by the C library, I expose a C release function and call it with defer immediately after checking the returned pointer. That keeps allocation and release in the same ownership domain. Wrapping a C allocation in a Go slice may avoid a copy, but it also makes lifetime assumptions much easier to hide. I copy unless profiling proves the copy matters.

Strings are another ownership test disguised as convenience. A Go string is not a NUL-terminated C string. Conversion may allocate. Embedded zero bytes have C semantics whether I find them philosophically agreeable or not. Passing length explicitly is better whenever the C API permits it.

Then I measured the crossing. I called a trivial C function in a loop and compared it with the same arithmetic written in Go. The absolute figures are not worth publishing because both cgo and the compiler are moving, but the shape was obvious: crossing for every pixel was disastrous; crossing once per image was lost in the actual work.

That changed my wrapper. The first version exposed the C library nearly function for function:

Go pixel loop -> cgo -> C operation -> return

The revised version sends a whole row or image:

Go request -> cgo -> C loop over image -> return

The second interface is less “complete” and much more useful. It minimizes transitions and expresses the operation at the level where ownership is clear.

Callbacks in the other direction are harder. They combine scheduler state, foreign threads, and object lifetime. I avoided them by collecting results in C and returning a batch. That is not always possible, but it is a better starting point than assuming a C callback can enter arbitrary Go code safely. The runtime is young and its constraints deserve respect, not exploratory production outages.

Failures need translation too. The C library reports integer status codes and sometimes leaves detail in a structure. My wrapper converts those into a small Go value implementing the snapshot’s os.Error convention. I do not leak C constants throughout callers. If the library returns a partial result, the wrapper states whether that result remains valid and who frees it.

The build is the least elegant part. Header search paths, linker flags, and platform differences have not vanished; they have merely moved to the package boundary. This is still better than spreading them through the program, but cgo does not make a C dependency portable by blessing it with a comment.

I keep one integration test that allocates, calls, copies, releases, and repeats. It catches ownership regressions more reliably than staring harder at the wrapper.

My conclusion is deliberately conservative. cgo is excellent for preserving a tested, substantial C implementation. It is poor as a shortcut for tiny functions that cross the boundary constantly. Design a coarse interface, keep ownership explicit, translate failures once, and benchmark the complete operation. A border can support trade. It should not run through the middle of the kitchen.

Most of my systems work still begins in C. If the job needs a user interface, it usually grows a Qt shell. If it needs to be finished before lunch, a Python script appears beside it and quietly becomes permanent.

That arrangement works, but every boundary charges rent. The C tool has ownership rules, the Qt side has objects and signals, and the Python helper has a different deployment story. I have spent an unreasonable amount of time explaining to machines where their libraries live.

I have been trying the experimental Go compiler from the weekly snapshots. It is plainly unfinished, and the language may change under this post, but it occupies an interesting spot: compiled programs, garbage collection, a small syntax, and concurrency that does not begin with a page of pthread ceremony.

My first useful experiment was the sort of filter I normally write in Python:

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    for {
        line, err := in.ReadString('\n')
        if len(line) != 0 {
            fmt.Printf("%d %s", len(line), line)
        }
        if err == os.EOF {
            break
        }
        if err != nil {
            fmt.Fprintf(os.Stderr, "read: %s\n", err.String())
            os.Exit(1)
        }
    }
}

ReadString may return bytes together with os.EOF, so the line is handled before the error. That keeps a final line without a newline. EOF ends input normally; another os.Error gets reported instead of masquerading as a clean finish.

On my snapshot, I build that directly with 6g and 6l. A later snapshot may spell an import or an I/O call differently; that is currently part of the admission price.

The pleasant surprise is not that this is shorter than C. Python already wins that contest while barely getting out of bed. The surprise is that the result is a small native executable and the source still exposes the mechanics I care about. There is no class hierarchy between the input and me.

I do miss deterministic destruction from C++, especially around Qt resources. Garbage collection is not a substitute for closing a file. Go’s defer looks like the intended answer for many such cases, and I plan to abuse it scientifically.

I am not replacing working C or Qt code. That would be migration as a hobby, a particularly expensive hobby. I am moving the little glue programs first and watching where the new language becomes awkward. So far, it feels less like Python made fast and more like C with several recurring arguments removed.