Blog

I had several sorted result files and wanted one sorted stream without loading everything into memory. The classic algorithm is a k-way merge: keep the next item from each input, emit the smallest, then advance only that input.

My first Go version gave every file reader a goroutine and a channel. The merger holds one current value per channel:

type item struct {
    value int
    open  bool
}

func source(values []int) <-chan int {
    out := make(chan int)
    go func() {
        for _, value := range values {
            out <- value
        }
        close(out)
    }()
    return out
}

The merge loop initializes one item from every source, scans those current values for the smallest, emits it, and receives the replacement from the chosen source. When that receive reports the channel closed, the source leaves consideration. Memory remains proportional to the number of sources, apart from buffering in the file readers.

A linear scan makes each output operation $O(k)$, where $k$ is the number of inputs. That is fine for four files and silly for four thousand. Replacing the scan with a binary heap makes selection $O(\log k)$. I implemented both and found the simple scan faster for my actual case of eight inputs. Algorithms still have constants, despite textbooks’ efforts to protect us from them.

Channels help isolate blocking input, but they do not improve the comparison algorithm. That distinction matters. Concurrency lets readers overlap waiting on disks or pipes; the heap changes CPU work. Combining both without measuring can add scheduling overhead to a problem that was already fast.

There is also a shutdown question. If the consumer stops early, source goroutines may remain blocked trying to send. My real version includes a separate stop channel selected by each producer, and the caller closes it when abandoning the merge. A finite example that always drains output can omit this, but reusable code cannot.

This code targets the January 2011 snapshot. Channel receive conventions and library calls should be checked against that compiler. The useful design survives those changes: one lookahead value per sorted source, explicit ownership of advancement, and a selection structure chosen for the actual number of streams.

I ran two independent CPU loops in goroutines and expected my dual-core machine to halve the time. It did not. Expectations remain the cheapest profiler available and the least accurate.

This runtime defaults to limited processor use. Setting GOMAXPROCS=2 for the experiment allowed Go work to execute on two operating-system threads:

$ time GOMAXPROCS=1 ./spin
real  0m3.84s

$ time GOMAXPROCS=2 ./spin
real  0m2.17s

The result is not exactly half. Both loops touch memory, the scheduler has work, and the rest of the machine has declined to disappear for my benchmark.

Goroutines and parallel execution are separate ideas. Thousands of goroutines can make a concurrent design clear while one thread runs them. Increasing the thread allowance can provide parallelism when there is independent CPU work and hardware to execute it.

The early scheduler also has rough edges. A tight loop with no calls may delay other goroutines more than I expect from mature thread schedulers. I add real synchronization rather than relying on hopeful fairness, and I test the weekly runtime I intend to use.

For I/O-heavy programs, two processor threads may change little. For CPU loops, it can help until memory bandwidth or coordination dominates. The variable is a knob, not a turbo button. Turbo buttons at least had a satisfying light.

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.

Coming from C, I first read a Go slice as a pointer with nicer indexing. That model works until append allocates a new backing array or a tiny subslice keeps a large allocation alive. The missing piece is that a slice is a small descriptor, not the array itself.

Conceptually, the descriptor contains three items:

+---------+--------+----------+
| pointer | length | capacity |
+---------+--------+----------+
     |
     v
+----+----+----+----+----+
| 10 | 20 | 30 | 40 | 50 |
+----+----+----+----+----+

The pointer identifies an element in a backing array. Length controls the elements currently accessible through indexing. Capacity describes how far the slice may grow from that starting point before another array is needed. This is a conceptual layout, not a promise that user code should depend on runtime internals.

Given an array and a slice:

a := [5]int{10, 20, 30, 40, 50}
s := a[1:3]

fmt.Println(len(s), cap(s))

my snapshot prints:

2 4

The slice sees 20 and 30, and it has capacity through the end of a. Assigning s[0] = 99 changes a[1] because both views refer to the same storage. Passing s to a function copies the descriptor, but both descriptors still point at that storage.

This explains a function that appears not to resize its caller:

func grow(s []int) {
    s = append(s, 60)
}

The local descriptor changes. The caller’s descriptor does not. If the append fits within capacity, the backing array may contain the new element, but the caller’s length still excludes it. If it does not fit, append obtains another backing array and the local slice points there. The useful pattern is to return the result:

func grow(s []int) []int {
    return append(s, 60)
}

s = grow(s)

The same mechanism makes append performance less mysterious. Growing one element at a time does not normally allocate an array on every call. Capacity grows in larger steps and existing elements are copied when storage changes. The exact growth policy belongs to this experimental runtime and should not become an application assumption.

I verified allocations indirectly by timing construction with and without an initial capacity:

a := make([]int, 0, 100000)
for i := 0; i < 100000; i++ {
    a = append(a, i)
}

When the final size is known, reserving capacity avoids repeated growth and copying. When it is not known, append’s policy is generally better than inventing my own allocation scheme. Capacity is a performance hint with semantic consequences, not a target to maximize.

Subslice lifetime is the less obvious consequence. I wrote a reader that loaded a large file, found one short token, and returned a slice containing that token. The token was only a few bytes, but its descriptor still pointed into the large backing array. As long as the small slice remained reachable, the collector could not reclaim the array.

The fix was to copy the useful bytes into a new, correctly sized slice:

token := make([]byte, end-start)
copy(token, data[start:end])
return token

Copying sounds wasteful until the alternative is retaining several megabytes for a twelve-byte identifier. Profiling the whole process settled that argument quickly.

Overlapping slices deserve similar care. copy is the operation intended for moving slice contents, including overlap supported by the implementation. Hand-written forward loops can overwrite input before reading it. This is one of those cases where code that looks closer to C is merely closer to a C bug.

Slices also make zero values useful. A nil slice has length and capacity zero, can be ranged over, and can be appended to. For many producers there is no need to allocate an empty slice eagerly. An empty non-nil slice may still matter at an encoding boundary, but inside the program I prefer the simpler zero value unless behavior says otherwise.

Arrays remain values with their length in the type. Assigning an array copies its elements, and [4]int differs from [5]int. Slices provide the flexible view normally wanted by functions. Remembering that distinction prevents a great deal of accidental copying and aliasing.

All of this describes the November 2010 toolchain I am using. Syntax, built-ins, and growth details may change before a stable release. The useful mental model is simpler: a slice is a copied descriptor over shared storage. Ask which descriptor changes, which array it references, and who keeps that array alive. That usually finds the surprise.

I wanted a diagnostic printer for configuration structures and reached for reflection. That is normally the moment a small helper begins applying for framework status, so I kept the experiment deliberately narrow.

An interface value carries a dynamic type and value. The reflect package exposes descriptions of those two parts. In my weekly snapshot the entry points and names differ from examples written against other snapshots, so I will not pretend this code is timeless:

v := reflect.NewValue(x)
t := reflect.Typeof(x)
fmt.Println(t.String(), v.Kind())

From there I can switch on kind, inspect structure fields, and recursively print supported values. The mechanism is not source-code introspection. It is runtime examination of type information retained for a value.

The first rule I learned is to separate validity, kind, and concrete type. A pointer is not its element. An interface can contain a pointer. A nil interface and an interface containing a nil pointer are different states. Reflection faithfully presents these distinctions, even when I would prefer it to edit my mistake.

The second rule is that settable values are special. Inspecting a copy obtained from an interface does not grant permission to modify the original. To change a caller’s value, reflection needs an addressable value, usually reached through a pointer and then its element. This is good friction. Generic mutation should look dangerous because it is.

I ended with a read-only printer supporting strings, integers, slices, and exported structure fields. Unsupported kinds produce an explicit marker. I did not add automatic conversion, tag syntax, or clever cycle handling because the tool does not need them.

Reflection trades compiler knowledge for runtime decisions. Misspelled field assumptions become execution-path problems, and every branch is harder to read than direct code. It is justified when the types truly vary, as in encoders and diagnostics. It is not justified merely to avoid writing three straightforward assignments.

My opinion after using it is positive but cautious. Go’s reflection model follows the interface representation and type system rather than inventing a parallel object universe. Still, if ordinary interfaces can express the job, they are clearer and checked earlier. Reflection is a sharp tool. Keeping the lights on means seeing both the blade and the fingers.