Performance optimization is hard because it's fundamentally a brute-force task • Hacker News Board

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

#91

Post by Validark » Tue, Apr 29, 2025, 9:08 PM UTC

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

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

#92

Post by Validark » Tue, Apr 29, 2025, 9:23 PM UTC

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.

A lot of people have ways of accomplishing this, but my way is using compile-time execution in Zig (I know at least D, C++, and Terra have their own versions of this feature). You can specify a parameter as `comptime` and then do different things based on whatever conditions you want. You can also execute a lot of code at compile-time, including your sqrt check.

E.g. I wrote a `pextComptime` function, which will compile to just a `pext` instruction on machines that have a fast implementation, otherwise it will try to figure out if it can use a few clever tricks to emit just a couple of instructions, but if those aren't applicable it will fallback on a naïve technique.

https://github.com/Validark/Accelerated-Zig-Parser/blob/8782...

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

#93

Post by purplesyringa » Tue, Apr 29, 2025, 9:31 PM UTC

Validark wrote: post #91

"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 abili…

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.

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

#94

Post by purplesyringa » Tue, Apr 29, 2025, 9:38 PM UTC

Validark wrote: post #92

purplesyringa wrote: post #61

Earlier quoted context omitted.

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.

A lot of people have ways of accomplishing this, but my way is using compile-time execution in Zig (I know at least D, C++, and Terra have their own versions of this feature). You can specify a parameter as `comptime` and then do different things based on whatever conditions you want. You can also execute a lot of code at compile-time, including your sqrt check. E.g. I wrote a `pextComptime` function, which will comp…

I think we're all talking past each other here.

Your suggestions introduce, in effect, a hypothetical `if` statement, only one branch of which is taken. I can change the condition arbitrarily, but ultimately it's still going to be either one or the other.

I want the `if` to take both branches at once. I want the compiler to assume that both branches trigger the exact same side effects and return the same results. I want it to try both approaches and determine the better one depending on the environment, e.g. the number of free registers, (lack of) inlining, facts statically known about the input -- all those things that you can't write a condition for on the source level.

Think about it this way. A standard compiler like LLVM contains passes which rewrite the program in order. If something has been rewritten, it will never be rolled back, except it another pass performs a separate rewrite that explicitly does that. In contrast, e-graphs-based compilers like Cranelift maintain an equivalence graph that represents all possible lowerings, and after the whole graph is built, an algorithm finds a single optimal lowering.

Existing solutions make me choose immediately without knowing all the context. The solution I'd like to see would delay the choice until lowering.

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

#95

Post by thrtythreeforty » Tue, Apr 29, 2025, 10:01 PM UTC

purplesyringa wrote: post #94

Validark wrote: post #92

Earlier quoted context omitted.

A lot of people have ways of accomplishing this, but my way is using compile-time execution in Zig (I know at least D, C++, and Terra have their own versions of this feature). You can specify a parameter as `comptime` and then do different things based on whatever conditions you want. You can also execute a lot of code at compile-time, including your sqrt check. E.g. I wrote a `pextComptime` function, which will comp…

I think we're all talking past each other here. Your suggestions introduce, in effect, a hypothetical `if` statement, only one branch of which is taken. I can change the condition arbitrarily, but ultimately it's still going to be either one or the other. I want the `if` to take both branches at once. I want the compiler to assume that both branches trigger the exact same side effects and return the same results. I w…

> e-graphs-based compilers like Cranelift maintain an equivalence graph that represents all possible lowerings, and after the whole graph is built, an algorithm finds a single optimal lowering

Do you have a good entrypoint reference for learning about how this works? This (and the associated mention in the article) is the first time I've heard of this approach.

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

#96

Post by purplesyringa » Tue, Apr 29, 2025, 10:05 PM UTC

purplesyringa wrote: post #94

Validark wrote: post #92

Earlier quoted context omitted.

A lot of people have ways of accomplishing this, but my way is using compile-time execution in Zig (I know at least D, C++, and Terra have their own versions of this feature). You can specify a parameter as `comptime` and then do different things based on whatever conditions you want. You can also execute a lot of code at compile-time, including your sqrt check. E.g. I wrote a `pextComptime` function, which will comp…

I think we're all talking past each other here. Your suggestions introduce, in effect, a hypothetical `if` statement, only one branch of which is taken. I can change the condition arbitrarily, but ultimately it's still going to be either one or the other. I want the `if` to take both branches at once. I want the compiler to assume that both branches trigger the exact same side effects and return the same results. I w…

@thrtythreeforty I think this RFC is a good start: https://github.com/bytecodealliance/rfcs/blob/main/accepted/.... Then read through these docs: https://docs.rs/egg/latest/egg/tutorials/. They document the behavior of a particular crate, but they also act as a very accessible high-level overview.

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

#97

Post by cogman10 » Tue, Apr 29, 2025, 10:12 PM UTC

dmurray wrote: post #29

titzer wrote: post #20

Earlier quoted context omitted.

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

> it won't show up in profiles except for ones that capture stacks I don't think I've ever used a profiler that couldn't report you were in F() here. One that only captures your innermost functions really doesn't seem that useful, for exactly the reasons you give.

The default usage of perf does this. There's also a few profilers I know of that will show the functions taking the most time.

IMO, those are (generally) nowhere near as useful as a flame/icicle graph.

Not saying they are never useful; Sometimes people do really dumb things in 1 function. However, the actual performance bottleneck often lives at least a few levels up the stack.

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

#98

Post by cogman10 » Tue, Apr 29, 2025, 10:23 PM UTC

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…

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

Most of the times I've seen this, the faster algorithm is literally just a dictionary with a well-defined key.

I honestly do not understand why that's not the first solution most devs think of and why n^2 seems to dominate.

As an example, I've seen code like this quiet a bit

    result = []
    for (item: items) {
        for (item2: items) {
        if (item != item2 && item.foo == item2.foo) {
          result.add(item)
        }
      }
    }

Easily replaced and massively easier to read as

    result = []
    itemFoo = HashSet()
    
    for (item: items) {
      if (itemFoo.contains(item.foo))
        result.add(item)
      else
        itemFoo.add(item.foo)
    }

The mindset of re-looking for values in a collection you are already iterating through is just foreign to me. The first solution for something like this in my mind is always utilizing dictionaries.

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

#99

Post by munificent » Tue, Apr 29, 2025, 10:23 PM UTC

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.

> When you write simple code, you spend less time writing code.

I have found that many engineers write complex code faster than simple code.

You're given requirements like: "the program should do W when the user does A, X when the user does B, Y when the user does C, and Z when the user does D." And a naive programmer will happily trot off and write a pile of code for each of those cases, often with a lot of redundancy between them.

It takes more time and judgement to analyze those cases, see what they have in common, and distill a simpler underlying model for the behavior that encompasses all of the requirements.

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

#100

Post by zahlman » Tue, Apr 29, 2025, 10:56 PM UTC

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…

> Optimizing is my happy place.

Interesting. For me, it's refactoring.