14 ms·

Compiler Optimizations are Awesome

203 points by turingbook 9y ago

deleted 9y ago
[deleted]
petters 9y ago
It should be quite easy to see the value of optimizing compilers. Compile your program with optimizations turned off. Now make it as fast as your release build again, while still keeping them off. For much of my code, I think this would take years.
- nullc 9y ago
  You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. I think DJB would argue that the compiler optimizations are insignificant in comparison to those improvements for a very large portion of hot code. Of course, even if I'm correct you could turn the optimizations back on and be faster still. One reason why you might not want to do that is the cost of increased miscompliation.
  - DannyBee 9y ago
    " I think DJB would argue that the compiler optimizations are insignificant in comparison to those improvements for a very large portion of hot code." Except he has no data to show this, and every piece of data i have (and my colleagues have), says that he is wrong. Additionally, the compilers can and do replace algorithms if users let them. Most users don't want it, even if it makes code faster. Remember that the vast majority of people want software that works and is reliable, or has fast development cycles, or a million other things, and happily choose that over software that is fast. Compilers changing algorithms on you isn't highly compatible with this, especially when, for example, most programming languages don't even give you a good way to express the invariants you are trying to maintain (except good ol' Ada). However, besides that, certainly you can see that in the end, the people lose. It's like arguing that computer would never win at go. If i really really really cared about some piece of hot code, i wouldn't pay an expert to optimize it, i'd throw the cycles of 100k spare cpus at optimizing it. That is also the other strange part of his argument to me, he assumes the capabilities of compilers based on compilers he sees that are meant to operate pretty much single threaded on single machines, and complains "they will never beat people". It's like looking at the machine learning algorithm that takes months or years or roughly forever to train on a single cpu and say "it'll never do a good job". The world is not that small anymore. It's blindingly obvious the optimizing compilers win if we want them to. In any case, this particular debate will restart again as gpus and accelerators follow the same old compiler cycle.
    - oconnor0 9y ago
      > Additionally, the compilers can and do replace algorithms if users let them. Most users don't want it, even if it makes code faster. What compilers do this? With what algorithms?
      - jerven 9y ago
        If you look at modern JIT compilers such as Truffle-Ruby, then yes it will change algorithms. e.g. changing sort algorithms depending on data size. if the data is small enough it will do a bubblesort on registers, when its big it will do TimSort on heap data etc...[1] [1]: http://chrisseaton.com/rubytruffle/small-data-structures/ http://chrisseaton.com/rubytruffle/small-data-structures/
        coldtea 9y ago
        This example is about the compiler changing between (existing) internal versions of sorting algorithms for language data structures. Not about changing what algorithms the user coded.
        danielbarla 9y ago
        Exactly, that's two completely different things. It's akin to a compiler using the famous "switch statement becomes if-else chain if less than 7 items, otherwise lookup table". The parent posts are referring to macro-level optimisations, where large changes to how a system works are implemented, in order to get massive gains in performance. Picking out the essence of the larger implementation would be a difficult task for a compiler, but more importantly it wouldn't have enough information about the context of the application to make optimisation decisions. Things like: do we need to read from that file each time we need this piece information, or is it a once-off that can be cached? Unless this contextual information is expressed somehow (and it basically never is), only the programmer will be able to make the change.
        jerven 9y ago
  - oconnor0 9y ago
    I think one of the issues here is what compiler optimizations encompass. In a language like C or C++, you may be able to write optimal algorithms but end up with poor performance because of memory access. An unoptimized compile puts almost everything on the stack - a = b + c involves two loads, one add, and one store in an unoptimized compile. All of that extra memory access is going to kill performance; even if you have optimal data structures and algorithms. I see "optimizations are bad/unnecessary/problematic/whatever" in my job writing a compiler. The underlying issue is almost never "I don't want optimizations" - even when someone thinks that's what they want; it's "I don't want optimizations that produce unexpected behavior".
  - dagw 9y ago
    You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. My HPC lecturer used to say that the speed difference between bad Matlab code and good Matlab code will often be greater than the speed difference between good Matlab code and good Fortran code. Tweaking the hell out of your code at the assembly level is a waste of time if you're using a naive O(2^N) algorithm.
    - gpderetta 9y ago
      ... unless N is small.
    - sllabres 9y ago
      You mean O(n^2). 2^n looks a more than 'naive' for most cases.
  - dom0 9y ago
    > You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. Implementation differences in the exact same, say, simple linear algorithm, can still add up to a tenfold difference. Compiler optimisations can take it further, though some are not generally applicable. E.g. I have made good experiences with PGO (careful analysis and/or knowing your workload is needed), but it's obviously not an option for the typical open source software distribution model. Obviously, combining a better algorithm with a better implementation that is optimized will be fastest.
  - Sean1708 9y ago
    > You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. Absolutely but often it's very hard to make those changes or those changes lead to a loss of accuracy, whereas compiling with -O3 is very easy and leads to no loss in accuracy (in the common case).
- std_throwaway 9y ago
  People use Python to actually do stuff. Performance-wise it's a nightmare but usability outweighs it in many many cases.
  - coldtea 9y ago
    Plus it's only a nightmare "performance-wise" when it's actually slow in wall clock time. Often it's so fast that it doesn't matter at all that it can be 1/100 slower then C. 0.1 sec is still good even if it's not 0.001 secs.
    - dom0 9y ago
      Python performance is uh ah... difficult. I work on a piece of software that has a lot of hot paths in Python code, and it's not nice. Combined with deployment and tooling issues it made me wonder quite a few times now, whether the a little bit lower contribution barrier is worth all these hassles.
      - aeroevan 9y ago
        Cython is a very nice way to transition hot python paths into a C extension. The best part is that it's a python superset, so it should provide some speed up without any typing information (and can be very fast once the hot paths are all in cdef'd functions).
        nickpsecurity 9y ago
        Beat me to it. Cython was a great solution to this problem.
        dom0 9y ago
        https://news.ycombinator.com/item?id=14376961 https://news.ycombinator.com/item?id=14376961 Further, it doesn't help with the required restructuring; when the functionality is scattered across a dozen or more modules (complex software + good Python practice), then you first have to pull the functionality needed for the path you're trying to get fast together. That leads to duplication, removing abstractions and most certainly vetoes from other people.
- wolfgke 9y ago
  > It should be quite easy to see the value of optimizing compilers. Compile your program with optimizations turned off. Now make it as fast as your release build again, while still keeping them off. For much of my code, I think this would take years. The problem is that, say, C does not allow to express the necessary details about the optimizations that you want to do. This is exactly something DJB calls for in programming languages.
zurn 9y ago
TL;DR "Optimizing compilers are still good to have because they are cheaper than programmer labour needed for hand optimization" The original DJB presentation, which this is a response to, is very good and interesting. It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout and data types/representations based on partial evaluation / profile feedback.
- sanxiyn 9y ago
  > It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout Interesting tidbit: LLVM was developed by Chris Lattner for his PhD thesis. It was titled "Macroscopic Data Structure Analysis and Optimization" and about "Instead of analyzing individual load/store operations or structure definitions, this approach identifies, analyzes, and transforms entire memory structures as a unit", in his own words. Apparently, the world was more interested in a good compiler framework than specific memory layout optimization proposed. http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html
- DannyBee 9y ago
  " like optimizing memory layout and data types/representations based on partial evaluation / profile feedback." They already can. The issue is usually one of what is allowable within language semantics, not of compiler optimization technology. One reason you may see this as neglected is that outside of, say, polyhedral loop optimizations, research in the 80's and 90's (and sometimes earlier) did a really really good job of exploring this area because fortran allowed so much freedom.
  - zurn 9y ago
    Compilers and languages of course co-evolve. And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA. And older language extensions that have ove time become everyday stuff, like SIMD intrinsics. So I don't think "languages don't support it" is a good excuse.
nullc 9y ago
I'm disappointed at the lack of figures.
lukego 9y ago
I often think about Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years. Sure, optimizing compilers are nice to have, but maybe their complexity is disproportionate to their benefit? I love the way Dynamo [1] is able to reproduce many of the benefits with a fraction of the complexity by doing some of the optimizations at runtime with simpler algorithms. Can we use this approach to "garbage collect" some of the complexity embodied in humongous projects like LLVM? [1] Dynamo: https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/bala00dynamo.pdf https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall20...
- xoroshiro 9y ago
  Got a bit confused here. I was thinking about a very old software I used in college for my systems dynamics class. Completely different (unless I am mistaken), but still brings back painful memories of that class. https://en.wikipedia.org/wiki/DYNAMO_(programming_language) https://en.wikipedia.org/wiki/DYNAMO_(programming_language)
- Joky 9y ago
  You're mentioning "disproportionate complexity" for current compilers and at the same time advocating for a runtime system modifying and caching the code on the fly? Ouch... Note also that I don't believe that Dynamo "reproduce many of the benefits [...]", since the paper you linked benchmarked running Dynamo on top of the O2 generated code (by a ~20y old compiler). It isn't clear if they ripped "low-hanging fruit" that static compilers are catching nowadays. Also the same thing on top of a PGO+LTO build may be a more fair comparison.
  - lukego 9y ago
    The exciting possibility, from my perspective, is that many optimizations may be simpler to implement dynamically (JIT) than statically. So perhaps you can have 10% of the compiler code to get 90% of the benefit. I see this as the basic premise of LuaJIT. Motivating example: The CPU can predict whether branch instructions will be taken with uncanny accuracy. This is achieved using simple dynamic heuristics. I believe it would be much more challenging for the compiler to predict these branches statically.
jcranmer 9y ago
Several years ago, I happened on a blog post where someone demonstrated a very fast variant of the N-queens solution based on hand-written, SSE vectorized that was presented as very fast. I managed to write a faster, non-vectorized C solution that was recursive and that the compiler couldn't vectorize, and much easier to understand than the vectorized original it was based off of. Turns out that main reason the vaunted "overkilled" solution was so abysmally slow was that the author happily used BSF and BTC in the hottest part of the loop... which are actually rather slow instructions, particularly when you're using them to control a branch (compare-and-jump is a fused µop in practice, but BTC-and-jump is not). The point of this tail is that if you want to absolutely wring the last clock cycle out of a hot path, you usually need good microarchitectural knowledge about which operations are going to be faster and which are not. Sure, you can beat a compiler with hand-written, hand-optimized assembly code most of the time--but the people who have the skills to write such code are going to be the people working on the compilers. The tools for optimizing compilers are getting better, and probably faster than we are capable of pumping out performance engineers to hand-craft the inner loops. In the past decade, we've seen polyhedral loop transformations become production-quality. Auto-vectorization is getting better, particularly when user-directed (think #pragma openmp simd); I know Intel has been pushing "outer-loop vectorization" very hard in the past few years. The other big fruit on the horizon is superoptimizers: I suspect we'll see superoptimizers shipping in production compilers within a decade or two.
- innocenat 9y ago
  I think it depends a lot. I have work on some hand-crafted SIMD for multimedia use before. It is fairly easy to outperform the auto-vectorization in that field IMO. I have also played around with various attempts to hand-craft inner loop (SIMD and no SIMD) for other project but most of the time I failed to outperform the compiler.
  - w0utert 9y ago
    Yes, it depends a lot. Typical signal-processing tasks you will definitely want to hand-optimize, no matter how good the compiler is, it will never be able to get close to hand-crafted SIMD code in combination with careful memory-layout, reducing the working set, eliminating dependencies, maximizing cache usage etc. There's a lot involved with that kind of optimizations that supposes semantic knowledge of the data going through the algorithm to be able to make transformations to optimize the code. For the other 99% of code it's hard (and definitely not worthwhile to try) to beat the compiler though. I sometimes watch programming streams where people go very deep into the compiler-generated code to analyze runtime behavior of their code, and it's almost scary to see the kinds of things compilers can do these days.
fizixer 9y ago
Great talk by DJB. IMO he couldn't give a convincing answer to the guy who asked about LuaJIT author being out of a job. But there's a clear answer. JIT authors are not out of job not because optimizing compilers are not dead, but because they're writing compilers, their distinguishing ability is writing "pre-compiled" code. You might say, "well a JIT author sped up your code's execution so he/she is writing an optimizing compiler". Well you have to realize that, traditionally, JIT authors don't just translate the code into object code, they also apply these things called "compiler optimizations". The point is that if they didn't do that, and simply produced a faithful translation of the code, they would still make the code faster because of pre-compilation (and if they enabled the "compiler optimizations", the code wouldn't run significantly faster than the simply pre-compiled code). Regardless of whether I agree with it or not, "Optimizing compilers are dead" is not the same as saying "JIT authors will be out of business". (Even compiler writers won't be out of business).
- samth 9y ago
  I was that guy in the audience. Your suggestion is that a templating JIT that just drops in some machine code that matches the method, doing no optimization, would get all the win. Such a compiler is indeed much faster than an interpreter, but it's nowhere close to an optimizing compiler. Mike Pall, the author of LuaJIT, would be very surprised if you suggested that his compiler performed similarly to something simple like that.
  - mikemike 9y ago
    Actually, LuaJIT 1.x is just that: a translator from a register-based bytecode to machine code using templates (small assembler snippets) with fixed register assignment. There's only a little bit more magic to that, like template variants depending on the inferred type etc. You can compare the performance of LuaJIT 1.x and 2.0 yourself on the benchmark page (for x86). The LuaJIT 1.x JIT-compiled code is only slightly faster than the heavily tuned LuaJIT 2.x VM plus the 2.x interpreter written in assembly language by hand. Sometimes the 2.x interpreter even beats the 1.x compiler. A lot of this is due to the better design of the 2.x VM (object layout, stack layout, calling conventions, builtins etc.). But from the perspective of the CPU, a heavily optimized interpreter does not look that different from simplistic, template-generated code. The interpreter dispatch overhead can be moved to independent dependency-chains by the CPU, if you're doing this right. Of course, the LuaJIT 2.x JIT compiler handily beats both the 2.x interpreter and the 1.x compiler.
fovc 9y ago
In the linked slides, DJB talks about a language for communication with the compiler, separating optimizations from specification. This reminded me of VPRI's "Meaning separated from optimization" [1] principle. Does anyone know what became of that line of thinking? Is this idea making it's way into Ohm? I remember reading a post/paper about optimizing Nile/Gezira to better exploit the CPU cache (and the struggle to use SIMD), but can't seem to find it now. [1] http://www.vpri.org/pdf/rn2006002_nsfprop.pdf http://www.vpri.org/pdf/rn2006002_nsfprop.pdf
- nickpsecurity 9y ago
  IBM's old PL/S language allowed you to give hints like where data would go or what checks would happen right in the function declaration. The compiler would handle it from there.
lmm 9y ago
> If an optimizing compiler can speed up code by, for example, 50%, then suddenly we need to optimize a lot less code by hand. This doesn't follow at all. If you had one hot loop and a bunch of cold code, and auto-optimize your code to be a measly factor of 2 faster, you're still going to need to hand-optimize the hot loop and what it does to the cold code is irrelevant. > hand-optimized code has higher ongoing maintenance costs than does portable source code; we’d like to avoid it when there’s a better way to meet our performance goals. True, but again, only applies if you can optimize by enough to make hand-optimization unnecessary. > we’d also have to throw away many of those 16 GB phones that are cheap and plentiful and fairly useful today. This part is nonsense. No-one's got anything like 16GB of code on their phone. Optimization could be valuable but current compilers are too opaque, making optimization too much of a black art. I believe we need to do something along the lines of "turning the database inside out" ( https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/ https://www.confluent.io/blog/turning-the-database-inside-ou... ); we should turn the compiler inside out, build it as more of a library, give the developer more insight into what's going on, have a high level language that lets you understand how it compiles. Interesting and vaguely along the same lines: https://www.microsoft.com/en-us/research/publication/coq-worlds-best-macro-assembler/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fnick%2Fcoqasm.pdf https://www.microsoft.com/en-us/research/publication/coq-wor... .
- tom_mellior 9y ago
  > auto-optimize your code to be a measly factor of 2 faster, you're still going to need to hand-optimize the hot loop Huh? You start with performance goals. If compiler-optimized code meets your performance goals, you are done. You do not "need to hand-optimize" in that case. Why would a "factor of 2" not be good enough? What is it compared to? What makes you so sure that you must optimize further, disregarding any possible context?
  - w0utert 9y ago
    Additionally, if a factor 2 improvement by the compiler on top of a factor 4 improvement by using better algorithms and data structures can give you an 8x improvement overall, why would you not take it? Reading through the various comments asserting that optimizing compilers should not be necessary if you 'just use better algorithms' and whatnot, I'm kind of wondering why it has to be one thing or the another. Who wouldn't want to have both?
jerrre 9y ago
> Compiler optimization reduces code size Nope, much is gained by unrolling loops, inlining functions etc, which all increase code size. Of course C++ compilation with no optimization at all can be rather wasteful with performance and code size, but to squeeze the final performance out you probably need to sacrifice code size (whether manual or automatic)
- aidenn0 9y ago
  > Nope, much is gained by unrolling loops, inlining functions etc, which all increase code size. That's because those are performance optimizations, not size optimizations (though as an aside, inlining functions can reduce code size in the event that the inlined version is smaller than the function-call overhead, or in the case where the function is used only once). There are plenty of size optimizations that can be performed. -Os will enable them on gcc/clang if you want to try for yourself.
faragon 9y ago
Is there any compiler using "machine learning" for SIMD optimization?
- Verdex_2 9y ago
  I'm not sure, but I remember seeing some research into using it for Haskell stream fusion (can't find the video, sorry). I believe that the basic idea was that not all rewrites end up being equally fast ( a * b * c can be fused into ab * c, but maybe a * bc is faster). Trying all the combinations is an option in theory, but you get a combinatorial explosion so you normally dont get far in practice. Enter machine learning. I'm not sure how successful they were, but I imagine that the same sort of thing could be applied to SIMD.
CJefferson 9y ago
Having used some language with awful compilers, compiler optimisations let me write cleaner code. In languages with bad optimisers I have to worry about separating code in a hot loop out into a function -- the cost of a function call is too high. This one in particular I find can lead to some horrible code, as functions grow larger and larger and lots of cutting+pasting happens to avoid function call costs. On a smaller note, making sure I cache the values of function calls which won't change -- when instead I could trust the compiler to know the value won't change and the the caching itself.
- gruez 9y ago
  There isnt some forcelinline attribute in gcc?
  - Paul_S 9y ago
    Yeah, #define.
  - JoachimSchipper 9y ago
    Your parent is probably not talking about gcc, or even about C; gcc does indeed have __attribute__((always_inline)).
  - CJefferson 9y ago
    There is, but in practice just normal inline, or even trusting the compiler to decide what to inline itself, are just fine. The problem comes when you are using other languages (scripting ones like Python come to mind) where inlining is but a dream (ignoring systems like PyPy).
mrkgnao 9y ago
I'm posting this as a top-level comment, but it's really a reply to the discussion downthread about compilers being able to work magic if we let them. Better still, why not help them? Something I took for granted for the longest time about Haskell (which remains the only language I know of with the feature) is the ability to write user-defined "rewrite rules". You can say, "okay, GHC, I know for a fact that if I use these functions in such-and-such way, you can replace it by this instead". {-# RULES foo x (bar x) = superOptimizedFooBar x #-} A rule like this would be based on the programmer's knowledge of FooBar theory, which tells her that such an equality holds. The compiler hasn't studied lax monoidal FooBaroids and cannot be expected to infer this on its own. :) Now, anywhere a user of this code writes something like foo [1,2,3] (bar [1,2,3]) the compiler will substitute superOptimizedFooBar [1,2,3] in its place. This is a nice way to bring the compiler "closer" to the programmer, and allow the library author to integrate domain-specific knowledge into the compiler's optimizations. You can also "specialize" by using faster implementations in certain cases. For example, timesFour :: Num a => a -> a timesFour = a + a + a + a timesFourInt :: Int -> Int timesFourInt x = rightShift x 2 {-# RULES timesFour :: Int -> Int = timesFourInt #-} If you call timesFour on a double, it will use addition (ha!) but using it on an Int uses bitshifting instead because this rule fires. High-performance Haskell libraries like vector, bytestring, text, pipes, or conduit capitalize on this feature, among other techniques. When compiling code written using libraries like this, this is how it goes: - rule #1 fires somewhere - it rewrites the code into something that matches rule #2, "clearing the way" for it to fire - rule #2 fires - rule #3 fires - rule #1 fires again - rule #4 fires and so on, triggering a "cascade" of optimizations. The promise of Haskell is that we already have a "sufficiently smart compiler": today, with good libraries, GHC is capable of turning clear, high-level, reusable functional code with chains of function compositions and folds and so on into tight, fast loops. -- I must add, though, that getting rewrite rules to fire in cascades to get "mad gainz" requires one to grok how the GHC inliner/specializer works. http://mpickering.github.io/posts/2017-03-20-inlining-and-specialisation.html http://mpickering.github.io/posts/2017-03-20-inlining-and-sp... Data.Vector also utilizes an internal representation that makes fusion explicit and hence predictable (inevitable, even) called a "bundle": https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Data-Vector-Fusion-Bundle.html https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Da... but this relies on rewrite rules too, e.g. the previous module contains this rule: {-# RULES "zipWithM xs xs [Vector.Stream]" forall f xs. zipWithM f xs xs = mapM (\x -> f x x) xs #-}
scraft 9y ago
Is anyone else in games development here? If we are looking to run the game at 60 FPS, we have 16.67 ms per frame to do everything required to run the game. Because of this real time requirement, a decent amount of profiling is typically done on each game. I typically see that the frame time is getting split up over a whole array of different sections of the game, i.e.: - Calculating skeleton animations (updating bone positions, sometimes skinning vertices too) - Clipping geometry in the scene (finding out what things are inside/outside the camera frustum, etc.) - Processing game logic, things like AI can be quite costly, so much is game dependent - Walking through all the geometry that needs drawing and issueing draw calls - Decompressing streaming audio and sending it to a sound driver buffer/queue - Stepping the physics world (integrating positions/rotation working and resolving out intersections, etc.) The difference between a non optimized, and an optimized build, is often 5 FPS and 60 FPS, and optimizing a single hot file or function would not get the game running anywhere near 60 FPS. I think the idea that optimizing compilers aren't required is completely laughable, but then again I only have one perspective from the games development scene - maybe someone else will reply and say they make AAA games in C/C++ and don't need compiler optimizations :)
- AstralStorm 9y ago
  Those gains are often caused by globally applied optimizations like inlining and devirtualization. These then can enable actual stream processing and loop chunking optimizations which are of important but lesser effect. Perhaps dead code and constant elimination of you leave in flags. In other words, if you rewrite the algorithms from object oriented into stream processing, you would get most of the gains. This is caused by all CPU, FPU and GPUs actually internally being simple numerical stream machines.
- zurn 9y ago
  A bit of trivia: Computation is frequently pipelined so that part of the work is done during previous frame(s). This of course means that the game logic latency is longer than 1 frametime.
- mwkaufma 9y ago
  AAA dev here. The performance gains mostly come from designing data, not code. Factoring an array of structures into a structure of arrays and accessing linearly, e.g., makes better use of the processor cache and saturates throughput. Code optimization mostly gives us the confidence that there aren't unnecessary accesses or branches interleaved that might bust the cache.

203 points by turingbook 9y ago

deleted 9y ago

[deleted]

It should be quite easy to see the value of optimizing compilers. Compile your program with optimizations turned off. Now make it as fast as your release build again, while still keeping them off. For much of my code, I think this would take years.

nullc 9y ago
You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. I think DJB would argue that the compiler optimizations are insignificant in comparison to those improvements for a very large portion of hot code. Of course, even if I'm correct you could turn the optimizations back on and be faster still. One reason why you might not want to do that is the cost of increased miscompliation.
- DannyBee 9y ago
  " I think DJB would argue that the compiler optimizations are insignificant in comparison to those improvements for a very large portion of hot code." Except he has no data to show this, and every piece of data i have (and my colleagues have), says that he is wrong. Additionally, the compilers can and do replace algorithms if users let them. Most users don't want it, even if it makes code faster. Remember that the vast majority of people want software that works and is reliable, or has fast development cycles, or a million other things, and happily choose that over software that is fast. Compilers changing algorithms on you isn't highly compatible with this, especially when, for example, most programming languages don't even give you a good way to express the invariants you are trying to maintain (except good ol' Ada). However, besides that, certainly you can see that in the end, the people lose. It's like arguing that computer would never win at go. If i really really really cared about some piece of hot code, i wouldn't pay an expert to optimize it, i'd throw the cycles of 100k spare cpus at optimizing it. That is also the other strange part of his argument to me, he assumes the capabilities of compilers based on compilers he sees that are meant to operate pretty much single threaded on single machines, and complains "they will never beat people". It's like looking at the machine learning algorithm that takes months or years or roughly forever to train on a single cpu and say "it'll never do a good job". The world is not that small anymore. It's blindingly obvious the optimizing compilers win if we want them to. In any case, this particular debate will restart again as gpus and accelerators follow the same old compiler cycle.
  - oconnor0 9y ago
    > Additionally, the compilers can and do replace algorithms if users let them. Most users don't want it, even if it makes code faster. What compilers do this? With what algorithms?
    - jerven 9y ago
      If you look at modern JIT compilers such as Truffle-Ruby, then yes it will change algorithms. e.g. changing sort algorithms depending on data size. if the data is small enough it will do a bubblesort on registers, when its big it will do TimSort on heap data etc...[1] [1]: http://chrisseaton.com/rubytruffle/small-data-structures/ http://chrisseaton.com/rubytruffle/small-data-structures/
      - coldtea 9y ago
        This example is about the compiler changing between (existing) internal versions of sorting algorithms for language data structures. Not about changing what algorithms the user coded.
        danielbarla 9y ago
        Exactly, that's two completely different things. It's akin to a compiler using the famous "switch statement becomes if-else chain if less than 7 items, otherwise lookup table". The parent posts are referring to macro-level optimisations, where large changes to how a system works are implemented, in order to get massive gains in performance. Picking out the essence of the larger implementation would be a difficult task for a compiler, but more importantly it wouldn't have enough information about the context of the application to make optimisation decisions. Things like: do we need to read from that file each time we need this piece information, or is it a once-off that can be cached? Unless this contextual information is expressed somehow (and it basically never is), only the programmer will be able to make the change.
        jerven 9y ago
- oconnor0 9y ago
  I think one of the issues here is what compiler optimizations encompass. In a language like C or C++, you may be able to write optimal algorithms but end up with poor performance because of memory access. An unoptimized compile puts almost everything on the stack - a = b + c involves two loads, one add, and one store in an unoptimized compile. All of that extra memory access is going to kill performance; even if you have optimal data structures and algorithms. I see "optimizations are bad/unnecessary/problematic/whatever" in my job writing a compiler. The underlying issue is almost never "I don't want optimizations" - even when someone thinks that's what they want; it's "I don't want optimizations that produce unexpected behavior".
- dagw 9y ago
  You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. My HPC lecturer used to say that the speed difference between bad Matlab code and good Matlab code will often be greater than the speed difference between good Matlab code and good Fortran code. Tweaking the hell out of your code at the assembly level is a waste of time if you're using a naive O(2^N) algorithm.
  - gpderetta 9y ago
    ... unless N is small.
  - sllabres 9y ago
    You mean O(n^2). 2^n looks a more than 'naive' for most cases.
- dom0 9y ago
  > You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. Implementation differences in the exact same, say, simple linear algorithm, can still add up to a tenfold difference. Compiler optimisations can take it further, though some are not generally applicable. E.g. I have made good experiences with PGO (careful analysis and/or knowing your workload is needed), but it's obviously not an option for the typical open source software distribution model. Obviously, combining a better algorithm with a better implementation that is optimized will be fastest.
- Sean1708 9y ago
  > You may be significantly underestimating your ability to get phenomenal gains from algorithmic improvements. Absolutely but often it's very hard to make those changes or those changes lead to a loss of accuracy, whereas compiling with -O3 is very easy and leads to no loss in accuracy (in the common case).
std_throwaway 9y ago
People use Python to actually do stuff. Performance-wise it's a nightmare but usability outweighs it in many many cases.
- coldtea 9y ago
  Plus it's only a nightmare "performance-wise" when it's actually slow in wall clock time. Often it's so fast that it doesn't matter at all that it can be 1/100 slower then C. 0.1 sec is still good even if it's not 0.001 secs.
  - dom0 9y ago
    Python performance is uh ah... difficult. I work on a piece of software that has a lot of hot paths in Python code, and it's not nice. Combined with deployment and tooling issues it made me wonder quite a few times now, whether the a little bit lower contribution barrier is worth all these hassles.
    - aeroevan 9y ago
      Cython is a very nice way to transition hot python paths into a C extension. The best part is that it's a python superset, so it should provide some speed up without any typing information (and can be very fast once the hot paths are all in cdef'd functions).
      - nickpsecurity 9y ago
        Beat me to it. Cython was a great solution to this problem.
      - dom0 9y ago
        https://news.ycombinator.com/item?id=14376961 https://news.ycombinator.com/item?id=14376961 Further, it doesn't help with the required restructuring; when the functionality is scattered across a dozen or more modules (complex software + good Python practice), then you first have to pull the functionality needed for the path you're trying to get fast together. That leads to duplication, removing abstractions and most certainly vetoes from other people.
wolfgke 9y ago
> It should be quite easy to see the value of optimizing compilers. Compile your program with optimizations turned off. Now make it as fast as your release build again, while still keeping them off. For much of my code, I think this would take years. The problem is that, say, C does not allow to express the necessary details about the optimizations that you want to do. This is exactly something DJB calls for in programming languages.

zurn 9y ago

TL;DR "Optimizing compilers are still good to have because they are cheaper than programmer labour needed for hand optimization" The original DJB presentation, which this is a response to, is very good and interesting. It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout and data types/representations based on partial evaluation / profile feedback.

sanxiyn 9y ago
> It would really be nice if the field of compiler engineering started to address the obvious neglected areas, like optimizing memory layout Interesting tidbit: LLVM was developed by Chris Lattner for his PhD thesis. It was titled "Macroscopic Data Structure Analysis and Optimization" and about "Instead of analyzing individual load/store operations or structure definitions, this approach identifies, analyzes, and transforms entire memory structures as a unit", in his own words. Apparently, the world was more interested in a good compiler framework than specific memory layout optimization proposed. http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html
DannyBee 9y ago
" like optimizing memory layout and data types/representations based on partial evaluation / profile feedback." They already can. The issue is usually one of what is allowable within language semantics, not of compiler optimization technology. One reason you may see this as neglected is that outside of, say, polyhedral loop optimizations, research in the 80's and 90's (and sometimes earlier) did a really really good job of exploring this area because fortran allowed so much freedom.
- zurn 9y ago
  Compilers and languages of course co-evolve. And we already have fairly widespread production use of invasive language extensions/dialects designed to enable use of parallelism, such as OpenMP and CUDA. And older language extensions that have ove time become everyday stuff, like SIMD intrinsics. So I don't think "languages don't support it" is a good excuse.

nullc 9y ago

I'm disappointed at the lack of figures.

lukego 9y ago

I often think about Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years. Sure, optimizing compilers are nice to have, but maybe their complexity is disproportionate to their benefit? I love the way Dynamo [1] is able to reproduce many of the benefits with a fraction of the complexity by doing some of the optimizations at runtime with simpler algorithms. Can we use this approach to "garbage collect" some of the complexity embodied in humongous projects like LLVM? [1] Dynamo: https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/bala00dynamo.pdf https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall20...

xoroshiro 9y ago
Got a bit confused here. I was thinking about a very old software I used in college for my systems dynamics class. Completely different (unless I am mistaken), but still brings back painful memories of that class. https://en.wikipedia.org/wiki/DYNAMO_(programming_language) https://en.wikipedia.org/wiki/DYNAMO_(programming_language)
Joky 9y ago
You're mentioning "disproportionate complexity" for current compilers and at the same time advocating for a runtime system modifying and caching the code on the fly? Ouch... Note also that I don't believe that Dynamo "reproduce many of the benefits [...]", since the paper you linked benchmarked running Dynamo on top of the O2 generated code (by a ~20y old compiler). It isn't clear if they ripped "low-hanging fruit" that static compilers are catching nowadays. Also the same thing on top of a PGO+LTO build may be a more fair comparison.
- lukego 9y ago
  The exciting possibility, from my perspective, is that many optimizations may be simpler to implement dynamically (JIT) than statically. So perhaps you can have 10% of the compiler code to get 90% of the benefit. I see this as the basic premise of LuaJIT. Motivating example: The CPU can predict whether branch instructions will be taken with uncanny accuracy. This is achieved using simple dynamic heuristics. I believe it would be much more challenging for the compiler to predict these branches statically.

jcranmer 9y ago

Several years ago, I happened on a blog post where someone demonstrated a very fast variant of the N-queens solution based on hand-written, SSE vectorized that was presented as very fast. I managed to write a faster, non-vectorized C solution that was recursive and that the compiler couldn't vectorize, and much easier to understand than the vectorized original it was based off of. Turns out that main reason the vaunted "overkilled" solution was so abysmally slow was that the author happily used BSF and BTC in the hottest part of the loop... which are actually rather slow instructions, particularly when you're using them to control a branch (compare-and-jump is a fused µop in practice, but BTC-and-jump is not). The point of this tail is that if you want to absolutely wring the last clock cycle out of a hot path, you usually need good microarchitectural knowledge about which operations are going to be faster and which are not. Sure, you can beat a compiler with hand-written, hand-optimized assembly code most of the time--but the people who have the skills to write such code are going to be the people working on the compilers. The tools for optimizing compilers are getting better, and probably faster than we are capable of pumping out performance engineers to hand-craft the inner loops. In the past decade, we've seen polyhedral loop transformations become production-quality. Auto-vectorization is getting better, particularly when user-directed (think #pragma openmp simd); I know Intel has been pushing "outer-loop vectorization" very hard in the past few years. The other big fruit on the horizon is superoptimizers: I suspect we'll see superoptimizers shipping in production compilers within a decade or two.

innocenat 9y ago
I think it depends a lot. I have work on some hand-crafted SIMD for multimedia use before. It is fairly easy to outperform the auto-vectorization in that field IMO. I have also played around with various attempts to hand-craft inner loop (SIMD and no SIMD) for other project but most of the time I failed to outperform the compiler.
- w0utert 9y ago
  Yes, it depends a lot. Typical signal-processing tasks you will definitely want to hand-optimize, no matter how good the compiler is, it will never be able to get close to hand-crafted SIMD code in combination with careful memory-layout, reducing the working set, eliminating dependencies, maximizing cache usage etc. There's a lot involved with that kind of optimizations that supposes semantic knowledge of the data going through the algorithm to be able to make transformations to optimize the code. For the other 99% of code it's hard (and definitely not worthwhile to try) to beat the compiler though. I sometimes watch programming streams where people go very deep into the compiler-generated code to analyze runtime behavior of their code, and it's almost scary to see the kinds of things compilers can do these days.

fizixer 9y ago

Great talk by DJB. IMO he couldn't give a convincing answer to the guy who asked about LuaJIT author being out of a job. But there's a clear answer. JIT authors are not out of job not because optimizing compilers are not dead, but because they're writing compilers, their distinguishing ability is writing "pre-compiled" code. You might say, "well a JIT author sped up your code's execution so he/she is writing an optimizing compiler". Well you have to realize that, traditionally, JIT authors don't just translate the code into object code, they also apply these things called "compiler optimizations". The point is that if they didn't do that, and simply produced a faithful translation of the code, they would still make the code faster because of pre-compilation (and if they enabled the "compiler optimizations", the code wouldn't run significantly faster than the simply pre-compiled code). Regardless of whether I agree with it or not, "Optimizing compilers are dead" is not the same as saying "JIT authors will be out of business". (Even compiler writers won't be out of business).

samth 9y ago
I was that guy in the audience. Your suggestion is that a templating JIT that just drops in some machine code that matches the method, doing no optimization, would get all the win. Such a compiler is indeed much faster than an interpreter, but it's nowhere close to an optimizing compiler. Mike Pall, the author of LuaJIT, would be very surprised if you suggested that his compiler performed similarly to something simple like that.
- mikemike 9y ago
  Actually, LuaJIT 1.x is just that: a translator from a register-based bytecode to machine code using templates (small assembler snippets) with fixed register assignment. There's only a little bit more magic to that, like template variants depending on the inferred type etc. You can compare the performance of LuaJIT 1.x and 2.0 yourself on the benchmark page (for x86). The LuaJIT 1.x JIT-compiled code is only slightly faster than the heavily tuned LuaJIT 2.x VM plus the 2.x interpreter written in assembly language by hand. Sometimes the 2.x interpreter even beats the 1.x compiler. A lot of this is due to the better design of the 2.x VM (object layout, stack layout, calling conventions, builtins etc.). But from the perspective of the CPU, a heavily optimized interpreter does not look that different from simplistic, template-generated code. The interpreter dispatch overhead can be moved to independent dependency-chains by the CPU, if you're doing this right. Of course, the LuaJIT 2.x JIT compiler handily beats both the 2.x interpreter and the 1.x compiler.

fovc 9y ago

In the linked slides, DJB talks about a language for communication with the compiler, separating optimizations from specification. This reminded me of VPRI's "Meaning separated from optimization" [1] principle. Does anyone know what became of that line of thinking? Is this idea making it's way into Ohm? I remember reading a post/paper about optimizing Nile/Gezira to better exploit the CPU cache (and the struggle to use SIMD), but can't seem to find it now. [1] http://www.vpri.org/pdf/rn2006002_nsfprop.pdf http://www.vpri.org/pdf/rn2006002_nsfprop.pdf

nickpsecurity 9y ago
IBM's old PL/S language allowed you to give hints like where data would go or what checks would happen right in the function declaration. The compiler would handle it from there.

lmm 9y ago

> If an optimizing compiler can speed up code by, for example, 50%, then suddenly we need to optimize a lot less code by hand. This doesn't follow at all. If you had one hot loop and a bunch of cold code, and auto-optimize your code to be a measly factor of 2 faster, you're still going to need to hand-optimize the hot loop and what it does to the cold code is irrelevant. > hand-optimized code has higher ongoing maintenance costs than does portable source code; we’d like to avoid it when there’s a better way to meet our performance goals. True, but again, only applies if you can optimize by enough to make hand-optimization unnecessary. > we’d also have to throw away many of those 16 GB phones that are cheap and plentiful and fairly useful today. This part is nonsense. No-one's got anything like 16GB of code on their phone. Optimization could be valuable but current compilers are too opaque, making optimization too much of a black art. I believe we need to do something along the lines of "turning the database inside out" ( https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/ https://www.confluent.io/blog/turning-the-database-inside-ou... ); we should turn the compiler inside out, build it as more of a library, give the developer more insight into what's going on, have a high level language that lets you understand how it compiles. Interesting and vaguely along the same lines: https://www.microsoft.com/en-us/research/publication/coq-worlds-best-macro-assembler/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fnick%2Fcoqasm.pdf https://www.microsoft.com/en-us/research/publication/coq-wor... .

tom_mellior 9y ago
> auto-optimize your code to be a measly factor of 2 faster, you're still going to need to hand-optimize the hot loop Huh? You start with performance goals. If compiler-optimized code meets your performance goals, you are done. You do not "need to hand-optimize" in that case. Why would a "factor of 2" not be good enough? What is it compared to? What makes you so sure that you must optimize further, disregarding any possible context?
- w0utert 9y ago
  Additionally, if a factor 2 improvement by the compiler on top of a factor 4 improvement by using better algorithms and data structures can give you an 8x improvement overall, why would you not take it? Reading through the various comments asserting that optimizing compilers should not be necessary if you 'just use better algorithms' and whatnot, I'm kind of wondering why it has to be one thing or the another. Who wouldn't want to have both?

jerrre 9y ago

> Compiler optimization reduces code size Nope, much is gained by unrolling loops, inlining functions etc, which all increase code size. Of course C++ compilation with no optimization at all can be rather wasteful with performance and code size, but to squeeze the final performance out you probably need to sacrifice code size (whether manual or automatic)

aidenn0 9y ago
> Nope, much is gained by unrolling loops, inlining functions etc, which all increase code size. That's because those are performance optimizations, not size optimizations (though as an aside, inlining functions can reduce code size in the event that the inlined version is smaller than the function-call overhead, or in the case where the function is used only once). There are plenty of size optimizations that can be performed. -Os will enable them on gcc/clang if you want to try for yourself.

faragon 9y ago

Is there any compiler using "machine learning" for SIMD optimization?

Verdex_2 9y ago
I'm not sure, but I remember seeing some research into using it for Haskell stream fusion (can't find the video, sorry). I believe that the basic idea was that not all rewrites end up being equally fast ( a * b * c can be fused into ab * c, but maybe a * bc is faster). Trying all the combinations is an option in theory, but you get a combinatorial explosion so you normally dont get far in practice. Enter machine learning. I'm not sure how successful they were, but I imagine that the same sort of thing could be applied to SIMD.

CJefferson 9y ago

Having used some language with awful compilers, compiler optimisations let me write cleaner code. In languages with bad optimisers I have to worry about separating code in a hot loop out into a function -- the cost of a function call is too high. This one in particular I find can lead to some horrible code, as functions grow larger and larger and lots of cutting+pasting happens to avoid function call costs. On a smaller note, making sure I cache the values of function calls which won't change -- when instead I could trust the compiler to know the value won't change and the the caching itself.

gruez 9y ago
There isnt some forcelinline attribute in gcc?
- Paul_S 9y ago
  Yeah, #define.
- JoachimSchipper 9y ago
  Your parent is probably not talking about gcc, or even about C; gcc does indeed have __attribute__((always_inline)).
- CJefferson 9y ago
  There is, but in practice just normal inline, or even trusting the compiler to decide what to inline itself, are just fine. The problem comes when you are using other languages (scripting ones like Python come to mind) where inlining is but a dream (ignoring systems like PyPy).

mrkgnao 9y ago

I'm posting this as a top-level comment, but it's really a reply to the discussion downthread about compilers being able to work magic if we let them. Better still, why not help them? Something I took for granted for the longest time about Haskell (which remains the only language I know of with the feature) is the ability to write user-defined "rewrite rules". You can say, "okay, GHC, I know for a fact that if I use these functions in such-and-such way, you can replace it by this instead". {-# RULES foo x (bar x) = superOptimizedFooBar x #-} A rule like this would be based on the programmer's knowledge of FooBar theory, which tells her that such an equality holds. The compiler hasn't studied lax monoidal FooBaroids and cannot be expected to infer this on its own. :) Now, anywhere a user of this code writes something like foo [1,2,3] (bar [1,2,3]) the compiler will substitute superOptimizedFooBar [1,2,3] in its place. This is a nice way to bring the compiler "closer" to the programmer, and allow the library author to integrate domain-specific knowledge into the compiler's optimizations. You can also "specialize" by using faster implementations in certain cases. For example, timesFour :: Num a => a -> a timesFour = a + a + a + a timesFourInt :: Int -> Int timesFourInt x = rightShift x 2 {-# RULES timesFour :: Int -> Int = timesFourInt #-} If you call timesFour on a double, it will use addition (ha!) but using it on an Int uses bitshifting instead because this rule fires. High-performance Haskell libraries like vector, bytestring, text, pipes, or conduit capitalize on this feature, among other techniques. When compiling code written using libraries like this, this is how it goes: - rule #1 fires somewhere - it rewrites the code into something that matches rule #2, "clearing the way" for it to fire - rule #2 fires - rule #3 fires - rule #1 fires again - rule #4 fires and so on, triggering a "cascade" of optimizations. The promise of Haskell is that we already have a "sufficiently smart compiler": today, with good libraries, GHC is capable of turning clear, high-level, reusable functional code with chains of function compositions and folds and so on into tight, fast loops. -- I must add, though, that getting rewrite rules to fire in cascades to get "mad gainz" requires one to grok how the GHC inliner/specializer works. http://mpickering.github.io/posts/2017-03-20-inlining-and-specialisation.html http://mpickering.github.io/posts/2017-03-20-inlining-and-sp... Data.Vector also utilizes an internal representation that makes fusion explicit and hence predictable (inevitable, even) called a "bundle": https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Data-Vector-Fusion-Bundle.html https://www.stackage.org/haddock/lts-8.16/vector-0.11.0.0/Da... but this relies on rewrite rules too, e.g. the previous module contains this rule: {-# RULES "zipWithM xs xs [Vector.Stream]" forall f xs. zipWithM f xs xs = mapM (\x -> f x x) xs #-}

scraft 9y ago

Is anyone else in games development here? If we are looking to run the game at 60 FPS, we have 16.67 ms per frame to do everything required to run the game. Because of this real time requirement, a decent amount of profiling is typically done on each game. I typically see that the frame time is getting split up over a whole array of different sections of the game, i.e.: - Calculating skeleton animations (updating bone positions, sometimes skinning vertices too) - Clipping geometry in the scene (finding out what things are inside/outside the camera frustum, etc.) - Processing game logic, things like AI can be quite costly, so much is game dependent - Walking through all the geometry that needs drawing and issueing draw calls - Decompressing streaming audio and sending it to a sound driver buffer/queue - Stepping the physics world (integrating positions/rotation working and resolving out intersections, etc.) The difference between a non optimized, and an optimized build, is often 5 FPS and 60 FPS, and optimizing a single hot file or function would not get the game running anywhere near 60 FPS. I think the idea that optimizing compilers aren't required is completely laughable, but then again I only have one perspective from the games development scene - maybe someone else will reply and say they make AAA games in C/C++ and don't need compiler optimizations :)

AstralStorm 9y ago
Those gains are often caused by globally applied optimizations like inlining and devirtualization. These then can enable actual stream processing and loop chunking optimizations which are of important but lesser effect. Perhaps dead code and constant elimination of you leave in flags. In other words, if you rewrite the algorithms from object oriented into stream processing, you would get most of the gains. This is caused by all CPU, FPU and GPUs actually internally being simple numerical stream machines.
zurn 9y ago
A bit of trivia: Computation is frequently pipelined so that part of the work is done during previous frame(s). This of course means that the game logic latency is longer than 1 frametime.
mwkaufma 9y ago
AAA dev here. The performance gains mostly come from designing data, not code. Factoring an array of structures into a structure of arrays and accessing linearly, e.g., makes better use of the processor cache and saturates throughput. Code optimization mostly gives us the confidence that there aren't unnecessary accesses or branches interleaved that might bust the cache.