Blog

Measuring a hot stack split

One benchmark had a strange cliff: adding an innocent-looking local array made a short recursive walk much slower. I suspected cache effects first. The CPU profile pointed at the runtime’s stack-growth path instead.

A goroutine begins with a small stack. Before a function uses its frame, generated code checks whether enough stack remains. If not, the runtime grows the stack by adding another segment and resumes the call. A special stack-splitting path does the unpleasant bookkeeping so ordinary Go code can continue pretending stacks are infinite, at least until memory becomes considerably less theoretical.

The benchmark was more useful as a depth sweep than as one headline number. I ran the same walk at depths 8, 16, 32, 64, and 128, then repeated it with a slightly larger local frame. Most points scaled smoothly. One narrow range jumped when calls repeatedly reached the end of a segment.

The segmented arrangement makes the initial cost of a goroutine small, but it is not magic. Each goroutine still has scheduler state and a stack segment. Every additional segment consumes memory. Deep recursion can grow a stack dramatically, and keeping the goroutine alive keeps its stack alive as well.

That narrow range is the interesting bit. If a function arrives with almost, but not quite, enough room, it grows the stack; returning can release the segment, and the next call grows it again. This “hot split” makes a particular call depth look much worse than its neighbours. A single benchmark depth can therefore blame the algorithm for standing on an implementation seam.

I checked the profile at the slow depth, then moved the benchmark one call shallower and deeper. The runtime samples faded at both neighbours. That was better evidence than merely noticing that recursion was involved. Changing the benchmark’s local array size moved the cliff too.

I did not contort the application to dodge one segment boundary. The runtime implementation will change, and ordinary code should not depend on today’s segment size. I did keep the depth sweep: it tells me whether a future optimization improves the work or merely moves the cliff.

Small stacks still make many goroutines practical. They also leave fingerprints in microbenchmarks. When one input size falls off a ledge, profile it and test both sides before rewriting the loop.

FOR is evil or something

Have you ever wondered how FORs impact your code? How they are limiting your design and more important how they are transforming your code into an amount of lines without any human meaning?

How can you not want to read an article that starts like that? I had to steal the intro from the original. Seriously, I have used FOR since I learned BASIC back in the day. I never thought about how it was limiting my design. I. Must. Learn. How.

The article I am referring to is, Avoiding FORs – Anti-If Campaign. Eager learner I, I could not not read it.

After the resplendent intro, Avoiding FOR goes on to show “how to transform a simple example of a for […], to something more readable and well designed.”

It takes this unreadable piece of code — that I now recognize as unreadable:

[java]
public class Department {

private List resources = new ArrayList();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {

    for (Resource resource : resources) {
        if(resource.lastContract().deadline().after(new Date())) {

            System.out.println(resource.name());
            System.out.println(resource.salary());
        }
    }
}

}[/java]

My eyes hurt already. Thankfully the author transforms the aberration above into this clean, much more readable snippet:

[java]public class ResourceOrderedCollection {

    private Collection<Resource> resources = new ArrayList<Resource>();



public ResourceOrderedCollection() {
    super();
}

public ResourceOrderedCollection(Collection<Resource> resources) {
    this.resources = resources;
}

public void add(Resource resource) {
    this.resources.add(resource);
}

public void forEachDo(Block block) {
    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        block.evaluate(iterator.next());
    }

}

public ResourceOrderedCollection select(Predicate predicate) {

    ResourceOrderedCollection resourceOrderedCollection = new ResourceOrderedCollection();

    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        Resource resource = iterator.next();
        if(predicate.is(resource)) {
            resourceOrderedCollection.add(resource);
        }
    }

    return resourceOrderedCollection;
}

}

public class Department {

private List<Resource> resources = new ArrayList<Resource>();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {
    new ResourceOrderedCollection(this.resources).select(new InForcePredicate()).forEachDo(new PrintSlip());
}

}[/java]

Wait, what? Is this an Onion article?

Snarky Mode Off.

I understand what the author wanted to do, but really, the example used is so off the left field that it’s not even funny.

Where did that Go value escape to?

I changed a small parser to reuse a helper and made it slower. This was irritating because the new version looked cleaner, performed the same amount of useful work, and did not contain the traditional performance feature known as “a very silly loop.”

The reduced example looked like this:

type point struct {
	x, y int
}

func origin() *point {
	p := point{}
	return &p
}

Anyone arriving from C may feel a brief alarm here. p is local, yet the function returns its address. Go makes this safe by deciding where the value must live. The important distinction is not whether the source declares a value inside a function. It is whether the compiler can prove that the value stops being reachable when that function returns.

If it cannot, the value escapes and is allocated somewhere with a lifetime long enough for its uses, normally the heap. If it can prove the value remains local, it can use the goroutine’s stack. This analysis is why Go can permit returning a pointer to a local without turning every local variable into a heap allocation.

A small experiment

I wrote two deliberately uninteresting benchmarks:

var sink *point

func local() int {
	p := point{x: 20, y: 22}
	return p.x + p.y
}

func escaping() int {
	p := point{x: 20, y: 22}
	sink = &p
	return p.x + p.y
}

The arithmetic is identical. The assignment to the package variable is not. After escaping returns, another function can read sink, so p must survive. The compiler cannot put it in a dead stack frame and hope nobody notices.

The compiler can print its decisions. Building with the compiler’s escape-analysis diagnostics enabled is considerably more useful than staring at new(point) and guessing. The exact wording and flags are compiler details and may change, but reports identifying values moved to the heap make a good starting point.

This matters because source syntax alone is a poor allocation detector. new(T) does not decree that T lives on the heap. Returning a value does not decree that a copy must be heap allocated. Conversely, innocent-looking interface conversions, closures, or calls through code the compiler cannot fully inspect may cause values to escape.

Interfaces and hidden addresses

Suppose I replace a direct call with this:

func printAny(v interface{}) {
	fmt.Println(v)
}

func report() {
	p := point{x: 20, y: 22}
	printAny(p)
}

Putting p into an interface constructs an interface value containing dynamic type information and the value’s data. Depending on what the compiler knows about the call and how that data is represented, it may need storage beyond the current frame. The right answer is not “interfaces allocate.” The right answer is to inspect this particular program with this compiler, then measure it. Blanket rules age badly.

Closures offer a more obvious case:

func counter() func() int {
	n := 0
	return func() int {
		n++
		return n
	}
}

The returned function still uses n, so n cannot disappear when counter returns. The compiler arranges storage for the captured variable. This is not a leak. It is the semantics I asked for, delivered with a bill attached.

Stack is not a moral achievement

It is tempting to read an escape report as a list of compiler failures. That is not helpful. Heap allocation is necessary whenever data outlives a call, and Go’s garbage collector exists precisely because many useful objects do. The report says where the compiler could prove a lifetime, not whether the code is virtuous.

Still, allocations have costs. Allocating requires runtime work. More live heap data gives the garbage collector more to consider. A short-lived object may be cheap, but a hot loop producing millions of them deserves attention. I use benchmarks to establish that the path matters, allocation diagnostics to locate candidates, and another benchmark to verify the change. Reversing this order produces beautifully optimized code nobody needed.

Sometimes a small API change keeps a value local. A function can fill a caller-owned value instead of returning a pointer:

func setOrigin(p *point) {
	p.x = 0
	p.y = 0
}

func distance() int {
	var p point
	setOrigin(&p)
	return p.x + p.y
}

Passing an address does not automatically force escape. If the compiler can see that setOrigin does not retain it, p may remain on the caller’s stack. Again, the analysis follows lifetime, not punctuation.

I fixed my parser by removing one retained pointer from a frequently called helper. The result allocated less and recovered the lost time. I did not redesign every function to avoid pointers, because that would exchange a measured problem for a readability problem.

Escape analysis is best treated as an explanation facility. It tells me why the runtime is allocating when a profile says allocation matters. That is much better than the old C technique of declaring stack allocation “fast,” then accidentally returning its address and discovering a more exciting category of performance bug.

Rolling out your own Fusion Drive with the recovery partition

disk utility showing Fusion Drive

My Macbook Pro has two disks, an HDD and an SSD, each of 240GB or so. With the details of Apple’s Fusion Drive coming out I decided to do what any reasonable geek would do to their production computer: I’ve decided to implement my own untested, highly experimental and barely understood Fusion Drive.

One of the things that initially put me off doing this was that according to the 3,471,918 tutorials that have popped up in the last 10 minutes would cause me to lose my Mountain Lion recovery partition because these partitions are not supported in a Fusion drive. Turns out this is not exactly true.

Fusion Drive is just a marketing term for a what essentially is a CoreStorage logical volume spanning an SSD and an HDD. And although you cannot have the recovery partition inside a CS logical volume, it doesn’t mean you can’t have both a recovery partition and a Fusion Drive at the same time. It’s all in the diskutil man page, by the way:

Create a CoreStorage logical volume group. The disks specified will become the (initial) set of physical volumes; more than one may be specified. You can specify partitions (which will be re-typed to be Apple_CoreStorage) or whole-disks (which will be partitioned as GPT and will contain an Apple_CoreStorage partition). The resulting LVG UUID can then be used with createVolume below. All existing data on the drive(s) will be lost. Ownership of the affected disk is required.

What matters is what’s in bold above: we’re not limited to using whole disks. So here’s what I did.

I rebooted my system and held the option key so I could select my recovery partition as the start up disk. Once the OSX recovery started up, I launched a terminal to do the dirty work.

diskutil list

From this I noted two things: (a) the main SSD partition (the one holding my OSX and that sited by my recovery partition) and (b) the disk name of my HDD. They were respectively disk0s2 and disk1 in my case, but they’ll very likely be different for you. Then the magic begins.

diskutil cs create "Fusion Drive" disk0s2 disk1

(For crying out loud, you need to change disk0s2 and disk1 for whatever makes sense on your system!)

That created the coreStorage logical volume. Then I listed it all again to note what the new logical volume UUID was.

diskutil list

The UUID is a long number identifier like F47AC10B-58CC-4372-A567-0E02B2C3D479. You’ll need that one next to actually create the volume where you’ll be installing your system.

diskutil coreStorage createVolume F47AC10B-58CC-4372-A567-0E02B2C3D479 jhfs+ "Macbook FD" 100%

The command above will create a volume named “Macbook FD” using 100% of the logical volume we had created earlier.

I then restored my Time Machine backup and that’s it.

Update: Note that after this process, the Recovery partition will still be present and things that require it (such as Find My Mac) will work fine. Some people correctly pointed out, however, that you can no longer boot from the recovery partition by using the menu from holding ⌥ (option) during boot. I’m not sure why that is, but fear not, it will still boot normally from pressing ⌘R (command + R).

Not a-ok

I have a little confession to make: our family is going through a rough patch. Both my wife and I are having problems. No, not between us. And both are experiencing very different sorts of problems. But the happening-at-the-same-time complicates the one-supports-the-other thing.

And to compound to that, I have been sick.

As I sat in the waiting room at the hospital the other day, waiting for some exams, I felt like this is one of the worst times of my life. I feel tired, unmotivated, unappreciated, and generally unhappy. And fucking hopeless. That’s the worst part, I suppose.

I also have been distancing myself from friends lately. Ostensibly to avoid distractions in a time where I am having to give all and a bit more to a project I do not believe in. Truth be told, I just don’t feel like small talk but I also don’t want bring others down to my Dark Hole of Misery. And so I’m trying to keep some distance.

I feel lost. I look at my friends and how they all seem to have it all figured out already. I’m still trying to figure out who the fuck I am. I was so sure when I was younger. I was so fucking good at what I did. Now? I just don’t know anymore. I feel unhappy.

I know some people who will be So. Fucking. Happy. reading the paragraph above. This one’s for free for you guys.

But not all is bad news. I actually got some good news last night. I can’t tell the details although I know some of you know exactly what this is about. Anyway, I now have a set date for it and it’s in under six months from now.

I’m actually confident that this will make it all better somehow. Just have to wait.

Sorry for the downer, but I felt like writing something.