News for hackers. Stuff that matters.
Re:Random Acts of Optimization by forrestthewoods on Thursday October 29, 2015 @04:05PM (#10473893)
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.
Re:Random Acts of Optimization by saosebastiao on Thursday October 29, 2015 @04:29PM (#10474047)
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-comp...

http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

Re:Random Acts of Optimization by jerf on Thursday October 29, 2015 @04:45PM (#10474148)
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.)

Re:Random Acts of Optimization by johncolanduoni on Thursday October 29, 2015 @06:06PM (#10474715)
> 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.

Re:Random Acts of Optimization by saosebastiao on Thursday October 29, 2015 @04:54PM (#10474201)
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.
Re:Random Acts of Optimization by tel on Thursday October 29, 2015 @05:18PM (#10474379)
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.
Re:Random Acts of Optimization by haberman on Thursday October 29, 2015 @04:46PM (#10474152)
> 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.

Re:Random Acts of Optimization by saosebastiao on Thursday October 29, 2015 @05:06PM (#10474285)
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.
Re:Random Acts of Optimization by haberman on Thursday October 29, 2015 @05:51PM (#10474619)
> 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.

Re:Random Acts of Optimization by saosebastiao on Thursday October 29, 2015 @07:22PM (#10475165)
> 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.

Re:Random Acts of Optimization by haberman on Thursday October 29, 2015 @07:57PM (#10475363)
> 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.

Re:Random Acts of Optimization by barrkel on Friday October 30, 2015 @10:07PM (#10481527)
If we followed your advice, the differential between worst case and best case performance would be large.

There are good reasons for preferring a less extreme difference in potential performance for general computing with AOT compiled languages. In particular, we should ensure the worst case performance isn't awful. We wouldn't want e.g. an occasional exception getting thrown to act like a DoS attack on a web server.

Re:Random Acts of Optimization by haberman on Saturday October 31, 2015 @02:21PM (#10483556)
Nothing I was suggesting would create "awful" performance. Inlining and unrolling are not necessary to get reasonable performance -- just try gcc or Clang with -Os.

For an occasional exception to "act like a DoS attack", the cold path would have to be thousands or millions of times slower than the hot paths. But compiler optimizations don't create anywhere near these kinds of constant factors. Even from -O0 to -O3 is more like a 5-10x difference, maybe 100x in extreme cases. The difference between -Os and -O3 is much more modest, more like 0-50%. Nothing that is going to cause anything remotely resembling a DoS.

Re:Random Acts of Optimization by vitalyd on Thursday October 29, 2015 @06:34PM (#10474871)
>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.

Re:Random Acts of Optimization by haberman on Thursday October 29, 2015 @07:01PM (#10475035)
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.
Re:Random Acts of Optimization by vitalyd on Thursday October 29, 2015 @07:19PM (#10475145)
Yes, this is a side benefit to exceptions (or some other language's way to highlight errors and thus likely cold paths).
Re:Random Acts of Optimization by darkmighty on Thursday October 29, 2015 @07:59PM (#10475375)
> 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_op...

This does not hold, of course, if you could automatically simulate the users themselves...

Re:Random Acts of Optimization by vitalyd on Thursday October 29, 2015 @06:31PM (#10474852)
Profiling comes with its own baggage, nothing's perfect. A lot of times one actually knows the likely/unlikely paths at development time; that's certainly true for error conditions. It makes sense to inform the compiler of those cases using the builtins.
Re:Random Acts of Optimization by haberman on Thursday October 29, 2015 @07:08PM (#10475073)
Sure I'm not saying profiling is perfect. I was just taking exception to the statement that profiling is nothing but a poor man's substitute for a cost model.

Explicit annotations for hot/cold paths are useful, I agree. I would probably be more excited about them except last time I actually tried them with GCC, they slowed my code down (admittedly this was five years ago or so). But that's just an implementation problem, the concept is sound.

Re:Random Acts of Optimization by vitalyd on Thursday October 29, 2015 @07:17PM (#10475133)
I agree - profile and cost model are orthogonal and complementary. Former tells you what to optimize, latter dictates how to optimize it.
Re:Random Acts of Optimization by oso2k on Thursday October 29, 2015 @04:44PM (#10474141)
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/

[1] https://xkcd.com/1445/

Re:Random Acts of Optimization by forrestthewoods on Thursday October 29, 2015 @05:23PM (#10474412)
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!

Re:Random Acts of Optimization by gambiting on Thursday October 29, 2015 @06:48PM (#10474958)
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.
Re:Random Acts of Optimization by roel_v on Thursday October 29, 2015 @08:08PM (#10475396)
I probably misunderstand, but if this is a critical part in your workflow, why wouldn't you

- put 'data baking' (I presume that means things like packing images into blobs etc?) on a separate server - put another few computers into your 'compile farm' if you're using distributed builds already anyway

How much of, let's say, an hour is spend on compiling, linking and packaging? Compiling is 'trivially' (for some values of that word) parallelizable.

Re:Random Acts of Optimization by bhrgunatha on Thursday October 29, 2015 @10:31PM (#10475821)
> Compiling is 'trivially' (for some values of that word) parallelizable.

Really? I've always heard that it's virtually impossible to parallelize. Or do you mean a particular step in the pipeline can be parallelised - like parsing separate source files?

Re:Random Acts of Optimization by roel_v on Friday October 30, 2015 @12:02AM (#10476091)
The actual compilation of each "translation unit" (roughly, ".cpp file"), so the preprocessing, lexing, parsing, AST generation as well as the first-pass code generation, can be done in parallel. A project with 1000 .cpp files would (theoretically) need only as much time for that phase as the longest of the 1000 would take (plus time for the overhead of transferring files to build machines).

Of course after that there is global optimization and linking, maybe those take the majority of the time on the GP's case, which is why I was asking. In my experience, even for optimizing release builds, those phases are just a small part though - 25% or so for my projects, as a high-end guesstimate? But as I said, maybe it's very different for others.

Products like Incredibuild do just that.

(of course it's not 'trivial' as in 'I'll set it up over lunch', there are many many details to work out, which is why I said 'for some values of that word' - i.e., the engineer's meaning of 'trivial').

Re:Random Acts of Optimization by gambiting on Friday October 30, 2015 @05:19AM (#10476830)
We actually use Incredibuild(and SM-DBS as well). Those times are distributed build times. Compiling on a single machine would take at least an hour.

Also - we do bake data on a separate server too, I just prefer to do it myself because then I have several configs(one small one with a test map, one bigger one with the main story etc), and they all work with my changes.

I would say that if I got latest right now, it would take me at least an hour to start the game for the first time on either console(game server is part of Win64 solution so I need to build that first).

Re:Random Acts of Optimization by bhrgunatha on Friday October 30, 2015 @02:37AM (#10476408)
I suppose I'm thinking of compilers in general, rather than C/C++ specifically though.

Scala (to pick a random example) is quite hairy to compile efficiently from what I've heard.

Re:Random Acts of Optimization by pandaman on Friday October 30, 2015 @12:18AM (#10476137)
In C++ (and C for that matter) separate source files are separate compilation units. So it is trivial to parallelize. The compilation process produces object code, which, generally, has to be linked into an executable to be useful and that is usually not a parallelized task even though nothing prevents you from writing a parallel linker in theory. Unless LTO (link-time optimization) is enabled, the bulk of the linker's time is in I/O so making it parallel would not produce any performance gains till recently. Nowadays we have SSDs that can benefit from deeply queued I/O and, probably, somebody will write a parallel linker eventually.
Re:Random Acts of Optimization by oso2k on Thursday October 29, 2015 @07:27PM (#10475202)
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

Re:Random Acts of Optimization by forrestthewoods on Thursday October 29, 2015 @08:31PM (#10475473)
If you offered me mildly faster iteration OR mildly framerate at 10x compile I'd also choose the former. Iteration speed is king.

But it's not either/or. If you offered me Debug/Release/Retail(LTCG)/SuperRetail(GPO) I'd love to have that fourth option. It doesn't have to come at the expensive of any other build configurations. Even if PGO takes 10 hours to compile. It's part of the overnight build. Great! There's no shortage of AAA games that have an overnight 12 hour process to build lightmaps for a single level. And that's using a build farm.

But so far I've never heard a major, or even minor, PGO success story so it's all kinda moot. :)

Re:Random Acts of Optimization by adrianN on Friday October 30, 2015 @03:08AM (#10476476)
Count yourself lucky. It takes me 90 minutes just to compile the module tests for one module.