10 ms·

I wish this was given in a better format instead of just slides, hopefully the talk is actually better. Here's what I think the talk is about: The pervasive vi

I wish this was given in a better format instead of just slides, hopefully the talk is actually better. Here's what I think the talk is about: The pervasive view of software performance is that compilers are better than humans at optimizing code, but the few humans who optimize important bits of code to the maximum extent disagree Similarly, computer programs today are increasingly diverging into a state where there is a tiny amount of extremely performance critical code, and a large amount of code where performance is so good on our hardware today that even horribly unoptimized code has no noticeable effect on performance. Thus, optimizing compilers are useless on the first type of code (humans are better), and useless on the second (performance doesn't matter). So what good are they at all? If optimizing compilers aren't useful, what system should we use instead for making performant code? The author and collaborators' experience suggests that the reasons a compiler can't optimize code as well as a human when it matters is that our current programming languages don't give the compiler enough information about the intent of the code to optimize it. Therefore we should design programming languages that on the surface look very unoptimized, but specify enough information that compilers can do a really good job. It sounds like no one knows what such a programming language would look like.

ch 12y ago
Haskell? :)
- AnimalMuppet 12y ago
  Details?
- spectre256 12y ago
  I was thinking Ruby actually, although Haskell could probably be close too. In any case is sounds like the suggestion is to move away from imperative, procedural programming, which has been talked about a lot in various ways.
  - astrange 12y ago
    From the insides of a compiler, imperative and procedural have little meaning. C turns into a purely functional programming language called static single assignment form very easily. Actually, when you start thinking about everything like your compiler does, they stop having meaning in real life too! If you want to make a language easier to optimize, you need to reduce runtime decisions the program might have to make and incidental details about the program the compiler has to preserve[1]. That's "it". I think the closest languages for some problems would be Julia, array languages, OpenCL, etc. Not so much Ruby… [1] Like function signatures, structure layout, error behavior on bad inputs, memory aliasing, dynamic method calls, integer overflows, array overflows, stuff like that.
    - MichaelGG 12y ago
      SSA turns C into a pure functional language? What about globals, volatile, etc.?
      - astrange 12y ago
        It's inside a memory monad.
        andrewflnr 12y ago
        What on earth are you talking about? SSA has nothing to do with monads. http://en.wikipedia.org/wiki/Static_single_assignment_form http://en.wikipedia.org/wiki/Static_single_assignment_form
    - vidarh 12y ago
      Ruby is the language I like best to work in, but you're right. When I started Ruby, I wanted everything to be as static as possible, and I still do. What seduced me with Ruby was how clean it reads to a human. But as someone who writes compilers as a hobby, Ruby is also a massive challenge. Even reasoning about a simple Ruby program as a human is hard unless you make a lot of assumptions about how a reasonable developer will behave. What does "2 + 2" do? In Ruby you technically don't know without knowing what's lead up to that point. Some trickster might have overridden Fixnum#+ to return "42" on every addition. Or format your hard drive. And if there's a single "eval" with user controllable input before that point, you can't statically determine what it will do, because that trickster may or may not be present at the keyboard for any specific run. Instead a JIT will need to be preferred to de-optimize and re-optimize code differently if you want efficiency, or an AOT compiler will need to add all kinds of guards and fallback paths to handle the crazy alternatives wherever whole-program analysis is insufficient to rule out the tricksters.. And here's the kicker: common Ruby libraries use eval() all over the place. Often for inconsequential things that a compiler could in theory figure out. But not without a whole lot of extra analysis. For ahead-of-time compilation there are a ton of further challenges, such as the practice of executing code to alter the load path and executing code to determine exactly what "require" calls are made to pull in code. 99% of the time it results in a static set of "require" calls and you could just compile it as normal. That 1% it's a plugin mechanism, and the intent is for you to load and eval() code at runtime. Ultimately very few mainstream languages have such a fluid distinction between read/compile time and runtime as Ruby, and are as hard to statically analyse as Ruby. That's part of what makes it fun to try to ahead-of-time compile Ruby, but also drives me crazy at times when trying to figure out how to do it semi-efficiently. A lot of this can be resolved with relatively small tweaks, or even just current language features that most people don't use. E.g. if you were to do "Fixnum.freeze", the class can't be modified any more. Now we know what 2+2 means, assuming we know what Fixnum looked like at the point of freezing. One can make it vastly easier to reason about, and optimize, Ruby just with careful application of a few things like that. Unfortunately, because current Ruby implementations does not reward behaviour like that, nobody takes those steps.
- eru 12y ago
  Haskell is a good starting point. It's rather high level. I'd like to see a variant that banishes bottom _|_ to the same corner that unsafePerformIO already occupies today. I want to see total Haskell. If all programs had to halt by default, the compiler would be much freer in choosing evaluation models---strict vs lazy would make no semantic difference.
  - gamegoblin 12y ago
    See the Morte language proposed (not sure if actively developed) by Gabriel Gonzalez, author of many popular Haskell libraries.
    - agumonkey 12y ago
      Found this discussion pretty interesting on the subject : http://www.reddit.com/r/haskell/comments/2g6wsx/haskell_for_all_morte_an_intermediate_language/ http://www.reddit.com/r/haskell/comments/2g6wsx/haskell_for_...
  - narrator 12y ago
    Bitcoin script has to halt by default to prevent DOSs on nodes that evaluate the blockchain. However it doesn't have looping or flow control besides if/else.
    - derefr 12y ago
      I don't think you need looping or flow control, even for a general-purpose language; what you really want is the ability for almost all the code you write to be in terms of "step functions" with the flow control lifted out (e.g. edge functions in finite-state machines; recursive functions that recurse using a Y combinator instead of knowing that they're calling themselves; cellular automata where you only get to define the local transformation, not the automata itself; etc.) In other words—in the same way that Haskell hides IO "within" the implementation, giving the programmer an encapsulated abstraction in the form of an IO monad where it's effectively immaterial whether real IO happened or not—you could have a language even purer, where you only get to specify comonads, and the definitions of monads (where all non-halting behavior leaks into the language) themselves are abstracted away and inaccessible to the language programmer, except perhaps within the equivalent of Rust's unsafe{} blocks. In such a language, what monads were used to run the program would be up to the implementation—thus allowing the same program to be given unbounded resources, or bounded resources, for any given resource, as a run-time-configurable decision.
- neutronicus 12y ago
  My token attempts at writing numerical code in Haskell have been ... underwhelming.
DannyBee 12y ago
" It sounds like no one knows what such a programming language would look like." Actually, they do. The answer is "a mess" See things like "high performance fortran" (Led by the now-sadly-passed Ken Kennedy, who was doing compiler optimizations since well before most people here were born - 1971) http://dl.acm.org/citation.cfm?id=1238844.1238851 http://dl.acm.org/citation.cfm?id=1238844.1238851 And more recently, things like fortress: http://en.wikipedia.org/wiki/Fortress_%28programming_language%29 http://en.wikipedia.org/wiki/Fortress_%28programming_languag...
- jacobolus 12y ago
  How do you feel about the Halide language/project, which seems to me like a fairly promising application of these ideas. http://halide-lang.org http://halide-lang.org http://people.csail.mit.edu/jrk/halide12/halide12.pdf http://people.csail.mit.edu/jrk/halide12/halide12.pdf http://people.csail.mit.edu/jrk/halide-pldi13.pdf http://people.csail.mit.edu/jrk/halide-pldi13.pdf
  - DannyBee 12y ago
    Halide is a domain specific language. I think Halide is wonderful, and i think if you have a domain, it's entirely possible to make great things for that domain. But if your domain is "general purpose", i haven't seen anything that has come out well. IE i think it is exactly the restriction to given domains or choices that enable you to do the kinds of things halide does.
    - jacobolus 12y ago
      Doesn’t most performance-critical code involve some sort of similar “domain”? The examples people have been talking about in this thread, like media codecs, cryptography, matrix solvers, databases, etc. all seem to.
      - DannyBee 12y ago
        Yes, but these domains are all very different, and would require different languages, which would defeat the point.
bcg1 12y ago
I'd like to add, based on this quotation: "The programmer using such a system will write his beautifully-structured, but possibly inefficient, program P; then he will interactively specify transformations that make it efficient." Sounds to me as if what he is suggesting is that coding could take place in whatever language... but then during compilation they would "interactively" give the compiler answers to questions to that previous systems could not answer just by analyzing the program. Its not clear to me how the author envisions this "dialog" to take place... would the compiler literally pause and "ask" a person sitting at the console about the use cases? Maybe... and then perhaps it would cache those responses for future builds. Or perhaps the compiler might request another program to feed it sets of typical input for that particular section of code, etc. Definitely an interesting idea if that's where they're going with this.
- derefr 12y ago
  You don't want to make the compiler itself interactive. Compilers have a well-known interface: either they spit out an output binary and exit cleanly, or they spit out an error. This is a case where I'd imagine the compiler could just spit out an error: something like "not 100% confident on the correct way to optimize the following lines: [...]" (this is oddly reminiscent of INTERCAL's "please" directives, actually.) What the compiler would be expecting, would be an "optimization annotation file" to exist alongside each source file, that it would take as batch input. If said file has all the answers it needs, it compiles cleanly; if it doesn't (because the program changed, or because it doesn't exist yet) then it'll error out. The important bit is that an IDE can read such an error, and transform that into some form of semi-interactive process to create/modify the optimization-annotation file. But to the compiler, everything stays a pipeline, like usual.
  - sounds 12y ago
    Could those be specified in comments in the file? Most development nowdays is done in an IDE that could intelligently "hide" the comments when you're just reading the code, and then when you're looking at optimizing the code you could start annotating things that way. A similar approach is to use #pragma directives, though many languages do not have an analogue to that. Java Annotations are probably wrong. The compiler can benefit from more freedom (and finer grained detail), so for Java comments seem like a better choice to me.
deleted 12y ago
[deleted]
- Gibbon1 12y ago
  Not a game programmer but, impression I get is a number of games use interpreted languages as glue. Certainly sound to me like thee is a dichotomy between must run fast at all costs, and must be flexible speed matters not at all. I think game programming is an area where a high percentage of the code base needs to run fast, even if it's not run very often. If it causes the frame rate to slip, the user is going to notice. In my case, embedded, optimizing for size is everything. And usually only a very small portion of the code needs to run fast. One problem that people are running into with optimizing compilers is with embedded often you are interested in the physical side effects of your code, not it's mathematical end state. Optimizing compilers are increasing not respecting the former in preference to the latter.
scythe 12y ago
>Similarly, computer programs today are increasingly diverging into a state where there is a tiny amount of extremely performance critical code, and a large amount of code where performance is so good on our hardware today that even horribly unoptimized code has no noticeable effect on performance. >Thus, optimizing compilers are useless on the first type of code (humans are better), and useless on the second (performance doesn't matter). Even today, in practice, this is a false dilemma. Consider Postgres, Firefox, or Photoshop for that matter: I expect the user-experience of these products to be significantly degraded when compiled with -O0. The trouble with this analysis is that it assumes that a codebase is a static, finalizable goal: it will be written, it will be done, and then it is perfect. And that might be true of... oh, I don't know... qmail. But the development of most software is an ongoing process, and the tradeoff between developer time and runtime will never go away: nobody in the video-game industry would consider for a second the idea that performance-critical code doesn't need to make deadlines! A great deal of performance-critical code is written with a deadline, by people who would never pass a tenure hearing. If you can eliminate all "hot" parts of your application by linking assembly libraries, even today, you're in a very, very small minority! The amount of hand-written assembly in the wild is so small that unless you work on [cryptography, scientific computing, emulation, embedded] you'll rarely cross paths with it. The call at the end of the presentation for an "interactive optimizer" of sorts is a bit of a non-sequitur: we might ask as a necessary prerequisite the demonstration of any system which can effectively compete with (∆t ≤ 10%) hand-written assembly on any problem of a significant size. This extremely-tuned linear algebra optimizer ("AUGEM"): http://xianyi.github.io/paper/augem_SC13.pdf http://xianyi.github.io/paper/augem_SC13.pdf demonstrates that it can beat g++, but no comparison with OpenBLAS is given (the researchers used an old version of GotoBLAS, which is sort of unfair by their own admission). Can human-parity ASM can be generated efficiently with an interactive compiler? I have no bloody idea.
- simonster 12y ago
  Re: the AUGEM paper, the generated kernel is the OpenBLAS kernel. Xianyi is one of two(?) primary OpenBLAS developers, and it says in the paper that "the GEMM kernel generated by our framework for the Intel Sandy Bridge CPU has been adopted as a part of our open-source BLAS library OpenBLAS."
Crito 12y ago
> Similarly, computer programs today are increasingly diverging into a state where there is a tiny amount of extremely performance critical code, and a large amount of code where performance is so good on our hardware today that even horribly unoptimized code has no noticeable effect on performance. > Thus, optimizing compilers are useless on the first type of code (humans are better), and useless on the second (performance doesn't matter). It seems to me that while speed may not matter much anymore, power consumption matters now more than ever before (the proliferation of computers that are run off of batteries). If you're computer spends less time running code and more time idle, even if we are talking about milliseconds that the end user won't use, you might use noticeably less power over the course of several hours. The difference between "the phone ran out of power when I was still 5 minutes away from home" and "the phone ran out of power after I walked through the front door and kicked back for the evening" may be the difference between "the battery-life on this is shit, buy [competitors product]!" and "no complaints".
- ori_b 12y ago
  The point is that all of the time spent running code is spent running only a small portion of code -- This is still case 1 listed above.
  - deleted 12y ago
    [deleted]
  - im3w1l 12y ago
    One difference is that before only bursts needed to be super tight, now idle performance have to be in addition. Maybe his rule is still valid, but the two cases do seem a little bit different to me. Previously it used to be about optimizing that innermost loop that was only a few instructions long so it went twice as fast. A small local change with inline assembly. But idle behaviour involves architectural optimizations. Like pushing events instead of polling for them.
    - ori_b 12y ago
      > now idle performance have to be in addition. Your idle time should be with all processes blocked in select()/poll()/epoll() and friends, and the CPU fully shut off with no code at all running. If your CPU isn't fully asleep -- if it's running instructions -- you've already lost. There was a bug with my cellphone where a service was holding a wakelock and preventing the CPU from shutting off. This was enough to drain enough power that it would drain even while on the charger.
guygurari 12y ago
I recently wrote a simulation that involved some heavy numerical calculations. Without optimization it was dog slow and would have taken probably years to produce the results I needed. With compiler optimization it took a few days, which was good enough for me. Perhaps I could have improved on that with manual optimizations, but the speed was good enough so instead of spending time optimizing I did other things. The implicit assumption in the talk (based on this summary) is that we always want the most optimized code. But in fact that is never the case -- what we really want is for the code to be fast enough (or be space-optimized enough). So the relevant question is this: in what percentage of cases do compiler optimizations take us from 'not fast enough' to 'fast enough'. In all these cases the compiler is useful, because it saves us the cost of doing our own optimizations. In my experience this percentage is far from negligible, so at least for me optimizing compilers are highly valuable.
- panic 12y ago
  I think there's an interesting distinction here between general-purpose software and single-use code. General-purpose software has many users with many kinds of data. Unless your domain is intrinsically limited, it's impossible to be "fast enough" -- you can always find some data that your code will take to long to process. There's always an incremental benefit to optimization, and with enough users, it's irresponsible to waste collective years of people's time by leaving performance on the table. What you've said makes perfect sense for one-off simulations, however. And in practice, optimizers are designed to make tight numerical code run fast. I don't think your use case will ever be ignored. It's just that most systems today are not made of tight loops of arithmetic operations. We need more tools to optimize the kind of code that actually makes our computers slow: code that allocates and deallocates memory, code that transforms data between different formats, code that constructs and operates on complex data structures -- that sort of thing.
  - valm- 12y ago
    I don't entirely disagree, but I would like to make one point. Taking 1 millisecond from 1000 people, does not translate to 1 second of lost human productivity. There's no way to collect all those little slices of time and they are not appreciable individually. (Assuming those milliseconds are sufficiently spread out, i.e., not 1 ms out of every 2, or something like that)
groby_b 12y ago
Yeah, except there are large amounts of code that could stand being faster, but it is not worth the cost to hand-optimize. So what are they good at? Optimizing large amounts of code well enough at a negligible cost. In other words, scaling productivity. The thing machines usually are good at :)
modeless 12y ago
How about just giving up on automatic optimization? I love the approach taken by http://halide-lang.org/ http://halide-lang.org/. The programmer writes code, but then instead of having a compiler do the optimizations automatically, the programmer also explicitly specifies the optimizations to perform! The advantage is that changing the optimizations cannot affect the correctness of the algorithm. So you get to write your algorithm once, verify its correctness, and then try drastically changing data layout, order of computations, parallelization, etc, as freely as you want. You can even change the optimizations you're using to match the data you're processing, so you can do much better than an optimizing compiler could do without profile-guided optimization. Edit: After looking more closely at the presentation, I think Halide is essentially the realization of the hypothetical language described in the last few slides. Somebody should tell DJB about it!
- Joky 12y ago
  Halide is quite domain specific though, it won't help you to create a new database system for instance, or help you on your hadoop algorithm.
  - andrewflnr 12y ago
    GP suggested using the same approach as Halide, not Halide itself. Obviously you would first need to apply it to a general-purpose language.
userbinator 12y ago
As one of those "few humans", I'd just like to say that I think the default -O0 of compilers today should really be more like what they call -O1 or -Os, since the unoptimised compiler output I've seen is ridiculously stupid and contains things no sane human programmer would do even when not making any attempt at optimisation. O0 is more like pessimisation, in my opinion. To be clear, I'm not saying to apply fancy SIMD instructions/autovectorisation, loop transformations/unrolling, or any of those other advanced techniques. I just don't want to see things like saving/restoring registers that are never ever used in the function, lots of unnecessary memory accesses and data movement instructions, and register allocation that looks more like register non-allocation (e.g. always using the same 2-3 registers and memory instead of the other 4-5 that are available.) Also, for rarely-run pieces of code (micro-)performance may not matter, but size certainly does - the smaller the non-performance-critical code, the more room there is in the cache for the performance-critical code. On a larger scale, the smaller the whole process is, the less chance there is of the non-performance-critical code being swapped out (and suddenly becoming very performance-critical...) when memory is constrained, and of course it also reduces overall memory usage, which is a good thing in a multiprocess environment. Perhaps we need to fundamentally change how compilers and their optimisers work, since the current model seems to be "generate the most stupidly unoptimised code possible, then apply optimisation passes to it". I think it's a rather counterintuitive and wasteful way of doing it, compared to the "generate only the code you need" method a human would likely follow. Thus I'd say that current compiler optimisations are still useful, if only for cleaning up the mess they would make otherwise. :-)
- jeffbush 12y ago
  Yeah, exactly. I feel like the author is missing the point of the optimizer. It's not something that attempts to fix bad code, it just expresses the programmers intent efficiently. For example, if I have a common subexpression, I would expect the compiler to notice it and take care of it automatically instead of me having to tediously code it explicitly to do the right thing. Given how large open source libraries are today, all of those little inefficiencies add up (in size and space) if we just let the compiler be stupid. But the easiest counterargument is to just to tell someone to compile their program at -O0 (which I've done inadvertently on an number of occasions). The program is noticeably bigger and slower.
btown 12y ago
> Therefore we should design programming languages that on the surface look very unoptimized, but specify enough information that compilers can do a really good job. It sounds like no one knows what such a programming language would look like. This entire post would be painfully familiar to anyone working with probabilistic programming. An intriguing overview of the state of the art was posted here a little while ago: https://moalquraishi.wordpress.com/2015/03/29/the-state-of-probabilistic-programming/ https://moalquraishi.wordpress.com/2015/03/29/the-state-of-p... The task here (I'm adapting an older comment of mine) is that the human should write a relatively simple procedural program that says "if we were to fix a bunch of properties/states of the natural world and provide them as input, here's the output/reading you'd hypothetically get," and then from that, the "compiler" and runtime create a function that, given a large number of outputs/readings, provides a posterior probability distribution over those hidden properties/states of the world. The implementation choices for this "function" can make a difference of days or weeks of runtime on huge computer clusters. The problem is that machine learning researchers use all sorts of insights to make manual optimizations when hand-rolling machine learning code - for instance, if there are real-world reasons why a certain type of search over your space may be well-suited or ill-suited to the problem domain. And not only can the languages not capture these insights yet, but even if they could, there's fragmentation in the community (since it's at such an early stage), and there's no standardized way to map heuristics detecting optimizable patterns to actual optimizations. I'd imagine optimizing compilers looked very similar at one point, though... so only time will tell how far the community progresses!
JoachimS 12y ago
It is a typical DJB presentation. Hard to read with repeated text all over (since he wants a transition effect of adding text during the talk). This one actually contains images. DJB is very consistent in the way he do presentations.
frik 12y ago
Good point. I had a professor who worked on the Java HotSpotVM and was a proponent of optimizing compiler. His attitude was RAM is cheap. But he also thought us LL1 Pascal style compilers too. In real world, native compiled applications written in C/C++/ObjectC/Rust rule the desktop world. In the enterprise/backend server we see a lot of Java/DotNet VM based memory hungry applications, Interpreter or modern VM based languages like PHP(HHVM/PHP7)/LuaJIT(nginx/openresty)/Javascript(Nodejs v8)/PyPy dominate the web and on smartphone one can decide to go native with iOS or the 8-core CPU and still a bit laggy Java lang VM based Android. Fortran and C and their compilers are still the benchmark to beat. As modern CPUs optimize and predict branches, some automatic optimization techniques in higher levels are counter productive.
ubernostrum 12y ago
The actually useful question is not whether there are humans who, in their domains of expertise, can out-perform a general-purpose compiler. The actually useful question is how many humans actually possess or can reasonably be expected to gain the knowledge to write screaming-fast bare-metal hand-tooled compiler-beating code safely on modern processor architectures, and figure out the trade-off if we decide to abandon optimizing compilers -- even though there will always be some nonzero number of humans who can write faster code -- in favor of either forcing every programmer to hand-roll performance-critical code or re-tooling everything and everyone everywhere to a hypothetical language (and probably a hypothetical hardware architecture) you don't even know how to describe in general terms yet. (for the record, my money is on the "useless" compilers winning that cost-benefit analysis)
astrobe_ 12y ago
Perhaps the authors deliberately ignored the embedded systems "niche". Embedded systems have this "unusual" property that the one-time cost of software development is dwarfed by the 10^N-times cost of more expensive components. This is also true in theory in the desktop world, but it's so easy to shame your customer for not using a high-end computer that it's a non-issue. Optimizing compilers are needed for embedded systems because low-end micro-controllers don't have the horsepower of desktops or even your latest smartphone, but yet the more features/the smarter behaviour the better. So you have better things to do than optimizing stuff for a processor you don't know very well and that may be replaced in 5 years.
digi_owl 12y ago
> If optimizing compilers aren't useful, what system should we use instead for making performant code? The author and collaborators' experience suggests that the reasons a compiler can't optimize code as well as a human when it matters is that our current programming languages don't give the compiler enough information about the intent of the code to optimize it. Therefore we should design programming languages that on the surface look very unoptimized, but specify enough information that compilers can do a really good job. It sounds like no one knows what such a programming language would look like. Sounds like one hell of a rabbit hole. Could have sworn that codifying intent is one of those things that humans have struggled with since the dawn of civilization. As in, what is a clever optimizing hack on society vs a criminal offense.
Houshalter 12y ago
> the few humans who optimize important bits of code to the maximum extent disagree That sounds like selection bias. The only people who would spend time hand writing assembly are those who don't like compilers.

ch 12y ago

Haskell? :)

AnimalMuppet 12y ago
Details?
spectre256 12y ago
I was thinking Ruby actually, although Haskell could probably be close too. In any case is sounds like the suggestion is to move away from imperative, procedural programming, which has been talked about a lot in various ways.
- astrange 12y ago
  From the insides of a compiler, imperative and procedural have little meaning. C turns into a purely functional programming language called static single assignment form very easily. Actually, when you start thinking about everything like your compiler does, they stop having meaning in real life too! If you want to make a language easier to optimize, you need to reduce runtime decisions the program might have to make and incidental details about the program the compiler has to preserve[1]. That's "it". I think the closest languages for some problems would be Julia, array languages, OpenCL, etc. Not so much Ruby… [1] Like function signatures, structure layout, error behavior on bad inputs, memory aliasing, dynamic method calls, integer overflows, array overflows, stuff like that.
  - MichaelGG 12y ago
    SSA turns C into a pure functional language? What about globals, volatile, etc.?
    - astrange 12y ago
      It's inside a memory monad.
      - andrewflnr 12y ago
        What on earth are you talking about? SSA has nothing to do with monads. http://en.wikipedia.org/wiki/Static_single_assignment_form http://en.wikipedia.org/wiki/Static_single_assignment_form
  - vidarh 12y ago
    Ruby is the language I like best to work in, but you're right. When I started Ruby, I wanted everything to be as static as possible, and I still do. What seduced me with Ruby was how clean it reads to a human. But as someone who writes compilers as a hobby, Ruby is also a massive challenge. Even reasoning about a simple Ruby program as a human is hard unless you make a lot of assumptions about how a reasonable developer will behave. What does "2 + 2" do? In Ruby you technically don't know without knowing what's lead up to that point. Some trickster might have overridden Fixnum#+ to return "42" on every addition. Or format your hard drive. And if there's a single "eval" with user controllable input before that point, you can't statically determine what it will do, because that trickster may or may not be present at the keyboard for any specific run. Instead a JIT will need to be preferred to de-optimize and re-optimize code differently if you want efficiency, or an AOT compiler will need to add all kinds of guards and fallback paths to handle the crazy alternatives wherever whole-program analysis is insufficient to rule out the tricksters.. And here's the kicker: common Ruby libraries use eval() all over the place. Often for inconsequential things that a compiler could in theory figure out. But not without a whole lot of extra analysis. For ahead-of-time compilation there are a ton of further challenges, such as the practice of executing code to alter the load path and executing code to determine exactly what "require" calls are made to pull in code. 99% of the time it results in a static set of "require" calls and you could just compile it as normal. That 1% it's a plugin mechanism, and the intent is for you to load and eval() code at runtime. Ultimately very few mainstream languages have such a fluid distinction between read/compile time and runtime as Ruby, and are as hard to statically analyse as Ruby. That's part of what makes it fun to try to ahead-of-time compile Ruby, but also drives me crazy at times when trying to figure out how to do it semi-efficiently. A lot of this can be resolved with relatively small tweaks, or even just current language features that most people don't use. E.g. if you were to do "Fixnum.freeze", the class can't be modified any more. Now we know what 2+2 means, assuming we know what Fixnum looked like at the point of freezing. One can make it vastly easier to reason about, and optimize, Ruby just with careful application of a few things like that. Unfortunately, because current Ruby implementations does not reward behaviour like that, nobody takes those steps.
eru 12y ago
Haskell is a good starting point. It's rather high level. I'd like to see a variant that banishes bottom _|_ to the same corner that unsafePerformIO already occupies today. I want to see total Haskell. If all programs had to halt by default, the compiler would be much freer in choosing evaluation models---strict vs lazy would make no semantic difference.
- gamegoblin 12y ago
  See the Morte language proposed (not sure if actively developed) by Gabriel Gonzalez, author of many popular Haskell libraries.
  - agumonkey 12y ago
    Found this discussion pretty interesting on the subject : http://www.reddit.com/r/haskell/comments/2g6wsx/haskell_for_all_morte_an_intermediate_language/ http://www.reddit.com/r/haskell/comments/2g6wsx/haskell_for_...
- narrator 12y ago
  Bitcoin script has to halt by default to prevent DOSs on nodes that evaluate the blockchain. However it doesn't have looping or flow control besides if/else.
  - derefr 12y ago
    I don't think you need looping or flow control, even for a general-purpose language; what you really want is the ability for almost all the code you write to be in terms of "step functions" with the flow control lifted out (e.g. edge functions in finite-state machines; recursive functions that recurse using a Y combinator instead of knowing that they're calling themselves; cellular automata where you only get to define the local transformation, not the automata itself; etc.) In other words—in the same way that Haskell hides IO "within" the implementation, giving the programmer an encapsulated abstraction in the form of an IO monad where it's effectively immaterial whether real IO happened or not—you could have a language even purer, where you only get to specify comonads, and the definitions of monads (where all non-halting behavior leaks into the language) themselves are abstracted away and inaccessible to the language programmer, except perhaps within the equivalent of Rust's unsafe{} blocks. In such a language, what monads were used to run the program would be up to the implementation—thus allowing the same program to be given unbounded resources, or bounded resources, for any given resource, as a run-time-configurable decision.
neutronicus 12y ago
My token attempts at writing numerical code in Haskell have been ... underwhelming.

DannyBee 12y ago

" It sounds like no one knows what such a programming language would look like." Actually, they do. The answer is "a mess" See things like "high performance fortran" (Led by the now-sadly-passed Ken Kennedy, who was doing compiler optimizations since well before most people here were born - 1971) http://dl.acm.org/citation.cfm?id=1238844.1238851 http://dl.acm.org/citation.cfm?id=1238844.1238851 And more recently, things like fortress: http://en.wikipedia.org/wiki/Fortress_%28programming_language%29 http://en.wikipedia.org/wiki/Fortress_%28programming_languag...

jacobolus 12y ago
How do you feel about the Halide language/project, which seems to me like a fairly promising application of these ideas. http://halide-lang.org http://halide-lang.org http://people.csail.mit.edu/jrk/halide12/halide12.pdf http://people.csail.mit.edu/jrk/halide12/halide12.pdf http://people.csail.mit.edu/jrk/halide-pldi13.pdf http://people.csail.mit.edu/jrk/halide-pldi13.pdf
- DannyBee 12y ago
  Halide is a domain specific language. I think Halide is wonderful, and i think if you have a domain, it's entirely possible to make great things for that domain. But if your domain is "general purpose", i haven't seen anything that has come out well. IE i think it is exactly the restriction to given domains or choices that enable you to do the kinds of things halide does.
  - jacobolus 12y ago
    Doesn’t most performance-critical code involve some sort of similar “domain”? The examples people have been talking about in this thread, like media codecs, cryptography, matrix solvers, databases, etc. all seem to.
    - DannyBee 12y ago
      Yes, but these domains are all very different, and would require different languages, which would defeat the point.

bcg1 12y ago

I'd like to add, based on this quotation: "The programmer using such a system will write his beautifully-structured, but possibly inefficient, program P; then he will interactively specify transformations that make it efficient." Sounds to me as if what he is suggesting is that coding could take place in whatever language... but then during compilation they would "interactively" give the compiler answers to questions to that previous systems could not answer just by analyzing the program. Its not clear to me how the author envisions this "dialog" to take place... would the compiler literally pause and "ask" a person sitting at the console about the use cases? Maybe... and then perhaps it would cache those responses for future builds. Or perhaps the compiler might request another program to feed it sets of typical input for that particular section of code, etc. Definitely an interesting idea if that's where they're going with this.

derefr 12y ago
You don't want to make the compiler itself interactive. Compilers have a well-known interface: either they spit out an output binary and exit cleanly, or they spit out an error. This is a case where I'd imagine the compiler could just spit out an error: something like "not 100% confident on the correct way to optimize the following lines: [...]" (this is oddly reminiscent of INTERCAL's "please" directives, actually.) What the compiler would be expecting, would be an "optimization annotation file" to exist alongside each source file, that it would take as batch input. If said file has all the answers it needs, it compiles cleanly; if it doesn't (because the program changed, or because it doesn't exist yet) then it'll error out. The important bit is that an IDE can read such an error, and transform that into some form of semi-interactive process to create/modify the optimization-annotation file. But to the compiler, everything stays a pipeline, like usual.
- sounds 12y ago
  Could those be specified in comments in the file? Most development nowdays is done in an IDE that could intelligently "hide" the comments when you're just reading the code, and then when you're looking at optimizing the code you could start annotating things that way. A similar approach is to use #pragma directives, though many languages do not have an analogue to that. Java Annotations are probably wrong. The compiler can benefit from more freedom (and finer grained detail), so for Java comments seem like a better choice to me.

deleted 12y ago

[deleted]

Gibbon1 12y ago
Not a game programmer but, impression I get is a number of games use interpreted languages as glue. Certainly sound to me like thee is a dichotomy between must run fast at all costs, and must be flexible speed matters not at all. I think game programming is an area where a high percentage of the code base needs to run fast, even if it's not run very often. If it causes the frame rate to slip, the user is going to notice. In my case, embedded, optimizing for size is everything. And usually only a very small portion of the code needs to run fast. One problem that people are running into with optimizing compilers is with embedded often you are interested in the physical side effects of your code, not it's mathematical end state. Optimizing compilers are increasing not respecting the former in preference to the latter.

scythe 12y ago

>Similarly, computer programs today are increasingly diverging into a state where there is a tiny amount of extremely performance critical code, and a large amount of code where performance is so good on our hardware today that even horribly unoptimized code has no noticeable effect on performance. >Thus, optimizing compilers are useless on the first type of code (humans are better), and useless on the second (performance doesn't matter). Even today, in practice, this is a false dilemma. Consider Postgres, Firefox, or Photoshop for that matter: I expect the user-experience of these products to be significantly degraded when compiled with -O0. The trouble with this analysis is that it assumes that a codebase is a static, finalizable goal: it will be written, it will be done, and then it is perfect. And that might be true of... oh, I don't know... qmail. But the development of most software is an ongoing process, and the tradeoff between developer time and runtime will never go away: nobody in the video-game industry would consider for a second the idea that performance-critical code doesn't need to make deadlines! A great deal of performance-critical code is written with a deadline, by people who would never pass a tenure hearing. If you can eliminate all "hot" parts of your application by linking assembly libraries, even today, you're in a very, very small minority! The amount of hand-written assembly in the wild is so small that unless you work on [cryptography, scientific computing, emulation, embedded] you'll rarely cross paths with it. The call at the end of the presentation for an "interactive optimizer" of sorts is a bit of a non-sequitur: we might ask as a necessary prerequisite the demonstration of any system which can effectively compete with (∆t ≤ 10%) hand-written assembly on any problem of a significant size. This extremely-tuned linear algebra optimizer ("AUGEM"): http://xianyi.github.io/paper/augem_SC13.pdf http://xianyi.github.io/paper/augem_SC13.pdf demonstrates that it can beat g++, but no comparison with OpenBLAS is given (the researchers used an old version of GotoBLAS, which is sort of unfair by their own admission). Can human-parity ASM can be generated efficiently with an interactive compiler? I have no bloody idea.

simonster 12y ago
Re: the AUGEM paper, the generated kernel is the OpenBLAS kernel. Xianyi is one of two(?) primary OpenBLAS developers, and it says in the paper that "the GEMM kernel generated by our framework for the Intel Sandy Bridge CPU has been adopted as a part of our open-source BLAS library OpenBLAS."

Crito 12y ago

ori_b 12y ago
The point is that all of the time spent running code is spent running only a small portion of code -- This is still case 1 listed above.
- deleted 12y ago
  [deleted]
- im3w1l 12y ago
  One difference is that before only bursts needed to be super tight, now idle performance have to be in addition. Maybe his rule is still valid, but the two cases do seem a little bit different to me. Previously it used to be about optimizing that innermost loop that was only a few instructions long so it went twice as fast. A small local change with inline assembly. But idle behaviour involves architectural optimizations. Like pushing events instead of polling for them.
  - ori_b 12y ago
    > now idle performance have to be in addition. Your idle time should be with all processes blocked in select()/poll()/epoll() and friends, and the CPU fully shut off with no code at all running. If your CPU isn't fully asleep -- if it's running instructions -- you've already lost. There was a bug with my cellphone where a service was holding a wakelock and preventing the CPU from shutting off. This was enough to drain enough power that it would drain even while on the charger.

guygurari 12y ago

I recently wrote a simulation that involved some heavy numerical calculations. Without optimization it was dog slow and would have taken probably years to produce the results I needed. With compiler optimization it took a few days, which was good enough for me. Perhaps I could have improved on that with manual optimizations, but the speed was good enough so instead of spending time optimizing I did other things. The implicit assumption in the talk (based on this summary) is that we always want the most optimized code. But in fact that is never the case -- what we really want is for the code to be fast enough (or be space-optimized enough). So the relevant question is this: in what percentage of cases do compiler optimizations take us from 'not fast enough' to 'fast enough'. In all these cases the compiler is useful, because it saves us the cost of doing our own optimizations. In my experience this percentage is far from negligible, so at least for me optimizing compilers are highly valuable.

panic 12y ago
I think there's an interesting distinction here between general-purpose software and single-use code. General-purpose software has many users with many kinds of data. Unless your domain is intrinsically limited, it's impossible to be "fast enough" -- you can always find some data that your code will take to long to process. There's always an incremental benefit to optimization, and with enough users, it's irresponsible to waste collective years of people's time by leaving performance on the table. What you've said makes perfect sense for one-off simulations, however. And in practice, optimizers are designed to make tight numerical code run fast. I don't think your use case will ever be ignored. It's just that most systems today are not made of tight loops of arithmetic operations. We need more tools to optimize the kind of code that actually makes our computers slow: code that allocates and deallocates memory, code that transforms data between different formats, code that constructs and operates on complex data structures -- that sort of thing.
- valm- 12y ago
  I don't entirely disagree, but I would like to make one point. Taking 1 millisecond from 1000 people, does not translate to 1 second of lost human productivity. There's no way to collect all those little slices of time and they are not appreciable individually. (Assuming those milliseconds are sufficiently spread out, i.e., not 1 ms out of every 2, or something like that)

groby_b 12y ago

Yeah, except there are large amounts of code that could stand being faster, but it is not worth the cost to hand-optimize. So what are they good at? Optimizing large amounts of code well enough at a negligible cost. In other words, scaling productivity. The thing machines usually are good at :)

modeless 12y ago

How about just giving up on automatic optimization? I love the approach taken by http://halide-lang.org/ http://halide-lang.org/. The programmer writes code, but then instead of having a compiler do the optimizations automatically, the programmer also explicitly specifies the optimizations to perform! The advantage is that changing the optimizations cannot affect the correctness of the algorithm. So you get to write your algorithm once, verify its correctness, and then try drastically changing data layout, order of computations, parallelization, etc, as freely as you want. You can even change the optimizations you're using to match the data you're processing, so you can do much better than an optimizing compiler could do without profile-guided optimization. Edit: After looking more closely at the presentation, I think Halide is essentially the realization of the hypothetical language described in the last few slides. Somebody should tell DJB about it!

Joky 12y ago
Halide is quite domain specific though, it won't help you to create a new database system for instance, or help you on your hadoop algorithm.
- andrewflnr 12y ago
  GP suggested using the same approach as Halide, not Halide itself. Obviously you would first need to apply it to a general-purpose language.

userbinator 12y ago

As one of those "few humans", I'd just like to say that I think the default -O0 of compilers today should really be more like what they call -O1 or -Os, since the unoptimised compiler output I've seen is ridiculously stupid and contains things no sane human programmer would do even when not making any attempt at optimisation. O0 is more like pessimisation, in my opinion. To be clear, I'm not saying to apply fancy SIMD instructions/autovectorisation, loop transformations/unrolling, or any of those other advanced techniques. I just don't want to see things like saving/restoring registers that are never ever used in the function, lots of unnecessary memory accesses and data movement instructions, and register allocation that looks more like register non-allocation (e.g. always using the same 2-3 registers and memory instead of the other 4-5 that are available.) Also, for rarely-run pieces of code (micro-)performance may not matter, but size certainly does - the smaller the non-performance-critical code, the more room there is in the cache for the performance-critical code. On a larger scale, the smaller the whole process is, the less chance there is of the non-performance-critical code being swapped out (and suddenly becoming very performance-critical...) when memory is constrained, and of course it also reduces overall memory usage, which is a good thing in a multiprocess environment. Perhaps we need to fundamentally change how compilers and their optimisers work, since the current model seems to be "generate the most stupidly unoptimised code possible, then apply optimisation passes to it". I think it's a rather counterintuitive and wasteful way of doing it, compared to the "generate only the code you need" method a human would likely follow. Thus I'd say that current compiler optimisations are still useful, if only for cleaning up the mess they would make otherwise. :-)

jeffbush 12y ago
Yeah, exactly. I feel like the author is missing the point of the optimizer. It's not something that attempts to fix bad code, it just expresses the programmers intent efficiently. For example, if I have a common subexpression, I would expect the compiler to notice it and take care of it automatically instead of me having to tediously code it explicitly to do the right thing. Given how large open source libraries are today, all of those little inefficiencies add up (in size and space) if we just let the compiler be stupid. But the easiest counterargument is to just to tell someone to compile their program at -O0 (which I've done inadvertently on an number of occasions). The program is noticeably bigger and slower.

btown 12y ago

> Therefore we should design programming languages that on the surface look very unoptimized, but specify enough information that compilers can do a really good job. It sounds like no one knows what such a programming language would look like. This entire post would be painfully familiar to anyone working with probabilistic programming. An intriguing overview of the state of the art was posted here a little while ago: https://moalquraishi.wordpress.com/2015/03/29/the-state-of-probabilistic-programming/ https://moalquraishi.wordpress.com/2015/03/29/the-state-of-p... The task here (I'm adapting an older comment of mine) is that the human should write a relatively simple procedural program that says "if we were to fix a bunch of properties/states of the natural world and provide them as input, here's the output/reading you'd hypothetically get," and then from that, the "compiler" and runtime create a function that, given a large number of outputs/readings, provides a posterior probability distribution over those hidden properties/states of the world. The implementation choices for this "function" can make a difference of days or weeks of runtime on huge computer clusters. The problem is that machine learning researchers use all sorts of insights to make manual optimizations when hand-rolling machine learning code - for instance, if there are real-world reasons why a certain type of search over your space may be well-suited or ill-suited to the problem domain. And not only can the languages not capture these insights yet, but even if they could, there's fragmentation in the community (since it's at such an early stage), and there's no standardized way to map heuristics detecting optimizable patterns to actual optimizations. I'd imagine optimizing compilers looked very similar at one point, though... so only time will tell how far the community progresses!

JoachimS 12y ago

It is a typical DJB presentation. Hard to read with repeated text all over (since he wants a transition effect of adding text during the talk). This one actually contains images. DJB is very consistent in the way he do presentations.

frik 12y ago

Good point. I had a professor who worked on the Java HotSpotVM and was a proponent of optimizing compiler. His attitude was RAM is cheap. But he also thought us LL1 Pascal style compilers too. In real world, native compiled applications written in C/C++/ObjectC/Rust rule the desktop world. In the enterprise/backend server we see a lot of Java/DotNet VM based memory hungry applications, Interpreter or modern VM based languages like PHP(HHVM/PHP7)/LuaJIT(nginx/openresty)/Javascript(Nodejs v8)/PyPy dominate the web and on smartphone one can decide to go native with iOS or the 8-core CPU and still a bit laggy Java lang VM based Android. Fortran and C and their compilers are still the benchmark to beat. As modern CPUs optimize and predict branches, some automatic optimization techniques in higher levels are counter productive.

ubernostrum 12y ago

The actually useful question is not whether there are humans who, in their domains of expertise, can out-perform a general-purpose compiler. The actually useful question is how many humans actually possess or can reasonably be expected to gain the knowledge to write screaming-fast bare-metal hand-tooled compiler-beating code safely on modern processor architectures, and figure out the trade-off if we decide to abandon optimizing compilers -- even though there will always be some nonzero number of humans who can write faster code -- in favor of either forcing every programmer to hand-roll performance-critical code or re-tooling everything and everyone everywhere to a hypothetical language (and probably a hypothetical hardware architecture) you don't even know how to describe in general terms yet. (for the record, my money is on the "useless" compilers winning that cost-benefit analysis)

astrobe_ 12y ago

Perhaps the authors deliberately ignored the embedded systems "niche". Embedded systems have this "unusual" property that the one-time cost of software development is dwarfed by the 10^N-times cost of more expensive components. This is also true in theory in the desktop world, but it's so easy to shame your customer for not using a high-end computer that it's a non-issue. Optimizing compilers are needed for embedded systems because low-end micro-controllers don't have the horsepower of desktops or even your latest smartphone, but yet the more features/the smarter behaviour the better. So you have better things to do than optimizing stuff for a processor you don't know very well and that may be replaced in 5 years.

digi_owl 12y ago

> If optimizing compilers aren't useful, what system should we use instead for making performant code? The author and collaborators' experience suggests that the reasons a compiler can't optimize code as well as a human when it matters is that our current programming languages don't give the compiler enough information about the intent of the code to optimize it. Therefore we should design programming languages that on the surface look very unoptimized, but specify enough information that compilers can do a really good job. It sounds like no one knows what such a programming language would look like. Sounds like one hell of a rabbit hole. Could have sworn that codifying intent is one of those things that humans have struggled with since the dawn of civilization. As in, what is a clever optimizing hack on society vs a criminal offense.

Houshalter 12y ago

> the few humans who optimize important bits of code to the maximum extent disagree That sounds like selection bias. The only people who would spend time hand writing assembly are those who don't like compilers.