There’s a very interesting article just out, C Is Not a Low-level Language;. in which David Chisnall punctures the comforting illusion that C is really a “close-to-the-metal” language and relates this illusion to the high costs of Spectre and other processor-level bugs.
Those of us who think seriously about language design have long been aware that C’s flat-address-space model is increasingly at odds with the real world of memory-caching hierarchies. Chisnall’s main contribution is to notice that speculative execution, the feature at the bottom of the Spectre and Meltdown bugs, is essentially a hack implemented to allow C programmers to maintain the illusion that they’re running on a really fast serial machine. But he has other interesting points as well.
I recommend reading Chisnall’s article before you go further with this post.
It’s no news to my regulars that I’ve been putting increasing investment into the Go language and now believe it a plausible candidate to replace C and C++ over most of C/C++’s range – that is, outside of kernels and hard realtime. So the question that immediately occurred to me upon reading the article was: Is Go necessarily productive of the same kind of kludge that Chisnall is calling out?
Because if it is – but something else isn’t – that could be a reason not to overcommit to Go. The twin pressures of demand for lower security defects and the increasing complexity costs of speculative execution are bound to toll heavily against Go if it does demand massive speculative execution and there’s any realistic alternative that does not. Do we need something much more divergent from C (Erlang? Ocaml? Even perhaps Haskell?) for systems programming to follow where the hardware is going?
So let’s walk through Chisnall’s discussion points, bounce Go off each one, and see what we can see. What we’ll find implies, I think, some more general conclusions about what will and won’t work in matching language design to real-world workloads and processor architectures.
On C requiring high “instruction-level parallelism”: So will Go if you write it like C. Sometimes this is not avoidable.
To write Go in a way that will keep a modern Intel processor’s instruction pipeline full you need, by Chisnall’s argument, to fruitfully decompose each serial algorithm into somewhere around 180 worker threads. Otherwise you need to do speculative execution to avoid having a significant chunk of your transistor budget simply behaving like a space heater.
Go, in itself, doesn’t solve this problem. Sure, it lowers the barriers – its implementation of CSP via channels and goroutines is quite elegant and a handier toolkit for writing massively concurrent code than I’ve ever seen before. But it’s only a toolkit; a naive translation of serial C code to Go is not going to use it and not going to solve your processor-utilization issue.
On the other hand, every other potential competitor to Go has the same problem. It might be the case that (say) Erlang or Rust or Haskell imply a better toolkit for massively concurrent programming, if one but knew how to use it. The problem is that the difficulty of moving any given chunk of production C code, or of writing a functional equivalent for it, rises in direct proportion to the ontological gap you have to jump to get from C to your new language.
The real cost of obsolescing speculative execution isn’t moving away from C, it’s what you have to do in your replacement language to go from a naive serial translation of your code to one that seriously jacks up the percentage of your processor clocks doing productive work by using concurrency in some appropriate way. And the real issue is that sometimes this isn’t possible at all.
This isn’t just a theoretical issue for me. I’m now scoping the job of moving reposurgeon from Python to Go in order to improve performance on large repositories and and it runs head-on into that wall. Python’s Global Interpreter Lock makes it C-equivalent for this discussion – yes it has a richer type ontology than C, and GC, but this turns out to help remarkably little with thread decomposition. It makes the trivial resource management issues a bit easier, but that just means you hit the question of how to write an algorithm that really exploits concurrency sooner.
Some of reposurgeon’s core operations can’t be factored into things done by a flock of threads at all, because for each commit you might want to vectorize over they do lookups unpredictably far back in time in the repository metadata. Some other operations could be because there are no time-order dependencies, but it’s going to require map-reduce-like partitioning of the metadata, with a high potential for bugs at the joins. Bad news: I think this is going to turn out to be a typical transition problem, not an unusually difficult one.
The implication is that the C-like requirement to look like a superfast serial machine (a) is not going away even partially without a lot of very hard work changing our algorithms, and (b) never going to go away entirely because there is an awkward residuum: some serial algorithms don’t have an equivalent that exploits concurrency. I dub these SICK algorithms, for “Serial Intrinsically; Cope, Kiddo!”
SICK algorithms include but are not limited to: Dijkstra’s n-least-paths algorithm; cycle detection in directed graphs (with implications for 3-SAT solvers); depth first search; computing the nth term in a crypto hash chain; network-flow optimization…and lots of other problems in which you either have to compute sub-results in a strict time order or you have wickedly bad lookup locality in the working set (which can make the working set un-partitionable).
There’s actually another Go-specific implementation issue here, too. Theoretically Go could provide a programming model that exposes hardware-level threading in a tractable way. Whether it actually does so – how much heavier the runtime cost of actual Go threads is – is not clear to me. It depends on details of the Go runtime design that I don’t know.
This generalizes. To jack up processor utilization to a degree that makes speculative execution unnecessary, we actually need two preconditions. (1) We need a highly concurrent algorithm (not just 1 or 2 threads but in the neighborhood of 180), and (2) we need the target language’s threading overhead to be sufficiently low on the target architecture that it doesn’t swamp the gains.
While Go doesn’t solve the problem of SICK algorithms, it doesn’t worsen the problem either. The most we can say is that relative to its competitors it somewhat reduces the friction cost of implementing an algorithmically-concurrent translation of code if there is one to be found.
Chisnall also argues that C hides the cache memory hierarchy, making elaborate and sometimes unsuccessful hackery required to avoid triggering expensive cache misses. This is obviously correct once pointed out and I kind of kick myself for not noticing the contextual significance of cache-line optimization sooner.
Missing from Chisnall’s argument is any notion of how to do better here. Are we supposed to annotate our programs with cache-priority properties attached to each storage allocation? It’s easy to see how that could have perverse results. Seems like the only realistic alternative would be for the language to have a runtime that behaves like a virtual memory manager, doing its best to avoid cache misses at each level by aging out allocation blocks to the next lower level on an LRU or some similar scheme.
Again, Go doesn’t solve this problem, but no more do any of its let’s-replace-C competitors. You couldn’t even really tackle it without making every pointer in the language a double indirect through trampoline storage. (IIRC there was a language on the pre-Unix Mac that actually did this, long ago.)
We do get a little help here from the absence of pointer arithmetic in Go. And a little more from the way slices work; they are effectively trampoline storage pointing at elements that could be transparently relocated by a GC – or a VM embedded in the language runtime.
Combining those, though? I don’t think it’s been done yet, in Go or anywhere else – and excuse me, but I don’t want to be the poor bastard who has to debug a language runtime implementing that hot mess.
Next, Chisnall has some rather penetrating things to say about how the C language model impedes optimization. Here for he first time we get some serious help from Go that is already implemented – doesn’t depend on a hypothetical property of the runtime. The fact that for loops in Go naturally use a dedicated iterator construct rather than pointers is going to help a lot with loop-independence proofs in the typical slice or array case. (Rust makes the same call for the same benefit.)
Unlike C, Go does not guarantee properties that imply structure field order is fixed to source order. The existing Go implementations don’t reorder to optimize, but they could. There are no exposed pointer offsets, so a compiler is allowed to insert padding to speed up stride access. In general, the C features that Chisnall notes would impede vectorization and SROA have been carefully omitted from Go.
Chisnall then describes the problems with loop unswitching in C. I don’t see Go giving any additional optimization leverage here, unless you count the effects of uninitialized variables always being zeroed. That (as Chisnall points out) also guarantees that you can’t have program behavior that is randomly variable depending on the prior contents of memory.
Go sweeps away most of the issues under “understanding C”. Padding is never visible, bare pointers and pointer offsets are absent, pointers are strongly typed and cannot be interconverted with integer (well, trivially they can but the specification does not guarantee they will round-trip).
Integer overflow is the exception. To reduce the runtime overhead of arithmetic Go opts not to overflow-check each operation, the same choice as C’s. That choice could start a whole other argument about speed-vs-safety tradeoffs, but it’s an argument that would wander some distance from Chisnall’s principal concerns and mine, so I’m not going to pursue it.
Instead I want to return to the initial question about Go, and then consider in more detail what the existence of SICK algorithms means for processor design.
So, is Go a “low-level language” for modern processors? I think the answer is really “No, because there are very good reasons we’ll never have a ‘low-level’ language again.” While the ability to manage lots of concurrency fairly elegantly does pull Go in the direction of what goes on on a modern multi-core processor, CSP is a quite abstract and simplified interface to the reality of buzzing threads and lots of test-and-set instructions that has to be going on underneath. Naked, that reality is unmanageable by mere human brains – at least that’s what the defect statistics from the conventional mutex-and-mailbox approach to doing so say to me.
Chisnall begins the last section of his argument by suggesting “Perhaps it’s time to stop trying to make C code fast and instead think about what programming models would look like on a processor designed to be fast.” Here, where he passes from criticism to prescription, is where I think his argument gets in serious trouble. It trips over the fact that there are lots of important SICK algorithms.
His prescription for processor design is “Let’s make flocks of threads much faster”. Well, OK – but I think if you interpret that as a bargain you can make to eliminate speculative execution (which is what Chisnall wants to do, though he never quite says it) there’s a serious risk that you could wind up with an architecture badly matched to a of lot of actual job loads.
In fact, I think there is a strong case that this has already happened with the processors we have now. My hexacore Great Beast already has more concurrency capacity than reposurgeon’s graph-surgery language can use effectively (see ‘wickedly bad lookup locality’ above), and because some operations bottleneck on on SICK algorithms it is certain that getting out from under Python’s GIL won’t entirely fix the problem.
Underlying my specific problem is a general principle: you can reduce the demand for instruction-level parallelism to zero only if your job load never includes SICK algorithms. A GPU can pretty much guarantee that. A general Turing machine cannot.
Chisnall seems to me to be suffering from a bit of a streetlight effect here. He knows concurrency can make some things really fast, so he recommends making the streetlight brighter even though there are lots of SICK problems we can’t drag to where it shines. To be fair, he’s far from alone in this – I’ve noticed it in a lot of theoretically-oriented CS types.
He finishes by knocking down a strawman about parallel programming being hard for humans, when the real question is whether it can be applied to your job load at all.
There is, for some real problems, no substitute for plain old serial speed, and therefore we seem to be stuck with speculative execution. There’s nothing for it but to embrace that SICK.