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

11–20 of 128 posts

Re: Random Acts of Optimization

#11

Post by huac »

bpicolo wrote: post #4
mmanfrin wrote: post #3

This is an interesting article, but Riot hasn't really earned any trust of mine at all as it comes to code quality; for a while they couldn't show the damage output of a spell because it caused the user's other summoner spell to go on cooldown for 15 minutes[1] when they tried. [1] ( https://www.reddit.com/r/leagueoflegends/comments/2hvukl/smi... )

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

One large storyline in the ongoing LoL world championships revolves around a major, longstanding bug: the 2nd most popular competitive jungler had to be disabled halfway through the tournament because one of his abilities suddenly became useless. This has had a large impact on competitive strategy, forcing teams to rethink strats on the fly.

Tech debt isn't just salty players whining - it has a major impact on LoL's biggest stage.

Re: Random Acts of Optimization

#12

Post by debacle »

bpicolo wrote: post #4
mmanfrin wrote: post #3

This is an interesting article, but Riot hasn't really earned any trust of mine at all as it comes to code quality; for a while they couldn't show the damage output of a spell because it caused the user's other summoner spell to go on cooldown for 15 minutes[1] when they tried. [1] ( https://www.reddit.com/r/leagueoflegends/comments/2hvukl/smi... )

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

Re: Random Acts of Optimization

#13

Post by mmanfrin »

huac wrote: post #11
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.

One large storyline in the ongoing LoL world championships revolves around a major, longstanding bug: the 2nd most popular competitive jungler had to be disabled halfway through the tournament because one of his abilities suddenly became useless. This has had a large impact on competitive strategy, forcing teams to rethink strats on the fly. Tech debt isn't just salty players whining - it has a major impact on LoL's…

Not to mention the ward in the baron pit during (CLGs?) group stage game that their pink ward could not see inexplicably -- the game had to be stopped so that the officiants could tell CLG that the ward could still see them.

Re: Random Acts of Optimization

#14

Post by tormeh »

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.

Re: Random Acts of Optimization

#15

Post by saosebastiao »

forrestthewoods wrote: post #10
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 such a thing as profile guided optimization. I don't think their results are particularly impressive. You're basically saying "can't you just" to which the answer is almost always no. No you can't just.

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 forego profiling altogether because they evaluate optimizations against a hardware/architecture cost model. In other words, PGO isn't even necessary to accomplish what I'm talking about.

And yes, yes you can.

https://justindomke.wordpress.com/2009/02/23/the-stalin-comp...

http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

Re: Random Acts of Optimization

#16

Post by ajkjk »

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.

A rewrite would murder them. I'm not going to link that article everyone links about "never rewriting your code", because I don't think it's got the argument right, but I strongly feel that if they tried to rewrite a system as complex as theirs, they would either a) never finish or b) stop developing the game and, by the time they finished their rewrite, have no customers left.

Anyway, it would end up being called a sequel.

Re: Random Acts of Optimization

#17

Post by JoachimSchipper »

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…

> All of these steps can be efficiently automated.

Good luck with that. Yes, a compiler will do a good job with i * 28, but the optimization in the article - which is a pretty simple case, chosen to fit in a blog post - requires manipulating the algorithm beyond the capability of any compiler I'm aware of.

We do have good tooling to show what code is slow, for instance, so it's not like automation doesn't help here.

Re: Random Acts of Optimization

#18

Post by AngrySkillzz »

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 is actually usable in a real-world environment, just that the techniques do exist.

[1] https://en.wikipedia.org/wiki/Stalin_%28Scheme_implementatio... [2] https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... [3] http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

Re: Random Acts of Optimization

#19

Post by oso2k »

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…

Many compilers will iterate the so called classical optimizations until they produce no effect (an iteration where no optimization took place) or some artificial limit (say 4 or 8 iterations through a basic block or a function). At some point, you risk several accidental de-optimizations such as inducing cache thrashing, cache spilling, architectural limitation, or, even optimization clashing where one optimization de-optimizes a previous optimization on one iteration that then gets re-optimized in the following iteration (A->Opt B->"De-"Opt A->Opt B->...). Another poster suggested profile directed optimization and that usually is even more effective naively iterating through optimization steps.
Post reply on HN