8 ms·

This brings up a thought that I've had for a very long time. Almost every type of optimization that a programmer could employ is repeatable. It involves matchin

This brings up a thought that I've had for a very long time. Almost every type of optimization that a programmer could employ is repeatable. It involves matching patterns ("Identification" in the context of this article), analysis ("Comprehension"), and rewriting ("Iteration"). All of these steps can be efficiently automated. And it turns out that compiler writers collectively know about the vast majority of these techniques, but refuse to implement most of them for what I would consider to be the ultimate copout ever: Compile times. I don't know about you, but I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'm not sure who wouldn't, especially if it also allows you to eliminate technical debt, eliminate leaky abstractions, and improve code comprehensibility. Perhaps I'm being overly idealistic, but I can't help but hope for a day that I can work with a high level language and have the compiler take care of optimizations that range from removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2. And if I have to wait all day long for a release build of something, so be it.

shepardrtc 11y ago
There was a HN thread a day or two ago in which someone suggested the idea of a common, open source KV database where compiler optimizations could be stored and curated by a committee. So whenever a compiler recognizes a pattern, it could quickly look up the latest and greatest optimization.
forrestthewoods 11y ago
There is such a thing as profile guided optimization. I don't think their results are particularly impressive. You're basically saying "can't you just" to which the answer is almost always no. No you can't just.
- saosebastiao 11y ago
  I've gotten pretty good results from PGO as well as JIT optimizations (which isn't conceptually much different), but even if I hadn't, your comment is still a fallacy on two accounts: 1) JITs were slow until they weren't. Poor results from existing experimental PGO compilers do not prove that the concept is flawed. 2) Profiling is a heuristic substitute for a real cost model. The most advanced optimizing compilers forego profiling altogether because they evaluate optimizations against a hardware/architecture cost model. In other words, PGO isn't even necessary to accomplish what I'm talking about. And yes, yes you can. https://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
  - jerf 11y ago
    And in theory, dependent types are the awesomest thing ever. But they're not ready yet, and there's no guarantee they ever will be. There's a gulf between even having a few focused, carefully-chosen proofs of concept and a practically-useful technology. (For that matter, I just grabbed that example off the top of my head as the thing I knew that most resembled the various fancy optimizers I've seen over the years, but it seems to me that dependent typing are full of things that would be darned useful for an optimizer. It would be funny if the fastest path towards whole-program optimization went through dependent types being practical.)
    - saosebastiao 11y ago
      I think dependent types are amazing, but even the tiny subset of dependent types known as refinement types opens up huge avenues for optimization. Some optimizations (loop nest optimizations for a simple example) might only be feasible with static range definitions or with profile guided optimization...but if you throw in refinement types, you now have static guarantees as to the cardinality or range of a variable, and loop nest optimizations can be statically determined. I think full dependent typing could be great, but compilers can still be improved with small language improvements.
    - tel 11y ago
      They're ready in small forms in Haskell today. The compiler doesn't take a whole lot of advantage of these yet, but you start to see avenues toward it.
    - johncolanduoni 11y ago
      > And in theory, dependent types are the awesomest thing ever. But they're not ready yet, and there's no guarantee they ever will be. I think the reason dependent types haven't made it into practical programming has less to do with them being not ready and more to do with them being fundamentally challenging to learn. I have a pretty strong pure math background and it still took me a significant amount of time to wrap my head around them to the point that I could write non-trivial proofs using them, let alone programs. For programmers who have never done much formal logic or who have never heard of a category, I can't imagine how much time it would take to get the prerequisite knowledge. Another issue is the fundamental problem of creating a new language; you have to build up a ton of extra machinery (libraries, tooling, etc.) to even think about it becoming more than a toy, even if you don't care about it being mainstream. Rust has the backing of a large open-source company and a ton of really smart people dedicated to bringing it to primetime, but it is still going to take a long time for it to get there. Dependently typed languages like F* and Idris don't have the same manpower behind them and also have to face fundamental challenges like integrating formally verified code with a world full of unverified (but useful) code.
- oso2k 11y ago
  It's not that results are unimpressive, but the market has dictated faster compile times. When a PGO compilation is an order of magnitude slower, for the 90% of applications out there where the extra 5-25% improvement means less than a 60 sec improvement, then you won't care about PGO. You need to have an application an order of magnitude larger (in run time) to care about PGO. Smaller than Google, bigger than your startup. See xkcd [0][1] for when to care. [0] https://xkcd.com/1205/ https://xkcd.com/1205/ [1] https://xkcd.com/1445/ https://xkcd.com/1445/
  - forrestthewoods 11y ago
    For video games you usually have at least Debug, Release, Retail builds. Where Retail turns on Link Time Code Generation (LTCG) which is quite slow but can give a few percent extra perf. If PGO took 10x to compile but gave a 20% perf boost it'd be an absolute no brainer for game development. Keeping in mind that article shared here was a video game. It's possible that PGO is pretty awesome these days and people just don't realize it. Just because I've heard unimpressive results from other devs doesn't mean it's actually bad!
    - gambiting 11y ago
      I work on a major AAA title due to be released in a few months - our compile times are 20-25 minutes for Windows build(Debug/Release/Final), 10-15 minutes for Xbox One/PS4(consoles link much faster), and for Retail builds, with link time optimization, the build takes anywhere between an hour, hour and a half. That's on a machine with a 6-core, 12 threaded intel Xeon(we use distributed build anyway), 64GB of ram and the source code sitting on a 1TB SSD. The baking of data takes another 10-30 minutes depending on config. Anything that improves our workflow is very,very,very welcome.
      - oso2k 11y ago
        Thank you for proving my point gambiting. @forrestthewoods, asset baking is already 50-200% of the gambiting's non-Retail workflow build time. This is before PGO. Ask him, if had to choose between reducing his build time 10% (without a game performance penalty), or, increasing his build time 1000% (with a game performance improvement of 15%), I think he'll quickly choose the first option. Debug time/feedback is much more valuable (usually) [0]. [0] http://prog21.dadgum.com/47.html http://prog21.dadgum.com/47.html
tormeh 11y ago
We should have -O4 meaning "however long it takes" or something.
- joosters 11y ago
  We already do. That's what high optimisation levels mean.
- Jweb_Guru 11y ago
  You're assuming that the hard part is finding optimizable patterns and transforming them, and not deciding whether applying the transformation will actually be an optimization.
  - bmh100 11y ago
    In regards to superoptimization, that actually is the case. See this blog post about the use of Souper in LLVM [1]. [1]: http://blog.regehr.org/archives/1146 http://blog.regehr.org/archives/1146
    - Jweb_Guru 11y ago
      That blog post (which I've read) doesn't provide any evidence for that (or even talk about it), and only discusses a small subset of optimizations.
JoachimSchipper 11y ago
> All of these steps can be efficiently automated. Good luck with that. Yes, a compiler will do a good job with i * 28, but the optimization in the article - which is a pretty simple case, chosen to fit in a blog post - requires manipulating the algorithm beyond the capability of any compiler I'm aware of. We do have good tooling to show what code is slow, for instance, so it's not like automation doesn't help here.
- spawndog 11y ago
  Indeed. Often the slowest code for us is due to cache friendliness more than algorithmic complexity. For the data to be laid out correctly the problem needs to be solved way earlier in your toolchain as well as downstream with a rewrite of any algorithm that touches it
AngrySkillzz 11y ago
There is a Scheme compiler called Stalin[1] which apparently does some very sophisticated full-program and lifetime analysis. This of course leads to very long compile times, but the code is also very fast compared to other Schemes, and even C in some cases, from the benchmarks I've seen[2][3] etc. You can find more benchmarks for it, and similar compilers like MLton. Of course, I can't comment on whether or not it is actually usable in a real-world environment, just that the techniques do exist. [1] https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementation%29 https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementatio... [2] https://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... [3] http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
- fanf2 11y ago
  A more recent example of a whole-program functional programming language compiler is Haskell's jhc http://repetae.net/computer/jhc/ http://repetae.net/computer/jhc/
oso2k 11y ago
Many compilers will iterate the so called classical optimizations until they produce no effect (an iteration where no optimization took place) or some artificial limit (say 4 or 8 iterations through a basic block or a function). At some point, you risk several accidental de-optimizations such as inducing cache thrashing, cache spilling, architectural limitation, or, even optimization clashing where one optimization de-optimizes a previous optimization on one iteration that then gets re-optimized in the following iteration (A->Opt B->"De-"Opt A->Opt B->...). Another poster suggested profile directed optimization and that usually is even more effective naively iterating through optimization steps.
evincarofautumn 11y ago
Insulation from performance concerns also makes your performance model less predictable. Because the ends of optimisations are observable, but their means are not, people resort to “butterfly programming”. As a small example, in ActionScript 3, people used to write their conditionals like this: if (a) if (b) { ... } Rather than this: if (a && b) { ... } Because the dumb compiler generated better code for the former. In the real world, I’ve seen seemingly benign code changes prevent optimisations from firing—optimisations we didn’t know we were relying on. So people start coding to the implementation, rather than the language or the human, without even being able to see what they’re doing. I really don’t like that. Optimisers are like garbage collectors—they give you better ergonomics than, and equal average performance to the manual alternative, if you’re willing to relinquish predictability and a non-voodoo mental model of your code’s performance.
- mikeash 11y ago
  I wonder if it would be practical to expose the optimizations to the programmer and allow the complex ones that are easy to accidentally disable to be invoked explicitly. Your code would look something like: optimization(fold_constant_vector_lookup_access_frobnitz) { complex code here } And if the compiler can't apply the optimization, it can produce an error rather than slow code.
  - evincarofautumn 11y ago
    That works. We already have some things like that, like “__attribute__((always_inline))”. Of course, forcing some optimisations could implicitly prevent others, but that’d also be true if you did it manually. With expressive enough metaprogramming, you could also do some of these explicit optimisations in user code.
- johncolanduoni 11y ago
  > Optimisers are like garbage collectors—they give you better ergonomics than, and equal average performance to the manual alternative, if you’re willing to relinquish predictability and a non-voodoo mental model of your code’s performance. This is why I'd like to see optimizers become less opaque. It would be great if we could not only suggest optimizations to the compiler (and more sophisticated ones that just inlining), but actually see the process which our code went through. One language that has some interesting things going on in this area is Nim, which lets you write your own domain-specific optimizations[1]. [1]: http://hookrace.net/blog/what-is-special-about-nim/#add-your-own-optimizations-to-the-compiler http://hookrace.net/blog/what-is-special-about-nim/#add-your...
legulere 11y ago
The analysis part mostly is about legality of the transformation. Humans have a larger view of the program and change code to behave slightly different but way faster. A compiler can't change the behavior of the program.
z3t4 11y ago
I love that v8 (nodejs /chromium, JavaScript) does JIT compiler optimizations. It means I can build for maintainability and still get the same performance as if I had built for speed. Ex: array vs object literal, or array vs object properties. I still do higher level optimizations though, like caching and tweaking formulas (less computations), when needed.
Splines 11y ago
Maybe for some cases, but sometimes (IMO) a compiler is just not going to know. For example, if instead of hitting the network on initialization for some information we delay load that later (say, for example, the MOTD), a compiler is never going to know it could do that.
astrange 11y ago
If you don't regularly run your program with the same optimizations you're using on the final product, you haven't tested it. And if your automatic optimizations are so slow that you can't just re-run them all the time, you can't tune what you're sending into them in the first place. That's for classic compilation, but these days all the good stuff is in JIT on a mobile device, and there your optimizer really can't afford to waste your time.
- comex 11y ago
  It is? iOS has always used ahead-of-time compilation and Android switched semi-recently from the JIT-based Dalvik to the AOT Android Runtime. The only important JIT left is in the browser...
  - astrange 11y ago
    Right, but browsers are pretty important, and a lot of apps are just web views. (Can't remember if JIT works in web apps on iOS these days though.) They also load all that crazy ad tracking javascript from everywhere, optimizing that on every page load has power costs!
joosters 11y ago
Please show us some of these promised optimizations. I don't think they actually exist. Most of the larger code / algorithm tweaks require subtle changes to the behaviour. The compiler can't choose to do that by itself, as it could break the program. Programmers need to make these choices for themselves. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize compile time if they wish. There are plenty of people who would give anything for faster code, no matter what the compile time is. Please prove me wrong and explain a few of these supposed too-slow optimizations.
- johncolanduoni 11y ago
  Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which are made strict at a later time. Each call creates a new sequence, and many take closures. Both of these require memory allocation and indirect dispatch. However, in many cases it extremely straightforward to convert these into loops. For example, the following C# code: list.Select(f).Where(p).SelectMany(g).ToList() Could be turned into: var outList = new List<T>(); foreach(var x in list) { var y = f(x); if(!p(y)) continue; foreach(var z in g(y)) { outList.Add(z) } } This works, even if we known nothing about f, p, and g (e.g. they can be impure functions). This optimization is especially effective if these functions are lambdas. It is also always going to be faster and safe; the only difference is that we removed a series of extra allocations and indirect function calls. This example is admittedly simple, but many functional patterns and behaviors can be rewritten into longer imperative variants that avoid extra allocations. You are right that you can have subtle changes in behavior with similar high level optimizations. For example, most functional languages make calls like these actually create a new collection at each call. If any of these functions can throw and exception or cause an effect, then we cannot perform the above rewriting because if will call the functions out of order. But if a compiler can take the time to analyze functions for external purity, these can be optimized as well.
andrepd 11y ago
>Perhaps I'm being overly idealistic, but I can't help but hope for a day that I can work with a high level language and have the compiler take care of optimizations I believe optimizing compilers are already a thing. Am I missing something here?
- jstelly 11y ago
  Currently for game development optimizing compilers are useful but hardly free you from worrying about optimizations. At least when you are using C++: a) Optimizing compilers can't organize your data to be cache friendly. b) optimizing compilers can't re-organize your code to prefer sequential access to that data so the HW prefetch can prevent cache misses c) optimizing compilers can't separate out the parallelizable parts of an algorithm and push those into threaded jobs d) optimizing compilers can't find most cases of work you are doing that doesn't need to be done. They find some trivial/local cases of this but not any of the deep or difficult cases. e) compilers can't rewrite your code or data to not need features or to use simpler features that can be optimized f) compilers can't generate caches (as in the simple example in the article) and find and handle all of the cases where they need to be updated. If you are working on an application where performance is one of the most important features (like many games) you will find yourself working on performance problems like these often. In even higher level languages compilers have more flexibility around some of the fundamental constraints in the C++ world, but there are still few cases where those compilers produce faster code than humans do with C++. Of course the optimized C++ usually requires vastly more effort and returns to that effort are diminishing over time with faster hardware.
  - vitalyd 11y ago
    Optimizers are mostly about stripping away abstraction costs of the language. If anyone is asking for more, they're disillusioned :).
    - roel_v 11y ago
      That's very generous of you, but I think that "delusional" isn't an exaggeration in this case...
siegecraft 11y ago
There was an interesting paper linked on here about automatic optimization of Photostop filters via machine learning. I think the novel part was that it operated on binary code, not source. Can't find the link at the moment, but searching for it yielded a bunch of similar papers about machine learning-aided optimization.
- roel_v 11y ago
  That was highly specific for the type of operation they were looking at. Still spiffy, but not something that can be folded into a general-purpose compiler.
- fanf2 11y ago
  Dynamic optimization of binary code is 25 years old or more. The first widely deployed JITs were for running binary executables on different architectures, such as the Mac 68k -> PowerPC transition. https://en.wikipedia.org/wiki/Binary_translation#Dynamic_binary_translation https://en.wikipedia.org/wiki/Binary_translation#Dynamic_bin...
RiotTony 11y ago
I think that the Identification and iteration stages can be automated, but the comprehension stage is still a while off. No compiler is going to understand more about the what the context of the program is than a human. For example, knowing that a particle system is transparent enough (or somehow insignificant enough) that it doesn't need to be rendered in the shadow pass is a difficult thing to automatically optimise for. Compilers are generic beasts, they need to work accurately for all valid combinations of code and data (which is a complex problem in itself) and optimisation is another layer of complexity on top of that. Current compiler optimisations work on predominantly local data and code, as that is all the state that the compiler can guarantee is accurate. If a function called from a parent is optimised for that parent, then it is conceivable that this same optimisation could be suboptimal when called from another parent (especially if the compiler was able to modify data layout). The other issue is iteration time. This is a crucial part of software development - lowering iteration time boosts productivity immensely. If, as a programmer, you no longer care about performance due to a compiler that can optimise your code to make it run twice as fast but the compile time is hours, you are rarely going to run the optimised build. And you are going to end up hand optimising the debug/test builds yourself to make them run fast enough. I do think that we could have better tools to help us understand where our code bottlenecks could be - I would love a plugin that somehow coloured my code's variables by cache locality.
WalterBright 11y ago
> I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'd implement that if I knew about such optimization technology, and I bet other compiler guys would, too.
zamalek 11y ago
> I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. If you're referring to super-optimization, it can take far more than 100x and isn't something that is being "classically automated" as humans likely can't do it in the first place. In addition, super-optimization will yield better results if you give it a better starting point. It's nothing at all like the optimization discussed in the blog post. Either way, it can be done against LLVM IR[4] and I'm sure it will creep into clang at some point. So far as using profiling data to optimize code in the way that humans would: MSVC supports it[1], clang supports it[2] and gcc supports it[3]. Supposedly Microsoft saw a 30% performance increase [with a very specific workload] when they tried POGO on an internal build of SQL Server. Under normal circumstances, PGO should net you around 7% free perf. [1]: https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx [2]: http://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization http://clang.llvm.org/docs/UsersManual.html#profile-guided-o... [3]: http://dom.as/2009/07/27/profile-guided-optimization-with-gcc/ http://dom.as/2009/07/27/profile-guided-optimization-with-gc... [4]: https://github.com/google/souper https://github.com/google/souper
dom96 11y ago
How about a language which allows you to define your own optimisations in source code? This reminds me of Nim's term rewriting macros which let you do precisely that: http://nim-lang.org/docs/manual.html#term-rewriting-macros http://nim-lang.org/docs/manual.html#term-rewriting-macros

shepardrtc 11y ago

There was a HN thread a day or two ago in which someone suggested the idea of a common, open source KV database where compiler optimizations could be stored and curated by a committee. So whenever a compiler recognizes a pattern, it could quickly look up the latest and greatest optimization.

forrestthewoods 11y ago

There is such a thing as profile guided optimization. I don't think their results are particularly impressive. You're basically saying "can't you just" to which the answer is almost always no. No you can't just.

saosebastiao 11y ago
I've gotten pretty good results from PGO as well as JIT optimizations (which isn't conceptually much different), but even if I hadn't, your comment is still a fallacy on two accounts: 1) JITs were slow until they weren't. Poor results from existing experimental PGO compilers do not prove that the concept is flawed. 2) Profiling is a heuristic substitute for a real cost model. The most advanced optimizing compilers forego profiling altogether because they evaluate optimizations against a hardware/architecture cost model. In other words, PGO isn't even necessary to accomplish what I'm talking about. And yes, yes you can. https://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
- jerf 11y ago
  And in theory, dependent types are the awesomest thing ever. But they're not ready yet, and there's no guarantee they ever will be. There's a gulf between even having a few focused, carefully-chosen proofs of concept and a practically-useful technology. (For that matter, I just grabbed that example off the top of my head as the thing I knew that most resembled the various fancy optimizers I've seen over the years, but it seems to me that dependent typing are full of things that would be darned useful for an optimizer. It would be funny if the fastest path towards whole-program optimization went through dependent types being practical.)
  - saosebastiao 11y ago
    I think dependent types are amazing, but even the tiny subset of dependent types known as refinement types opens up huge avenues for optimization. Some optimizations (loop nest optimizations for a simple example) might only be feasible with static range definitions or with profile guided optimization...but if you throw in refinement types, you now have static guarantees as to the cardinality or range of a variable, and loop nest optimizations can be statically determined. I think full dependent typing could be great, but compilers can still be improved with small language improvements.
  - tel 11y ago
    They're ready in small forms in Haskell today. The compiler doesn't take a whole lot of advantage of these yet, but you start to see avenues toward it.
  - johncolanduoni 11y ago
    > And in theory, dependent types are the awesomest thing ever. But they're not ready yet, and there's no guarantee they ever will be. I think the reason dependent types haven't made it into practical programming has less to do with them being not ready and more to do with them being fundamentally challenging to learn. I have a pretty strong pure math background and it still took me a significant amount of time to wrap my head around them to the point that I could write non-trivial proofs using them, let alone programs. For programmers who have never done much formal logic or who have never heard of a category, I can't imagine how much time it would take to get the prerequisite knowledge. Another issue is the fundamental problem of creating a new language; you have to build up a ton of extra machinery (libraries, tooling, etc.) to even think about it becoming more than a toy, even if you don't care about it being mainstream. Rust has the backing of a large open-source company and a ton of really smart people dedicated to bringing it to primetime, but it is still going to take a long time for it to get there. Dependently typed languages like F* and Idris don't have the same manpower behind them and also have to face fundamental challenges like integrating formally verified code with a world full of unverified (but useful) code.
oso2k 11y ago
It's not that results are unimpressive, but the market has dictated faster compile times. When a PGO compilation is an order of magnitude slower, for the 90% of applications out there where the extra 5-25% improvement means less than a 60 sec improvement, then you won't care about PGO. You need to have an application an order of magnitude larger (in run time) to care about PGO. Smaller than Google, bigger than your startup. See xkcd [0][1] for when to care. [0] https://xkcd.com/1205/ https://xkcd.com/1205/ [1] https://xkcd.com/1445/ https://xkcd.com/1445/
- forrestthewoods 11y ago
  For video games you usually have at least Debug, Release, Retail builds. Where Retail turns on Link Time Code Generation (LTCG) which is quite slow but can give a few percent extra perf. If PGO took 10x to compile but gave a 20% perf boost it'd be an absolute no brainer for game development. Keeping in mind that article shared here was a video game. It's possible that PGO is pretty awesome these days and people just don't realize it. Just because I've heard unimpressive results from other devs doesn't mean it's actually bad!
  - gambiting 11y ago
    I work on a major AAA title due to be released in a few months - our compile times are 20-25 minutes for Windows build(Debug/Release/Final), 10-15 minutes for Xbox One/PS4(consoles link much faster), and for Retail builds, with link time optimization, the build takes anywhere between an hour, hour and a half. That's on a machine with a 6-core, 12 threaded intel Xeon(we use distributed build anyway), 64GB of ram and the source code sitting on a 1TB SSD. The baking of data takes another 10-30 minutes depending on config. Anything that improves our workflow is very,very,very welcome.
    - oso2k 11y ago
      Thank you for proving my point gambiting. @forrestthewoods, asset baking is already 50-200% of the gambiting's non-Retail workflow build time. This is before PGO. Ask him, if had to choose between reducing his build time 10% (without a game performance penalty), or, increasing his build time 1000% (with a game performance improvement of 15%), I think he'll quickly choose the first option. Debug time/feedback is much more valuable (usually) [0]. [0] http://prog21.dadgum.com/47.html http://prog21.dadgum.com/47.html

tormeh 11y ago

We should have -O4 meaning "however long it takes" or something.

joosters 11y ago
We already do. That's what high optimisation levels mean.
Jweb_Guru 11y ago
You're assuming that the hard part is finding optimizable patterns and transforming them, and not deciding whether applying the transformation will actually be an optimization.
- bmh100 11y ago
  In regards to superoptimization, that actually is the case. See this blog post about the use of Souper in LLVM [1]. [1]: http://blog.regehr.org/archives/1146 http://blog.regehr.org/archives/1146
  - Jweb_Guru 11y ago
    That blog post (which I've read) doesn't provide any evidence for that (or even talk about it), and only discusses a small subset of optimizations.

JoachimSchipper 11y ago

> All of these steps can be efficiently automated. Good luck with that. Yes, a compiler will do a good job with i * 28, but the optimization in the article - which is a pretty simple case, chosen to fit in a blog post - requires manipulating the algorithm beyond the capability of any compiler I'm aware of. We do have good tooling to show what code is slow, for instance, so it's not like automation doesn't help here.

spawndog 11y ago
Indeed. Often the slowest code for us is due to cache friendliness more than algorithmic complexity. For the data to be laid out correctly the problem needs to be solved way earlier in your toolchain as well as downstream with a rewrite of any algorithm that touches it

AngrySkillzz 11y ago

There is a Scheme compiler called Stalin[1] which apparently does some very sophisticated full-program and lifetime analysis. This of course leads to very long compile times, but the code is also very fast compared to other Schemes, and even C in some cases, from the benchmarks I've seen[2][3] etc. You can find more benchmarks for it, and similar compilers like MLton. Of course, I can't comment on whether or not it is actually usable in a real-world environment, just that the techniques do exist. [1] https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementation%29 https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementatio... [2] https://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... [3] http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

fanf2 11y ago
A more recent example of a whole-program functional programming language compiler is Haskell's jhc http://repetae.net/computer/jhc/ http://repetae.net/computer/jhc/

oso2k 11y ago

Many compilers will iterate the so called classical optimizations until they produce no effect (an iteration where no optimization took place) or some artificial limit (say 4 or 8 iterations through a basic block or a function). At some point, you risk several accidental de-optimizations such as inducing cache thrashing, cache spilling, architectural limitation, or, even optimization clashing where one optimization de-optimizes a previous optimization on one iteration that then gets re-optimized in the following iteration (A->Opt B->"De-"Opt A->Opt B->...). Another poster suggested profile directed optimization and that usually is even more effective naively iterating through optimization steps.

evincarofautumn 11y ago

Insulation from performance concerns also makes your performance model less predictable. Because the ends of optimisations are observable, but their means are not, people resort to “butterfly programming”. As a small example, in ActionScript 3, people used to write their conditionals like this: if (a) if (b) { ... } Rather than this: if (a && b) { ... } Because the dumb compiler generated better code for the former. In the real world, I’ve seen seemingly benign code changes prevent optimisations from firing—optimisations we didn’t know we were relying on. So people start coding to the implementation, rather than the language or the human, without even being able to see what they’re doing. I really don’t like that. Optimisers are like garbage collectors—they give you better ergonomics than, and equal average performance to the manual alternative, if you’re willing to relinquish predictability and a non-voodoo mental model of your code’s performance.

mikeash 11y ago
I wonder if it would be practical to expose the optimizations to the programmer and allow the complex ones that are easy to accidentally disable to be invoked explicitly. Your code would look something like: optimization(fold_constant_vector_lookup_access_frobnitz) { complex code here } And if the compiler can't apply the optimization, it can produce an error rather than slow code.
- evincarofautumn 11y ago
  That works. We already have some things like that, like “__attribute__((always_inline))”. Of course, forcing some optimisations could implicitly prevent others, but that’d also be true if you did it manually. With expressive enough metaprogramming, you could also do some of these explicit optimisations in user code.
johncolanduoni 11y ago
> Optimisers are like garbage collectors—they give you better ergonomics than, and equal average performance to the manual alternative, if you’re willing to relinquish predictability and a non-voodoo mental model of your code’s performance. This is why I'd like to see optimizers become less opaque. It would be great if we could not only suggest optimizations to the compiler (and more sophisticated ones that just inlining), but actually see the process which our code went through. One language that has some interesting things going on in this area is Nim, which lets you write your own domain-specific optimizations[1]. [1]: http://hookrace.net/blog/what-is-special-about-nim/#add-your-own-optimizations-to-the-compiler http://hookrace.net/blog/what-is-special-about-nim/#add-your...

legulere 11y ago

The analysis part mostly is about legality of the transformation. Humans have a larger view of the program and change code to behave slightly different but way faster. A compiler can't change the behavior of the program.

z3t4 11y ago

I love that v8 (nodejs /chromium, JavaScript) does JIT compiler optimizations. It means I can build for maintainability and still get the same performance as if I had built for speed. Ex: array vs object literal, or array vs object properties. I still do higher level optimizations though, like caching and tweaking formulas (less computations), when needed.

Splines 11y ago

Maybe for some cases, but sometimes (IMO) a compiler is just not going to know. For example, if instead of hitting the network on initialization for some information we delay load that later (say, for example, the MOTD), a compiler is never going to know it could do that.

astrange 11y ago

If you don't regularly run your program with the same optimizations you're using on the final product, you haven't tested it. And if your automatic optimizations are so slow that you can't just re-run them all the time, you can't tune what you're sending into them in the first place. That's for classic compilation, but these days all the good stuff is in JIT on a mobile device, and there your optimizer really can't afford to waste your time.

comex 11y ago
It is? iOS has always used ahead-of-time compilation and Android switched semi-recently from the JIT-based Dalvik to the AOT Android Runtime. The only important JIT left is in the browser...
- astrange 11y ago
  Right, but browsers are pretty important, and a lot of apps are just web views. (Can't remember if JIT works in web apps on iOS these days though.) They also load all that crazy ad tracking javascript from everywhere, optimizing that on every page load has power costs!

joosters 11y ago

Please show us some of these promised optimizations. I don't think they actually exist. Most of the larger code / algorithm tweaks require subtle changes to the behaviour. The compiler can't choose to do that by itself, as it could break the program. Programmers need to make these choices for themselves. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize compile time if they wish. There are plenty of people who would give anything for faster code, no matter what the compile time is. Please prove me wrong and explain a few of these supposed too-slow optimizations.

johncolanduoni 11y ago
Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which are made strict at a later time. Each call creates a new sequence, and many take closures. Both of these require memory allocation and indirect dispatch. However, in many cases it extremely straightforward to convert these into loops. For example, the following C# code: list.Select(f).Where(p).SelectMany(g).ToList() Could be turned into: var outList = new List<T>(); foreach(var x in list) { var y = f(x); if(!p(y)) continue; foreach(var z in g(y)) { outList.Add(z) } } This works, even if we known nothing about f, p, and g (e.g. they can be impure functions). This optimization is especially effective if these functions are lambdas. It is also always going to be faster and safe; the only difference is that we removed a series of extra allocations and indirect function calls. This example is admittedly simple, but many functional patterns and behaviors can be rewritten into longer imperative variants that avoid extra allocations. You are right that you can have subtle changes in behavior with similar high level optimizations. For example, most functional languages make calls like these actually create a new collection at each call. If any of these functions can throw and exception or cause an effect, then we cannot perform the above rewriting because if will call the functions out of order. But if a compiler can take the time to analyze functions for external purity, these can be optimized as well.

andrepd 11y ago

>Perhaps I'm being overly idealistic, but I can't help but hope for a day that I can work with a high level language and have the compiler take care of optimizations I believe optimizing compilers are already a thing. Am I missing something here?

jstelly 11y ago
Currently for game development optimizing compilers are useful but hardly free you from worrying about optimizations. At least when you are using C++: a) Optimizing compilers can't organize your data to be cache friendly. b) optimizing compilers can't re-organize your code to prefer sequential access to that data so the HW prefetch can prevent cache misses c) optimizing compilers can't separate out the parallelizable parts of an algorithm and push those into threaded jobs d) optimizing compilers can't find most cases of work you are doing that doesn't need to be done. They find some trivial/local cases of this but not any of the deep or difficult cases. e) compilers can't rewrite your code or data to not need features or to use simpler features that can be optimized f) compilers can't generate caches (as in the simple example in the article) and find and handle all of the cases where they need to be updated. If you are working on an application where performance is one of the most important features (like many games) you will find yourself working on performance problems like these often. In even higher level languages compilers have more flexibility around some of the fundamental constraints in the C++ world, but there are still few cases where those compilers produce faster code than humans do with C++. Of course the optimized C++ usually requires vastly more effort and returns to that effort are diminishing over time with faster hardware.
- vitalyd 11y ago
  Optimizers are mostly about stripping away abstraction costs of the language. If anyone is asking for more, they're disillusioned :).
  - roel_v 11y ago
    That's very generous of you, but I think that "delusional" isn't an exaggeration in this case...

siegecraft 11y ago

There was an interesting paper linked on here about automatic optimization of Photostop filters via machine learning. I think the novel part was that it operated on binary code, not source. Can't find the link at the moment, but searching for it yielded a bunch of similar papers about machine learning-aided optimization.

roel_v 11y ago
That was highly specific for the type of operation they were looking at. Still spiffy, but not something that can be folded into a general-purpose compiler.
fanf2 11y ago
Dynamic optimization of binary code is 25 years old or more. The first widely deployed JITs were for running binary executables on different architectures, such as the Mac 68k -> PowerPC transition. https://en.wikipedia.org/wiki/Binary_translation#Dynamic_binary_translation https://en.wikipedia.org/wiki/Binary_translation#Dynamic_bin...

RiotTony 11y ago

I think that the Identification and iteration stages can be automated, but the comprehension stage is still a while off. No compiler is going to understand more about the what the context of the program is than a human. For example, knowing that a particle system is transparent enough (or somehow insignificant enough) that it doesn't need to be rendered in the shadow pass is a difficult thing to automatically optimise for. Compilers are generic beasts, they need to work accurately for all valid combinations of code and data (which is a complex problem in itself) and optimisation is another layer of complexity on top of that. Current compiler optimisations work on predominantly local data and code, as that is all the state that the compiler can guarantee is accurate. If a function called from a parent is optimised for that parent, then it is conceivable that this same optimisation could be suboptimal when called from another parent (especially if the compiler was able to modify data layout). The other issue is iteration time. This is a crucial part of software development - lowering iteration time boosts productivity immensely. If, as a programmer, you no longer care about performance due to a compiler that can optimise your code to make it run twice as fast but the compile time is hours, you are rarely going to run the optimised build. And you are going to end up hand optimising the debug/test builds yourself to make them run fast enough. I do think that we could have better tools to help us understand where our code bottlenecks could be - I would love a plugin that somehow coloured my code's variables by cache locality.

WalterBright 11y ago

> I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'd implement that if I knew about such optimization technology, and I bet other compiler guys would, too.

zamalek 11y ago

> I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. If you're referring to super-optimization, it can take far more than 100x and isn't something that is being "classically automated" as humans likely can't do it in the first place. In addition, super-optimization will yield better results if you give it a better starting point. It's nothing at all like the optimization discussed in the blog post. Either way, it can be done against LLVM IR[4] and I'm sure it will creep into clang at some point. So far as using profiling data to optimize code in the way that humans would: MSVC supports it[1], clang supports it[2] and gcc supports it[3]. Supposedly Microsoft saw a 30% performance increase [with a very specific workload] when they tried POGO on an internal build of SQL Server. Under normal circumstances, PGO should net you around 7% free perf. [1]: https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx [2]: http://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization http://clang.llvm.org/docs/UsersManual.html#profile-guided-o... [3]: http://dom.as/2009/07/27/profile-guided-optimization-with-gcc/ http://dom.as/2009/07/27/profile-guided-optimization-with-gc... [4]: https://github.com/google/souper https://github.com/google/souper

dom96 11y ago

How about a language which allows you to define your own optimisations in source code? This reminds me of Nim's term rewriting macros which let you do precisely that: http://nim-lang.org/docs/manual.html#term-rewriting-macros http://nim-lang.org/docs/manual.html#term-rewriting-macros