Earlier quoted context omitted.
People forget that Big O is only part of the story, they also need to consider Little o and average runtime. Just because something is n^2 or worse asymptotically doesn't mean the average runtime will be that bad. There are many cases where the average runtime is closer to Little o almost all the time.
Average is useful but is Little o relevant outside of very low latency things like games? If the input is small it will run fast for any solution anyway.
14,000x Speedup (2015)
231–237 of 237 posts
Re: 14,000x Speedup (2015)
#232Re: 14,000x Speedup (2015)
#233Earlier quoted context omitted.
I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…
> On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs). I assume you mean that these improvements would not be visible on a flame chart because they were not in perf output? (assuming one was built from the other?) Flame graph by definition shows where the time is spent and i…
The data can be wrong in a number of dimensions. In general, code that gets called the most sometimes get underreported. Look at invocation counts. Ask questions.
One, they can clear the CPU cache, causing sibling functions to be overreported (one of many sources of how changing a slow function may bring less of an improvement than expected). This shows up strongest when I‘ve gotten a 10% runtime improvement from fixing a function reported as 5% of total time, or a 10x reduction in time from removing half the calls to a remote service.
Two, duplicate or idiomatic code will be scattered across different parts of the code stack, reducing the apparent magnitude of a pattern of logic below the threshold of attention of most people. Code that is in four places may represent 5% of total time and not get looked at, even if it’s an easy fix. The nickels and dimes add up quickly.
Three, functions that operate near the limits of the clock resolution will be counted properly but the cumulative timing rounded down, again putting it below the noise floor for most people. I’ve made a lot of hay re-sorting the results by invocation count and benchmarking changes to functions that never hit the top 20 list.
And last but not least, functions that create but don’t destroy their own memory allocations end up shedding timing that gets picked up by the recipients, homogenizing the timing graph. In particular in GCed languages, a function that is called in a loop that exhausts most but not all of the free heap will invariably end up stalling out in the next phase of a large calculation.
With all four of these, there are several failures of imagination I commonly saw. A flat timing graph is taken as evidence that it is time to stop optimizing, even if the target improvement has not been met. When the “tent poles” are even, getting people to care how tall they are is challenging. Few people will make six changes to the code to achieve a 10% speed up. The Rust compiler may be the first time I’ve witnessed anyone else brag about a 1% performance gain, other than me. They either don’t do it, or they apologize for achieving so little. 10% is 10%, and I don’t care where you found it, if your code quality is high enough. And perhaps most importantly, speed improvements are multiplicative, not cumulative. Use a time budget the way game devs do. If an interaction takes 10x as long as your target, every method that takes 0.5% of current run time represents 5% of your target. This is, in particular, how you spot duplicated slow code. You ignore them at our peril.
Particularly in the era of QA cycles, using a “zone defense” (optimizing one module at a time, instead of going after tall tent poles) netted a higher rate of return per hour of labor and a much larger cumulative improvement, on its own merits and by increasing the budget allotted to perf. It seems concentrating the changes in one area at a time decreases optimization fatigue. On two projects I kept that initiative alive for more than two years, and I was the one that gave up because I had cycled around the entire system and was finding few things to correct (you only learn new tricks so fast, and they go asymptotic eventually). Everyone came to expect every release to be a bit faster than the previous, and I got feedback that this narrative increased sales, and manager buy-in. People will take a chance on you when they like where you’re going, even if you haven’t gotten there yet. Narrative matters, if they trust you, and usually you have to earn it.
Re: 14,000x Speedup (2015)
#234Earlier quoted context omitted.
You're not wrong. This entire article is a classic example of Computer Science failure. It's someone who knows program optimisation in the abstract and nothing about the actual target problem from a domain knowledge perspective. They went about optimising bad code as in quality of thought level, rather than actually getting to grips with the true requirement first. Though perhaps a computer science win, but a softwar…
In a lot of ways, the original implementation makes a lot more sense than this "optimized" solution. Something like the original brute force, compare all the points' distances variant is how I'd be inclined to write one of my unit tests for the grid alignment routines. Trying a few dozen points on a few dozen grid variants is a way to make sure I've not completely screwed up math-- whether off by one, rounding proble…
Re: 14,000x Speedup (2015)
#235Earlier quoted context omitted.
In a lot of ways, the original implementation makes a lot more sense than this "optimized" solution. Something like the original brute force, compare all the points' distances variant is how I'd be inclined to write one of my unit tests for the grid alignment routines. Trying a few dozen points on a few dozen grid variants is a way to make sure I've not completely screwed up math-- whether off by one, rounding proble…
I mean maybe but if you told me you could take my code that runs in less than a second and make it more readable but it would take 30 minutes to run instead . . . hell no I'm not taking you up on your offer. I'll just comment and document the existing solution better and call it a day.
The solution here is faster than the absolute naive solution of finding all distances, but it is both slower and less readable than integer math grid conversion..
I could see why you would make the choice of the naive, slow solution. I could see why you would choose the fast, integer math grid conversion one. But I don't see why you would choose something slower than the optimum solution that is also much, much less readable.
That is, the naive solution and the integer math solution are Pareto-optimal choices... and this abomination ain't.
Re: 14,000x Speedup (2015)
#236Earlier quoted context omitted.
> On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs). I assume you mean that these improvements would not be visible on a flame chart because they were not in perf output? (assuming one was built from the other?) Flame graph by definition shows where the time is spent and i…
This got longer than I intended, but that just illustrates that the rabbit hole is deeper than many people are willing to go. The data can be wrong in a number of dimensions. In general, code that gets called the most sometimes get underreported. Look at invocation counts. Ask questions. One, they can clear the CPU cache, causing sibling functions to be overreported (one of many sources of how changing a slow functio…
You still need to understand how the data was gathered and what it really means. It is also true that flame charts are more useful on projects that are not yet heavily optimized; they clearly show the parts that are very slow compared to others. And when you don't see anything else that can be optimized, it doesn't mean that everything is optimal - the limit is imagination (and knowledge), not the problem space.
Re: 14,000x Speedup (2015)
#237Earlier quoted context omitted.
I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…
I'd argue that none of that is the hardest part of programming, or at least what I'd focus on in terms of what comes up the most and what effects users and developers and suits the most. Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time. If we ignore importance and…