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

61–70 of 153 posts

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

#61

Post by purplesyringa »

almostgotcaught wrote: post #19
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 d…

I was going for something different: I don't want to choose a different implementation in runtime, I want the compiler to see through my code and apply constant propagation -- not just for constant inputs, but inputs with known properties, like `n m` function always returns `m` such that `m^2 <= n`. None of this is possible with runtime selection because runtime selection was never the point.

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

#63

Post by hinkley »

tmoertel wrote: post #53
jmward01 wrote: post #22

I have almost always found that simple code runs faster than complex code. I think this is because optimization is likely an NP problem and like all NP problems, the best algorithm we have for solving it is divide and conquer. The core thing about D&C is that you divide until you reach a level that you can actually find the optimum answer within the resources given but accept that by dividing the problem you will lik…

I think that there is a different reason that an emphasis on simple code often results in faster systems. When you write simple code, you spend less time writing code. Therefore, you have more time left to invest in optimizing the very small subset of your overall system that actually matters. You didn't burn engineering resources for speed where it didn't matter.

Simplifying complex code often exposes optimization opportunities. Kernighan’s Law applies to performance as well as debugging.

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

#65

Post by jmward01 »

tmoertel wrote: post #53
jmward01 wrote: post #22

I have almost always found that simple code runs faster than complex code. I think this is because optimization is likely an NP problem and like all NP problems, the best algorithm we have for solving it is divide and conquer. The core thing about D&C is that you divide until you reach a level that you can actually find the optimum answer within the resources given but accept that by dividing the problem you will lik…

I think that there is a different reason that an emphasis on simple code often results in faster systems. When you write simple code, you spend less time writing code. Therefore, you have more time left to invest in optimizing the very small subset of your overall system that actually matters. You didn't burn engineering resources for speed where it didn't matter.

I'd argue that is a big part of the point I am making. If you take too big of a bite the time it takes to build it optimally goes up in an NP manor. If the bites are the right size then it balances the time/resources you have compared to all the other bites you make to get a locally optimal answer given all resource constraints. Long story short, cutting a problem into manageable pieces is a solid strategy. I will add one thing though, and that is that most people think they have cut things into manageable pieces but in reality they have left them too intertwined and they aren't really independent pieces. For divide and conquer to actually work requires that the pieces have clearly defined, and very limited, communication.

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

#66

Post by purplesyringa »

oqtvs wrote: post #18

Question coming from the article: what would be better tooling instead of profilers and MCA?

I'd love to use a tool that shows the state of every CPU component at each point in time. Performance counters demonstrate global behavior, while what actually matters during optimization is local behavior. I'd like to be able to inspect pipeline stalls and conditions that led to these situations, I'd like to get an estimate on the efficiency of port allocation, I'd like to be able to compare the rate of memory accesses vs computation and get exact numbers, e.g. "you can access 20% more data over the bus without adding CPU stalls".

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

#67

Post by [deleted] »

mystified5016 wrote: post #38
9rx wrote: post #28

Earlier quoted context omitted.

Well, he's saying that intuition does work... But does it really? If a problem area is so intuitively obvious, why would you introduce the problem in the first place? In reality, performance optimizations are usually needed where you least expect them. Which means that you can't get there intuitively. Hence, the suggestion of using profiling to help track down where the problem is instead.

Do you want to claim you've never written quick and ugly code to get something working to come back and fix it up later? Pretty much everyone I know will throw down an O(n^2) algorithm or whatever in their first pass and replace it with something more thought out once they have the time to think deeply about it. If you're fretting about optimization at every stage of development, you're really doing it wrong. This is…

[deleted]

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

#68

Post by hinkley »

ForOldHack wrote: post #47

The word is 'Grock' you have to Grock the performance to optimize it. My father had a PhD in Operations Research/Industrial Engneering.

> Grock

Grock was a famous Swiss clown and once the highest paid entertainer in Europe.

The non-clown word you’re looking for is grok and Robert Heinlein coined it in 1961.

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

#69

Post by Capricorn2481 »

purplesyringa wrote: post #59
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…

You're right, I could've phrased that better. Profiling to find suboptimal code is perfectly fine. Then you need to figure out how to fix it. Many people don't understand how performance optimization works, so they blindly add caching, improve constant time by invoking more low-level methods, etc. This obviously doesn't work, yet intuitively (to those people, anyway) it should produce good results. That's why the man…

Sounds like a tricky balancing act. There are things that are extremely difficult to "game out." CPUs are very complicated. There are optimizations that seem like they could be cache friendly in theory, but aren't in practice.

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

#70

Post by purplesyringa »

trhway wrote: post #44

>Performance optimization is hard because it’s fundamentally a brute-force task, and there’s nothing you can do about it. fundamentally disagree. First it is a building of a mental model of what happens, a kind of analysis stage, and then compare it to the mental model of how it should or could work or producing a more efficient algorithm/way of accomplishing the target task. When people try to brute-force, lets try…

The problem is that way too often, the model simply doesn't capture enough complexity to be applicable. This happens rarely during high-level optimization but is very common during microoptimization. You can build a model, and it will give you good enough results, but you won't be able to extract those last bits of performance you need to surpass SOTA.
Post reply on HN