Random Acts of Optimization
engineering.riotgames.com
engineering.riotgames.com
All of these steps can be efficiently automated. And it turns out that compiler writers collectively know about the vast majority of these techniques, but refuse to implement most of them for what I would consider to be the ultimate copout ever: Compile times. I don't know about you, but I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'm not sure who wouldn't, especially if it also allows you to eliminate technical debt, eliminate leaky abstractions, and improve code comprehensibility.
Perhaps I'm being overly idealistic, but I can't help but hope for a day that I can work with a high level language and have the compiler take care of optimizations that range from removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2. And if I have to wait all day long for a release build of something, so be it.
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
(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.)
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.
Even a perfect cost model can't tell you the difference between hot paths and cold paths. Profiling can.
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.
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.
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.
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.
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.
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.
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...
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.
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!
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. :)
- 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.
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?
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').
Scala (to pick a random example) is quite hairy to compile efficiently from what I've heard.
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).
Good luck with that. Yes, a compiler will do a good job with i * 28, but the optimization in the article - which is a pretty simple case, chosen to fit in a blog post - requires manipulating the algorithm beyond the capability of any compiler I'm aware of.
We do have good tooling to show what code is slow, for instance, so it's not like automation doesn't help here.
For the data to be laid out correctly the problem needs to be solved way earlier in your toolchain as well as downstream with a rewrite of any algorithm that touches it
Of course, I can't comment on whether or not it is actually usable in a real-world environment, just that the techniques do exist.
[1] https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementatio... [2] https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... [3] http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
if (a) if (b) {
...
}
if (a && b) {
...
}
In the real world, I’ve seen seemingly benign code changes prevent optimisations from firing—optimisations we didn’t know we were relying on. So people start coding to the implementation, rather than the language or the human, without even being able to see what they’re doing. I really don’t like that.
Optimisers are like garbage collectors—they give you better ergonomics than, and equal average performance to the manual alternative, if you’re willing to relinquish predictability and a non-voodoo mental model of your code’s performance.
optimization(fold_constant_vector_lookup_access_frobnitz) {
complex code here
}
With expressive enough metaprogramming, you could also do some of these explicit optimisations in user code.
This is why I'd like to see optimizers become less opaque. It would be great if we could not only suggest optimizations to the compiler (and more sophisticated ones that just inlining), but actually see the process which our code went through.
One language that has some interesting things going on in this area is Nim, which lets you write your own domain-specific optimizations[1].
[1]: http://hookrace.net/blog/what-is-special-about-nim/#add-your...
Unfortunately, the nature of optimizations makes tracking these sorts of things really hard. They don't occur in a vacuum - nearly every optimization transformation interacts with a dozen other transforms, sometimes with very surprising (and usually counterproductive) results.
If you simply implement "book" optimizations, you'll find that they often don't even work without some considerable re-engineering from the bottom up. Many book optimizations make the code slower. And then there are the myriad of optimizations that make code faster on one CPU and slower on the next release of that CPU.
If you think that compiler optimizer writers are holding out on you, they aren't. It's a bit of an arcane art, like samurai sword making technique.
I still do higher level optimizations though, like caching and tweaking formulas (less computations), when needed.
That's for classic compilation, but these days all the good stuff is in JIT on a mobile device, and there your optimizer really can't afford to waste your time.
They also load all that crazy ad tracking javascript from everywhere, optimizing that on every page load has power costs!
Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize compile time if they wish. There are plenty of people who would give anything for faster code, no matter what the compile time is.
Please prove me wrong and explain a few of these supposed too-slow optimizations.
For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which are made strict at a later time. Each call creates a new sequence, and many take closures. Both of these require memory allocation and indirect dispatch.
However, in many cases it extremely straightforward to convert these into loops. For example, the following C# code:
list.Select(f).Where(p).SelectMany(g).ToList()
var outList = new List<T>();
foreach(var x in list) {
var y = f(x);
if(!p(y))
continue;
foreach(var z in g(y)) {
outList.Add(z)
}
}
You are right that you can have subtle changes in behavior with similar high level optimizations. For example, most functional languages make calls like these actually create a new collection at each call. If any of these functions can throw and exception or cause an effect, then we cannot perform the above rewriting because if will call the functions out of order. But if a compiler can take the time to analyze functions for external purity, these can be optimized as well.
yes, it doesent matter often in the end, cause even bad code must wait for worser memory, but still..
I already gave two examples: "removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2". Neither of those optimizations are used by mainstream compilers, although it is possible that LLVM might include some optimizations like the latter due to work from the Souper project.
> Most of the larger code / algorithm tweaks require subtle changes to the behaviour. The compiler can't choose to do that by itself, as it could break the program. Programmers need to make these choices for themselves.
If it introduces a bug, then it is not an optimization, and it has no business being included in an optimizer (at least without explicit flags like -ffast-math).
> Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize compile time if they wish. There are plenty of people who would give anything for faster code, no matter what the compile time is.
My whole point is that -O3 is still weak sauce. There are tons of compiler optimizations that are excluded from both GCC and LLVM because of fears of compilation time impacts. Take a look at the specific techniques section of this wiki article: https://en.wikipedia.org/wiki/Optimizing_compiler
I can guarantee you that the mainstream C compilers cover maybe half of those, and for lesser known languages far less than half.
When is an element in a struct definition 'redundant'? Let's say I write a struct to a network socket, and my receiver (on the other side of the socket) expects a certain memory layout. But one of the fields isn't used in my code (but maybe it is by another program that uses the same header, like two programs that share a library with common data types).
How would that work? I just don't understand what you're saying.
Though it would probably take more time to rearrange things than it would to just do the original loop. The point is, you might be able to look at where the struct is used and change its structure when it moves in memory. If a function is a 'consumer' of structs, and doesn't need all the fields, there is no need to copy all the fields.
Why? Why would you copy at all? Are you saying that with small structs you'll be able to fit more of your data into caches? I haven't timed it (anyone have 20 minutes to spare?) but then you have to make full copy, very expensive not to mention having major implications on memory usage. If my compiler would do that under the hood, even when set to 'optimize for speed', I'd be pretty annoyed. The only way to know if such a thing is faster, is by looking at each use specifically - at which point we're not talking about a compiler anymore. Well ok we'd be talking about "runtime pgo", and approaching JIT territory.
Furthermore, such an 'optimization' would also have to, e.g., detect offsetof() and make sure that that works correctly, and account for packing and people relying on that, and unions, etc etc. I'm not going to spend much time here further on examining and deconstructing this whole concept, especially as I still fail to comprehend the goal.
gcc will do these kind of optimizations, when they make sense. But for 28, most processors will actually be faster doing the multiply.
Multiply instructions only take a few clock cycles. A sequence of adds and shifts can also be slower because they are a sequence of dependent instructions - you need the result of the first one to calculate the next. (You can do some of the adds in parallel, but you still need to total them up)
Here's some old data for an ancient ARM9 processor - http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.... - it takes 2-5 cycles for a MUL (3 for a MUL of 28), compared with 1 for an ADD, 2 for an ADD with shift.
So your 'optimization' would take 6 cycles on an ARM 9, while the MUL takes 3.
It's really easy to double check this. Compile this dumb code with 'gcc -s -O3 test.c'
#include <stdio.h>
int main(int argc, char *argv[])
{
int i = argc;
printf("%d\n", i*28);
return 0;
}
I believe optimizing compilers are already a thing. Am I missing something here?
At least when you are using C++:
a) Optimizing compilers can't organize your data to be cache friendly. b) optimizing compilers can't re-organize your code to prefer sequential access to that data so the HW prefetch can prevent cache misses c) optimizing compilers can't separate out the parallelizable parts of an algorithm and push those into threaded jobs d) optimizing compilers can't find most cases of work you are doing that doesn't need to be done. They find some trivial/local cases of this but not any of the deep or difficult cases. e) compilers can't rewrite your code or data to not need features or to use simpler features that can be optimized f) compilers can't generate caches (as in the simple example in the article) and find and handle all of the cases where they need to be updated.
If you are working on an application where performance is one of the most important features (like many games) you will find yourself working on performance problems like these often. In even higher level languages compilers have more flexibility around some of the fundamental constraints in the C++ world, but there are still few cases where those compilers produce faster code than humans do with C++. Of course the optimized C++ usually requires vastly more effort and returns to that effort are diminishing over time with faster hardware.
This is a very important caveat! It probably doesn't mean much for the pragmatic programmer today, and probably tomorrow, but there are research languages and compilers that try to tackle some of these issues. I myself am working on a compiler for a functional language, that already solves (a) and (b) in some cases, and (c) is doable by using an inherently parallel language. Issues (d)-(f) are about deeper algorithmic changes, and beyond even the frontiers of current research (although you can probably do (d) with a supercompiler if you have enough time).
Compilers are generic beasts, they need to work accurately for all valid combinations of code and data (which is a complex problem in itself) and optimisation is another layer of complexity on top of that. Current compiler optimisations work on predominantly local data and code, as that is all the state that the compiler can guarantee is accurate. If a function called from a parent is optimised for that parent, then it is conceivable that this same optimisation could be suboptimal when called from another parent (especially if the compiler was able to modify data layout).
The other issue is iteration time. This is a crucial part of software development - lowering iteration time boosts productivity immensely. If, as a programmer, you no longer care about performance due to a compiler that can optimise your code to make it run twice as fast but the compile time is hours, you are rarely going to run the optimised build. And you are going to end up hand optimising the debug/test builds yourself to make them run fast enough.
I do think that we could have better tools to help us understand where our code bottlenecks could be - I would love a plugin that somehow coloured my code's variables by cache locality.
I'd implement that if I knew about such optimization technology, and I bet other compiler guys would, too.
If you're referring to super-optimization, it can take far more than 100x and isn't something that is being "classically automated" as humans likely can't do it in the first place. In addition, super-optimization will yield better results if you give it a better starting point. It's nothing at all like the optimization discussed in the blog post. Either way, it can be done against LLVM IR[4] and I'm sure it will creep into clang at some point.
So far as using profiling data to optimize code in the way that humans would: MSVC supports it[1], clang supports it[2] and gcc supports it[3]. Supposedly Microsoft saw a 30% performance increase [with a very specific workload] when they tried POGO on an internal build of SQL Server. Under normal circumstances, PGO should net you around 7% free perf.
[1]: https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx [2]: http://clang.llvm.org/docs/UsersManual.html#profile-guided-o... [3]: http://dom.as/2009/07/27/profile-guided-optimization-with-gc... [4]: https://github.com/google/souper
This reminds me of Nim's term rewriting macros which let you do precisely that: http://nim-lang.org/docs/manual.html#term-rewriting-macros
I use xperf and friends a lot and find that they're pretty good, but if vTune offers something substantially better I wouldn't mind taking a look at it.
Also - interesting that you use the Chrome tools to visualize the graphs. I use WPA to view performance graphs and the breakdowns are somewhat similar. I think the regions of interest files can get you the rest of the way.
Thanks for the writeup. It's interesting to see how other people tackle perf analysis.
class AnimatedVariable {
int numValues;
std::vector<float> values;
// ...
}
if (!mPrecomputed) {
float idx = time * numValues;
float before = values[idx], after = values[idx+1];
return lerp(before, after, idx - (int)idx);
}
There is also other profile info which is gathered by Waffles, stuff like number of visible particles, texture calls, GPU cost per emitter, amongst others, and that information is gathered through another interface.
Talking about optimization, I always wonder why some people have those veeery long loading times. Actually I wonder what is loaded at all. Effects or something? Of course I have no idea of the insides of the game but looking from the outside the map and models should be easily cached.
It would be great to hear more about those loading challenges!
It's much similar to what you have written. When I first learnt about OODA, I was fascinated by how many areas I could suddenly see similar patterns.
BTW the fellow behind OODA (Colonel Boyd) has a fascinating biography that's well worth a read.
Clever! Never heard of doing that but it makes sense.
I work with Tony the author of the article and answer (or find someone to answer) any league questions you might have. Tony will be most likely be online later in the day as he works remotely with us from Australia.
[1] (https://www.reddit.com/r/leagueoflegends/comments/2hvukl/smi...)
Every code base has tech debt. You can't predict the requirements of the future, and even if you could, trying to account for them means you never release your product.
e: Addressing your edit:
Every code base has tech debt. You can't predict the
requirements of the future, and even if you could, trying
to account for them means you never release your product.
Tech debt isn't just salty players whining - it has a major impact on LoL's biggest stage.
Anyway, it would end up being called a sequel.
"Murdering them" how?
They have the most popular video game of all time and you think that a poorly written client is killing them? It has had some problems over the years that are annoying to users (and frankly embarrassing when compared to DOTA 2), but at the end of the day the quality of the client is insignificant to most players compared to the fun-factor of the game itself, as proven by their unprecedented success.
I play League a lot. There are bugs, sure, but altogether the game feels very polished. Much more so than many other games I have played. [There were two high-impact bugs in the current tournament that go counter to this, but they've been addressed already.]
The 'hard way' you espouse is ludicrous and far from the best way. It's not even an option. (Of course this is just my hunch, but it's a well-founded one)
[The ways that league does not feel polished are not related to code quality. They're much more around the new user experience and the toolset available to hardcore players (replays, sandboxes, among others).]
A team that 'made a mess' may think they know all the mistakes they have made in the code, but they have never proven it, and they haven't been practicing doing things 'the right way'. They haven't even learned how to push back on bad strategic decisions that made things worse.
How do you know that the rewrite will be profoundly better than the current version? I think you have rather a lot of evidence that it won't.
Take a team that cleans up their messes as they go. They know whether their new ideas are better or worse. They have proven they 'deserve' a better code base by building one. By the time they know for sure what's really wrong with the code, they no longer need a complete rewrite. They need a partial rewrite that they can string out over the course of a couple years.
If any of that is true, then the people who want a do over won't take advantage of it, and those that would benefit most wouldn't feel comfortable doing it.
Continuing to develop while totally rewriting the core leads to wasted effort and a "running to keep up" effect, though allows for a strong technical foundation, provided you actually finish it. Incrementally rewriting the codebase takes longer, but is easier to do in flight, and easy to test in a modular fashion -- and that's already happening.
> Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.57.217).
> Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.13.45).
Last year's event generated more global viewers than the NBA final.