4 ms·

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 comp

by 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.
  - sanxiyn 9y ago
    > I believe it would be much more challenging for the compiler to predict these branches statically. Why do you believe so? "Branch prediction for free" is a compiler literature classic, and was published in PLDI 1993.
    - lukego 9y ago
      Thanks for the reference. I would be interested in a comparison of modern static vs dynamic predictors. Do you know of one? The misprediction rates that I see in practice are much lower than the ~20% that they are talking about in this paper. For example, gcc compiling sqlite3 misses only ~3.8% of branches on my Haswell processor (see below.) I attribute this improvement to dynamic predictors using more information like recent history, return stack context, loop counter value, computed branch address, etc. This information seems beneficial and also challenging for a static predictor to use. $ perf stat -e branches,branch-misses gcc sqlite3.c 12,212,167,816 branches:u 463,727,878 branch-misses:u # 3.80% of all branches
      - nickpsecurity 9y ago
        "modern static vs dynamic predictors" That again. People jump right to static versus dynamic. Best to mix static and dynamic analysis to get best of both worlds. It was already done in both whole-program optimization and security to get some great benefits. My classic default is to feed the common case as test runs into an instrumented version of the system to get execution traces and measurements. That is combined with static analysis to provide better transformations or scheduling. Also, this is a high-level description of a solution that applies to many problems rather than just compiler components.

by lukego 9y ago

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.
- sanxiyn 9y ago
  > I believe it would be much more challenging for the compiler to predict these branches statically. Why do you believe so? "Branch prediction for free" is a compiler literature classic, and was published in PLDI 1993.
  - lukego 9y ago
    Thanks for the reference. I would be interested in a comparison of modern static vs dynamic predictors. Do you know of one? The misprediction rates that I see in practice are much lower than the ~20% that they are talking about in this paper. For example, gcc compiling sqlite3 misses only ~3.8% of branches on my Haswell processor (see below.) I attribute this improvement to dynamic predictors using more information like recent history, return stack context, loop counter value, computed branch address, etc. This information seems beneficial and also challenging for a static predictor to use. $ perf stat -e branches,branch-misses gcc sqlite3.c 12,212,167,816 branches:u 463,727,878 branch-misses:u # 3.80% of all branches
    - nickpsecurity 9y ago
      "modern static vs dynamic predictors" That again. People jump right to static versus dynamic. Best to mix static and dynamic analysis to get best of both worlds. It was already done in both whole-program optimization and security to get some great benefits. My classic default is to feed the common case as test runs into an instrumented version of the system to get execution traces and measurements. That is combined with static analysis to provide better transformations or scheduling. Also, this is a high-level description of a solution that applies to many problems rather than just compiler components.