15 ms·

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 f

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.
haberman 11y ago
> Profiling is a heuristic substitute for a real cost model. Even a perfect cost model can't tell you the difference between hot paths and cold paths. Profiling can.
- saosebastiao 11y ago
  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.
      - 11y ago

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.

haberman 11y ago

> Profiling is a heuristic substitute for a real cost model. Even a perfect cost model can't tell you the difference between hot paths and cold paths. Profiling can.

saosebastiao 11y ago
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.
    - 11y ago