Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Performance optimization is hard because it's fundamentally a brute-force task

purplesyringa.moe

Post reply on HN
Print view View original

11–20 of 153 posts

Re: Performance optimization is hard because it's fundamentally a brute-force task

#11

Post by ttd »

secondcoming wrote: post #10
ttd wrote: post #9

Good article that I agree with mostly. One interesting note is this: > There is no way to provide both optimized assembly and equivalent C code and let the compiler use the former in the general case and the latter in special cases. This is true, but can be seen as a failure of language and tooling. For example, Halide [1] pioneered (AFAIK) the concept of separating algorithm from implementation at the language level…

gcc supports function multiversioning: https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....

This is useful but not equivalent. Using this type of tooling you still have to write the algorithm itself in N versions. Changing the algorithm then requires changing all N implementations. This contrasts with the Halide approach where the algorithm is written once, and then schedules can be modified without worrying that you are changing the algorithm itself.

Re: Performance optimization is hard because it's fundamentally a brute-force task

#12

Post by hansvm »

> too many cases to analyze

One of my early-career successes was just creating a framework for generating every permutation of perf optimizations for every (log-scaled -- clz is very fast) input size and checking which was best, dropping the results into a lookup table of function pointers to branch on. The university had a large supply of heterogeneous computers, replete with all the normal problems like being able to double floating-point addition throughput on Haswell CPUs by abusing the fmadd instruction, so I made a framework (probably closer to a DSL) for encoding your algorithms in a way that you could analyze perf tradeoffs at compile time and tune your result for the given computer. It's kind of like what ATLAS does for some linear algebra tasks.

Such practices are almost never optimal, but they're pretty easy to implement, and the results are near-optimal for almost all inputs. In the tradeoff between human and computer performance, I think it's a nice option.

Re: Performance optimization is hard because it's fundamentally a brute-force task

#13

Post by jmull »

> I dislike the “intuition doesn’t work, profile your code” mantra because it seemingly says profiling is a viable replacement for theoretical calculations, which it isn’t.

This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan?

Measuring/profiling just means observing the system you want to optimize in a systematic way. You certainly won't be very effective at optimizing anything if you don't observe it.

Theoretical calculations means you've formed a model of what's happening and you're devising a plan to optimize against that model. But of course, a useful model needs to represent the significant aspects of your system (and a good model should exclude most insignificant ones). Failing to observe your system means your model could be bad -- focused on insignificant aspects and missing significant ones -- and you'd never know.

Re: Performance optimization is hard because it's fundamentally a brute-force task

#15

Post by klysm »

jmull wrote: post #13

> I dislike the “intuition doesn’t work, profile your code” mantra because it seemingly says profiling is a viable replacement for theoretical calculations, which it isn’t. This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan? Measuring/profiling just means observing the system you want to optimize in a systematic way. You certainly won't…

I think what he’s saying here is you can’t skip the basic math step to arrive at good performance. Staring at profiling results will lead you to a local minima

Re: Performance optimization is hard because it's fundamentally a brute-force task

#16

Post by jmull »

klysm wrote: post #15
jmull wrote: post #13

> I dislike the “intuition doesn’t work, profile your code” mantra because it seemingly says profiling is a viable replacement for theoretical calculations, which it isn’t. This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan? Measuring/profiling just means observing the system you want to optimize in a systematic way. You certainly won't…

I think what he’s saying here is you can’t skip the basic math step to arrive at good performance. Staring at profiling results will lead you to a local minima

Yeah, that's why I think it's nonsense.

Measuring doesn't mean don't think. Measuring and thinking are two different things. You need to do them both to optimize effectively.

Re: Performance optimization is hard because it's fundamentally a brute-force task

#17

Post by Joel_Mckay »

klysm wrote: post #15
jmull wrote: post #13

> I dislike the “intuition doesn’t work, profile your code” mantra because it seemingly says profiling is a viable replacement for theoretical calculations, which it isn’t. This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan? Measuring/profiling just means observing the system you want to optimize in a systematic way. You certainly won't…

I think what he’s saying here is you can’t skip the basic math step to arrive at good performance. Staring at profiling results will lead you to a local minima

Or optimizing a scheduling noop loop dozens of times given local encapsulation obscures global functional context.

The fact remains most projects that do small trivial modular prototypes first will ultimately know which paths are viable before painting themselves into a corner algorithmically.

Best of luck =3

Re: Performance optimization is hard because it's fundamentally a brute-force task

#19

Post by almostgotcaught »

ttd wrote: post #9

Good article that I agree with mostly. One interesting note is this: > There is no way to provide both optimized assembly and equivalent C code and let the compiler use the former in the general case and the latter in special cases. This is true, but can be seen as a failure of language and tooling. For example, Halide [1] pioneered (AFAIK) the concept of separating algorithm from implementation at the language level…

> Halide [1] pioneered (AFAIK) the concept of separating algorithm from implementation at the language level.

you don't need to go all the way to Halide to do what the article is claiming isn't possible - you can do it just by including a "micro-kernel" in your library and have the code branch to that impl (depending on something at runtime) instead of whatever the C code compiled down to. this is done every single day in every single GPU lib (famously cublas ships with hundreds/thousands of these of such ukernels for gemms depending on shapes).

Re: Performance optimization is hard because it's fundamentally a brute-force task

#20

Post by titzer »

jmull wrote: post #13

> I dislike the “intuition doesn’t work, profile your code” mantra because it seemingly says profiling is a viable replacement for theoretical calculations, which it isn’t. This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan? Measuring/profiling just means observing the system you want to optimize in a systematic way. You certainly won't…

No amount of measuring and squeezing--not even years of it--is a subsitute for high-level thinking. And vice versa.

Imagine: function F() { for (i = 0; i If we profile this code, we might find out, e.g. B takes the majority of the time--let's say 90%. So you spend hours, days, weeks, making B 2X faster. Great. Now you removed 45% of execution time. But the loop in the outer function F is just a few instructions, it is not "hot"--it won't show up in profiles except for ones that capture stacks.

If you're just stuck in the weeds optimizing hot functions that show up in profiles, it's possible to completely overlook F. That loop might be completely redundant, causing 10X the workload by repeatedly computing A, B, and C, which may don't need to be recomputed.

There are bazillions of examples like this. Say you find out that a function is super, super hot. But it's just a simple function. There are calls to it all over the code. You can't make it any faster. Instead you need to figure out how to not call it at all, e.g. by caching or rethinking the whole algorithm.

> How could measuring be a substitute for thinking/analyzing/predicting/forming a plan?

This happens more than you think. Understanding how the system works in enough detail and also at a high level to formulate a plan is in short supply. Jumping in and hacking in things, like a cache or something, is surprisingly common.

Post reply on HN