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

81–90 of 153 posts

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

#81

Post by jasonthorsness »

AaronAPU wrote: post #80
tikotus wrote: post #34

I once had this kind of body recovery/stress level measuring thingy on me for a few days, and a doctor would then analyze my health and such. I was under some stress those days and (according to the measurements) I wasn't recovering properly even during the nights. But then there was this one, long, flat, deep green curve in the middle of my work day. I checked from my VCS what I was doing during that period: I was o…

I spent 10 years straight doing C++ and assembly optimization. My work is still fun these days but that was probably the most enjoyable work of my career in terms of the actual day to day coding. Code cleanup in general is the same for me, but it’s really hard to justify putting much time into that when running your own company solo.

What tools did you use to assess the results of your changes?

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

#82

Post by inetknght »

Performance optimization isn't a brute-force task. It just (currently) requires a lot of skill, and it's hindered by terrible documentation; performance in software is only a brute-force task because 99% of software don't tell you what their performance impacts are.

In C++, you can achieve performance using the often-denigrated standard template library, if you would only pay attention to the documented performance requirements for given function calls. But even there it's not the panacae that it could be, because it often provides an amortized cost while handwashing the access pattern (for example: std::unordered_map is great in algorithmic cost theory and terrible in memory access patterns).

What's the algorithmic cost (big-O) of this function call? What's the memory footprint of that function call? Worse: is that documented big-O estimated across a contiguous dataset, discontiguous paged datasets, or does it have to dereference pointers? What's the network cost of a given call? It's hard to know if you don't know that `write()` to a socket could incur 40 or 400 bytes across a network, and don't know whether that network is 1mbps, 10mbps, 1gbit, or localhost, etc; and with how much latency.

For example, when I hand-rolled some x86_64 SIMD instructions to analyze some DNA, I found the Intel Intrinsics Guide [0] 1000% helpful because many of the instructions detailed what sort of performance to expect on specific processor architectures (or, at least, in general). If you read the Intel Instruction Set Reference [1], a lot of similar performance information can be found. The performance I achieved was approximately the theoretical bottleneck between CPU and main RAM; getting better performance would have required a complete algorithm change which would have been Ph.D paper publishing worthy.

Of course, sometimes even low level hardware can have performance-killing bugs.

[0]: https://www.intel.com/content/www/us/en/docs/intrinsics-guid...

[1]: https://www.intel.com/content/www/us/en/developer/articles/t...

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

#83

Post by purplesyringa »

inetknght wrote: post #82

Performance optimization isn't a brute-force task. It just (currently) requires a lot of skill, and it's hindered by terrible documentation; performance in software is only a brute-force task because 99% of software don't tell you what their performance impacts are. In C++, you can achieve performance using the often-denigrated standard template library, if you would only pay attention to the documented performance r…

I don't think we're in disagreement. You have to consider big-O cost, memory footprint, exact numbers, know what performance to expect from various abstractions, etc. -- and then you need to choose between multiple alternatives. The first half of this process is absolutely skill-based, but I'm arguing that when you're trying to push performance to its limit, the second half unavoidably becomes expensive and brute-forcy.

For example: do you compression data sent over the network? What level of compression do you use? Changing the data format can affect the optimal compression level, and vice versa, using a higher compression level means you can keep the underlying data simpler. For example, you can replace deserialization with zero-cost casts. But that might mean you spend more memory. Do you have that much memory? If you do, would giving that memory to the database for use as cache be better? And so on.

The individual choices are simple, but they compound and affect the overall performance in unpredictable ways. The only way to be sure you aren't missing something obvious is to check all, or at least most combinations.

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

#84

Post by optymizer »

tikotus wrote: post #34

I once had this kind of body recovery/stress level measuring thingy on me for a few days, and a doctor would then analyze my health and such. I was under some stress those days and (according to the measurements) I wasn't recovering properly even during the nights. But then there was this one, long, flat, deep green curve in the middle of my work day. I checked from my VCS what I was doing during that period: I was o…

I see you.

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

#85

Post by nostrademons »

This is coming from the perspective of a performance engineer whose day job is squeezing every last bit of performance out of system libraries and low-level code. This is important work, and it can pay very well if you get one of the few positions in it. But for an application developer whose primary day job is cranking out features and then spending 10% of the time at the end optimizing them, the conclusion (and the headline) very much does not hold.

For them, the systematic way to optimize goes: profile your code, and then apply domain knowledge of the product to optimize the hotspots with these common techniques:

Don't do repeated work. (If you have an expensive invariant calculation in a loop or function call, move it out, to a higher level of the program where it can be done once.)

Save your work. (Caching and memoization.)

Do less work. (Alter the product requirements to use less computationally-intensive techniques in cases where users won't notice the difference.)

Do work when the user isn't looking. (Move computations to background tasks, apply concurrency, perform async requests.)

If all else fails, call in a performance engineer like the author to micro-optimize your building blocks.

You can often get speedups of 3-6 orders of magnitude by applying these techniques, simply because the original code is so brain-dead. Performance engineers like the author tend to work on code that has already been tightly optimized, and so there is less low-hanging fruit to pick.

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

#86

Post by AaronAPU »

jasonthorsness wrote: post #81
AaronAPU wrote: post #80

Earlier quoted context omitted.

I spent 10 years straight doing C++ and assembly optimization. My work is still fun these days but that was probably the most enjoyable work of my career in terms of the actual day to day coding. Code cleanup in general is the same for me, but it’s really hard to justify putting much time into that when running your own company solo.

What tools did you use to assess the results of your changes?

The routines were individually benchmarked using some custom tools (iterate repeatedly and use statistical analysis to converge on an estimate). Always compared against a plain C reference implementation.

Then there was a system for benchmarking the software as a whole on a wide variety of architectures, including NUMA. With lots of plots and statistics.

Usually you’d eventually end up at a point where the improvements are below the noise floor or they help on some systems and cause regression on others. The rule was usually “no regressions”

VTune for multithreading optimization. Built a fibers and lockfree system for efficient scheduling.

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

#87

Post by mnahkies »

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…

I think there's a related problem where profiling/measurements can be made poorly and not reflect the real world.

Eg: indexing or partitioning a database table may appear to make things slower if you don't have both a representative amount of data and representative query patterns when you're measuring the change.

You should still measure your changes, but sometimes you need to be careful about measuring them in the right way, and possibly simulating a future context (eg: more scale) before drawing a conclusion.

Intuition about how the context will evolve and what effect that might have on the tradeoffs of different approaches is helpful

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

#88

Post by scratcheee »

necovek wrote: post #76
purplesyringa wrote: post #59

Earlier quoted context omitted.

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…

"Intuitively" literally means without having to learn something. Adding caches or switching to lower-level calls is definitely something learned, and I wouldn't call it "intuitive". What I think you are referring to is that sometimes, simply reading and understanding the code can tell you where the problem really is — still, my experience is that you want to measure the before and after to at least identify the gener…

And yet their statement makes perfect sense to me.

Caching and lower level calls are generic solutions that work everywhere, but are also generally the last and worst way to optimise (thus why they need such careful analysis since they so often have the opposite effect).

Better is to optimise the algorithms, where actual profiling is a lesser factor. Not a zero factor of course, as a rule of thumb it’s probably still wise to test your improvements, but if you manage to delete an n^2 loop then you really don’t need a profiler to tell you that you’ve made things better.

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

#89

Post by almostgotcaught »

purplesyringa wrote: post #61
almostgotcaught wrote: post #19

Earlier quoted context omitted.

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

i have no idea what that has to do with what op quoted from your article:

> 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 manifestly obviously possible (as i've said).

what you're talking about is something completely different goes by many names and uses many techniques (symbex, conex, sccp, scev, blah blah blah). many of these things are implemented in eg LLVM.

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

#90

Post by MoonGhost »

loeg wrote: post #30

This is like, tip of the spear stuff, and that's very cool. But in most of the software world, I would argue, performance optimization is knocking out extremely low-hanging, obvious fruit -- it's relatively obvious what's slow, and why, and just picking any of N better approaches is good enough to eliminate the problem.

In big projects it's not that obvious. I've seen people optimizing for their desktop applications which are intended for server. It's nice for progress reporting though.
Post reply on HN