On the Madness of Optimizing Compilers

http://prog21.dadgum.com/217.html

by _isus • 10 years ago

85 76 10 years ago

prog21.dadgum.com

If I'm writing code that actually needs to be optimized, then I usually put it into its own object file and tweak the compiler flags as necessary to get the assembly to look the way I want. The C compiler supporting this saves me time.

For any other language except C(Haskell, Java, C++, C#, Go, etc.), I don't actually care that much about compiler performance as long as it does the obvious optimizations. Generally you can look at performance at a higher semantic level as soon as your code starts implying calls to malloc() - and conversely, you can start looking at the assembly as soon as you've removed all calls to malloc() in the offending section.

The other thing that transcends compilers or languages are the actual bits that get stored in memory or on disk. Even if I'm writing Perl, it makes a difference if I'm packing something into a contiguous array or just packing a bunch of pointers or references to all over my heap. Or if I can shave a couple bytes off every record in a hundred million records.

Javascript might be the one exception, since people using it don't have any other choice. I don't know - is there such a thing as an FFI for Javascript, using a browser extension or something?

gliese1337• 10 years ago

Native objects are probably as close as you come in most implementations. Windows Scripting Host does have a more general ability to call foreign code from inside JScript (the Microsoft implementation of ECMAScript). I used to write quite a bit of JScript code that called out into windows executables and DLLs.

dclowd9901• 10 years ago

Asm.js lets you write a strictly typed subset of JS. Most prototypes of it are compiled C running (compiled to JavaScript, yes) 3D games. When compiled, Asm hints the JIT so that it can further optimize around the loose typing of JS.

evincarofautumn• 10 years ago

put it into its own object file and tweak the compiler flags as necessary

This is a good approach, as are finer-grained optimisation pragmas & attributes, #ifdeffed as needed.

Ideally, I’d like the compiler to do only cursory optimisations by default, just enough that I can read the assembly and not say “wow, this is stupid”.

For anything else, I’d rather have a dialogue with the profiler & compiler heuristics, wherein they suggest optimisations, but I choose which ones I want using optimisation pragmas, and the compiler does the grunt work of program transformation.

For example, the compiler would say “this function is only ever called in cold paths; I suggest adding the ‘cold’ attribute” or “this loop can be vectorized; I suggest adding the ‘vectorize’ attribute”.

sanxiyn• 10 years ago

I've seen arguments that some people desperately need every last bit of performance, and even a few cycles inside a loop is the difference between a viable product and failure.

This is a strawman. The usual argument is that 1% better performance is, well, 1% better. That's a whole server if you have 100 servers. People are not desperate, but do want an additional server for free.

Assuming that's true, then they should be crafting assembly code by hand.

This, and "a few cycles inside a loop", is another strawman. What usually happens is a good compiler saves a bit everywhere, which helps when the program is optimized to flat profile without hotspot. Since saving is everywhere, "crafting assembly" amounts to lots and lots of assembly, not just a few in strategic places.

trungaczne2• 10 years ago

To add to this, performance is very important in certain domains.

Take game development for instance, if your code runs a bit faster that's more frames you're rendering per second. This can mean the difference between a laggy, unplayable mess and a good gaming experience on an average machine (a laptop, or a non-gaming rig).

randomsearch7• 10 years ago

Most software is not games or scientific computing. Most software is not speed critical. This is why most new software is not written in C.

dkopi5• 10 years ago

And a good compiler doesn't only optimize for speed. It also optimizes for code size, memory usage.

I do however agree with underlying premise of this post: Code that works 100% of the time is better than higher performant code that explodes in your face every once in a while.

golergka• 10 years ago

Code that works 100% of the time is better than higher performant code that explodes in your face every once in a while.

That depends. In game programming, if I had a choice between a render that will crash once every 10 hours and produce 60 fps (in some model envrionment) vs a render that never crashes but produces 45 fps, I would choose the first one.

0x07c04• 10 years ago

And a good compiler doesn't only optimize for speed. It also optimizes for code size, memory usage.

No they don't. Code size is rarely a problem (embedded probably cares..). Optimizations will in most cases lead to larger code, loop unrolling, inline expansion etc. In c the compiler cant't, in most cases do anything about memory usage. (Probably could pack structs.. , but that is not something the compiler would do I think, you would break ABI with non optimized code). In managed languages, memory usages is probably more depended on the runtime system GC, then compilers.

GCC has a flag for code size optimization -Os https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

randomsearch7• 10 years ago

That's a whole server if you have 100 servers. People are not desperate, but do want an additional server for free.

Renting an extra server costs practically nothing comparing to wage costs for a tech company.

So I'd say they'd care more about the compiler being reliable and predictable.

DannyBee3• 10 years ago

Maybe when it's 1 server.

I have a team that regularly generates savings of XX% of the entire datacenter CPU cycles of a very large fleet through better compiler optimization (that pretty much never breaks any of our programs. In fact, we break them more through almost anything other than better optimization. Shocking, i know, but you can test this stuff really well it turns out, and write sanitizers to find behavior you wouldn't discover at compile time and ...)

I know at least another 100 large companies where the cost savings of doing this kind of thing also totals in the tens to hundreds of millions, per year.

and that's just the normal X% a year, not the "we put a team of experts targeting your use case and they got you 100x" type of savings.

So yeah, there are people for whom this matters ... a lot, and dismissing them casually is not a great idea :)

Truthfully, IME, compiler-optimization induced bugs are so infrequent compared to normal you-wrote-really-wrong code bugs that IMHO it's missing the forest for the trees. (now, maybe people suck more at tracking them down, but ...)

Heck, I had once screwed up some code in GCC that caused it to essentially remove random stores and loads from the program being compiled. It only caused one visible failure across a bunch of real world apps that had serious validation suites.

From reading hacker news, you'd get the idea compiler optimizations follows your code down alleyways to mug it. In truth, people are so busy overflowing buffers and whatnot that we are lucky if we can break their code due to optimizing.

asdfaoeu• 10 years ago

Assuming that's true, then they should be crafting assembly code by hand.

This guy, what a fucking joke. Yeah to avoid bugs instead of using these fancy compilers (which rarely if ever are the cause of bugs) we should be assembling our programs by hand.

titzer2• 10 years ago

I've seen people go to extreme lengths to teach compilers particular optimizations that only apply in extremely narrow circumstances. Worse, they usually end up additionally have to introduce a way for a compiler to assume invariants that would break normal programs (e.g. overcome weaknesses in alias analysis). I've seen people go to extreme lengths and rely on C++ undefined behavior to get some weird quirk out of some specific machine instruction. All of that is extremely brittle; move to a new compiler version, new compiler, or even slightly alter the code, and suddenly the optimization either stops working or the compiler generates wrong code.

At some point, for extremely hot loops, there may be no choice but to write a few pages of assembly by hand. If this saves tens of thousands of lines of compiler code that doesn't generalize, and is used on thousands or millions of machines, it's worth it, IMO.

yxhuvud• 10 years ago

The straightforward "every program all the time" compiler is likely within 2-3x of the fully optimized version (for most things)

Citation needed. Pulling numbers out of your ass doesn't an argument make.

chubot• 10 years ago

I agree it's not really an argument, but I think the implementation of the Go compilers is evidence towards his point. The compilers were straightforward and didn't use fancy representations or optimizations AFAIK (being based on old Plan 9 compilers).

And with that philosophy, I believe it was within 2-3x of C++ in most benchmarks, despite being in a higher level language (though no doubt it's much slower on some benchmarks).

That said, they continue to optimize the compilers (e.g. https://news.ycombinator.com/item?id=9099744). People obviously do want speed; 2x slower isn't acceptable in many cases.

mpweiher2• 10 years ago

On Proebsting's Law[1].

"The results of our experiment suggest that Proebsting’s Law is probably true. The reality is somewhat grimmer than Proebsting initially supposed."

"Proebsting has suggested that the compiler and programming language research communities should focus less on optimization and more on programmer productivity"

[1] http://www.cs.virginia.edu/~techrep/CS-2001-12.pdf

0x07c04• 10 years ago

That number my have be true pre 2000, but with the move to parallel architectures it is grossly wrong. Optimization is not about saving a few cycles here and there. It is about using the whole machine, multiple chips, all with multiple cores. This cores are vector cores (AVX/SSE, altivec, etc). The chips are on different NUMA domains, the cores has pipelines, caches, etc, that has to be exploited... Compilers really don't do to much about this. This is now the job of the programmer. Speedup for codes that can exploit this, at least 20-30x. This adds up to loot of computer time... (add multiple accelerators (GPGPUs, MIC), and you can have 200-300x speedup on one node)

chadaustin• 10 years ago

Speaking of madness, James Hague drives me a little crazy. I get it - people tend to focus too much on performance. But it seems like his blog is a series of repeated arguments that nobody needs maximum performance out of their machine. Try compiling your web browser or operating system with -O0 and then tell me the performance is satisfactory. Or your video encoder. Or VMware. There is a huge market for high-performance software where performance comes from more than a few inner loops, and optimizing compilers, while complicated and huge and occasionally buggy, are necessary for the user experience we desire.

rtpg• 10 years ago

I think this advice is for people who don't necessarily need it.

I don't know if there's a name for it, but I've started reading "Don't do X" as "Don't do X unless you have a realllllly good reason to." Nothing in life is absolute, after all.

Similar advice is "Use a GC". There are (similar) use cases where you shouldn't use a GC. But if you don't have a strong case for paying the price of not using a GC (in terms of potential bugs and code complexity), then using a GC by default is pretty good advice.

But yeah, if you're writing VMWare, you're hopefully also skilled enough in the domain to know that you should try to get maximum performance. But if you're writing some shell scripts or webapp, a lot of the time your bit-twiddling optimisations will be noise relative to the variation from I/O alone.

vmorgulis3• 10 years ago

But it seems like his blog is a series of repeated arguments that nobody needs maximum performance out of their machine.

Not false. He seems sometimes contradictory.

http://www.dadgum.com/james/performance.html

junke• 10 years ago

I don't understand what is contradictory here.

The golden rule of programming has always been that clarity and correctness matter much more than the utmost speed. Very few people will argue with that. And yet do we really believe it? If we did, then 99% of all programs would be written in something like Python. Or Erlang. Even traditional disclaimers such as "except for video games, which need to stay close to the machine level" usually don't hold water any more.

He claims that you can usually choose any language you want to develop your software and that it will not make any visible difference. Systems are so fast nowadays that the trying to optimize for speed will need to an effort that is probably not justified.

zamalek• 10 years ago

Take data-oriented design as an example: if you really read into it, it does actually relegate the compiler to something marginally better than a dumb code generator. The mundane optimizations (inlining, constant propagation, etc.) are expected of the compiler and the developer focuses on things like using the stack well (from the article) or being cache friendly.

Saying that C++ categorically cannot be used to create good machine code is ignoring much evidence to the contrary.

pjmlp3• 10 years ago

All good examples, however the problem are those developers micro-benchmarking each code line they write even if the user of the program doesn't care if it takes 1ms or 1s to achieve what they are doing.

This mentality is quite common in certain programming circles.

joosters2• 10 years ago

They can do that all they like as long as the binary still works in all the same situations. Fine by me. I even gave the compiler permission to do it with the -O flags.

Or are you trying to dictate what compiler writers should be focusing on? They're free to choose what to work on, so don't use their compiler if you disagree with it.

rlpb• 10 years ago

"If you get any of this wrong, even in an edge case, the user is presented with non-working code for a valid program, and the compiler writer has failed at his or her one task."

Perhaps languages could be designed so as to make this task easier?

In language design we end up torn between making things easier for the programmer and making things easier for the compiler-designed-for-performance. Doing both things well is perhaps something that language design will be able to improve upon in the future.

dkopi5• 10 years ago

Languages and compilers actually do have constructs for programmers to make things easier for the compiler.

"inline" and "register" are two very known examples. Other examples are function attributes in gcc: https://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html

nkurz• 10 years ago

I presume you're aware that you've chosen two controversial examples? "register" has been formally deprecated in C++, and has been ignored by (almost?) all C compilers for decades: http://stackoverflow.com/questions/20618008/replacement-for-...

And most current wisdom is that "inline" no longer serves as a useful performance suggestion to the compiler, but instead should only be used as a linkage directive to allow multiple declarations of the same function: http://stackoverflow.com/questions/29796264/is-there-still-a...

0x07c04• 10 years ago

restrict is probably a better example! https://en.wikipedia.org/wiki/Restrict

akkartik• 10 years ago

A degenerate case is my project, which makes people write assembly, but in a very safe way that it can check. You lose the expressivity of conventional HLLs, but still get their safety benefits.

https://github.com/akkartik/mu

jcr• 10 years ago

After reading the mu link you posted, I was going to ask you to submit it as a "Show HN" post... but it seems I'm about a month too late:

https://news.ycombinator.com/item?id=11092067

It's great reading. thanks.

carussell• 10 years ago

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.

bijection• 10 years ago

Halide is a neat example of this approach in an image processing context [1] [2]

[1] http://halide-lang.org/

[2] https://people.csail.mit.edu/jrk/jrkthesis.pdf "Decoupling Algorithms from the Organization of Computation for High Performance Image Processing"

legulere• 10 years ago

So this article says that optimizing compilers are unreliable? I don't think this is the case.

Compiler bugs are pretty rare, a bigger problem are insane language standards that have undefined behaviour lingering behind every corner.

randomsearch7• 10 years ago

Compiler bugs are not rare, quite the opposite, and this is often because of premature optimisation.

For example, GPGPU compilers are awful:

http://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2015/PLDI...

DannyBee3• 10 years ago

It's more that compiler vendors who compete mainly on the basis of worthless benchmarks do awful things.

This is one of the reasons gcc/llvm won: they don't care about that stuff. I mean, they care about performance, but not at all costs like these guys care.

At some point, people wanted compilers that did less stupid things. So they moved to the vendors who did that.

The reason it's so awful in the GPGPU space is because none of these vendors produce compilers yet. Instead, the vendors you have are those whose main goal in life is to generate better performance numbers than the other guy.

Ask anyone about the old days of fortran compilers and early optimizing C compilers and what have you.

What exists now is essentially "what happened after the market pushed back". Sadly, it didn't go as far as some people want (in either direction).

MichaelBurge2• 10 years ago

I run into so many compiler bugs. Examples: g++, ghc, booc. I remember one time playing around with Unity3D, and for some reason decided to use the Boo language to write my code. I ended up having to patch booc to work around about a dozen different bugs.

There's also the time I caused a kernel panic on CentOS 5 by running g++ on my code. It did so reliably, so I moved development to CentOS 6.

Older gdbs on CentOS 4 will segfault if you run it on a binary compiled with ghc and ask for a backtrace.

One time, I wrote a Perl module that unintentionally trashed the Perl interpreter's error tracking information. So if the module compiled, it worked fine. But if you had even a single variable mis-spelled or missing semicolon, all you'd get from perl is the error "Unknown error".

Or even something as simple as writing a negative integer literal bugs out ghc: https://ghc.haskell.org/trac/ghc/ticket/9533

Compilers are absolutely riddled with bugs.

mkj• 10 years ago

Your examples sound more like bugs in the Linux kernel or gdb.

loup-vaillant2• 10 years ago

(Edit: oops, I haven't read your second line…)

[Indeed,] There's more to it than bugs.

Undefined behaviour for instance is generally understood by the programmer as being runtime driven craziness. Divide by zero for instance will raise a clean error (generally resulting in a clean crash) on most platform.

Popular C compilers such as GCC and LLVM however, have a different understanding, based on the wording of the standard. They are allowed to assume that undefined behaviour simply doesn't happen, and use that assumptions in optimizations such as dead code elimination or alias analysis. With this stuff, a program that would have exhibited undefined behaviour if compiled straightforwardly is allowed to go bananas at any time. This is compile time driven craziness, a rather different beast.

A classic example of this is signed integer overflow. You perform some arithmetic that may overflow, then check for overflow after the fact. Most architectures perform two's complement modulo arithmetic, so it works without problem. Except that in C, this is undefined behaviour. So your compiler is allowed to assume it never happens. Which means your test that `x >= x+1` is going to be "true" all the time. Which means that your error handling branch is dead code. And that could allow nasty stuff such as buffer overflows.

You could say it's the user's fault for relying on undefined behaviour (that is nevertheless well defined on x86 and ARM assembly). But you gotta admit that's not very intuitive. Yes, in some obscure platforms such an overflow could make your CPU jump in a random place. Yes, relying on this is not portable. But C is supposed to be close to the metal. Few C users would expect the compiler to optimize it all away even if it would work on their platform.

On the other hand, things like strict aliasing are explicitly about enabling compiler optimizations.

riscy2• 10 years ago

This is a meaningless article. A compiler that chooses to perform an optimization (transformation) which does not preserve the defined semantics of the language has a bug, by the definition of what a compiler is. What is the argument?

jfoutz• 10 years ago

something like -Ofast is well defined. the thing is, it defines another language closely related to the source language but with some extra constraints. So you have C, and also C'. It may be the case that all the C in your program happens to be valid C', but probably not. If you're not acutely aware of the rules of C', you won't get what you want. And, some poor hapless C programmer may find themselves working on a C' project and not know it, or the expert is suddenly a beginner again, because they need to learn the extra rules of the game.

It's all well defined. it's a social problem. it's something to be aware of.

riscy2• 10 years ago

If you're not acutely aware of the rules of C', you won't get what you want.

The same can be said of any language that lacks a rigorous definition; misusing -Ofast is just an example of one. Even then, the definition can be too large or tricky for anybody to truly understand, but that's a bit of a grey area... at some point you have to draw the line and say the programmer made a mistake. The only sensible thing to do is draw the line at the definition of the language, otherwise there is chaos.

lmm• 10 years ago

But why would people who don't need that last 1% of performance be using C at all in this day and age? The article talks about crafting assembly by hand, but C is often spoken of as a cross-platform assembler.

mpweiher2• 10 years ago

I blame:

(a) free compilers

(b) the C standard

Crazy talk, surely! Let me explain: each of these is a Good Thing™, but together they have put us in our current predicament. It used to be that compilers were reasonably expensive products, so as a vendor you had a clear incentive not to piss off your customers. In addition (in the very olden days), there as no C standard so the definition of "correct" was very customer-based: if customer code compiled well, you were doing a good job, if not, you would probably suffer.

With compilers becoming free, the incentive structure changed, customers now matter very little. Instead, you get ahead in that pecking order by improving some SPEC benchmark by 0.2%. At the same time, the C standard, which was worded very inclusively so even compilers for odd architectures could be ANSI/ISO compliant, was used as a substitute for "my customers' code works", and people started to say silly things like "if you have undefined behaviour, demons can fly out your nose".

Well: I had a pre-ANSI compiler. ALL its behaviour was "undefined". And yet it took fewer liberties with the code than many of today's compilers do. Because the creators (a) were reasonable people and (b) had real customers.

dalailambda• 10 years ago

While I understand the argument the author is making, I think it's important to consider that while a mild focus on performance could only benefit your code a little, applied across your entire stack, the performance benefits start to add up, and become worthwhile.

gambiting• 10 years ago

"I've seen arguments that some people desperately need every last bit of performance, and even a few cycles inside a loop is the difference between a viable product and failure. Assuming that's true, then they should be crafting assembly code by hand, or they should be writing a custom code generator with domain-specific knowledge built-in."

Well, I work in the games industry and that "last bit of performance" is quite frequently the difference between having a 60fps game and something that doesn't quite hit the vsync and looks a lot worse. Seriously, this is one of the very few industries where I can say with a straight face "don't do context switching because the 5 microsecond delay is too much" and "a missed L2 cache hit costs us 50 cycles, and it a major problem here".

Rexxar• 10 years ago

I think the problem is not too much optimizations but the undefined behaviors/compiler bugs detection. There should be an "optimized debug" mode that apply all optimizations requested but add asserts to check every assumptions made by the compiler. In this way we can run the "optimized debug" binary and check it doesn't trigger any assert.

sharpneli• 10 years ago

I don't understand the point of the article. Using optimizations in a compiler is fully voluntary act. You can just compile everything with -O0 and be done with it.

Some of us actually do need them. Soft realtime programs (games as an example) are perfect example where they are crucial. Reaching same level of performance using non optimizing compiler would balloon the development costs up multiple times.

I would understand the complaint if compilers would mess things up and you couldn't get around it.

On the Madness of Optimizing Compilers

Related Stories