4 ms·

Actually, they can, and quite well actually. The dotnet native compiler actually does quite a few analyses for "hotness", mostly centered around maintaining cac

Actually, they can, and quite well actually. The dotnet native compiler actually does quite a few analyses for "hotness", mostly centered around maintaining cache locality. However if there is a lot of entropy in the possible code paths, it might not be computationally feasible to analyze the hotness of all of the paths. In those cases, we accept heuristic substitutes, of which both JITs and PGO have shown good results.

haberman 11y ago
> it might not be computationally feasible to analyze the hotness of all of the paths It has nothing to do with computational feasibility. It has to do with the fact that it depends on the input. In many cases there simply is not enough information at compile time to determine which paths are hotter than others. For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. > In those cases, we accept heuristic substitutes, of which both JITs and PGO have shown good results. JIT and PGO aren't heuristic, they are based on measurement. By your logic, if I look at the speedometer in my car that is just a "heuristic" of my speed. It's not a heuristic, it's an empirical measurement.
- vitalyd 11y ago
  >For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. At least for .NET that path is likely throwing an exception. If you don't have a profile, statically assuming those paths are cold is likely to be correct.
  - haberman 11y ago
    That's an interesting point -- my background is more in C and C++-without-exceptions. But in exception-based languages, I can see how the presence of "throw" would be a very useful signal for static analysis.
    - vitalyd 11y ago
      Yes, this is a side benefit to exceptions (or some other language's way to highlight errors and thus likely cold paths).
- saosebastiao 11y ago
  > It has nothing to do with computational feasibility. It has to do with the fact that it depends on the input. In many cases there simply is not enough information at compile time to determine which paths are hotter than others. That's a fair point, but still quite a bit overstated. There are a variety of analyses that compilers can and do perform to understand possible input before it ever receives the input. I'm familiar with a handful of probabilistic and set-cardinality estimation techniques used in math optimization pre-solvers (a form of compiler) that do exactly this, and I'm pretty sure both GCC and LLVM already do several similar analyses. Furthermore, a very large subset of optimizations won't have any path dependence in the optimization that it choses, and a significant subset after that has choice thresholds that are trivially computable given an accurate cost model. When the former happens, profiling gives no advantage at all, and when the latter happens, it is typically more efficient to branch on that threshold than it is to try to guess at which choice is more efficient by measuring sample input. > For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. That might be true of some languages, but not so with others. Exceptions are obviously error paths, and several strongly typed languages have error paths encoded in the type system. > JIT and PGO aren't heuristic, they are based on measurement. By your logic, if I look at the speedometer in my car that is just a "heuristic" of my speed. It's not a heuristic, it's an empirical measurement. But that's the thing, measurement of your input is a heuristic. If your program execution is heavily influenced by its input, and you optimize using profiling, you are assuming that past input is predictive of future input. That assumption is a heuristic. It might be a really good heuristic, but it still is a heuristic.
  - haberman 11y ago
    > Furthermore, a very large subset of optimizations won't have any path dependence in the optimization that it choses Hot code should be: optimized for speed, inlined, unrolled (where it helps), kept local with other hot code, and register-allocated with other hot code. Cold code should be: optimized for size, not inlined, not unrolled, kept away from hot code, and should never be accommodated in register allocation for any reason (ie. should never reduce availability of registers needed by hot paths). So I don't agree that optimizations should be performed in a path-independent way. > But that's the thing, measurement of your input is a heuristic. By that standard, everything is heuristic. The assumption that your cost model matches the actual CPU the code will run on is a heuristic.
- darkmighty 11y ago
  > It has to do with the fact that it depends on the input. A special case of: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op... This does not hold, of course, if you could automatically simulate the users themselves...

haberman 11y ago

> it might not be computationally feasible to analyze the hotness of all of the paths It has nothing to do with computational feasibility. It has to do with the fact that it depends on the input. In many cases there simply is not enough information at compile time to determine which paths are hotter than others. For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. > In those cases, we accept heuristic substitutes, of which both JITs and PGO have shown good results. JIT and PGO aren't heuristic, they are based on measurement. By your logic, if I look at the speedometer in my car that is just a "heuristic" of my speed. It's not a heuristic, it's an empirical measurement.

vitalyd 11y ago
>For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. At least for .NET that path is likely throwing an exception. If you don't have a profile, statically assuming those paths are cold is likely to be correct.
- haberman 11y ago
  That's an interesting point -- my background is more in C and C++-without-exceptions. But in exception-based languages, I can see how the presence of "throw" would be a very useful signal for static analysis.
  - vitalyd 11y ago
    Yes, this is a side benefit to exceptions (or some other language's way to highlight errors and thus likely cold paths).
saosebastiao 11y ago
> It has nothing to do with computational feasibility. It has to do with the fact that it depends on the input. In many cases there simply is not enough information at compile time to determine which paths are hotter than others. That's a fair point, but still quite a bit overstated. There are a variety of analyses that compilers can and do perform to understand possible input before it ever receives the input. I'm familiar with a handful of probabilistic and set-cardinality estimation techniques used in math optimization pre-solvers (a form of compiler) that do exactly this, and I'm pretty sure both GCC and LLVM already do several similar analyses. Furthermore, a very large subset of optimizations won't have any path dependence in the optimization that it choses, and a significant subset after that has choice thresholds that are trivially computable given an accurate cost model. When the former happens, profiling gives no advantage at all, and when the latter happens, it is typically more efficient to branch on that threshold than it is to try to guess at which choice is more efficient by measuring sample input. > For example, error paths are generally very cold, but how is a compiler supposed to know that a path is an error path? They just look like regular conditionals. That might be true of some languages, but not so with others. Exceptions are obviously error paths, and several strongly typed languages have error paths encoded in the type system. > JIT and PGO aren't heuristic, they are based on measurement. By your logic, if I look at the speedometer in my car that is just a "heuristic" of my speed. It's not a heuristic, it's an empirical measurement. But that's the thing, measurement of your input is a heuristic. If your program execution is heavily influenced by its input, and you optimize using profiling, you are assuming that past input is predictive of future input. That assumption is a heuristic. It might be a really good heuristic, but it still is a heuristic.
- haberman 11y ago
  > Furthermore, a very large subset of optimizations won't have any path dependence in the optimization that it choses Hot code should be: optimized for speed, inlined, unrolled (where it helps), kept local with other hot code, and register-allocated with other hot code. Cold code should be: optimized for size, not inlined, not unrolled, kept away from hot code, and should never be accommodated in register allocation for any reason (ie. should never reduce availability of registers needed by hot paths). So I don't agree that optimizations should be performed in a path-independent way. > But that's the thing, measurement of your input is a heuristic. By that standard, everything is heuristic. The assumption that your cost model matches the actual CPU the code will run on is a heuristic.
darkmighty 11y ago
> It has to do with the fact that it depends on the input. A special case of: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op... This does not hold, of course, if you could automatically simulate the users themselves...