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

121–130 of 153 posts

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

#121

Post by Ygg2 »

saagarjha wrote: post #120
Ygg2 wrote: post #114

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

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.

I see. Luckily mobile phone cut `.contains(&c)` perfectly. And you see scrollbars only when you click the text.

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

#122

Post by purplesyringa »

almostgotcaught wrote: post #102
purplesyringa wrote: post #94

Earlier quoted context omitted.

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…

> I want the `if` to take both branches at once. this is called symbolic execution - as i have already told you, many compilers do this in the form sccp and scev. you don't need silly things like egraphs for this. > If something has been rewritten, it will never be rolled back this is patently false - not only do passes get rolled back to catch/correct errors but there is a fixed-point iteration system (at least in M…

I don't see how symbolic execution is relevant to this. Yes, symbolic execution does "check both paths" for some definition of "check", but ultimately I as a programmer still need to write a condition, and that condition is on the source level, so it can't access information on e.g. register pressure, which is what I would like to comptime-branch on.

> not only do passes get rolled back to catch/correct errors but there is a fixed-point iteration system (at least in MLIR) that will apply passes as long as they are "profitable"

Huh? I'm not arguing against fixed-point iteration, that's perfectly fine because it's still a unidirectional process. What do you mean by "passes get rolled back to catch/correct errors" though? Certain rewrites can certainly be not performed in the first place if they pessimize the code, but that's not what I'm talking about.

If there's pass 1 that chooses between rewrite A and B, pass 2 that chooses between rewrite C or D, and pass 3 choosing between E or F, in a typical compiler, this choices would be made one by one mostly greedily. An e-graph style approach allows all of those eight combinations to be tried out without necessarily leading to a combinatorial explosion.

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

#123

Post by purplesyringa »

YZF wrote: post #113
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…

If you look at some SIMD accelerated algorithms they're anything but simple. They involve clever ways of breaking up the work into streams and clever ways of computing those streams including conditionals without breaking the data flow. They are very much not the simplest possible implementation of the algorithm and they run an order of magnitude faster for some algorithms.

I do still see their point. SIMD is very rarely applicable, so you could argue that SIMD can only be applied to simple enough code. The idea is: write stupid code because it'll be easier to optimize on a micro level, e.g. with SIMD.

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

#124

Post by alion02 »

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…

I recently ran down approximately the same rabbit hole when trying to figure out what to do about x86 treating addition and bitwise OR differently. There's https://llvm.org/docs/LangRef.html#id171, but it can't generally be synthesized in Rust. So I went on a short-lived quest:

- https://internals.rust-lang.org/t/expose-llvms-or-disjoint-i...

- https://github.com/rust-lang/libs-team/issues/373

- https://github.com/rust-lang/rust/pull/124601

Which ultimately culminated in an opinion that should sound familiar - https://github.com/rust-lang/rust/pull/124601#issuecomment-2....

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

#125

Post by dkersten »

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 also love optimising, especially low level code.

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

#126

Post by MawKKe »

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…

Was the need for optimization work something that was on your mind the whole time? Like a nagging feeling in the back of the head that the code is not working as well as it _should_ be working? i.e. stress.

And when you finally "fixed" the issue through optimization, your mind allowed itself to let go of these open loops (borrowing the GTD terminology), leading to relaxation?

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

#127

Post by n4r9 »

munificent wrote: post #99
tmoertel wrote: post #53

Earlier quoted context omitted.

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

Definitely true. "Give me a week, and I can implement this 1000-LOC feature. Give me a month and I can do it in 100 LOC."

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

#128

Post by IsTom »

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 this is because optimization is likely an NP

Optimization of computer programs is a fundamentally uncomputable affair due to Rice's theorem – in the general case you can't check if two programs are equivalent.

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

#129

Post by somethingsome »

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

Post reply on HN