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

131–140 of 153 posts

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

#131

Post by phanimahesh »

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…

Might explain why factorion is so popular. Not just factorion but the entire genre of games it spawned

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

#132

Post by Sesse__ »

saagarjha wrote: post #117
YZF wrote: post #111

Earlier quoted context omitted.

Which is why the defaults for perf always drive me crazy. You want to see the entire call tree with the cumulative and exclusive time spent in all the functions.

I’m honestly curious why the defaults are the way they are. I have basically never found them to be what I want. Surely the perf people aren’t doing something completely different than I am?

I almost never find graph usage useful, TBH (and flamegraphs are worse than useless). And perf's support for stack traces is always wonky _somehow_, so it's not easy to find good defaults for the cases where I need them (I tend to switch between fp, lbr and dwarf depending on a whole lot of factors).

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

#133

Post by Sesse__ »

cogman10 wrote: post #98
mystified5016 wrote: post #38

Earlier quoted context omitted.

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

The first version is more readable, faster for small n (which is the common case), can not run out of memory due to the hash table, compiles to less code, does not need item to be hashable and cannot accidentally copy elements (depending on language). It _should_ be your default. (Well, except you should start from the items after item1, so that you don't need the item1 != item2 test.)

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

#134

Post by Jean-Papoulos »

devnull3 wrote: post #116
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 think optimization triggers fundamental instincts in humans: 1. Tracking i.e. navigating through jungles for hunting or find where the bottleneck is. 2. The thrill of the hunt. The joy after finding the hotspot or the bottleneck. It makes your day. 3. The actual hunt i.e. shooting an arrow/spear or using clever way of fixing. 4. Brag about the hunt or writing a blog post or tech talk on how difficult and awesome th…

Ah yes, completely unfounded behavioral "science" to explain a modern thing. My favorite.

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

#135

Post by [deleted] »

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?

[deleted]

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

#136

Post by HideousKojima »

Capricorn2481 wrote: post #69
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…

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

Sure, but avoiding CPU cache misses is hardly the only form of optimization. Some optimizations are blatantly obvious. As an example, there was some code I was working on that called the database every single time it was executed. The data it was pulling from the database got updated once a year, and the entire dataset could fit into about 4kb of memory. Caching it in memory was an obvious fix, and given how fast the rest of the code ran once it had this data it was basically a 500% speedup that anyone with half a brain could have roughly estimated.

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

#137

Post by someguyorother »

IsTom wrote: post #128
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.

Users of practical software would probably not accept the program taking forever, so you could implement a runtime constraint. With a runtime constraint, every TM effectively halts, so making nontrivial observations about them should at least be computable.

Not that it would be easy.

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

#138

Post by Sesse__ »

purplesyringa wrote: post #66
oqtvs wrote: post #18

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

I'd love to use a tool that shows the state of every CPU component at each point in time. Performance counters demonstrate global behavior, while what actually matters during optimization is local behavior. I'd like to be able to inspect pipeline stalls and conditions that led to these situations, I'd like to get an estimate on the efficiency of port allocation, I'd like to be able to compare the rate of memory acces…

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

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

#139

Post by cogman10 »

Sesse__ wrote: post #133
cogman10 wrote: post #98

Earlier quoted context omitted.

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

The first version is more readable, faster for small n (which is the common case), can not run out of memory due to the hash table, compiles to less code, does not need item to be hashable and cannot accidentally copy elements (depending on language). It _should_ be your default. (Well, except you should start from the items after item1, so that you don't need the item1 != item2 test.)

> The first version is more readable

Disagree

> faster for small n (which is the common case)

How can you know that? And for smaller n, the choice hardly matters.

> can not run out of memory due to the hash table

If n gets large enough that hash table size becomes a problem, n is large enough that you need the hash table or some other structure that reduces the complexity down from O(n^2).

> compiles to less code

This is just nonsense. Any codebase of significant size already has a hashtable setup and unless you are using a language like C++, the code size of using a hash table anywhere is constant. The cost is already paid.

The actual amount of compiled code from the switch is identical.

> does not need item to be hashable

True.

There would be reasons not to choose option 2, but it should be default until it's been proven to be a problem. And even then, the next step is almost certainly not going to be option 1.

But then this could also be language and application specific. I deal primarily with backend services/Java where memory is plentiful, and allocation is fast. Algorithmic complexity is for my applications very often the better indicator of what good code should be.

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

#140

Post by cogman10 »

YZF wrote: post #112
cogman10 wrote: post #98

Earlier quoted context omitted.

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

For many people performance optimization really starts with your second version. I'm not even sure what this is supposed to do exactly but the O(N^2) is just bad/sloppy code. Optimization is usually more about getting the right algorithms to execute faster. At least that's how I think about it.

Yet, as you'll see in this thread at least 1 other commentor is arguing that option 1 is better. What you and I see as bad/sloppy code, they see as the ideal starting point.

A pretty common attitude that I've ran into. People take the "premature optimization" quote to mean "Never think about big oh when writing code".

Post reply on HN