8 ms·
When Optimising Code, Measure
- osigurdson 3y agoIf you don't have a performance culture your app will not be performant. The idea that performance problems are easy to reproduce and a profiler will always point to a single, easy to fix problem is naive.
- edward28 3y agoClearly, the only option is rewrite it in rust.
- asQuirreL 3y agoYou joke but in Rust all of versions 1 to 4 would probably have compiled to the same machine code because LLVM would use Loop Invariant Code Motion and Induction Variable Analysis to perform the same optimisations that are being done by hand here. (Same would be true of most modern C/C++ compilers)
- lifthrasiir 3y agoWhile modern compilers do such analyses, the loop in question is too complex to be fully analyzed---it has two independent induction variables in a single loop after all.
- asQuirreL 3y agoYou're right -- I got nerd-sniped by this, and ended up rewriting the benchmarks in Rust. The compiler successfully inlines the square root operation, simplifies the exponentiation into multiplication and then does common-subexpression elimination over it, but no induction variable analysis, and therefore also no loop-invariant code motion. Here's it is in Godbolt: https://godbolt.org/z/Pa6cqd1fb https://godbolt.org/z/Pa6cqd1fb But the funny thing is, I tried it on my machine, and guess what, the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants: https://gist.github.com/amnn/4be5c05975c250d0ea88b62c03f1719e https://gist.github.com/amnn/4be5c05975c250d0ea88b62c03f1719... So that's fun.
- ColinWright 3y ago> ... the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants: I'm getting this comment a lot, but so far the reason has been that people are using smallish numbers, and implementing the square root in floats. In the context where this exploration is taking place, you can't do that. We're working with exact huge integers, and while a square root on floats can get you in the ballpark, you then need to refine the answer to get the exact value, and that takes order of magnitude the same time.
- asQuirreL 3y agoHow big are we talking? The benchmarks I tried the two numbers in your example, but yes, if you go above 2^53, then you will run into trouble with the naive solution, but that is for correctness reasons, not performance reasons.
- ColinWright 3y agoThis is an experiment on aspects of a factoring algorithm ... we're going to be talking about a few hundred digits base 10. So up to around 10^200 or so, which is around 2^600.
- asQuirreL 3y agoWell yes, that definitely changes the game!!
- GrumpySloth 3y agoRewriting from Python to anything else would make it faster.
- billyzs 3y ago> a2, c = a2+c, c+2 > is faster than > a2 += c > c += 2 > My guess is that in the first case the two evaluations and assignments can happen in parallel, and so may happen on different cores Not sure I follow, isn't Python single threaded by default? Changes to GIL is coming but does it change how the interpreter uses CPU?
- saagarjha 3y agoRunning that across two cores would be a slowdown, not a speedup. You cannot parallelize work like this, because it's too small to be worth it.
- kristofferc 3y agoYeah, this isn't benchmarking anything related to the CPU etc. It is benchmarking the quirks of the Python interpreter.
- danybittel 3y agoThere is instruction level parallelism in modern CPUs. They have multiple "calculation units", that do for example addition. If one doesn't depend on the other they get executed at the same time.
- epcoa 3y agoLOL. The amount of machinery going on under the hood in evaluating those expressions in CPython is staggering. A microscopic detail like a single instruction data dependency has nothing to do with it. (How many CPU add instructions are executed just for those statements? Probably hundreds.) This is much more likely a quirk of the interpreter (or possibly a fucked up test). CPU details are like 10000 feet down.
- reitzensteinm 3y agoYou're absolutely right, but laughing at the notion is unnecessarily rude.
- lifthrasiir 3y agoMeasure, but know that measurements may (very frequently) go wrong. In this particular case, there seems no actually measurable difference between two codes. You can verify that the actual bytecode change is `c = a2 + c` vs. `c += a2`, but Python int doesn't have a separate implementation for `+=` (`__iadd__`, or `nb_inplace_add` in C) presumably because all integers have to be immutable anyway, so they can't differ that much. [1] And others have pointed out that Python in general doesn't run anything in parallel unless explicitly requested. Therefore any difference is very likely to be due to the faulty benchmark method. The post suspiciously doesn't mention any benchmarking code (and even what the heck is `square_root_ceil`, which I assumed to be `lambda x: int(math.ceil(math.sqrt(x)))` below), but I did a quick benchmarking and got the following result in a particular environment: #3, small #3, large #4, small #4, large ----------- ----------- ----------- ----------- min avg min avg min avg min avg ----- ----- ----- ----- ----- ----- ----- ----- 0.188 0.228 0.609 0.687 0.203 0.244 0.610 0.695 0.203 0.215 0.610 0.642 0.203 0.211 0.625 0.653 0.203 0.214 0.609 0.641 0.188 0.208 0.609 0.627 0.203 0.213 0.609 0.622 0.187 0.208 0.609 0.630 0.187 0.209 0.609 0.622 0.187 0.208 0.609 0.630 Here I'm calling `factor_fermat3` with small and large arguments, repeat that 10 times (so 20 calls), then do the same for `factor_fermat4`, and then report a single line. I did this 5 times in a row, and it is evident that the first few runs were substantially slower than later. Modern CPUs vary their frequency to save power, and it takes some (or even much) time for CPUs to adapt to the new workload that demands higher or lower frequency. If I have put `time.sleep` between each run it might be possible that the first run repeats every time, but that would be inaccurate. For multicore systems it's also possible that the core may change over time, with separate power states, so a proper benchmarking needs some core pinning to avoid such issues. If you only did the first run you may have concluded that #4 was slower than #3, but subsequent runs show that this is not true and they are more or less same especially when you consider the minimum time per call. The average time in comparison is highly variable and you need lots of considerations to stabilize that, which I never did in this case. Also you need statistical testing to conclude that such difference was not a fluke, which is another vast subject. In any case, this post doesn't show any such attempt. [1] Note that `c += a2` is equivalent to `c = c + a2` and not `c = a2 + c`, which can make a difference when multiprecision arithmetic routines do not account for such cases. I tested both cases and got the same result, however.
- reitzensteinm 3y agoIf you're measuring performance and haven't seen this talk by Emery Berger, I highly recommend it. It's mind blowing, but also terrifying when you realize how many mistakes you've been making up until this point. https://youtu.be/7g1Acy5eGbE https://youtu.be/7g1Acy5eGbE
- screye 3y agoNot everyday you see Emery be the top comment on HN. I was lucky to be in his courses in grad-school. It's the most fun I've had in an American classroom, all while discussing serious systems stuff. A gem of a professor.
- tialaramex 3y agoI've watched another version of this talk (maybe at Strange Loop), but I'm pretty sure I hadn't seen this hangup on measuring weird C++ artefacts against Python before which comes before the interesting stuff and for me was a big disappointment. Comparing the size of C++ int (which will be the 32-bit signed integer because hey why not) against Python's integers (which are just fully arbitrary big integers) is unfair. But it doesn't stop there, next it measures std::list<int> which is a doubly linked list, a container that C++ keeps around partly because it is infested with the sort of programmers who've heard this data structure is sometimes a good choice (it is) and therefore reach for it first -- exactly the sort of bad optimization we're warning against. Python doesn't even have a doubly linked list. Then it compares std::map<int,int> against Python's dict, but std::map is a red-black tree of linked lists, Python's dict is a hashtable, because of course it is. So these aren't anywhere close to comparing like with like either.
- andrewstuart 3y agoEasy to say but often quite hard to do. Measuring, gathering, reporting, understanding what you’re seeing. These are often very complex and time consuming.
- maccard 3y agoIf you can't measure it to prove that before and after are different, then you shouldn't optimise it. You run the risk of making things worse.
- IshKebab 3y agoSometimes things are obviously going to be slow even without measurement. For example not reserving a large vector. Or doing unbuffered IO.
- bluGill 3y agoI just measured a large vector and reserving makes minimal differnce for my case. Ammortized growth is a not slow. Ymmv of course which is why we measure.
- IshKebab 3y agoAt worst it makes no difference and at best it makes a big difference - maybe on an input that you didn't even measure!
- maccard 3y agoAt worst it will make it slower, and at best it will make it faster[0]. The only way to know is to measure with an input that's representative, and this case is exactly why you measure. [0] https://stackoverflow.com/questions/48535727/why-are-c-stl-vectors-1000x-slower-when-doing-many-reserves https://stackoverflow.com/questions/48535727/why-are-c-stl-v...
- bluGill 3y ago
- thom 3y agoWorth pointing out that this is actually what Knuth meant by premature optimisation. Nothing to do with optimising too early in a project or some sense of YAGNI, but rather optimising before you know where the actual time is spent.
- jraph 3y agoI didn't know this, thanks for pointing it out. I think this has been a costly misinterpretation of "premature optimisation". This phrase has been taken as justification for writing inefficient code, understanding it as "performance doesn't matter [for what we do]". It almost always matters, and I believe it is possible to write both efficiently and in a readable way. Unfortunately, inefficient code is well established, in habits and even in (sometimes mandatory) coding styles. This inefficiency also often translates to hard to follow code because of too much abstraction. Maybe we could counter this misinterpretation of "premature optimisation" with "premature abstraction".
- ReleaseCandidat 3y ago> This phrase has been taken as justification for writing inefficient code, understanding it as "performance doesn't matter [for what we do]". There is no contradiction. Writing inefficient code is perfectly fine until you _know_ (this means you have measurements that show that) it is _too_ inefficient and has to be optimised. How do you measure the "optimisation" without "inefficient code" as baseline to begin with?
- edflsafoiewq 3y agoIn that case, how do you know you're measuring the "optimization" and not "how awful the original code was"?
- jraph 3y ago> Writing inefficient code is perfectly fine until you _know_ (this means you have measurements that show that) it is _too_ inefficient and has to be optimised. What about inefficient code only if you _know_ that it does not matter? I'm not talking about optimizing. I'm talking about avoiding inefficiencies in the first place. This is what I'm talking about: we are in "inefficient by default" mode. That leads to requiring powerful hardware to display the most lambda websites.
- StarlaAtNight 3y agoThese online tech spaces always assume that saving on compute, storage, and memory are the ultimate targets for optimization. I’ve worked (mostly on business/data teams) in companies for 10 years, and have to say, saving on technical debt and human inefficiency w/ a codebase typically far outweighs the computational metrics How might we incorporate that in a metric-like way?
- karles 3y agoWell, human processes can be visulised and their completion time can be estimated, as can possible breakdowns. Eliminating breakdowns thus eliminate "waste" in required effort, coordination etc. So I don't see how human processes differs from technical ones that much...
- lysecret 3y agoI agree. However simple to understand code with high human efficiency is nearly impossible to measure. Honestly, maybe ChatGPT could give you the best evaluation/measure of that.
- Shish2k 3y ago“write code clear enough that an LLM can look at it and create an accurate summary of the high-level goals” gives me similar vibes to “explain like I’m 5”, which seems like it could be an interesting metric (and my gut tells me that things will go horribly wrong as soon as somebody turns this metric into a target :D)
- marcosdumay 3y agoIt looks like a metric of the kind of lines of code. Hugely useful for measuring a lot of things. But obviously bad for optimizing even if it's not a formal target.
- adammarples 3y agoIt's easy to measure. You sit a dev down in front of it and time how long it takes them to understand it. That's not just an estimate that's the key value itself.
- sergioisidoro 3y agoI could think of a nice corollary for this: If it's not worth measuring, it's not worth optimising.
- stinos 3y agoHow to decide whether it's worth measuring without measuring?
- OscarDC 3y agoIt may be that the entire performance including the logic is satisfactory. Or it may be that the conditions to reach that logic are too rare to make the time to measure and optimize worthwhile. In any case, I understand it as: if you're not bothered about measuring the performance of something, it may be that you don't need to optimize it.
- WJW 3y ago> It may be that the entire performance including the logic is satisfactory. In which case you have already measured it, even if not very precisely. > Or it may be that the conditions to reach that logic are too rare to make the time to measure and optimize worthwhile. This too cannot be determined without measuring how often it happens.
- OscarDC 3y agoBy what I understood of your reply, everything is a measure and I fail to see how something cannot be measured. Or perhaps I wasn't clear in what I meant initially? > In which case you have already measured it, even if not very precisely. If you're doing a CLI tool for example and it responds soon enough for it to be a bother, you won't want to measure a sub-part of its logic. You may be blindly "measuring" the time the whole command took with your eyes and thoughts, but you're not measuring in any way the time taken by the corresponding logic in the whole thing. > This too cannot be determined without measuring how often it happens. If the CLI tool logic sub-part is in a specific combination of flags and conditions that you for now didn't see a use case for or even sometimes possibility yet, you may also not measure it, without needing to have to "measure how often it happens". For example you may want to skip some optimizations in what you think will be rarely encountered error handling code, even if you actually never measured it. Even if it does happen more often than you thought, low performance may still be acceptable in some unexpected code (e.g. after a typo in a CLI tool flags).
- vlovich123 3y agoWhat techniques do people use to profile code where the core path takes <<1ms? A sampling profiler is max 1khz and thus aliasing artifacts will hide the true source of hotspots I find and valgrind is too slow. The other problem I have is that diffuse hotspots are hard to root cause when running the optimized version (eg hard to spot bounds checking). I’m not confident that simply running the code under test longer helps with the aliasing artifacts (probably because if the core loop is running in 1us then I have to run for 1000x longer to remove the sampling bias due to Nyquist if that’s even the right strategy?)
- alright2565 3y agoI'm confused here. Does this core path only run once per second? I've had no problems profiling blocks of code that short, because it sounds like every inner loop to me. If you're looking to optimize a few hundred instructions, then focus on reading and understanding the code manually at the instruction level. A profiler will never help you there, CPUs are too complex: 1. I don't trust that the profiler has equal probability of pausing on any specific instruction 2. CPUs do no execute instructions in sequence, but in parallel. So you will need to understand data dependencies & maybe pipeline structures for your target processor. If you're getting really serious, you'll want something like https://uops.info/table.html https://uops.info/table.html
- vlovich123 3y agoSo I’m toying with my own database implementation and I’m getting ~20M writes per second. The write operation is a critical path that takes 1/20Mhz (ie 50ns). A sampling profiler will only capture max 1000hz (and even that is pushing it). And a hot spot here is 5-10ns probably. And similarly it could very well be memory transfer costs vs cpu which I’ve found hard to distinguish. I’ve had luck with valgrind but just reading individual instructions has been uninformative as the code path is too complex for that kind of analysis.
- phkahler 3y ago>> What techniques do people use to profile code where the core path takes <<1ms? Make a loop that runs the code 5000 times and time that. What do you mean by "diffuse hot spots"? If a piece of code taking 1ms is called infrequently then optimizing it is not going to have a meaningful impact on your overall execution time. You can measure the time for longer running higher level functions that do a lot. If you then optimize some small function that's a leaf in the call graph, you can see the impact on the larger function - and it probably won't be much. One thing that can happen when nobody cares about performance is that every part of the code gets little inefficiencies and fixing any one of them has very little impact, but fixing ALL of them can be really significant. In that case you should start by profiling or timing the higher level functions and finding ones that have relatively small call trees that you can work on. Once you optimize one piece, the effects of optimizing others are a bit more significant because they are a larger part of overall execution time.
- ChrisMarshallNY 3y agoThis was the lesson that my team learned, as we optimized image processing pipeline code (C++). The most interesting results, were cache hits. It could have a huge impact (like 1000X), if you could keep execution and data in lower-level caches. Often, the fix was cut-and-paste repeated code, as opposed to loops or function calls, FP-like static functions, small stack frames, etc.
- dspillett 3y agoAlso measure many times, and make sure any difference you see isn't accounted for by variation in the test system (CPU frequency scaling due to temperature, your test being run partly (or entirely) on low-power cores if your CPU has such a distinction, network contention if you aren't working locally or over a link dedicated to the tests, etc.). Also where IO is at all involved remember to test both cold and warm starts, and make sure that if your new version seems faster in the results that it actually is rather than a previous run having “warmed up” something. Make sure any prep you do before each measurement doesn't inadvertently change the results – keep prep and actual the tests separate (and cool down between if trying to analyse cold-run performance). On this latter point I once had a heck of a time convincing someone that his new index hadn't sped up a SQL query by an order of magnitude – he was correctly running from cold each time but was adding the index and running the query immediately (without dropping cached pages between), the affected table was small enough to fit in memory and adding the index caused a full scan so when the actual test was done the system was no longer cold.
- JonChesterfield 3y agoCompetently measuring performance is difficult. Stuff like the OS accumulating cruft over time can dominate trend lines. Broadly irrelevant reshuffles of program layout can have noticeable impacts on cache behaviour. I don't bother with competent performance measurement. That involves statistics and the like. Instead I run the thing through callgrind and use that as a proxy for reality, or play fewer-branches-better. That and wall clock time to warn me if I've walked off the edge of some quadratic algorithm. In principle I'd like to measure performance carefully and reliably, but that probably involves running under an emulator hacked to tell you things about performance, or on bare metal as the only code executing on the chip. Both are difficult.