When Optimising Code, Measure
solipsys.co.uk
solipsys.co.uk
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.
What people tend to miss in my view is that he is advocating writing in an efficient style, which may not be obvious to an inexperienced developer. For example, writing a linear algebra routine in which you traverse column wise in an inner loop when the data is laid out row wise is going to be very slow and a simple change of algorithm or restructuring of the data can lead to an enormous speed up. This should be done immediately if discovered. But a skilled programmer will also be unlikely to traverse in the wrong order anyway because they already know the data layout and have thought about the order of traversal as part of their thinking process. In other words, the "optimization" of traversing in the fast way is something they would just do naturally and has no influence on the development time.
Conversely, they may also suspect that with some clever bit-twiddling hacks, they may be able to squeeze another 5-10% performance out of the routine. Unless you know that the code is being distributed at scale, this is almost certainly a waste of time. It will be hard to write as well as brittle and error prone. It deflects your attention from more important problems. It is evil both because of the opportunity cost of chasing these small efficiencies as well as the increased complexity that they often introduce for minimal gain.
"There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools or seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off."
I certainly agree with the interpretation that the _cost_ is maintainability of prematurely optimised code and this is the evil he's describing. But this is also all in the context of efficiency as a virtue in itself - i.e. something you should be seeking, but seeking in the correct places.
A profiler can't tell you that an entire operation would become completely unnecessary if you maintain a certain invariant elsewhere, and this can go as far out as you let it, e.g. entirely changing your in-memory data model to prepare it for the operations you know you'll be performing in the critical path.
I know because I've been fortunate to work in environments full of seasoned experts writing world-scale software in C++ and Rust, that I was still able to optimize 100x-1Mx by zooming out and solving the same problem from a new perspective, something a profiler cannot help with.
And I'm _nothing_ compared to the people that come around and make it another 10x faster with SIMD or some cutting edge computer science research I'm not across. (Remember when NFA regex was a breakthrough and now looks like a joke compared to DFA?). Even a profiler hinting that a hot function might benefit from SIMD can't tell you how you should arrange your overall data structures to fully benefit from SIMD, or cache locality for that matter.
This isn't an attack on what you said, and what I'm saying is bordering on incoherent because there's so much more to the performance optimization iceberg than the "profiling" tip that most engineers are permanently stuck on. But no, every time aggressive holistic optimization conversations come up, more than half of the audience will dismiss it as "premature" or insist on just profiling and decline to learn anything. Then people like me have to inherit and rewrite their projects because they've ground our global scale to a halt.
I have a fair bit of experience in optimisation and this is ridiculously... optimistic, shall we say. The only way you can get literally orders of magnitude speed up is if some pillock put literally orders of magnitude of slowdown in originally, typically by combining a couple of O(n^2) operations, and even then only seen that a few times and it's easy to fix.
Example: Writing what is effectively a graph algorithm where every edge/node lookup is a string key in a hash map. Transforming the string keys into dense integer offsets once-off costs nearly nothing, and reduces every single lookup into a direct memory offset. That one optimization alone was an over 30x speedup, and you can imagine that if they wrote it like this then there was a lot of other low hanging fruit.
These people passed one of the most famous computer science hiring bars in the industry, and this code passed review.
When I interview people with a puzzle version of a problem like this, 95% of candidates still use string keys instead of reducing them to integers, so this is shockingly common and not at all an edge case. It's just one of dozens of common performance antipatterns I see in code written by people with TC over $500k USD.
It's also why I call bullshit when people online claim that computer science interviewing is gatekeeping and they don't need algorithms in their day job. This is false both ways; it's not gatekeeping successfully enough because nonsense like this makes it to global production and costs tens of millions, and anyone who wants to succeed in this job is expected to know better.
The distinction is a lot more important today with the ~100x speed and power consumption differences between Ruby/Python/etc and C++/Java/Go/Rust/etc.
"Another important aspect of program quality is the efficiency with which the computer's resources are actually being used. I am sorry to say that many people nowadays are condemning program efficiency, telling us that it is in bad taste. The reason for this is that we are now experiencing a reaction from the time when efficiency was the only reputable criterion of goodness, and programmers in the past have tended to be so preoccupied with efficiency that they have produced needlessly complicated code; the result of this unnecessary complexity has been that net efficiency has gone down, due to difficulties of debugging and maintenance. The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming."
If you have a holistic definition of efficiency, then it might make sense to use a performant language for the performance critical parts of a wider system, but more productive languages elsewhere. You might make a similar argument about languages that add some productivity overhead to achieve stronger guarantees of safety or correctness.
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".
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?
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.
It's mind blowing, but also terrifying when you realize how many mistakes you've been making up until this point.
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.
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.
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.
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.
> 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).
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?
Hugely useful for measuring a lot of things. But obviously bad for optimizing even if it's not a formal target.
Eliminating breakdowns thus eliminate "waste" in required effort, coordination etc.
So I don't see how human processes differs from technical ones that much...
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.
The advice you’ve provided is correct philosophy but not actually actionable - I’m having trouble finding the inefficiencies.
As others have said, benchmark frameworks are great. Many systems have support for high-resolution perf counters these days. Just ran a quick test on my local system, it's able to make a timer accurate to 100ns.
Benchmark frameworks let you hook into your code in such a way that you can easily run a single fragment 10k-10m times and produce an analysis of the result that includes mean time, std deviation, and memory allocations. They usually let you setup a side by side comparison so you can directly compare 2+ methods.
If you use a language with a JIT then good frameworks for those include a warmup period to get the best-JIT version of the code in place before collecting data.
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
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.
A optimized implementation should only incur overhead around one hardware timestamp per function call which is generally around 10-100 ns. That is sufficient for benchmarking quantitative differences at the 1000 ns level and even clear qualitative differences at the 100 ns level. The bias is also fairly stable so you can generally even subtract it out with a little bit of care. And really, the microarchitectural state starts dominating at that point anyways, so anything more fine-grained than that starts depending on making sure the surrounding code did not mess up your L2 or branch predictor and such.
https://github.com/janestreet/magic-trace
Not that the exact tracing relies on Intel PT - support for AMD was added recently but uses perf so suffers from the same sampling/skew issues, but is still very useful.
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.
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?
To back up parent's point, if you compile the code and the resulting assembly is a direct translation, renaming will break the dependency and the CPU will execute the instructions in parallel. Write after read hazard is the applicable section:
This is much more likely a quirk of the interpreter (or possibly a fucked up test). CPU details are like 10000 feet down.
A CPU can do more than one thing at once by computing the next instruction while it's still writing the result of the previous one. However, the CPU can only do that if it's 100% sure that the next instruction does not depend on the previous instruction. This optimization sometimes can't trigger in an interpreter, because of highly mutable variables such as the program counter or the top of the interpreter stack. Fun illustration: https://www.youtube.com/watch?v=cMMAGIefZuM&t=288s
I guess the first thing worth doing when analyzing this would be looking at the differences in the bytecode, then looking at the C code implementing the differing bytecode ops. But there also other factors, like the new adaptive interpreter trying to JIT the code.
Single-line dual assignment:
2 2 LOAD_FAST 0 (a2)
4 LOAD_FAST 1 (c)
6 BINARY_OP 0 (+)
10 LOAD_FAST 1 (c)
12 LOAD_CONST 1 (2)
14 BINARY_OP 0 (+)
18 STORE_FAST 1 (c)
20 STORE_FAST 0 (a2)
2 2 LOAD_FAST 0 (a2)
4 LOAD_FAST 1 (c)
6 BINARY_OP 13 (+=)
10 STORE_FAST 0 (a2)
7 12 LOAD_FAST 1 (c)
14 LOAD_CONST 1 (2)
16 BINARY_OP 13 (+=)
20 STORE_FAST 1 (c)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.
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/4be5c05975c250d0ea88b62c03f1719...
So that's fun.
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.
So up to around 10^200 or so, which is around 2^600.
Measuring, gathering, reporting, understanding what you’re seeing. These are often very complex and time consuming.
IO buffering is also not as clear cut. If you're running on a terminal, sure. But if you're outputting to a log file, or running in a CI environment where your stdout is being captured and redirected to a parent process, moving to buffered IO changes the semantics significantly. Imagine this code:
log("dangerous precondition hit, logging some state:" + state);
function_crashes_here()
[0] https://stackoverflow.com/questions/48535727/why-are-c-stl-v...
You can't realistically measure everything. You start with a sensible design and implement the reasonable optimizations you learned by experience. Then measure and improve when and if you fail to hit your target.
Adding/removing IO buffering absolutely _does_ have side effects. If someone is running `./app >> /dev/null 2>&1`, then mucking arouind with IO buffering is going to have little to no effect.
[0] https://stackoverflow.com/questions/48535727/why-are-c-stl-v...
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
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.
The post doesn't say what units the terms a measured in, but it's evident from a quick test that the unit is ms. And when you're in the sub-ms time domain, if you don't know what you're doing, benchmarking is apt to reflect noise in its results.