7 ms·

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

303 points by todsacerdoti 2y ago

MatthiasWandel 2y ago
An interesting aspect is data dependencies. If your next statement reuses data you just computed, that can cause pipeline bubbles, as that result you want to use just isn't available yet. I dived into that topic for a video about relative performance of old PCs I just published today.
- jandrewrogers 2y ago
  Yes, there is non-obvious structure in some algorithms solely for the purpose of turning a single logical stream of dependent instructions into multiple concurrent streams of dependent instructions running through the same pipeline. The caveat of doing this, of course, is that it typically increases register pressure.
willvarfar 2y ago
I think it is worth making a distinction between "micro" (what the blogpost is about) and "macro", or "tactical" and "strategic", optimisations. Strategic optimisations is often basically free if you have domain expertise. It's that easy to know that the business wants x outcome and algorithm y is the right choice etc if its all internal thought processes. Whereas if you don't know enough then you're likely to make very expensive to undo decisions.
- jandrewrogers 2y ago
  I often refer to those as architectural optimizations. Even some of these tend to sensitive to the details of the operating environment.
raluk 2y ago
For low level benchmarking papi https://icl.utk.edu/papi/ https://icl.utk.edu/papi/ is great tool. It provides access for counters like cache misses, branch misses and number of cycles.
PaulKeeble 2y ago
When it comes to micro optimisations the issue is partly our usual tools in algorithm analysis and hardware intuition are very far apart. Random accessing memory is very slow compared to linear, some branches are considerably worse than others and it's actually quite hard to predict how much you can improve the low level details before you start, especially for big changes. Our tools can show us where time is being lost in inefficiencies but can't help us predict how changes will improve things.
enescakir 2y ago
The hardest bugs are the ones that only show up after you “optimize.”
- hinkley 2y ago
  The ones that only happen when you remove the debug statements are super fun.
ttd 2y ago
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. This separation lets you express the algorithm once, and then "schedule" it by specifying parallelism, vectorization, etc. You can provide multiple schedules for one algorithm, which allows you to specialize / make different choices depending on varying factors. It's a really interesting concept, though maybe limited in practice to DSLs. I'm not sure a general purpose language would be a good fit for this model, but then, for general purpose programs written in general purpose languages, perf optimization at the level TFA discusses is frequently limited to just specific hot sections. Those hot sections could be extracted out into specialized components written in such a DSL. 1 - https://halide-lang.org/ https://halide-lang.org/
- secondcoming 2y ago
  gcc supports function multiversioning: https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning.html https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....
  - ttd 2y ago
    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.
- almostgotcaught 2y ago
  > 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).
hansvm 2y ago
> 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.
jmull 2y ago
> 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.
- klysm 2y ago
  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
  - jmull 2y ago
    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.
  - Joel_Mckay 2y ago
    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
  - deleted 2y ago
    [deleted]
  - cogman10 2y ago
    Profiling doesn't mean you don't do the math. Profiling is simply there to show you that "hey, this is where the problems actually are". You do profiling because it's WAY too easy to get obsessed about theoretical problems when a simple measurement will show you the actual problems. You do the math on the actual problem location, not a method with O(n!) which only gets called with n=3. You still have to look at the entire call stack when profiling (which means thinking about the overarching algorithm).
mannyv 2y ago
Optimization is hard work because you need to understand how things work to be effective. It's really just debugging and troubleshooting, but with a different goal in mind.
oqtvs 2y ago
Question coming from the article: what would be better tooling instead of profilers and MCA?
- purplesyringa 2y ago
  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".
  - Sesse__ 2y ago
    FWIW, VTune will definitely give you estimates of port allocation efficiency. (I believe you can also somehow squeeze it out of perf, but I've never really tried.)
jmward01 2y ago
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 likely have some high level inefficiencies. This means simple code, code you understand all pieces of, can actually be locally optimum. When I see people try to optimize code I often see them fall into that trap of optimizing too large/complex a problem which leads to them not actually being able to find a true local optimum and, often, making far slower code than had they just tried for much simpler code. This likely NP behavior runs rampant in software development where we often think we can design some elaborate process to design things and when things fail it was because people failed to follow the process and not because the problem was NP. We all love building machines which is why we likely do this, but unless you know something the rest of the world doesn't then D&C, and admitting you are only looking for a local optimum, is the only algorithm we have for attacking NP problems. (Shameless plug here for smaller, far more autonomous teams instead of monolithic dev shops with one big shared feature list)
- tmoertel 2y ago
  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.
  - hinkley 2y ago
    Simplifying complex code often exposes optimization opportunities. Kernighan’s Law applies to performance as well as debugging.
    - tmoertel 2y ago
      Indeed!
deleted 2y ago
[deleted]
loeg 2y ago
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.
- MoonGhost 2y ago
  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.
interactivecode 2y ago
While actually measuring and profiling is great. In my experience most webapps can fix so much low hanging performance issues by mapping the API in a way that matches how its used in the client. It can remove so much mapping and combining for data all over.
Misdicorl 2y ago
I'll throw my hat in the ring for "disagree". Few kinds of work have such clear and unambiguous results as optimization work (its now X% faster!). Few kinds of work have such incredible and detailed tools to guide your hand in finding where to invest your effort (look at this hot loop!). The fact that sometimes optimization work is tricky or requires some pre-thinking, or is even gasp counter-intuitive is such a hilarious way to say "this is hard". That's just table stakes starting points for so-so-so much work. Edit: Heck, even deciding whether to prioritize optimization work or feature work is usually a harder problem than the actual optimization work itself.
- saagarjha 2y ago
  Performance optimizations are usually tradeoffs. Which ones you make affect the outcome.
tikotus 2y ago
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 optimizing. I've since noticed this many times. Optimizing is like meditation to me. It's very mechanical (measure), with a sprinkle of creative work (once you know what is slow, it's quite obvious how to make it faster, but just challenging enough to be engaging), and it has a very nice tight feedback loop: Something is slow. I make a change. Now it's fast. Next. Optimizing is my happy place.
- 01HNNWZ0MV43FF 2y ago
  I remember one fun time between jobs, that I stayed up till 4 or 5 am optimizing something. It always felt like I was making progress and about to beat the original implementation Unfortunately I had to give up when I was still 10 times slower than the reference lol
  - senderista 2y ago
    Same here, last time I was between jobs I optimized my defunct startup's database from ~50K TPS to nearly 5M TPS (no durability, if you're wondering), and that was unbelievably rewarding.
- toomuchtodo 2y ago
  https://en.wikipedia.org/wiki/Flow_(psychology) https://en.wikipedia.org/wiki/Flow_(psychology) https://en.wikipedia.org/wiki/Biofeedback https://en.wikipedia.org/wiki/Biofeedback
- AaronAPU 2y ago
  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.
hinkley 2y ago
It’s like dieting. Everyone wants to hear your one weird trick and zones out when you tell them it’s hard work. Yes, mechanical sympathy is a thing but usually pulling off a series of wins isn’t luck or particularly bad work by your peers, it’s being methodical and persistent. It’s about being stubborn as fuck, and not taking no for an answer.
trhway 2y ago
>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 this or this, without having the model in mind, that is frequently a waste, and even when/if it produces some improvement there is no understanding and guarantee what use cases the improvement will cover, whether it would regress some use cases, whether it still be there after we push those new features/fixes/etc.
- purplesyringa 2y ago
  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.
  - Mawr 2y ago
    Sure, but that's a different statement. "Micro performance optimizations are fundamentally brute force" - ok.
ForOldHack 2y ago
The word is 'Grock' you have to Grock the performance to optimize it. My father had a PhD in Operations Research/Industrial Engneering.
- hinkley 2y ago
  > 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.
karmakaze 2y ago
I agree with many of the comments here including some of the ones that are in disagreement. The difference is context where for most situations the starting point is far from optimal and the any of N better choices is a good improvement. That doesn't seem to be what this post it talking about. It seems to talking about well worn areas trying to improve the state of the art. An example that illustrates it for me is DeepMind's AlphaTensor finding a better way to multiply matrices[0] in 2022. It wasn't a brute-force solution, but the scale of it makes it appear so. > On 4x4 matrices, AlphaTensor unexpectedly discovered a solution with 47 multiplication steps, an improvement over the 49 required with Strassen’s algorithm of 1969, albeit restricted to mod 2 arithmetic. Similarly, AlphaTensor solved 5x5 matrices with 96 rather than Strassen's 98 steps. Based on the surprising discovery that such improvements exist, other researchers were quickly able to find a similar independent 4x4 algorithm, and separately tweaked Deepmind's 96-step 5x5 algorithm down to 95 steps in mod 2 arithmetic and to 97[24] in normal arithmetic.[25] Some algorithms were completely new: for example, (4, 5, 5) was improved to 76 steps from a baseline of 80 in both normal and mod 2 arithmetic. This to me shows that direct profiling and observation wouldn't have led to the optimization. Improvements needed a sort-of but not actually brute-force effort of many people trying, but also being clever with their attempts. [0] https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
deleted 2y ago
[deleted]
compiler-guy 2y ago
From the article: "Even Apple’s LLVM fork lacks scheduling annotations for Apple Silicon. How am I supposed to write efficient code when Apple doesn’t bother to tune their own compiler?" In addition to its public fork of LLVM, Apple also keeps a very private fork where (one assumes) they keep all the really juicy stuff. I agree that it is frustrating not to have the data, but don't confuse "I don't have the data" with "no one has the data".
deleted 2y ago
[deleted]
inetknght 2y ago
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-guide/index.html https://www.intel.com/content/www/us/en/docs/intrinsics-guid... [1]: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html https://www.intel.com/content/www/us/en/developer/articles/t...
- purplesyringa 2y ago
  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.
nostrademons 2y ago
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.
Validark 2y ago
"Register pressure is even worse because that is only a problem because of the ISA, not the microarchitecture." I'm not so sure. How many cycles would you expect this code to take? mov dword [rsi], eax add dword [rsi], 5 mov ebx, dword [rsi] According to Agner Fog, these 3 instructions have a latency of 15 cycles on an AMD Zen 1 processor. On Zen 2, its latency is 2 cycles. This is because the CPU was given the ability to assign a register to `dword [rsi]`, overcoming the limit of 16 registers. This optimization is subject to problems, obviously pointer aliasing will enable the CPU to make the wrong assumption at times, and cause a situation not entirely unlike a branch mispredict. There are constraints imposed by the micro-architecture for this feature. For you and I, a big one is it only works with general purpose registers. But is there a reason it couldn't or shouldn't be done for vectors? It seems like a micro-arch issue to me. Perhaps in a few years or in a lot of years, we'll have a CPU that can do this optimization for vectors.
- purplesyringa 2y ago
  I learn something new every day! Thanks for mentioning this. For other readers: Agner Fog documents this in 22.18 Mirroring memory operands. I've known that similar optimizations exist, namely store-to-load forwarding, but I didn't know that AMD has experimented with mapping in-flight writes straight into the register file. Sounds like they've abandoned this approach, though, and Zen 3 doesn't feature this, supposedly because it's expensive to implement. So for all intents and purposes, it doesn't exist anymore, and it probably won't be brought back in the same fashion. I do still think this is something better solved by ISA changes. Doing this on the uarch level will either be flaky or more costly. It is absolutely possible, but only with tradeoffs that may not be acceptable. The APX extension doubles the number of GPRs and improves orthogonality, so there's at least work in that direction on the ISA level, and I think that's what we're realistically going to use soon.
pavelstoev 2y ago
Optimizing AI performance is like peeling an onion — every time you remove one bottleneck, another layer appears underneath. What looks like a compute problem turns out to be a memory bottleneck, which then turns out to be a scheduling issue, which reveals a parallelism mismatch… and so on. It’s a process of continuous uncovering, and unless you have visibility across the whole stack — from kernel to cluster — you’ll spend all your time slicing through surface layers with lots of tears being shed. Fortunately, there are software automation solutions to this.
- saagarjha 2y ago
  They’re not very good, unfortunately.
bddicken 2y ago
This was a great read - thanks!
Ygg2 2y ago
> Any developer can see that the following two snippets are (supposed to be) equivalent Being how I fall under any developer, I'm going to bite the bullet and ask: How are they supposed to be equivalent? One is a HashSet, other is boolean? And what is `c`.
- saagarjha 2y ago
  c is an arbitrary object. The first puts two numbers and checks if c is present, which is only true if c is equal to one of the two numbers.
  - Ygg2 2y ago
    I see. Luckily mobile phone cut `.contains(&c)` perfectly. And you see scrollbars only when you click the text.
somethingsome 2y ago
I teach my students to make a tree of the promising optimizations and suboptimization (it can be rough), keep track of each interesting optimizations, then implement the branch that seems the more promising and at each step use the profiler massively, memory bound, compute bound, latency bound, number of flops, cache accesses, etc.. After narrowing the smallest leaf, think about another branch and if some optimizations studied could lead to nice results there too. With time they learn which branch is more promising and which optimizations are good beforehand with their problem. I guess this could be called branch and bound with memoization instead of brute force aha. Note: we write code in cuda
rurban 2y ago
perf? I value -fopt-info more. The optimizer does crazy things all the time, and hereby you find out what exactly is optimized, de-optimized or needs work.
fuzzfactor 2y ago
I think her immediate recognition and characterization of "pessimizations" is relevant. Not so much as collateral damage when different optimizations negatively interact though. Even when optimization is not further possible[0] a careful avoidance of distinct pessimizations themselves can lead toward the same kind of beneficial outcomes. [0] Or at the other extreme, not the least bit possible.
kazinator 2y ago
Compilers are typically not going to waste time looking for very complex, special case patterns which occur rarely (and are usually confounded by various considerations that have to be checked). For this we need programmable languages in which users can code their own optimization cases. There is such a thing as "I would like a certain optimization, that should not be upstreamed into the compiler". That's exactly what's in this article. The construct: HashSet::from([a, b]).contains(&c); has some definite AST pattern (or can be made to have one with a sufficiently pinned-down language). We can think about adding a pattern match for that AST pattern to the compiler, along with a right hand side to rewrite it into.

303 points by todsacerdoti 2y ago

An interesting aspect is data dependencies. If your next statement reuses data you just computed, that can cause pipeline bubbles, as that result you want to use just isn't available yet. I dived into that topic for a video about relative performance of old PCs I just published today.

jandrewrogers 2y ago
Yes, there is non-obvious structure in some algorithms solely for the purpose of turning a single logical stream of dependent instructions into multiple concurrent streams of dependent instructions running through the same pipeline. The caveat of doing this, of course, is that it typically increases register pressure.

willvarfar 2y ago

I think it is worth making a distinction between "micro" (what the blogpost is about) and "macro", or "tactical" and "strategic", optimisations. Strategic optimisations is often basically free if you have domain expertise. It's that easy to know that the business wants x outcome and algorithm y is the right choice etc if its all internal thought processes. Whereas if you don't know enough then you're likely to make very expensive to undo decisions.

jandrewrogers 2y ago
I often refer to those as architectural optimizations. Even some of these tend to sensitive to the details of the operating environment.

raluk 2y ago

For low level benchmarking papi https://icl.utk.edu/papi/ https://icl.utk.edu/papi/ is great tool. It provides access for counters like cache misses, branch misses and number of cycles.

PaulKeeble 2y ago

When it comes to micro optimisations the issue is partly our usual tools in algorithm analysis and hardware intuition are very far apart. Random accessing memory is very slow compared to linear, some branches are considerably worse than others and it's actually quite hard to predict how much you can improve the low level details before you start, especially for big changes. Our tools can show us where time is being lost in inefficiencies but can't help us predict how changes will improve things.

enescakir 2y ago

The hardest bugs are the ones that only show up after you “optimize.”

hinkley 2y ago
The ones that only happen when you remove the debug statements are super fun.

ttd 2y ago

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. This separation lets you express the algorithm once, and then "schedule" it by specifying parallelism, vectorization, etc. You can provide multiple schedules for one algorithm, which allows you to specialize / make different choices depending on varying factors. It's a really interesting concept, though maybe limited in practice to DSLs. I'm not sure a general purpose language would be a good fit for this model, but then, for general purpose programs written in general purpose languages, perf optimization at the level TFA discusses is frequently limited to just specific hot sections. Those hot sections could be extracted out into specialized components written in such a DSL. 1 - https://halide-lang.org/ https://halide-lang.org/

secondcoming 2y ago
gcc supports function multiversioning: https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning.html https://gcc.gnu.org/onlinedocs/gcc/Function-Multiversioning....
- ttd 2y ago
  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.
almostgotcaught 2y ago
> 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).

hansvm 2y ago

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

jmull 2y ago

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

klysm 2y ago
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
- jmull 2y ago
  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.
- Joel_Mckay 2y ago
  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
- deleted 2y ago
  [deleted]
- cogman10 2y ago
  Profiling doesn't mean you don't do the math. Profiling is simply there to show you that "hey, this is where the problems actually are". You do profiling because it's WAY too easy to get obsessed about theoretical problems when a simple measurement will show you the actual problems. You do the math on the actual problem location, not a method with O(n!) which only gets called with n=3. You still have to look at the entire call stack when profiling (which means thinking about the overarching algorithm).

mannyv 2y ago

Optimization is hard work because you need to understand how things work to be effective. It's really just debugging and troubleshooting, but with a different goal in mind.

oqtvs 2y ago

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

purplesyringa 2y ago
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".
- Sesse__ 2y ago
  FWIW, VTune will definitely give you estimates of port allocation efficiency. (I believe you can also somehow squeeze it out of perf, but I've never really tried.)

jmward01 2y ago

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 likely have some high level inefficiencies. This means simple code, code you understand all pieces of, can actually be locally optimum. When I see people try to optimize code I often see them fall into that trap of optimizing too large/complex a problem which leads to them not actually being able to find a true local optimum and, often, making far slower code than had they just tried for much simpler code. This likely NP behavior runs rampant in software development where we often think we can design some elaborate process to design things and when things fail it was because people failed to follow the process and not because the problem was NP. We all love building machines which is why we likely do this, but unless you know something the rest of the world doesn't then D&C, and admitting you are only looking for a local optimum, is the only algorithm we have for attacking NP problems. (Shameless plug here for smaller, far more autonomous teams instead of monolithic dev shops with one big shared feature list)

tmoertel 2y ago
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.
- hinkley 2y ago
  Simplifying complex code often exposes optimization opportunities. Kernighan’s Law applies to performance as well as debugging.
  - tmoertel 2y ago
    Indeed!

deleted 2y ago

[deleted]

loeg 2y ago

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.

MoonGhost 2y ago
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.

interactivecode 2y ago

While actually measuring and profiling is great. In my experience most webapps can fix so much low hanging performance issues by mapping the API in a way that matches how its used in the client. It can remove so much mapping and combining for data all over.

Misdicorl 2y ago

I'll throw my hat in the ring for "disagree". Few kinds of work have such clear and unambiguous results as optimization work (its now X% faster!). Few kinds of work have such incredible and detailed tools to guide your hand in finding where to invest your effort (look at this hot loop!). The fact that sometimes optimization work is tricky or requires some pre-thinking, or is even gasp counter-intuitive is such a hilarious way to say "this is hard". That's just table stakes starting points for so-so-so much work. Edit: Heck, even deciding whether to prioritize optimization work or feature work is usually a harder problem than the actual optimization work itself.

saagarjha 2y ago
Performance optimizations are usually tradeoffs. Which ones you make affect the outcome.

tikotus 2y ago

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 optimizing. I've since noticed this many times. Optimizing is like meditation to me. It's very mechanical (measure), with a sprinkle of creative work (once you know what is slow, it's quite obvious how to make it faster, but just challenging enough to be engaging), and it has a very nice tight feedback loop: Something is slow. I make a change. Now it's fast. Next. Optimizing is my happy place.

01HNNWZ0MV43FF 2y ago
I remember one fun time between jobs, that I stayed up till 4 or 5 am optimizing something. It always felt like I was making progress and about to beat the original implementation Unfortunately I had to give up when I was still 10 times slower than the reference lol
- senderista 2y ago
  Same here, last time I was between jobs I optimized my defunct startup's database from ~50K TPS to nearly 5M TPS (no durability, if you're wondering), and that was unbelievably rewarding.
toomuchtodo 2y ago
https://en.wikipedia.org/wiki/Flow_(psychology) https://en.wikipedia.org/wiki/Flow_(psychology) https://en.wikipedia.org/wiki/Biofeedback https://en.wikipedia.org/wiki/Biofeedback
AaronAPU 2y ago
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.

hinkley 2y ago

It’s like dieting. Everyone wants to hear your one weird trick and zones out when you tell them it’s hard work. Yes, mechanical sympathy is a thing but usually pulling off a series of wins isn’t luck or particularly bad work by your peers, it’s being methodical and persistent. It’s about being stubborn as fuck, and not taking no for an answer.

trhway 2y ago

>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 this or this, without having the model in mind, that is frequently a waste, and even when/if it produces some improvement there is no understanding and guarantee what use cases the improvement will cover, whether it would regress some use cases, whether it still be there after we push those new features/fixes/etc.

purplesyringa 2y ago
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.
- Mawr 2y ago
  Sure, but that's a different statement. "Micro performance optimizations are fundamentally brute force" - ok.

ForOldHack 2y ago

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

hinkley 2y ago
> 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.

karmakaze 2y ago

I agree with many of the comments here including some of the ones that are in disagreement. The difference is context where for most situations the starting point is far from optimal and the any of N better choices is a good improvement. That doesn't seem to be what this post it talking about. It seems to talking about well worn areas trying to improve the state of the art. An example that illustrates it for me is DeepMind's AlphaTensor finding a better way to multiply matrices[0] in 2022. It wasn't a brute-force solution, but the scale of it makes it appear so. > On 4x4 matrices, AlphaTensor unexpectedly discovered a solution with 47 multiplication steps, an improvement over the 49 required with Strassen’s algorithm of 1969, albeit restricted to mod 2 arithmetic. Similarly, AlphaTensor solved 5x5 matrices with 96 rather than Strassen's 98 steps. Based on the surprising discovery that such improvements exist, other researchers were quickly able to find a similar independent 4x4 algorithm, and separately tweaked Deepmind's 96-step 5x5 algorithm down to 95 steps in mod 2 arithmetic and to 97[24] in normal arithmetic.[25] Some algorithms were completely new: for example, (4, 5, 5) was improved to 76 steps from a baseline of 80 in both normal and mod 2 arithmetic. This to me shows that direct profiling and observation wouldn't have led to the optimization. Improvements needed a sort-of but not actually brute-force effort of many people trying, but also being clever with their attempts. [0] https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...

deleted 2y ago

[deleted]

compiler-guy 2y ago

From the article: "Even Apple’s LLVM fork lacks scheduling annotations for Apple Silicon. How am I supposed to write efficient code when Apple doesn’t bother to tune their own compiler?" In addition to its public fork of LLVM, Apple also keeps a very private fork where (one assumes) they keep all the really juicy stuff. I agree that it is frustrating not to have the data, but don't confuse "I don't have the data" with "no one has the data".

deleted 2y ago

[deleted]

inetknght 2y ago

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-guide/index.html https://www.intel.com/content/www/us/en/docs/intrinsics-guid... [1]: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html https://www.intel.com/content/www/us/en/developer/articles/t...

purplesyringa 2y ago
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.

nostrademons 2y ago

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.

Validark 2y ago

"Register pressure is even worse because that is only a problem because of the ISA, not the microarchitecture." I'm not so sure. How many cycles would you expect this code to take? mov dword [rsi], eax add dword [rsi], 5 mov ebx, dword [rsi] According to Agner Fog, these 3 instructions have a latency of 15 cycles on an AMD Zen 1 processor. On Zen 2, its latency is 2 cycles. This is because the CPU was given the ability to assign a register to `dword [rsi]`, overcoming the limit of 16 registers. This optimization is subject to problems, obviously pointer aliasing will enable the CPU to make the wrong assumption at times, and cause a situation not entirely unlike a branch mispredict. There are constraints imposed by the micro-architecture for this feature. For you and I, a big one is it only works with general purpose registers. But is there a reason it couldn't or shouldn't be done for vectors? It seems like a micro-arch issue to me. Perhaps in a few years or in a lot of years, we'll have a CPU that can do this optimization for vectors.

purplesyringa 2y ago
I learn something new every day! Thanks for mentioning this. For other readers: Agner Fog documents this in 22.18 Mirroring memory operands. I've known that similar optimizations exist, namely store-to-load forwarding, but I didn't know that AMD has experimented with mapping in-flight writes straight into the register file. Sounds like they've abandoned this approach, though, and Zen 3 doesn't feature this, supposedly because it's expensive to implement. So for all intents and purposes, it doesn't exist anymore, and it probably won't be brought back in the same fashion. I do still think this is something better solved by ISA changes. Doing this on the uarch level will either be flaky or more costly. It is absolutely possible, but only with tradeoffs that may not be acceptable. The APX extension doubles the number of GPRs and improves orthogonality, so there's at least work in that direction on the ISA level, and I think that's what we're realistically going to use soon.

pavelstoev 2y ago

Optimizing AI performance is like peeling an onion — every time you remove one bottleneck, another layer appears underneath. What looks like a compute problem turns out to be a memory bottleneck, which then turns out to be a scheduling issue, which reveals a parallelism mismatch… and so on. It’s a process of continuous uncovering, and unless you have visibility across the whole stack — from kernel to cluster — you’ll spend all your time slicing through surface layers with lots of tears being shed. Fortunately, there are software automation solutions to this.

saagarjha 2y ago
They’re not very good, unfortunately.

bddicken 2y ago

This was a great read - thanks!

Ygg2 2y ago

> Any developer can see that the following two snippets are (supposed to be) equivalent Being how I fall under any developer, I'm going to bite the bullet and ask: How are they supposed to be equivalent? One is a HashSet, other is boolean? And what is `c`.

saagarjha 2y ago
c is an arbitrary object. The first puts two numbers and checks if c is present, which is only true if c is equal to one of the two numbers.
- Ygg2 2y ago
  I see. Luckily mobile phone cut `.contains(&c)` perfectly. And you see scrollbars only when you click the text.

somethingsome 2y ago

I teach my students to make a tree of the promising optimizations and suboptimization (it can be rough), keep track of each interesting optimizations, then implement the branch that seems the more promising and at each step use the profiler massively, memory bound, compute bound, latency bound, number of flops, cache accesses, etc.. After narrowing the smallest leaf, think about another branch and if some optimizations studied could lead to nice results there too. With time they learn which branch is more promising and which optimizations are good beforehand with their problem. I guess this could be called branch and bound with memoization instead of brute force aha. Note: we write code in cuda

rurban 2y ago

perf? I value -fopt-info more. The optimizer does crazy things all the time, and hereby you find out what exactly is optimized, de-optimized or needs work.

fuzzfactor 2y ago

I think her immediate recognition and characterization of "pessimizations" is relevant. Not so much as collateral damage when different optimizations negatively interact though. Even when optimization is not further possible[0] a careful avoidance of distinct pessimizations themselves can lead toward the same kind of beneficial outcomes. [0] Or at the other extreme, not the least bit possible.

kazinator 2y ago

Compilers are typically not going to waste time looking for very complex, special case patterns which occur rarely (and are usually confounded by various considerations that have to be checked). For this we need programmable languages in which users can code their own optimization cases. There is such a thing as "I would like a certain optimization, that should not be upstreamed into the compiler". That's exactly what's in this article. The construct: HashSet::from([a, b]).contains(&c); has some definite AST pattern (or can be made to have one with a sufficiently pinned-down language). We can think about adding a pattern match for that AST pattern to the compiler, along with a right hand side to rewrite it into.