{"id":7979,"date":"2018-05-09T10:41:25","date_gmt":"2018-05-09T14:41:25","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=7979"},"modified":"2018-05-09T14:53:34","modified_gmt":"2018-05-09T18:53:34","slug":"embrace-the-sick","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=7979","title":{"rendered":"Embrace the SICK"},"content":{"rendered":"<p>There&#8217;s a very interesting article just out, <cite>C Is Not a Low-level Language<\/cite>;. in which David Chisnall punctures the comforting illusion that C is really a &#8220;close-to-the-metal&#8221; language and relates this illusion to the high costs of Spectre and other processor-level bugs.<\/p>\n<p>Those of us who think seriously about language design have long been aware that C&#8217;s flat-address-space model is increasingly at odds with the real world of memory-caching hierarchies. Chisnall&#8217;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&#8217;re running on a really fast serial machine.\u00a0 But he has other interesting points as well.<\/p>\n<p>I recommend <a href=\"https:\/\/queue.acm.org\/detail.cfm?id=3212479\">reading Chisnall&#8217;s article<\/a> before you go further with this post.<\/p>\n<p>It&#8217;s no news to my regulars that I&#8217;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++&#8217;s range &#8211; that is, outside\u00a0 of kernels and hard realtime.\u00a0 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?<\/p>\n<p>Because if it is &#8211; but something else isn&#8217;t &#8211; that could be a reason not to overcommit to Go.\u00a0 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&#8217;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?<\/p>\n<p>So let&#8217;s walk through Chisnall&#8217;s discussion points, bounce Go off each one, and see what we can see.\u00a0 What we&#8217;ll find implies, I think, some more general conclusions about what will and won&#8217;t work in matching language design to real-world workloads and processor architectures.<\/p>\n<p><!--more--><\/p>\n<p>On C requiring high &#8220;instruction-level parallelism&#8221;: So will Go if you write it like C.\u00a0 Sometimes this is not avoidable.<\/p>\n<p>To write Go in a way that will keep a modern Intel processor&#8217;s instruction pipeline full you need, by Chisnall&#8217;s argument, to fruitfully decompose each serial algorithm into somewhere around 180 worker threads.\u00a0 Otherwise you need to do speculative execution to avoid having a significant chunk of your transistor budget simply behaving like a space heater.<\/p>\n<p>Go, in itself, doesn&#8217;t solve this problem.\u00a0 Sure, it lowers the barriers &#8211; its implementation of CSP via channels and goroutines is quite elegant and a handier toolkit for writing massively concurrent code than I&#8217;ve ever seen before.\u00a0 But it&#8217;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.<\/p>\n<p>On the other hand, every other potential competitor to Go has the same problem.\u00a0 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.\u00a0 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.<\/p>\n<p>The real cost of obsolescing speculative execution isn&#8217;t moving away from C, it&#8217;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.\u00a0 And the real issue is that sometimes this isn&#8217;t possible at all.<\/p>\n<p>This isn&#8217;t just a theoretical issue for me.\u00a0 I&#8217;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.\u00a0 Python&#8217;s Global Interpreter Lock makes it C-equivalent for this discussion &#8211; yes it has a richer type ontology than C, and GC, but this turns out to help remarkably little with thread decomposition.\u00a0 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.<\/p>\n<p>Some of reposurgeon&#8217;s core operations can&#8217;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&#8217;s going to require map-reduce-like partitioning of the metadata, with a high potential for bugs at the joins.\u00a0 Bad news: I think\u00a0 this is going to turn out to be a typical transition problem, not an unusually difficult one.<\/p>\n<p>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&#8217;t <em>have<\/em> an equivalent that exploits concurrency.\u00a0 I dub these SICK algorithms, for &#8220;Serial Intrinsically; Cope, Kiddo!&#8221;<\/p>\n<p>SICK algorithms include but are not limited to:\u00a0Dijkstra&#8217;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&#8230;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).<\/p>\n<p>There&#8217;s actually another Go-specific implementation issue here, too.\u00a0 Theoretically Go could provide a programming model that exposes hardware-level threading in a tractable way.\u00a0 Whether it actually does so &#8211; how much heavier the runtime cost of actual Go threads is &#8211;\u00a0 is not clear to me.\u00a0 It depends on details of the Go runtime design that I don&#8217;t know.<\/p>\n<p>This generalizes. To jack up processor utilization to a degree that makes speculative execution unnecessary, we actually need two preconditions.\u00a0 (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&#8217;s threading overhead to be sufficiently low on the target architecture that it doesn&#8217;t swamp the gains.<\/p>\n<p>While Go doesn&#8217;t solve the problem of SICK algorithms, it doesn&#8217;t worsen the problem either.\u00a0 \u00a0The most we can say is that relative to its competitors it somewhat reduces the friction cost of implementing an algorithmically-concurrent translation of code\u00a0 if there is one to be found.<\/p>\n<p>Chisnall also argues that\u00a0 C hides the cache memory hierarchy, making elaborate and sometimes unsuccessful hackery required to avoid triggering expensive cache misses.\u00a0 This is obviously correct once pointed out and I kind of kick myself for not noticing the contextual significance of cache-line optimization sooner.<\/p>\n<p>Missing from Chisnall&#8217;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\u00a0 storage allocation?\u00a0 It&#8217;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.<\/p>\n<p>Again, Go doesn&#8217;t solve this problem, but no more do any of its let&#8217;s-replace-C competitors. You couldn&#8217;t even really tackle it without making every pointer in the language a double indirect through trampoline storage.\u00a0 (IIRC there was a language on the pre-Unix Mac that actually did this, long ago.)<\/p>\n<p>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 &#8211; or a VM embedded in the language runtime.<\/p>\n<p>Combining those, though?\u00a0 I don&#8217;t think it&#8217;s been done yet, in Go or anywhere else &#8211; and excuse me, but I don&#8217;t want to be the poor bastard who has to debug a language runtime implementing <em>that<\/em> hot mess.<\/p>\n<p>Next, Chisnall has some rather penetrating things to say about how the C language model impedes optimization.\u00a0 Here for he first time we get some serious help from Go that is already implemented &#8211; doesn&#8217;t depend on a hypothetical property of the runtime.\u00a0 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.\u00a0 (Rust makes the same call for the same benefit.)<\/p>\n<p>Unlike C, Go does not guarantee properties that imply structure field order is fixed to source order.\u00a0 The existing Go implementations don&#8217;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.<\/p>\n<p>Chisnall then describes the problems with loop unswitching in C. I don&#8217;t see Go giving any additional optimization leverage here, unless you count the effects of uninitialized variables always being zeroed.\u00a0 That (as Chisnall points out) also guarantees that you can&#8217;t have program behavior that is randomly variable depending on the prior contents of memory.<\/p>\n<p>Go sweeps away most of the issues under &#8220;understanding C&#8221;.\u00a0 Padding is never visible, bare pointers and pointer offsets are absent, pointers are strongly typed and cannot be interconverted with integer\u00a0 (well, trivially they can but the specification does not guarantee they will round-trip).<\/p>\n<p>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&#8217;s.\u00a0 That choice could start a whole other argument about speed-vs-safety tradeoffs, but it&#8217;s an argument that would wander some distance from Chisnall&#8217;s principal concerns and mine, so I&#8217;m not going to pursue it.<\/p>\n<p>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.<\/p>\n<p>So, is Go a &#8220;low-level language&#8221; for modern processors?\u00a0 I think the answer is really &#8220;No, because there are very good reasons we&#8217;ll never have a &#8216;low-level&#8217; language again.&#8221;\u00a0 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.\u00a0 Naked, that reality is unmanageable by mere human brains &#8211; at least that&#8217;s what the defect statistics from the conventional mutex-and-mailbox approach to doing so\u00a0 say to me.<\/p>\n<p>Chisnall begins the last section of his argument by suggesting &#8220;Perhaps it&#8217;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.&#8221;\u00a0 Here, where he passes from criticism to prescription, is where I think his argument gets in serious trouble.\u00a0 It trips over the fact that there are lots of important SICK algorithms.<\/p>\n<p>His prescription for processor design is &#8220;Let&#8217;s make flocks of threads much faster&#8221;.\u00a0 Well, OK &#8211; 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&#8217;s a serious risk that you could wind up with an architecture badly matched to a of lot of actual job loads.<\/p>\n<p>In fact, I think there is a strong case that this has already happened with the processors we have now.\u00a0 My hexacore Great Beast already has more concurrency capacity than reposurgeon&#8217;s graph-surgery language can use effectively (see &#8216;wickedly bad lookup locality&#8217; above), and because some operations bottleneck on on SICK algorithms it is certain that getting out from under Python&#8217;s GIL won&#8217;t\u00a0 entirely fix the problem.<\/p>\n<p>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.\u00a0 A GPU can pretty much guarantee that.\u00a0 A general Turing machine cannot.<\/p>\n<p>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&#8217;t drag to where it shines.\u00a0 To be fair, he&#8217;s far from alone in this &#8211; I&#8217;ve noticed it in a lot of theoretically-oriented CS types.<\/p>\n<p>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.<\/p>\n<p>There is, for some real problems, no substitute for plain old serial speed, and therefore we seem to be stuck with speculative execution. There&#8217;s nothing for it but to embrace that SICK.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>There&#8217;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 &#8220;close-to-the-metal&#8221; 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&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=7979\">Continue reading <span class=\"screen-reader-text\">Embrace the SICK<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,9],"tags":[],"class_list":["post-7979","post","type-post","status-publish","format-standard","hentry","category-software","category-technology","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7979","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7979"}],"version-history":[{"count":16,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7979\/revisions"}],"predecessor-version":[{"id":7996,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7979\/revisions\/7996"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7979"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7979"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}