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

111–120 of 128 posts

Re: Random Acts of Optimization

#111

Post by Jweb_Guru »

tormeh wrote: post #14
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…

We should have -O4 meaning "however long it takes" or something.

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.

Re: Random Acts of Optimization

#112

Post by roel_v »

bhrgunatha wrote: post #106
roel_v wrote: post #92

Earlier quoted context omitted.

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

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

#113

Post by pandaman »

bhrgunatha wrote: post #106
roel_v wrote: post #92

Earlier quoted context omitted.

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

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

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

#114

Post by evincarofautumn »

WalterBright wrote: post #107
evincarofautumn wrote: post #27

Earlier quoted context omitted.

Insulation from performance concerns also makes your performance model less predictable. Because the ends of optimisations are observable, but their means are not, people resort to “butterfly programming”. As a small example, in ActionScript 3, people used to write their conditionals like this: if (a) if (b) { ... } Rather than this: if (a && b) { ... } Because the dumb compiler generated better code for the former.…

> I really don’t like that. 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 considerabl…

Of course. I have no problem with generic, implicit optimisation. However, people often need to optimise further, manually. Without good language support, they start coding to a particular implementation: using less-than-portable intrinsics, or worse, trying to trigger heuristics that produce the optimisations they actually want.

Re: Random Acts of Optimization

#116

Post by bmh100 »

Jweb_Guru wrote: post #111
tormeh wrote: post #14

Earlier quoted context omitted.

We should have -O4 meaning "however long it takes" or something.

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

Re: Random Acts of Optimization

#117

Post by bmh100 »

spawndog wrote: post #21

Hi all, 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.

One interesting thought for me is, do you have areas of code where you suspect a good optimization exists but are unable to find it or justify the presumably exhaustive time to uncover it?

Re: Random Acts of Optimization

#118

Post by bhrgunatha »

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…

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

#119

Post by adrianN »

gambiting wrote: post #74
forrestthewoods wrote: post #51

Earlier quoted context omitted.

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…

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

Count yourself lucky. It takes me 90 minutes just to compile the module tests for one module.

Re: Random Acts of Optimization

#120

Post by newman314 »

RiotTony wrote: post #40

Hey everyone, I'm the author of this article and I'm glad you've found it interesting. I'll be keeping an eye on this thread, so if you have any questions or comments I'll address them as soon as I can. I can already see some awesome questions here - looking forward to the discussion.

When you get a chance, look up the OODA loop.

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.

Post reply on HN