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

91–100 of 128 posts

Re: Random Acts of Optimization

#91

Post by [deleted] »

josephg wrote: post #56
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.

Why scan the table of precomputed values? It seems like the code would be both cleaner and faster like this: class AnimatedVariable { int numValues; std::vector values; // ... } Then: if (!mPrecomputed) { float idx = time * numValues; float before = values[idx], after = values[idx+1]; return lerp(before, after, idx - (int)idx); } I guess there's a bit of float -> int coercion going on there, but it shouldn't be too b…

[deleted]

Re: Random Acts of Optimization

#92

Post by roel_v »

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…

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

#93

Post by roel_v »

saosebastiao wrote: post #88
joosters wrote: post #53

Earlier quoted context omitted.

Please show us some of these promised optimizations. I don't think they actually exist. 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. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize…

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

"removing redundant elements from struct definitions"

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.

Re: Random Acts of Optimization

#94

Post by roel_v »

siegecraft wrote: post #67
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…

There was an interesting paper linked on here about automatic optimization of Photostop filters via machine learning. I think the novel part was that it operated on binary code, not source. Can't find the link at the moment, but searching for it yielded a bunch of similar papers about machine learning-aided optimization.

That was highly specific for the type of operation they were looking at. Still spiffy, but not something that can be folded into a general-purpose compiler.

Re: Random Acts of Optimization

#95

Post by fanf2 »

saosebastiao wrote: post #88
joosters wrote: post #53

Earlier quoted context omitted.

Please show us some of these promised optimizations. I don't think they actually exist. 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. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize…

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

Those kinds of bitshift optimizations have been basic for 25 years or more. Read Hacker's Delight by Henry Warren for hundreds of pages of this kind of standard compiler technique.

Re: Random Acts of Optimization

#96

Post by roel_v »

vitalyd wrote: post #86
jstelly wrote: post #72

Earlier quoted context omitted.

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…

Optimizers are mostly about stripping away abstraction costs of the language. If anyone is asking for more, they're disillusioned :).

That's very generous of you, but I think that "delusional" isn't an exaggeration in this case...

Re: Random Acts of Optimization

#97

Post by joosters »

saosebastiao wrote: post #88
joosters wrote: post #53

Earlier quoted context omitted.

Please show us some of these promised optimizations. I don't think they actually exist. 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. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize…

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

  int main(int argc, char *argv[])
  {
     int i = argc;
     printf("%d\n", i*28);
     return 0;
  }
Try changing the 28 to different values and run a diff against each version (e.g. try 8, 9 and 10). On x86, gcc will use a variety of techniques based upon the multiplier.

Re: Random Acts of Optimization

#98

Post by fanf2 »

AngrySkillzz wrote: post #18
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…

There is a Scheme compiler called Stalin[1] which apparently does some very sophisticated full-program and lifetime analysis. This of course leads to very long compile times, but the code is also very fast compared to other Schemes, and even C in some cases, from the benchmarks I've seen[2][3] etc. You can find more benchmarks for it, and similar compilers like MLton. Of course, I can't comment on whether or not it i…

A more recent example of a whole-program functional programming language compiler is Haskell's jhc http://repetae.net/computer/jhc/

Re: Random Acts of Optimization

#99

Post by RiotTony »

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 think that the Identification and iteration stages can be automated, but the comprehension stage is still a while off. No compiler is going to understand more about the what the context of the program is than a human. For example, knowing that a particle system is transparent enough (or somehow insignificant enough) that it doesn't need to be rendered in the shadow pass is a difficult thing to automatically optimise for.

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.

Re: Random Acts of Optimization

#100

Post by forrestthewoods »

oso2k wrote: post #87
gambiting wrote: post #74

Earlier quoted context omitted.

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…

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…

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

Post reply on HN