Making Code Faster
tbray.org
tbray.org
Unfortunately, 9 times out of 10 I hear these often quoted phrases is when engineers defend their status quo bias during code review.
The full quote from Knuth is this;
“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.”
In your example clearly if there are two approaches and one is 20* faster than the other it's optimization in the right place.
But... it's the "at the wrong times" bit that's actually the most important part. If you have a working solution and you're spending time trying to make it faster without knowing it's too slow then you're trying to optimize at the wrong time. If you know both approaches then it's fine, and good, to pick the faster one. If you don't then you should use the one you know and come back later if you need to.
Most of the time you won't need to.
I sometime try this approach and write the better implementation in front of the dev if possible.
He breaks "making a program go faster" into 3 modes: (1) "optimization" which includes counting expected cycles or memory bandwidth, careful benchmarking, designing custom algorithms, etc which can be fun but is expensive and is only rarely applied; (2) "non-pessimization" which is simply avoiding adding extra unnecessary work for the cpu, which should be done 100% of the time but isn't in the industry today; (3) and "fake optimization" which is shallowly repeating 'optimization tips' and conclusions from unrelated cases of (1) without actually measuring it.
"non-pessimization" is my most loved technique because a design reduced to the minimum amount of necessary work and abstractions is more often than not has better performance and is easier to reason about.
The profiler, which can do CPU, memory, goroutines, blocking, etc. and can display all of that as a graph or a flame graph, as well as `go tool trace` which gives you a full execution trace, including lots of details about the work the GC does. All that with interactive local web-based viewers.
Performance optimization is always so fun with it.
Unless your software is intended to reload blog posts live like Hugo/Jekyll/other static site generators and it takes ~5,000 ms on an i9 machine when it could take 100 ms if different languages and different implementation choices were made. This is the story of modern software: "I don't care how much time and computing power I waste. It's not the core app of some FAANG giant, so I'm not going to bother, ever."
Could we have houses that are 100x stronger and longer lasting if we allowed a few extra weeks of construction time? Could we 10x battery capacity with a slightly more sophisticated manufacturing process?
I don't think many developers nowadays understand how fast computers are, nor how much needless bloat is in their software.
I dont know about construction or batteries.
Most, as in > 50%, of developers aren’t in a position to decide which languages, libraries and tools to use, or how much time they can spend on performance improvement.
What I was trying to get at was that in these cases the ruby/python/whatever parts are not actually fast, they just do much less stuff. Add that the database might be on another machine, so there's plenty of overhead as well.
Aside: You can sometimes get orders of magnitude of speed gains just by using an embedded database and a fast language on top if your workload allows it. Essentially you don't really do much to get this, just cut overhead.
From a "get the bills paid" point-of-view, any good project manager also has to know when to tell an engineer to focus on getting the product shipped instead of chasing that next 5% in throughput/latency reduction/overhead. I've seen my fair share of programmers (including myself) refuse to ship to a project because the pursuit of some "undesirable" latency and not finish more important features.
For tasks like video streaming, Automation software (CI pipelines to robotics), video games, professional tools for content creation (DAWs, video editing, Blender, etc.) performance is the feature, but then your product is helping them get the bills paid faster. Medical apparatus(es?) and guidance software on autonomous vehicles are examples of where latency is a life-or-death situation.
I think everyone would benefit from playing with OpenRTOS, or writing some code that deals with video/audio where there are hard deadlines on latency. But I'm never gonna hold some weekend-project static site generator in Ruby to the same standard as macOS.
> But for code that’s on the critical path of a service back-end running on a big sharded fleet with lots of zeroes in the “per second” numbers, it makes sense to think hard about performance at design time.
Your scenario falls under that category.
This falls into this?
> But for code that’s on the critical path of a service back-end running on a big sharded fleet with lots of zeroes in the “per second” numbers
A static site generator is a simple utility that should take 100ms at most on a modern crappy laptop. It's not some backend service that's in a critical path, but it's also not a difficult engineering task. Parse input, produce output. This isn't something that should take seconds, which I think is what the OP was getting at. But because of the language choices made, and the millions of lines of bloated code, it does take seconds.
In the former case, the performance really doesn't matter. If you've got a personal blog, does it matter if your update takes 10 seconds or 1 second? Probably not, if it does it's the most important blog in the world.
If you've got customers with many blogs and need to take their updates and render them, then the performance matters because it's shifted from 1 to many (hundreds? thousands?). And now that 10 second delay is a big issue, you're either using a fleet of servers to handle the load or some customers don't see updates for days (oops).
If you decided to deploy a tool that's designed to be run infrequently, and in a non-time-sensitive way, on a centralized service - it's up to you to make it fast or parallelize it (e.g. github pages).
Trying to say that some piece of software is badly written or designed because it can't be used in a way it's not designed to be used, just seems silly. If I use `grep` to do realtime audio processing, I'm probably going to have a bad time.
But if it's just a personal blog? Who cares if it takes 10 seconds or 1 second unless it's rendering many people's blogs? In which case it would, again, be moved to the system's critical path as a blog hosting service.
It shouldn't matter, but the fact that you framed the question as 1 second in the fast case shows that this does matter haha. The fast case in this scenario should be under 10ms, and the slow case should be half a second. It shouldn't take anywhere near 1 second to generate a static site!
A modern low end CPU can process upwards of 40GB/s of data. The last time I checked, the entire set of encyclopedia Brittanica is only around 1 GB. I don't know many blogs that approach that much information. At most, a blog probably only has around a few tens of Kilobytes of actual text. It should never take more than a second to process that, but it often takes upwards of 30 seconds to several minutes.
This is what I was trying to emphasize before haha. Even if code isn't in the critical path, there's no reason it should take several seconds to do almost anything, unless it involves communicating over a network. We can stream audio/video data over a network in real time on low end computers through Zoom. That's gotta be processing several MB of information at least every second in real time. If we can do that, surely we should be able to build a static site generator that can generate any blog in under a second, right?
What I'm trying to say is that those languages that everyone is quick to judge right now have given us 10, maybe 15 years of extra "life", a period when most of us have "made" our careers and, well, most of our money (those who have managed to make that money, that is). We wouldn't have had (what basically are) web companies worth tens, if not hundreds of billions of dollars, if the web had still meant relying on Struts or on whatever it is Microsoft was putting forward as a web framework in the mid-2000s. We wouldn't have had engineers taking home TC worth 500-600k and then complaining that Python or Ruby are not what the world needs.
Come to think of it maybe some data historians at Google can look through the Googlebot logs and not only and compare the percent of websites that they think were .php-run (let’s say) over all this period, in both nominal and relative terms. It is my hunch that those websites represented a big chunk of Googlebot’s hit targets for most of Google’s (the company) existence, hence why I think my comment is valid (among other things)
My beef with such technologies... is not with the technologies at all. It's with the people that can't let go and can't recognize that things do change (or they are simply afraid that they have to learn new skills; many programmers are very risk-averse and are very average Joes and Janes just wanting to make a living and they hate the idea of having to learn their entire careers -- not sure if that's "fine" but it obviously works well for millions of them out there).
Same as with these old non-GNU UNIX tools zealots; some of them still fiercely are against the GNU tools... meanwhile a lot of the DevOps people I know (and no small amount of programmers, yours truly included) already move about 75% of their scripting workloads either to the newer Rust variants (rg, exa, fd-find, tuc, and many others) or lightweight quick script-friendly languages like Nim or OCaml.
So my broader point was: "we should utilize nostalgia as a driving force much less than we do right now". Hence my question.
I'll agree with you that the alternative bleak early-dystopian future that PHP et.al. prevented would be horrid and -- again -- I'd recognize the role of the early free / open-source tech as a positive driving force of the IT history.
Edit: Oh and I should mention if you want the method level tracking on a run similar to some of his screenshots, if you pay for a Resharper license that comes with dotTrace I believe which gives you that sort of tracking.
There are very few companies that I'm really rooting for, but JetBrains is absolutely one.
One time at work I dug up something that removed 75% of the runtime of an application because it turned out taking the length of an image was actually a method even though it looked like a simple property, so I cached it at the start of processing each image instead of foring over it over and over. It was insane how much faster the code became. I tracked that down with dotTrace.
And yeah dotMemory is also fantastic, I've dug up some GNARLY memory usage with it. Probably should have mentioned it since I was bringing up the memory portion of BenchmarkdotNet.
These days, async profiler (https://github.com/jvm-profiling-tools/async-profiler) is much better than the Go tooling for performance. It is a joy to use and features a top-like view for the hottest methods. It works for locks, allocations and CPU time. It also integrates with JMH.
But my time is sometimes cheaper than 10 other developer's time. Or 50. Or all of our customers now and in the future: https://xkcd.com/1205/
Additionally, a fatal flaw of most project management theory is that it measures time as the constrained resource, which is rarely if ever the case. The real constraint is not time. It's either attention or energy, depending on the context (and motivation). We are not machines. Taking 10 minutes off of a process doesn't necessarily allow us to get 10 more minutes of work done, while taking 5 minutes off of another may actually save us 15.
1. Here is the input, e.g., https://data.sfgov.org/api/views/acdm-wktn/rows.json?accessT...
2. Here is the desired output, e.g., a sample showing what the output is supposed to look like
> Make it work, then make it right, then make it fast.
Applies to core language choice, I used to hear a lot about rewriting interpreted langs to something faster... but the reality is that a team that's just spent 1 year making an app in python aren't going to pivot to writing Java, Go, or Rust one day. The new team isn't going to be building something new and exciting, they are going to be on a tight timeline to deliver a port of something which already exists.
I have found that his advice on using profilers was very important. I thought I knew where it would be slow, but the profiler usually stuck its tongue out at me and laughed.
When I ran a C++ shop, optimization was a black art. Things like keeping code and pipelines in low-level caches could have 100X impact on performance, so we would do things like optimize to avoid breaking cache. This often resulted in things like copying and pasting lines of code to run sequentially, instead of in a loop, or as a subroutine/method.
It's difficult. There's usually some "low-hanging fruit" that will give awesome speedups, then, it gets difficult.
This is why it is frequently helpful to look at the code generated by the C++ compiler. It gives you insight into the kinds of optimizations the compiler can see and which ones it can't, so you can focus on the ones it struggles with. This knowledge becomes out-of-date on the scale of years, so I periodically re-check what I think I know about what the compiler can optimize.
For some things, like vectorization, the compiler's optimizer almost never produces a good result for non-trivial code and you'll have to do it yourself.
[1]: https://stackoverflow.com/questions/375913/how-can-i-profile...
The story I heard, is that the author threw it together to reinforce his side of an argument about code efficiency.
I wonder how Matt Godbolt feels about being used or about being called "it".
Joking of course - it was an odd choice to use $surname.org for one specific tool he built.
Compilers can and do allow themselves license to ignore ABI in some cases; for c and c++, this includes link-time-optimised programs and -fwhole-program &c, as well as straight-up localised transformations on localised data structures (for whatever value of 'local' you prefer). Many other programming languages, in particular including JIT-compiled ones, also do not specify any ABI at all.
Modern C++ in particular encourages the extensive use of expressive compile-time metaprogramming to automate optimization that the compiler cannot. In theory, the heavily optimized data structure and algorithm code that is often generated in C++ could be manually written in C or similar. However, in practice, few software engineers have the patience or time to systematically apply those optimizations manually to everything in their code base. I know for a fact that I didn't when I was writing C.
That modern C++ tends to produce the most highly optimized code is more a matter of economy than theoretical capability.
In Rust you can annotate a function with `#[inline(always)]` which makes is not a suggestion; it'll always inline it AFAIK (unless it calls itself recursively where, by definition, inlining is not possible).
Clang also has a flatten attribute which can be interesting: it does the conjugate of marking functions inline: the function to which it is applied to will have all its own content inlined, e.g. [[clang::flatten]] void f() { a(); b(); }
will inline a and b
Having recently worked on a large C/C++ code base which had a heavy focus on performance observation, I found myself wondering if tricks like dynamic Code Generation to avoid method overhead and unnecessary branch checks actually had a significant benefit on performance relative to the developer economy impact.
We tended to use clang/llvm.
I know that we often had to actively work against the native optimizations.
We had a team from Intel, that used to run these awesome tools on our code, and helped us to see a lot of these weird dichotomies.
It works if you have lots of things communicating over APIs.
Anyone who had the "pleasure" of using Amazon's internal tools can talk about how "Make it work ASAP" attitude has worked out for their internal tooling :) LPT anyone?
You don't actually have to make it fast, but you have to be designing w/ an eye towards eventual speed. Otherwise you end up w/ a mess that can be made faster, but never fast.
At least that's been my experience.
VisualVM <https://visualvm.github.io/> is quite good for Java/JVM profiling.
We have a number of algorithms in Solvespace that are O(n*2) some of them accidentally because certain list operations are O(n). One of the worst offenders was accidentally O(n*4) because an n*2 size input was handed to an O(n*2) algorithm. I wrote a smarter algorithm to avoid that inner call entirely.
TLDR it shouldn't be hard for tooling to produce useful time complexity estimates. Can we get this please?
You can spend all week shaving 15% off of an inner loop function or you can notice that it's being called 3x as much as you expected, fix that problem, and get a 60% performance improvement without changing a single line of that function.
"I approve too! But… Sometimes it just has to be fast, and sometimes that means the performance has to be designed in. Nelson agrees and has smart things to say on the subject."
- so... you're saying premature optimization isn't the root of all evil. Maybe it's time to retire this tired 'conventional wisdom'
>> 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.
Funny you mention it. I have a bit of a habit now of reminding people what the remainder of Knuth’s quote actually was.
“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%.”
The irony of walking away with the impression that Knuth was saying to not do optimization is that his point was the exact opposite of that, he was emphasizing the word premature, and then saying we absolutely should optimize, after profiling.
This all agrees completely with the article’s takeaways: build it right first, then measure, and then optimize the stuff that you can see is the slowest.
Anyone optimizing via microbenchmarks or wall time exclusively isn’t going to see this.
Identifying loops or recursion with many iterations (high N) with a high Big O order may also be avoided during the design stage, of you KNOW the N and O-order at design time. (And don't worry about the O-order for low N problems, that is premature optimization most of the time.).
On the other hand, tweaking every single statement or test in ways that save 1-2 cycles is rarely worth it. Often you end up with obfuscated code that may even make it harder for the compiler to optimize for. This is the 97% of the code where premature optimization makes things harder.
Some programmers may turn this on its head. They don't understand the implications of the design choices, but try to make up for that by employing all sorts of tricks (that may or may not provide some small benefit) in the main body of the code.
The only optimization type I understand that with is very isolated but convoluted fixes that buy performance at the cost of readability/etc. Intelligent architecture that is fast, so long as it is does not completely obfuscate the intent of the code, is not premature.
Even if we parse his "But..." as saying, "there exists some premature optimization which is not the root of an evil" (ignoring probably valid quibbles about whether the optimizations he's talking about truly are premature), this doesn't contradict the original statement.
In fact, "the root of all evil" seems to be an expression which invites us to commit the fallacy of denying the antecedent -- if premature optimization, then evil, in this case -- because it is almost always used to indicate that the first thing is bad.
I was going to "tongue-in-cheek overthinking" but I think it didn't really come through.
I hate this quote, but less than the "Memory is cheap" mantra..
For "CPU time", if it's a critical path for something with a lot of users and/or where performance is key, the engineer's time is just a fraction.
Somehow programmers care about the big O notation, but not when it's about other people's time.
Scale is key here, but fast software is always a much better user experience than slow stuff as well. With the compiler example, if it takes 1s as opposed to 1h, then users can iterate much more quickly and get a lot of flexibility.
If you require an ROI of 5 years, no interest included, you just created $600k in value over a few weeks.
Something that used to be precomputed offline can be done in real time. Something that used to work on a small samples can be applied to the whole data set. Something that used to be coarsely approximated can be computed precisely. Something that used to require large clusters of machines can be handled on customers’ client devices. Something that used to be only an end in itself can be used as a building block for a higher-level computation. Etc.
/logical comparison/ int greater_abs(int num, int x){ return (num > x) || (num+x < 0); }
/squared approach/ int greater_abs2(int num, int x){ return num*num > x; }
See it by yourself, with (and without) optimizations: https://godbolt.org/
What would happen if x is a compile-time constant?
How frequently am I calling `abs`?
Well if that were the case, I’d use a profiler to see if spending time on optimizing ‘abs’ would realistically be worth it.
In practice, just writing "abs(num) > x" gives quite good machine code, and it does so without introducing hard-to-see bugs.
In the 2nd, which I assume should be
{ return num*num > x * x; }
Godbolt uses whatever compilers, targets, and optimisations you ask it to.
It is, in fact, a very useful tool for comparing different compilers, architectures, and optimization settings.
Most real software has a complicated relationship with Amdahl's Law, and there are often ways to reduce latency without really changing the ops/sec. That's true for IPC, but also true for the processor itself. Sometimes using the 'wrong' instruction for an operation increases the instructions per cycle.