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

71–80 of 128 posts

Re: Random Acts of Optimization

#71

Post by vitalyd »

haberman wrote: post #61
saosebastiao wrote: post #37

Earlier quoted context omitted.

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

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

>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

#72

Post by jstelly »

andrepd wrote: post #64
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…

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

Re: Random Acts of Optimization

#73

Post by lunchTime42 »

johncolanduoni wrote: post #65
kibwen wrote: post #62

Earlier quoted context omitted.

Your example doesn't necessarily bolster this thread's original point, because compiler backends are already sophisticated enough to apply this sort of transformation regularly (e.g. you'll see this sort of code generated in Rust, where closures are stack-allocated, iterators are lazy and single-pass, and the resulting loops can even be vectorized).

You're absolutely right, I chose a simple example because it's one I expect most people have seen in one language or another. A better one would be rewriting a combinator based parser (e.g. one written in Parsec) into an imperative one.

Dont you cave in blindly believing into the infoscience gods of old having done good. Demand profile logs, demand numbers, demand evidence. Compilers do the most utterly unexpected nonsense, forget the most trivial optimisations. Take your code to https://gcc.godbolt.org/ and read what your "Compiler-knows-best" does with your code.

yes, it doesent matter often in the end, cause even bad code must wait for worser memory, but still..

Re: Random Acts of Optimization

#74

Post by gambiting »

forrestthewoods wrote: post #51
oso2k wrote: post #22

Earlier quoted context omitted.

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

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

#75

Post by lunchTime42 »

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.

Could the order of condition-statements-machine-code (as in the case handling code)e.g. in the particle code be made rearranging according to in-game-heat-counting?

Re: Random Acts of Optimization

#76

Post by haberman »

vitalyd wrote: post #71
haberman wrote: post #61

Earlier quoted context omitted.

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

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

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

#77

Post by joosters »

lunchTime42 wrote: post #73
johncolanduoni wrote: post #65

Earlier quoted context omitted.

You're absolutely right, I chose a simple example because it's one I expect most people have seen in one language or another. A better one would be rewriting a combinator based parser (e.g. one written in Parsec) into an imperative one.

Dont you cave in blindly believing into the infoscience gods of old having done good. Demand profile logs, demand numbers, demand evidence. Compilers do the most utterly unexpected nonsense, forget the most trivial optimisations. Take your code to https://gcc.godbolt.org/ and read what your "Compiler-knows-best" does with your code. yes, it doesent matter often in the end, cause even bad code must wait for worser mem…

Could you give an example of 'forgetting the most trivial optimizations' please? It would be a bug in a compiler and many people would be interested in fixing it.

Re: Random Acts of Optimization

#78

Post by haberman »

vitalyd wrote: post #70
haberman wrote: post #25

Earlier quoted context omitted.

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

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.

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

#79

Post by RiotTony »

sled wrote: post #69
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.

Are the data sources for Waffles and the Chrome visualizer different? It sounds like Waffles is real-time and the Chrome visualizer is not real-time. Do they use the same macros and route the buffer differently? Or do they have entirely different systems for gathering the profile data?

Waffles is more than just a profiler. It is a nice, high level interface into our (non-public) debugging API. You are correct that the profiling info there is real-time, while Chrome is post. They all use the same buffers, but just interpret the data a little differently.

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.

Re: Random Acts of Optimization

#80

Post by RiotTony »

Splines wrote: post #46
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.

What's the value gained from using vTune vs xperf sampled profiling? 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…

Xperf or WPA is an excellent tool for holistically analysing your application (and all the other applications running on your machine at the same time). We do use that tool for looking at lots of different things: file IO, thread contention, server performance, etc. But for a single client running, I find VTune to be excellent. Its very well integrated into Visual Studio, and provides a number of different perf experiments that you can run to isolate the causes of your bottlenecks. VTune is commercial, but you can use Very Sleepy for a free alternative.
Post reply on HN