- LuaJIT's interpreter (here is Mike Pall's famous post giving a detailed explanation of why this is, incidentally prompted by a question I asked: http://lua-users.org/lists/lua-l/2011-02/msg00742.html)

- x264, which has extensive acceleration implemented in assembly for a/v codecs (they even built their own assembly abstraction layer: http://x264dev.multimedia.cx/archives/191)

- GMP, which has extensive acceleration implemented in assembly for arbitrary-precision arithmetic.

I wouldn't go so far as to argue that any of this implies the death of optimizing compilers, so I will be very interested to see what Dan has to say.

  > The reality, unfortunately, is very much the opposite: 
  > general-purpose "optimizing" compilers are falling farther 
  > and farther behind the actual capabilities of modern 
  > processors.

  This is just flat out wrong.

In my personal experience (which is mostly compression and scientific computing), I find that I can get significantly higher x64 performance from Haswell than from earlier Intel generations --- frequently more than twice as fast as I can do for Sandy Bridge, due to a combination of better memory interactions, fewer scheduling gotcha's, and wider integer vectors. Very rarely do I find that compiler generated code (Clang, GCC, icc) achieves this level of speedup, and even more rarely do I find that the same code gets optimal performance on both of these generations. Even more rarely does the generated assembly surprise me by exceeding my expectations of maximal performance.

I'm not sure where Daniel is going with his presentation, but what I often find myself wanting is a non-brain-dead non-optimizing compiler. It makes me sad to know how to make code run fast, but be unable to keep the compiler from slowing it down. Obviously, this is a rare case, since only a tiny percentage of code will ever be allowed to be this highly optimized. But I sure wish that there was a way to return to "glorified assembly", and that I had a way to tell the compiler to keep its grubby little fingers off certain small sections of my consciously crafted code.

Yes. We now do things like http://drona.csa.iisc.ernet.in/~uday/publications/pluto+.pdf

Which will fully, automatically, parallelize and optimize loop nests to the target architecture, including tiling, interchange, cache blocking, blah blah blah Basically anything you can think of. You can't do this by hand. You can do something by hand, maybe tiling, maybe unrolling, maybe interchange but the math is too complex for you to get it right in the general case and to combine all these things at once. We couldn't do this 20 years ago. We couldn't even approach the performance of most architectures.

We can also vectorize whatever you want. The only hard part is calculating the cost vs benefit.

Past that, now we actually have the opposite problem. We come so close to optimal on most architectures that we can't do much more without using NP complete algorithms instead of heuristics. We can only try to get little niggles here and there where the heuristics get slightly wrong answers. We decided we care more about compile speed than doing stuff like this.

"Very rarely do I find that compiler generated code (Clang, GCC, icc) achieves this level of speedup, and even more rarely do I find that the same code gets optimal performance on both of these generations."

I don't know your code, so i really can't speak to this at all, but it's the opposite experience for us. In fact, moving platforms now makes little performance difference. Getting the compiler up to snuff for that architecture does. If what you say is true, it just tells me you need to spend a small amount of time figuring out why the compiler is doing the wrong thing. It's almost certainly just a small bug or tweak somewhere.

Thanks, I'll read this over.

In fact, moving platforms now makes little performance difference.

Interestingly, we are saying the same thing but coming to opposite conclusions. I agree that compiler generated code produces approximately the same performance on Sandy Bridge vs Haswell. But I also know that the performance potential on Haswell can be much higher than that of Sandy Bridge, thus see this as a drop in compiler performance. Whereas you seem to be concluding that because the compiler achieves comparable performance, there has been little hardware improvement across generations.

We decided we care more about compile speed than doing stuff like this.

I've never really understood the emphasis on compile speed --- it seems misguided. Sure, you don't want to wait for the compiler to slowly redo the same suboptimal "optimization" on every recompilation, but shouldn't there be some way to cache the previous "best" so you can start from there? And wouldn't it be more efficient if there was some way that you could specify to the compiler where you want it to spend its time, maybe even offline so it won't hold up everything else? Not just the spectrum from "don't optimize and while you are at it please pass all function variables on the stack" to "do the best you can as long as it doesn't take longer than a millisecond", but "do what it takes and I'll tell you when it's good enough"?[1]

It's almost certainly just a small bug or tweak somewhere.

Perhaps I can try to send you an example the next time I come across a compact example. I'm dubious that increasing the automatization is the right approach --- what I think I want is easier access to "manual mode". And I'm equally dubious that it's going to be an easy fix, but would be wonderful it it was.

As a quick example of the sort of issue, Haswell allows two 32B loads and one 32B store per cycle, and has three address generation ports to support this. Two of the AGP's can be used for stores or loads, and one (Port 7) is only for stores. But Port 7 can only generate "simple" addresses --- fixed offsets from a register.

I've yet to find a way to convince a compiler to generate two loads and a store that can be executed in a single cycle without resorting to assembly. Effectively, the cost of an instruction varies depending on what other instructions are executed the same cycle. They can't be scored independently, and the compiler gets stuck in a "local optimum" rather than finding the "global optimum".

Just the ability to say "No, really, I want both of these to be loop variables, and this one to be incremented, and this one to be decremented, and I want the loop to terminate when the decrement hits zero" would be tremendous. Or a least, I'd like to be able to specify this as a starting point for optimization, and have some guarantee that the compiler won't "simplify" by combining the registers unless the "simplification" actually has better performance.

[1] I feel like Dan Luu's excellent and under-discussed article on Software Testing is very applicable here: http://danluu.com/testing/ Like software testing, compilers seem to have settled into the strange expectation that they should do the same thing over and over again very quickly, rather than doing something once and well.

Large pages (2MB+) can sometimes contribute a nice amount of extra performance, of course depending on access patterns. It can also have negative effect under some circumstances, like some very random access patterns. Gigabyte pages could help there, but support isn't great.

Other thing I've investigated is memory channel interleaving. Local memory seems to be mostly 64 bytes each channel round robin, but I guess it can be more complicated too. NUMA systems seem to be either round robin 4096 byte per NUMA region or all CPU local memory in one multi-gigabyte (?) chunk. Understanding memory interleaving can help balancing the work between different memory channels.

It would be interesting to have an EDSL for representing compiler optimizations that could be tweaked on a per program basis.

While we are at it, maybe swapping out cache associativity, write back semantics and the branch predictor.

One application I'm thinking about right now is how to optimize "interpolative coding", which is a very tight way of compressing inverted indexes (better than Golomb/Rice/Elias), but so far very slow. It's not immediately obvious how vectorization can make it faster, but possibly some use of the BMI instructions should help, perhaps combined with a big lookup table. It's hard even to get close enough to the right form of solution that a superoptimizer can make headway.

I was wondering if something like, "ISDL: An Instruction Set Description Language for Retargetability" [0] would help? It would be fun to create a combinatoric instruction sequencer and then run them all in an attempt to find some sort of probabilistic heuristic about instruction costs and efficiencies. Something like FFTW, but it analyzes then entire universe of possibilities. Some of the research in synthesizing new instruction sets or operating on compressed instructions might attack the problem from the other side [1].

Stay Fresh!

[-1] https://chessprogramming.wikispaces.com/BMI1

[0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.8...

[1] http://www.well.com/~cwf/pro/vita.html#Books (look for 'compress')

That doesn't surprise me for two reasons: 1) DJB is a great programmer. 2) Compilers are so complex that there are lots of non-obvious reasons that they miss optimizations.

I'm not an expert, but it appears to me that, in the last 10 years, processors have gotten complex at higher rate than compilers have gotten better. There's just more room to do nontrivial things that have come up only recently.

I found this interesting portable ASM DSL on DJB's site: http://cr.yp.to/qhasm.html

Honest question: Can you write C that compiles to what his qasm programs do with a modern C compiler? (I suspect the answer is no, because DJB writes tons of C and wouldn't have written it othewise)

Older perf notes on his site: http://cr.yp.to/hardware/x86.html

On the other hand, DJB writes a very particular type of software (crypto and mathematical code lately), so I suspect his experience won't be that generalizable. But it will be correct and important, because his niches are important.

Is the fact that a compiler can beat you sometimes[1] really that controversial?

And he better have a large class of problems in which he can beat the compiler, without using too much time[2]. Or else the title is just needlessly provocative.

And thirdly: many of just rely on the compiler doing a good enough job. Not a better job than we would do if we were more careful.

[1] Or often times. Depends on who you ask, and in what domains.

[2] Or else you can just say that a programmer can beat a compiler given enough time, where time can be arbitrarily long. But all of us have some kind of time constraint.

A lot of the non-critical code is perfectly fine, performance-wise, in bytecode interpreted Squeak Smalltalk or even Ruby. On the other hand, perf critical code tends to require re-thinking your abstractions and often your layering, which can give you several orders of magnitude of performance improvement (I've frequently had 10x - 1000x).

So I don't need the optimizer for the first part, and it doesn't really help me with the second part. It can and sometimes does take out some of the drudgery, but it can also get in the way by being somewhat unpredictable.

What I find interesting is the approach talked about by VPRI of allowing manual optimization specifications sitting next to high-level code (some of the earliest AOP examples were like that). Less magic, more control, much more predictability and power.

https://gcc.gnu.org/onlinedocs/gcc-3.4.0/gcc/Optimize-Option...

Firefox is an example of an application that ships production binaries with PGO.

[1] It was actually supported earlier than this, but I didn't search further; the 3.4.0 manual says "New -fprofile-generate and -fprofile-use command-line options to simplify the use of profile feedback", implying it was there before in a less convenient form.