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

61–70 of 128 posts

Re: Random Acts of Optimization

#61

Post by haberman »

saosebastiao wrote: post #37
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.

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 error path? They just look like regular conditionals.

> In those cases, we accept heuristic substitutes, of which both JITs and PGO have shown good results.

JIT and PGO aren't heuristic, they are based on measurement. By your logic, if I look at the speedometer in my car that is just a "heuristic" of my speed. It's not a heuristic, it's an empirical measurement.

Re: Random Acts of Optimization

#62

Post by kibwen »

johncolanduoni wrote: post #59
joosters wrote: post #53

Earlier quoted context omitted.

Please show us some of these promised optimizations. I don't think they actually exist. 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 make these choices for themselves. Besides which, compilers can already select slow or fast optimizations on the command line, so users can minimize…

Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which a…

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

Re: Random Acts of Optimization

#63

Post by johncolanduoni »

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…

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

I think the reason dependent types haven't made it into practical programming has less to do with them being not ready and more to do with them being fundamentally challenging to learn. I have a pretty strong pure math background and it still took me a significant amount of time to wrap my head around them to the point that I could write non-trivial proofs using them, let alone programs. For programmers who have never done much formal logic or who have never heard of a category, I can't imagine how much time it would take to get the prerequisite knowledge.

Another issue is the fundamental problem of creating a new language; you have to build up a ton of extra machinery (libraries, tooling, etc.) to even think about it becoming more than a toy, even if you don't care about it being mainstream. Rust has the backing of a large open-source company and a ton of really smart people dedicated to bringing it to primetime, but it is still going to take a long time for it to get there. Dependently typed languages like F* and Idris don't have the same manpower behind them and also have to face fundamental challenges like integrating formally verified code with a world full of unverified (but useful) code.

Re: Random Acts of Optimization

#64

Post by andrepd »

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?

Re: Random Acts of Optimization

#65

Post by johncolanduoni »

kibwen wrote: post #62
johncolanduoni wrote: post #59

Earlier quoted context omitted.

Not the OP, but one I think about a lot is converting functional, monadic code that uses first class functions/closures to equivalent imperative variants. For example, manipulating collections with functions like map, flatMap, filter, etc. has become common, even in popular imperative languages like C# and Java. These calls are can be chained together to create non-strict sequences (IEnumerable, Stream, etc.) which a…

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.

Re: Random Acts of Optimization

#66

Post by temo4ka »

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

Some people continue to write JavaScript in such a way: https://github.com/greensock/GreenSock-JS/blob/1.18.0/src/un...

Re: Random Acts of Optimization

#67

Post by siegecraft »

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.

Re: Random Acts of Optimization

#68

Post by ralphael »

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.

thanks for the article Tony. Loved it, really enjoyed the detail you went into. Look forward to more.

Re: Random Acts of Optimization

#69

Post by sled »

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?

Re: Random Acts of Optimization

#70

Post by vitalyd »

haberman wrote: post #25
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…

> 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.
Post reply on HN