21 ms·

Random Acts of Optimization

279 points by sled 11y ago

885895 11y ago
>In our case we output the profile buffer to a file and read that into the visualization tool which is conveniently built into Chrome. (You can find more information about the tracing tool here and you can try it out by typing “chrome://tracing/” into your Chrome browser. It is designed for web page profiling, but the format of the input profile data is a simple json format that can be easily constructed from your own data.) Clever! Never heard of doing that but it makes sense.
- Drdrdrq 11y ago
  Another term for these profiling charts in Chrome is flame charts, you might be able to find even more tools by it.
  - cbab 11y ago
    Yup, basically Chrome is using an inverted flame graph (See [1] for additional infos and tools). [1] - https://github.com/brendangregg/FlameGraph https://github.com/brendangregg/FlameGraph
mmanfrin 11y ago
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/smite_damage_should_be_shown_on_the_icon/ https://www.reddit.com/r/leagueoflegends/comments/2hvukl/smi...)
- bpicolo 11y ago
  "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.
  - mmanfrin 11y ago
    This is one of many such issues -- one of the largest complaints about the game from the community is the stability of the game and the frequency with which 'gamebreaking' bugs occur. e: Addressing your edit: 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. League is a mature game at this point, they have had a lot of time to fix longstanding issues. This isn't 'release day' woes.
  - huac 11y ago
    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.
    - mmanfrin 11y ago
      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.
  - debacle 11y ago
    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.
    - ajkjk 11y ago
      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.
- Sevzinn 11y ago
  Video games programmers have to learn more and make less. I'll give them the benefit of the doubt, especially since I can barely understand this particular blog post.
debacle 11y ago
Dota 2 has custom games now. Maybe they can write the new client in Hammer.
saosebastiao 11y ago
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 techniques, but refuse to implement most of them for what I would consider to be the ultimate copout ever: Compile times. I don't know about you, but I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'm not sure who wouldn't, especially if it also allows you to eliminate technical debt, eliminate leaky abstractions, and improve code comprehensibility. 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 that range from removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2. And if I have to wait all day long for a release build of something, so be it.
- shepardrtc 11y ago
  There was a HN thread a day or two ago in which someone suggested the idea of a common, open source KV database where compiler optimizations could be stored and curated by a committee. So whenever a compiler recognizes a pattern, it could quickly look up the latest and greatest optimization.
- forrestthewoods 11y ago
  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.
  - saosebastiao 11y ago
    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-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
abledon 11y ago
p.s. The world finals of the e-sports game 'League of Legends' made by this company is happening this weekend. Last year's event generated more global viewers than the NBA final.
a3voices 11y ago
The biggest optimization would be to change their programming language.
- to3m 11y ago
  To...?
  - christianmann 11y ago
    Lisp, clearly. /s
    - Roodgorf 11y ago
      Real Optimizers use Fortran.
  - myth_buster 11y ago
    Assembly of course...
  - ojii 11y ago
    Javascript of course.
  - Twirrim 11y ago
    Go, of course. Or is it Rust this week? I forget..
- cosarara97 11y ago
  And use what language, in your opinion?
spawndog 11y ago
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 11y ago
  [deleted]
- lunchTime42 11y ago
  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?
  - RiotTony 11y ago
    You could, but I doubt it would have much of an effect on performance. Modern CPUs are ridiculously good at looking ahead and executing paths pre-emptively, meaning that branching is far less of an issue. On the older consoles, branching was a big issue, so that would have helped there.
- bmh100 11y ago
  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?
Nemo157 11y ago
Seems they don't want anyone using PIA to access their blog... Tried reconnecting and got denied again, had to switch endpoint country to actually get access. > Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.57.217). > Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.13.45).
- jdmichal 11y ago
  Or that's the end effect of having been attacked from those IP addresses, which I'm assuming are not unique to the user.
RiotTony 11y ago
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.
- Splines 11y ago
  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.
  - RiotTony 11y ago
    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.
- josephg 11y ago
  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<float> 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 bad.
  - 11y ago

279 points by sled 11y ago

>In our case we output the profile buffer to a file and read that into the visualization tool which is conveniently built into Chrome. (You can find more information about the tracing tool here and you can try it out by typing “chrome://tracing/” into your Chrome browser. It is designed for web page profiling, but the format of the input profile data is a simple json format that can be easily constructed from your own data.) Clever! Never heard of doing that but it makes sense.

Drdrdrq 11y ago
Another term for these profiling charts in Chrome is flame charts, you might be able to find even more tools by it.
- cbab 11y ago
  Yup, basically Chrome is using an inverted flame graph (See [1] for additional infos and tools). [1] - https://github.com/brendangregg/FlameGraph https://github.com/brendangregg/FlameGraph

mmanfrin 11y ago

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/smite_damage_should_be_shown_on_the_icon/ https://www.reddit.com/r/leagueoflegends/comments/2hvukl/smi...)

bpicolo 11y ago
"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.
- mmanfrin 11y ago
  This is one of many such issues -- one of the largest complaints about the game from the community is the stability of the game and the frequency with which 'gamebreaking' bugs occur. e: Addressing your edit: 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. League is a mature game at this point, they have had a lot of time to fix longstanding issues. This isn't 'release day' woes.
- huac 11y ago
  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.
  - mmanfrin 11y ago
    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.
- debacle 11y ago
  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.
  - ajkjk 11y ago
    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.
Sevzinn 11y ago
Video games programmers have to learn more and make less. I'll give them the benefit of the doubt, especially since I can barely understand this particular blog post.

debacle 11y ago

Dota 2 has custom games now. Maybe they can write the new client in Hammer.

saosebastiao 11y ago

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 techniques, but refuse to implement most of them for what I would consider to be the ultimate copout ever: Compile times. I don't know about you, but I would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization. I'm not sure who wouldn't, especially if it also allows you to eliminate technical debt, eliminate leaky abstractions, and improve code comprehensibility. 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 that range from removing redundant elements from struct definitions all the way down to bitshift optimizations like i * 28 == i<<4 + i<<3 + i<<2. And if I have to wait all day long for a release build of something, so be it.

shepardrtc 11y ago
There was a HN thread a day or two ago in which someone suggested the idea of a common, open source KV database where compiler optimizations could be stored and curated by a committee. So whenever a compiler recognizes a pattern, it could quickly look up the latest and greatest optimization.
forrestthewoods 11y ago
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.
- saosebastiao 11y ago
  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-compiler/ https://justindomke.wordpress.com/2009/02/23/the-stalin-comp... http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

abledon 11y ago

p.s. The world finals of the e-sports game 'League of Legends' made by this company is happening this weekend. Last year's event generated more global viewers than the NBA final.

a3voices 11y ago

The biggest optimization would be to change their programming language.

to3m 11y ago
To...?
- christianmann 11y ago
  Lisp, clearly. /s
  - Roodgorf 11y ago
    Real Optimizers use Fortran.
- myth_buster 11y ago
  Assembly of course...
- ojii 11y ago
  Javascript of course.
- Twirrim 11y ago
  Go, of course. Or is it Rust this week? I forget..
cosarara97 11y ago
And use what language, in your opinion?

spawndog 11y ago

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 11y ago
[deleted]
lunchTime42 11y ago
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?
- RiotTony 11y ago
  You could, but I doubt it would have much of an effect on performance. Modern CPUs are ridiculously good at looking ahead and executing paths pre-emptively, meaning that branching is far less of an issue. On the older consoles, branching was a big issue, so that would have helped there.
bmh100 11y ago
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?

Nemo157 11y ago

Seems they don't want anyone using PIA to access their blog... Tried reconnecting and got denied again, had to switch endpoint country to actually get access. > Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.57.217). > Error 1008 Access denied. The owner of this website (engineering.riotgames.com) has banned your IP address (108.61.13.45).

jdmichal 11y ago
Or that's the end effect of having been attacked from those IP addresses, which I'm assuming are not unique to the user.

RiotTony 11y ago

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.

Splines 11y ago
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.
- RiotTony 11y ago
  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.
josephg 11y ago
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<float> 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 bad.
- 11y ago