Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Random Acts of Optimization

engineering.riotgames.com

Post reply on HN
Print view View original

121–128 of 128 posts

Re: Random Acts of Optimization

#121

Post by Athas »

jstelly wrote: post #72
andrepd wrote: post #64

Earlier quoted context omitted.

>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 I believe optimizing compilers are already a thing. Am I missing something here?

Currently for game development optimizing compilers are useful but hardly free you from worrying about optimizations. 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…

> At least when you are using C++:

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).

Re: Random Acts of Optimization

#122

Post by zamalek »

saosebastiao wrote: post #7

This brings up a thought that I've had for a very long time. Almost every type of optimization that a programmer could employ is repeatable. It involves matching patterns ("Identification" in the context of this article), analysis ("Comprehension"), and rewriting ("Iteration"). All of these steps can be efficiently automated. And it turns out that compiler writers collectively know about the vast majority of these te…

> I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization.

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

Re: Random Acts of Optimization

#123

Post by lorenzhs »

joosters wrote: post #97
saosebastiao wrote: post #88

Earlier quoted context omitted.

> Please show us some of these promised optimizations. I don't think they actually exist. I already gave two examples: "removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i > 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 mak…

> i * 28 == i 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 stil…

it's even easier to play around with these things using https://gcc.godbolt.org

Re: Random Acts of Optimization

#124

Post by dom96 »

saosebastiao wrote: post #7

This brings up a thought that I've had for a very long time. Almost every type of optimization that a programmer could employ is repeatable. It involves matching patterns ("Identification" in the context of this article), analysis ("Comprehension"), and rewriting ("Iteration"). All of these steps can be efficiently automated. And it turns out that compiler writers collectively know about the vast majority of these te…

How about a language which allows you to define your own optimisations in source code?

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

Re: Random Acts of Optimization

#125

Post by gambiting »

roel_v wrote: post #112
bhrgunatha wrote: post #106

Earlier quoted context omitted.

> 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?

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 ther…

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

#126

Post by Jweb_Guru »

bmh100 wrote: post #116
Jweb_Guru wrote: post #111

Earlier quoted context omitted.

You're assuming that the hard part is finding optimizable patterns and transforming them, and not deciding whether applying the transformation will actually be an optimization.

In regards to superoptimization, that actually is the case. See this blog post about the use of Souper in LLVM [1]. [1]: http://blog.regehr.org/archives/1146

That blog post (which I've read) doesn't provide any evidence for that (or even talk about it), and only discusses a small subset of optimizations.

Re: Random Acts of Optimization

#127

Post by barrkel »

haberman wrote: post #89
saosebastiao wrote: post #84

Earlier quoted context omitted.

> 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…

> 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…

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

#128

Post by haberman »

barrkel wrote: post #127
haberman wrote: post #89

Earlier quoted context omitted.

> 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…

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.

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.

Post reply on HN