4 ms·

The exciting possibility, from my perspective, is that many optimizations may be simpler to implement dynamically (JIT) than statically. So perhaps you can have

by 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

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.