Hacker News Reader

Comment by juliansimioni | Hacker News Reader

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.

View on HN

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.

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.

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)

> Taking 1 millisecond from 1000 people, does not translate to 1 second of lost human productivity

I believe that it does. If you average over a large population even tiny imperceptible increases in e.g. page load time have a measurable effect. Perhaps 1000 people isn't a large enough sample to measure the effect from 1ms delay considering all the confounding factors at play, but I absolutely believe you could see it with precise enough measurement and a large enough sample.

Reminds me of this semi-relevant story about improving the boot times of the original Macintosh — http://www.folklore.org/StoryView.py?story=Saving_Lives.txt

The irony being that Jobs himself limited the memory in the original Mac, so it would have to go to disk more often!

Source?

Its a fairly well known story. The engineers ignored him and built in capability for 512k anyway.

http://www.informationweek.com/mobile/mobile-devices/steve-j...

He also hated fans and expansion slots.

Hmm I think the heart of the question is whether productivity is linear with time. I guess he's right that, for small values of t, productivity is highly superlinear. So giving 1 person an extra minute has an impact on that person, but because of superlinearity, if you distribute that among 60 persons the extra second won't allow anything new, like an original thought or whatever.

You're thinking about it wrong. Of course if you give 60 people 1 second each they won't be able to accomplish a task that takes a minute; that's obvious. Instead what if you give a group of people 59 seconds each to complete a task that takes 1 minute +-10 seconds, and then you give a different group of people 60 seconds each to complete the same task. More people in the second group will complete the task.

Well in your case there's a "phase transition" for the task around 1 minute, so in that case the return function is sublinear in t (if you assume given time G starts at 0. G=t), or linear in it (if you assume it starts at 50, G=50+t). I just wanted to highlight this principle: his statement is equivalent to "For small t, the return for freeing t seconds from computer tasks in superlinear on t". And in general: "The analysis of time redistribution hinges on the linearity of return function for the freed time t".

I do believe that for most persons and most situations, they do tasks in a segmented fashion, working to completion. So if you give them a small amount of extra time it's just going to shift their segments until it hits a synchronized event, like sleeping at a predetermined time or having a meeting -- so all that happens is they get e.g. a millisecond each before they sleep. Under this model it's quite clear to me for very small t the return function is superlinear, and it's better to give 1 person 100 seconds than 100k persons a millisecond (assuming this is one-off of course): for the 100k persons the millisecond is insufficient to elicit any change whatsoever. It's much less than a neuron firing time.

However the carbon footprint of the code does reduce like that. It would be very wasteful in terms of energy not to optimize a widely used binary.

Beware: optimising for speed and optimising for energy don't yield the same results.

If you want speed, you typically want to use your CPU as much as possible. If you want to save energy, you'll want to underclock your CPU. If we go all the way to hardware design, saving energy means going massively multicore, with simple, slow, in-order cores.

You can optimise both, to some extent. But there is a point where you have to chose one or the other.

> If you want to save energy, you'll want to underclock your CPU.

This is incorrect. To save energy, the strategy is to do your thing as quickly as possible, with maximum CPU clocks and enter power saving mode as soon as possible. Otherwise the leakage current in the CPU will consume more energy than can be saved by underclocking.

It may be counterintuitive but fast code consumes the least energy.

I insist: speed and energy savings are correlated to a point.

To. A. Point. Some instructions in your CPU may be faster, but slower alternative often consume less total energy (even taking everything into account —there have been experiments and power measurements). Even if it means your CPU is up a bit longer. Then there are considerations that save energy, but don't matter for speed at all, such as the width of integer operations: no need to go 32 bits wide or 64 bits wide, when no value exceeds 127.

Also, I'm not sure about current leakage exceeding the benefits of underclocking. Those benefits are massive. Lowering the frequency also means you can lower the voltage. In the talks I have seen, halving the speed of a core (and lowering the voltage accordingly) makes it dissipate about a fourth the power. Half the energy, considering everything takes twice the time. This of course ignores leakage, but I doubt it would counter such a strong effect.

Besides, with a phone running a number of background processes, I wonder how much power saving time you can get. Not to mention, the potential costs of switching in and out of CPU saving mode.

"Race to sleep" is a well known power saving strategy.

> This of course ignores leakage

You can't ignore leakage. The ability of a chip to turn off currently unused silicon is crucial to power management on modern devices.

Of course you can't. But if leakage consume 25% of CPU power, then halving the frequency is still worth it. Leakage may be important, but that doesn't mean it dominates.

Now if as an app developer you have zero control over the CPU frequency, sure, the best strategy is probably to write your code to be as fast as possible. But if you're really big on battery life, someone will have control over CPU clocking or voltage. In which case race to sleep is no longer the only viable strategy.

> 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.

I could just as easily claim that skilled developer's time is a precious resource, and it's irresponsible to waste it squeezing out performance when so much software still remains unwritten.

There's another side to that, as well.

Developers' time is expensive, and the time it takes to get feedback from code runs adds up when you have lots of developers. Especially if the roundtrip times are short enough not to allow switching between tasks, but long enough to cause constant "wall time waits".

I'd be more than willing to have couple of extremely skilled developers profile and optimise the common code so that the feedback loop becomes shorter for everyone. That way more of the yet-unwritten software might just be tackled.

My old boss once had me spend more than a week packaging and streamlining our access VPN configurations. When I asked him about it some time later, he explained that even though I was away from billable projects for that time, it would have cost a whole lot more overall to have all our developers and managers massage their setups every time something changed.

Large figures are sums of lots of small figures...

A typical compiler takes -O -O2 and so on flags for how much optimization you want. But what I would really like is a -O60s meaning, do as much optimization as you can in 60s and we're good to go. For the production version I might give it -O1h or -O12h and run it overnight. I am not aware of any product that does this.

The one issue with this type of compilation is that it encourages hisenbugs. You add debugging code, it can't spend as much time optimizing, and all of a sudden it is producing the correct results again.

But none the less, I agree.

I agree it's a trade-off, it always is :) But if the goal is to write performant code, there's a few more variables to consider.

An important one, IMO, is experience and practice.

Optimization can be found in the weirdest places. My latest experience is not with C or assembly instruction crunching, but with Processing/Java. If I weren't minded to tinker with and optimize my inner loops, I might have never discovered that the java.lang.Math routines are a lot faster than the equivalent Processing functions (functions like abs, max, etc).

Back when I was messing with 80x86 assembly code, I did the same. It's all about having a somewhat accurate model of what goes on inside. With Processing it's the model that the functions are probably wrapped in something. With assembly code it's (among other things) the model that the order of independent instructions matters for purposes of pipelining and preventing AGI-stalls (I dunno if those are still relevant, this was the 386 era).

When you get the hang of it, it's not really hard to experiment, measure, experiment, a few times and end up with spectacularly more performant code.

And really, if the optimized result took a few days to calculate, and an hour of tinkering might save you another day or two, isn't that (often) worth it?

Then there's the fact that I think it's fun :) Getting the code to work properly first, is a whole different process than spot-optimizing certain critical parts. I think it's refreshing to switch between these two different ways of looking at the same code.

How about just giving up on automatic optimization? I love the approach taken by 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!

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.

GP suggested using the same approach as Halide, not Halide itself. Obviously you would first need to apply it to a general-purpose language.

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. :-)

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.

One of the big problems here is that the C calling convention, which a lot of other languages use as well, requires a lot of that brain damage. Calls are supposed to put just the first argument in the A register, and everything else on the stack, save any potential register that an operation the function may use, and generally be painfully slow.

One of the things optimization does is figure out what rules it can break in order to make the program go faster -- when it can put more arguments in registers, because only the code being compiled will see that function, etc. So, in order to make compilers smarter and more intuitive, we have to agree to break binary compatibility, which is something people are rather gun shy about. But, I think it's time to have that conversation.

There is no such thing as a C calling convention. It isn't in the language spec.

Also I am not sure which one in common use behaves exactly as you say. On ia32 it's usually all stack. (Though I think Microsoft uses ECX for the c++ this pointer.) On amd64 it's common to use registers for the first few integers. (Say, 4 of them.)

Further, within a non-exported function it's fair game to break ABIs/calling conventions.

A convention is a convention. It doesn't need a spec.

C is a language with a spec. When you say "c calling convention" this implies that it is C, and not something else. There are various ABIs, some with specs and some with unwritten rules, but two C programs can run on the same platform conforming to differing ABIs and still be both C.

If this sounds far fetched, consider for example that it's common to experience a lot of pain trying to link code compiled with GCC against code compiled with the ms compiler or vice-versa. Same language, CPU, OS. Differing abi.

The C language spec alone is not sufficient to build a useful system. You're also going to need some kind of operating system interface (defined in POSIX), binary format (ELF), and so on.

The specification that you're both trying to find is called the "System V Application Binary Interface, AMD64 Architecture Processor Supplement" and is found here: http://www.x86-64.org/documentation/abi.pdf

There are similar variations for other architectures. Microsoft does something different, I don't know where their spec lives.

That is the sysv abi, popular with unixy platforms. It's one abi. You have already mentioned there are others. So how is it "what I was trying to find"? My point is there is not one that is called "C".

It's quite funny to hear somebody call for the reinvention of a field based on the quality of -O0 code.

Just get over yourself and pass -Os.

That'd be great but here is what Torvalds has to say about -Os

http://thread.gmane.org/gmane.linux.kernel/1927090/focus=192...

tl;dr - sometimes the smallest code being generated is slow and dumb

That's nothing compared to the -O0 crud that the GP was complaining about. It's also not a problem with the field of compiler design, but a (probably temporary) weakness in gcc.

(It is an interesting anecdote though.)

I think we should definitely reconsider how compilers are doing code generation, if by default they are generating far more code than necessary and need to use optimisation to make up for it.

The large volume of -O0 code is just a result of skipping register allocation to save compilation time. There's no problem here.

" 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

And more recently, things like fortress: http://en.wikipedia.org/wiki/Fortress_%28programming_languag...

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://people.csail.mit.edu/jrk/halide12/halide12.pdf http://people.csail.mit.edu/jrk/halide-pldi13.pdf

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.

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.

Yes, but these domains are all very different, and would require different languages, which would defeat the point.

Why? Why, if I care about performance, should I write my database, my kernel scheduler, my TCP stack, my JPEG codec, my cryptographic hash function, my physics engine, and my 3d-rendering pipeline in the same language?

If we assume (obviously this isn’t quite true today) the domain specific languages existed which would let me write more readable and modifiable source, in a highly portable way, with explicit control over optimization strategies so that I could get orders of magnitude better performance than the naive C++ version, why wouldn’t I use those whenever possible?

Then all the cold “glue” code that isn’t any kind of performance bottleneck can be written in whatever language, and doesn’t need to be optimized at all.

That shifts a lot of cost to defining and implementing many DSLs. (For an extreme case, consider the VPRI STEPS project where it looked like some of the DSLs were only used for one program.)

That extreme case may still be worth it, if the result (program + DSL implementation) is easier to maintain than the mainstream alternative (program in a general purpose language).

Besides, it wouldn't be that many DSLs. There are relatively few domains where performance is really critical. Cryptography, rendering, encoding/decoding… that's a few dozens at most, with global impact for each. If those DSL have any positive impact at all, they will be worth the cost a million times over.

So instead of writing a database, a kernel scheduler, a TCP stack, a JPEG codec, a cryptographic hash function, a physics engine, and a 3D rendering pipeline, we have to write a DSL for most/all of these programs and then the program itself. And this is less work than just writing them in hand-optimized C in the first place?

Less code / easier to read / less bugs / easier to maintain / easier to formally verify? Alan Kay seems to be a fan of this principle and from what I have seen it makes sense. He doesn't do it for optimisation per se but the same idea applies.

In many (but not all) cases, yes - because you don't just write programs. You have to read them and maintain them and update them too - sometimes 'forever'. A DSL is designed with the whole lifecycle in mind. Also, these tools can come with things like specialized analyzers, debuggers, verifiers etc for those specific domains, which can help increase assurances and improve your ROI a lot.

Cryptol is a decent example of a domain-specific cryptographic toolkit which can easily do verification of C code against specifications, for example. It can't do much besides writing crypto, but it's pretty good at that.

In other words, the idea is that the cost of the toolset implementation is amortized over the whole lifespan of the project, and multiplied many times over for every use - it's not just the initial implementation. Naturally this approach doesn't always work of course, for a million reasons that might be specific to your use case.

So then it stands to reason that we need a DSL for writing DSL's.

http://en.wikipedia.org/wiki/OMeta

Because these are all artificial boundaries you have created. Many of the operations within the domains you mention here are going to be the same. It all comes down to effects, data structures, and algorithms.

We have some very good tools for writing DSLs (Forth and Lisp come to mind). And since in both of those you in principle have access to an assembler (Lisps are less good about that nowadays, sadly) they seem like a decent option.

I read a couple of the Fortress specs as they were developing it, and quite liked the language. It was complicated, but (to me) the complexity was warranted. What about the language do you consider a mess? Or is it more that you believe that any language with similar goals would inevitably be a mess?

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.

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.

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.

What can comment say that an annotation could not? Heck, annotations can contain text strings.

Do you mean Java annotations?

I believe it's a question of where you put the optimisation hints. Alongside the code, or in a separate file?

Perhaps something along the lines of the compiler saying, "if you write this that way, then I know X is true and I can perform some more optimisations". But that may be even harder to do than a "compiler-friendly" language.

We have two problems: people don't want to know about what's best for their processor (that's the job of the compiler after all), and they don't want to know about when compiler optimizations can take place (which actually is kind of the same problem).

>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

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.

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."

Hi scythe,

I am Xianyi, a co-author of AUGEM paper and the developer of OpenBLAS.

We used the AUGEM generated assembly codes at OpenBLAS sandy bridge kernel(OpenBLAS/kernel/x86_64/dgemm_kernel_4x8_sandy.S).

Meanwhile, we need add some hand written codes to deal with the tail ( undivided by block size).

Thus, we didn't compare AUGEMM with OpenBLAS. However, we compared the performance with Intel MKL and AMD ACML.

Xianyi

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 :)

> 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-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!

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.

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)

> 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.

Haskell? :)

Details?

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.

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.

SSA turns C into a pure functional language? What about globals, volatile, etc.?

It's inside a memory monad.

What on earth are you talking about? SSA has nothing to do with monads. http://en.wikipedia.org/wiki/Static_single_assignment_form

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.

Ruby is the wrong direction. You need to make more information to the compiler statically. Haskell is the right direction here.

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.

See the Morte language proposed (not sure if actively developed) by Gabriel Gonzalez, author of many popular Haskell libraries.

Found this discussion pretty interesting on the subject : http://www.reddit.com/r/haskell/comments/2g6wsx/haskell_for_...

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.

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.

There are a bunch of languages like that. I've just done a project in HOL, where all functions must terminate. Proving that functions terminate is a pain in the backside, because for any trivial structurally recursive function you write (easy to prove), there's also a function that's nothing like that and will just be a waste of your time.

Also, without a lot of work, you'd get very little out of evaluation models. In particular, the only disadvantage at the moment is that you can't strictly evaluate arguments where the function isn't strict in that argument. That's cases where the argument might not get used. I don't think it would get you massive improvements that you couldn't already get in most cases by simply producing specialised versions of the function.

The big advantage is that you can prove more interesting stuff about your code (with again more effort). See Agda, where you can (for example) write a zip function that won't typecheck unless both lists are the same length.

> 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.

Lazy evaluation permits the use of infinite structures, which would be _|_ when evaluated strictly, but not when evaluated lazily.

Good point.

That's where lots of terms with `co-' in front come in. Co-recursion can deal with certain infinite structures.

My token attempts at writing numerical code in Haskell have been ... underwhelming.

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.

> 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".

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.

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.

> 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.

Yeah, hopefully nobody busyloops ala

    for(;;)checkForEvent();

But I could see someone doing

    for(;;){checkForEvent();sleep(sometime);}

    setInterval(checkForEvent, sometime);

This wouldn't be terrible but not ideal.

Bernstein’s logic applies equally well to power consumption as to pure runtime.

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.

> 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.

Reply on news.ycombinator.com