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

101–110 of 128 posts

Re: Random Acts of Optimization

#101

Post by fanf2 »

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.

Dynamic optimization of binary code is 25 years old or more. The first widely deployed JITs were for running binary executables on different architectures, such as the Mac 68k -> PowerPC transition. https://en.wikipedia.org/wiki/Binary_translation#Dynamic_bin...

Re: Random Acts of Optimization

#102

Post by Retra »

roel_v wrote: post #93
saosebastiao wrote: post #88

Earlier quoted context omitted.

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

I don't know what OP meant, but I could see some potential advantage to removeing fields from structs at interfaces. Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back.

Though it would probably take more time to rearrange things than it would to just do the original loop. The point is, you might be able to look at where the struct is used and change its structure when it moves in memory. If a function is a 'consumer' of structs, and doesn't need all the fields, there is no need to copy all the fields.

Re: Random Acts of Optimization

#103

Post by codesuki »

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.

Nice article! I totally agree with the iterated approach to optimization (and refactoring). Since I am casually playing LoL I hope you will make it better and better ;)

Talking about optimization, I always wonder why some people have those veeery long loading times. Actually I wonder what is loaded at all. Effects or something? Of course I have no idea of the insides of the game but looking from the outside the map and models should be easily cached.

It would be great to hear more about those loading challenges!

Re: Random Acts of Optimization

#104

Post by roel_v »

Retra wrote: post #102
roel_v wrote: post #93

Earlier quoted context omitted.

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

I don't know what OP meant, but I could see some potential advantage to removeing fields from structs at interfaces. Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back. Though it would probably take more time to rearrange things than it would to just do the original loop. The point is, you might be able to look at where the struct is use…

"Say you have a loop that goes over a million structs, but only accesses one field. Drop the extras, do the loop, then add them back."

Why? Why would you copy at all? Are you saying that with small structs you'll be able to fit more of your data into caches? I haven't timed it (anyone have 20 minutes to spare?) but then you have to make full copy, very expensive not to mention having major implications on memory usage. If my compiler would do that under the hood, even when set to 'optimize for speed', I'd be pretty annoyed. The only way to know if such a thing is faster, is by looking at each use specifically - at which point we're not talking about a compiler anymore. Well ok we'd be talking about "runtime pgo", and approaching JIT territory.

Furthermore, such an 'optimization' would also have to, e.g., detect offsetof() and make sure that that works correctly, and account for packing and people relying on that, and unions, etc etc. I'm not going to spend much time here further on examining and deconstructing this whole concept, especially as I still fail to comprehend the goal.

Re: Random Acts of Optimization

#105

Post by WalterBright »

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 would take 100x increase in compilation times for a release build over a 2x increase in development time due to manual optimization.

I'd implement that if I knew about such optimization technology, and I bet other compiler guys would, too.

Re: Random Acts of Optimization

#106

Post by bhrgunatha »

roel_v wrote: post #92
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…

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

> Compiling is 'trivially' (for some values of that word) parallelizable.

Really? I've always heard that it's virtually impossible to parallelize. Or do you mean a particular step in the pipeline can be parallelised - like parsing separate source files?

Re: Random Acts of Optimization

#107

Post by WalterBright »

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 really don’t like that.

Unfortunately, the nature of optimizations makes tracking these sorts of things really hard. They don't occur in a vacuum - nearly every optimization transformation interacts with a dozen other transforms, sometimes with very surprising (and usually counterproductive) results.

If you simply implement "book" optimizations, you'll find that they often don't even work without some considerable re-engineering from the bottom up. Many book optimizations make the code slower. And then there are the myriad of optimizations that make code faster on one CPU and slower on the next release of that CPU.

If you think that compiler optimizer writers are holding out on you, they aren't. It's a bit of an arcane art, like samurai sword making technique.

Re: Random Acts of Optimization

#108

Post by astrange »

comex wrote: post #49
astrange wrote: post #42

Earlier quoted context omitted.

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

Right, but browsers are pretty important, and a lot of apps are just web views. (Can't remember if JIT works in web apps on iOS these days though.)

They also load all that crazy ad tracking javascript from everywhere, optimizing that on every page load has power costs!

Re: Random Acts of Optimization

#110

Post by cbab »

Drdrdrq wrote: post #52
885895 wrote: post #2

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

Another term for these profiling charts in Chrome is flame charts, you might be able to find even more tools by it.

Yup, basically Chrome is using an inverted flame graph (See [1] for additional infos and tools).

[1] - https://github.com/brendangregg/FlameGraph

Post reply on HN