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

41–50 of 128 posts

Re: Random Acts of Optimization

#41

Post by mikeash »

evincarofautumn wrote: post #27
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…

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 wonder if it would be practical to expose the optimizations to the programmer and allow the complex ones that are easy to accidentally disable to be invoked explicitly. Your code would look something like:

    optimization(fold_constant_vector_lookup_access_frobnitz) {
        complex code here
    }
And if the compiler can't apply the optimization, it can produce an error rather than slow code.

Re: Random Acts of Optimization

#42

Post by astrange »

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…

If you don't regularly run your program with the same optimizations you're using on the final product, you haven't tested it. And if your automatic optimizations are so slow that you can't just re-run them all the time, you can't tune what you're sending into them in the first place.

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.

Re: Random Acts of Optimization

#43

Post by joosters »

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.

We already do. That's what high optimisation levels mean.

Re: Random Acts of Optimization

#44

Post by [deleted] »

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.

[deleted]

Re: Random Acts of Optimization

#45

Post by tel »

jerf wrote: post #24
saosebastiao wrote: post #15

Earlier quoted context omitted.

I've gotten pretty good results from PGO as well as JIT optimizations (which isn't conceptually much different), but even if I hadn't, your comment is still a fallacy on two accounts: 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 fo…

And in theory, dependent types are the awesomest thing ever. But they're not ready yet, and there's no guarantee they ever will be. There's a gulf between even having a few focused, carefully-chosen proofs of concept and a practically-useful technology. (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, bu…

They're ready in small forms in Haskell today. The compiler doesn't take a whole lot of advantage of these yet, but you start to see avenues toward it.

Re: Random Acts of Optimization

#46

Post by Splines »

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 you the rest of the way.

Thanks for the writeup. It's interesting to see how other people tackle perf analysis.

Re: Random Acts of Optimization

#48

Post by jlees »

debacle wrote: post #12
bpicolo wrote: post #4

Earlier quoted context omitted.

"Its defects do not reflect issues with our code base (though there are many), but rather my own hacky implementation." 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.

Riot's code base has a massive amount of technical debt, to a point where a rewrite is likely the best choice because of past technology decisions.

"The best choice" is a woolly phrase. Best for whom? Stopping all development to totally rewrite the core game engine is best from a technical perspective, but that's not necessarily the optimal solution for player enjoyment -- and would have impact on other things, e.g. the competitive aspect of the game.

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.

Re: Random Acts of Optimization

#49

Post by comex »

astrange wrote: post #42
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…

If you don't regularly run your program with the same optimizations you're using on the final product, you haven't tested it. And if your automatic optimizations are so slow that you can't just re-run them all the time, you can't tune what you're sending into them in the first place. 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 a…

It is? iOS has always used ahead-of-time compilation and Android switched semi-recently from the JIT-based Dalvik to the AOT Android Runtime. The only important JIT left is in the browser...
Post reply on HN