The Optim(al|um) Way to Optimize Optimization


Note: This article is a version of what later became two separate articles exclusive to the Toptal Engineering Blog: Code Optimization: The Optimal Way to Optimize and How to Avoid the Curse of Premature Optimization.

I’m an optimist, Optimus.

At least, I’m going to pretend to be an optimist while I write this article. For your part, you can pretend your name is Optimus, so this will speak more directly to you.

Attracted here by the title? Optimization of any kind is clearly a good thing, judging by its etymology, so naturally, you would like to do it better. Not just to set yourself apart from the crowd as a Better Developer Who Will Hopefully Not End Up Being Mocked on TheDailyWTF, but because it’s the Right Thing to Do. You take pride in your work. You wonder at how computer hardware keeps getting faster, but whatever simple thing that you Just Want to Be Able to Do, Dammit keeps taking longer with each new simple thing. (It’s called Wirth’s Law, BTW, having been popularized by Pascal inventor Niklaus Wirth.)

You want to buck that trend. Be lean. Efficient. Awesome. Someone like the Rock Star Programmers after which those job postings are clamoring. So when you write code, you make sure it’s Done Right the First Time (even if “right” is a highly relative term, here), because that’s the Way of the Clever Coder, and also the Way of the Those Who Don’t Need to Waste Time Refactoring Later. I feel that. The force of perfectionism is sometimes strong within me, too. You want to spend a little time now to save a lot of time later, because you’ve slogged through your share of Shitty Code Other People Wrote and What the Hell Were They Thinking? That’s SCOPWWHWTT for short–because I know you like acronyms as much as Flint Lockwood–and you don’t want your code to be that for someone else.

That’s noble of you, but stop.

§ Just stop!

You are in gravest danger of thwarting your own goals, no matter how experienced you are at programming. The pre-emptively badass code you are writing is even more likely to become SCOPWWHWTT for the next unlucky person who has to comprehend your FLDSMDFRcode, which may even be yourself. And someone smart and capable, like you, can avoid sabotaging your own code, by keeping your noble ends, but re-evaluating the means, despite the fact that they seem to be unquestionably intuitive.

Let us listen to the advice of the sages, here, as we explore together Michael A. Jackson’s famous rules of program optimization:

  1. Don’t do it.
  2. (For experts only!) Don’t do it yet.

§ 1. Don’t do it: Channeling perfectionism

I’m going to start with a rather embarrassingly extreme example from a time, long ago, when I was just getting my feet wet in the wonderful, have-your-cake-and-eat-it-too world of SQL. The problem was, I then stepped on the cake, and didn’t want to eat it anymore, because then it was wet and smelled like feet.

Wait, let me back out of the car-wreck of a metaphor I just made, and explain.

I was doing R&D for an intranet app, which I hoped would one day become a completely integrated management system for the small business where I worked. It would track everything for them, and unlike their system at the time, it would never lose their data, because it would be Backed by an RDBMS, Not Some Flaky Home-Grown Flat File Thing That Other Developer Used. I wanted to design everything as smartly as possible from the beginning, because I had a blank slate. Ideas for this system were exploding like fireworks in my mind, and I started designing tables. Contacts and their many contextual variations. A CRM. How accounting, inventory, and purchasing would fit in. Project management, which I would soon be dogfooding.

That all ground to a halt, development- and performance-wise, because of…you guessed it, optimization.

I saw that so many ‘objects’ (represented as table rows) could have multiple different relationships to each other in the real world, and that we could benefit from tracking these relationships: First, we would just be better-organized, and second, at some point they could help automate business analysis all over the place. And somehow this manifest itself as an engineering problem of some kind, but I forget the details. So I did something that seemed like an optimization of the system’s flexibility.

At this point, it’s important to look out for your face, because I will not be held responsible if your palm hurts it. Ready? I created two tables: relationship and one it had a foreign-key reference to, relationship_type. relationship could refer to any two rows anywhere in the whole database, and describe the nature of the relationship between them.

Oh, man. I had just optimized that flexibility so damn bad. Too much, in fact. Now I had a new problem: a given relationship_type would naturally not make sense between every given combination of rows. While it might make sense that a person had a employed by relationship to a company, that wouldn’t really fit (at least semantically) the relationship between, say, two documents.

OK, no problem. We’ll just add two columns to relationship_type, specifying which tables this relationship could be applied to. (Bonus points here if you guess that I thought about normalizing this by moving those two columns to a new table referring to relationship_type.id, so that relationships that could semantically apply to more than one pair of tables would not have the table names duplicated. After all, if I needed to change a table name, and forgot to update it in all applicable rows, that could create a bug! In retrospect, at least bugs would have provided food for the spiders inhabiting my skull.)

Thankfully, I was knocked unconscious in a cluestick storm before travelling too far down this path. When I woke up, I realized I had managed to, more or less, re-implement the internal foreign-key-related tables of the RDBMS on top of itself. (Normally I enjoy moments that end with me making the swaggering proclamation that “I’m so meta,” but this, unfortunately, wasn’t one of them.) Forget failing to scale: the horrendous bloat of this design made the back-end of my still-simple app, whose DB was hardly populated with any test data yet, nearly unusable.

Just use the foreign keys, Luke. (Insert meme graphic here.)

In this case, the optimization wasn’t even premature, because flexibility is in the realm of architecture. I didn’t even need to benchmark it, because it failed so spectacularly in both the metric I wanted to improve (it became way too flexible) and one I wasn’t even looking at yet (it became completely unperformant.) We’ll come back to those two concepts soon, but meanwhile this is certainly an example of optimization gone awry. My perfectionism completely imploded: my cleverness had lead me to produce one of the most objectively unclever solutions that I have ever made.

§ Welcome to this being an art

My cobwebby brain likes to create order where possible, so it will take every ounce of optimism for me to consider what I’m about to say to be a good thing.

I am going to take the nice, simple rule of Don’t do it, which sounds quite easy to follow rigidly, and tell you that not everybody agrees with it. I also don’t agree with it completely. Some people will simply write better code out of the gate than others, and hopefully, for any given person, the quality of the code they would write in a greenfield project will generally improve over time. But I know that, for many (most?) programmers, this will not be the case, because they more they know, the more ways in which they will be tempted to prematurely optimize.

So this Don’t do it is not, and cannot be, an exact science, but is only meant to counteract your internal urge to Solve the Puzzle. This, after all, is what attracts many programmers to the craft in the first place. I get that. But save it. Resist the temptation. If you need a puzzle-solving outlet right now, dabble in the Sunday paper’s Sudoku, or pick up a Mensa book, or whatever. But leave it out of your code until the proper time. Almost always this is the wiser path.

I’m not saying we should pick the most brain-dead way we can think of at every level of design. Of course not. But instead of picking the most clever-looking, we can consider other values:

  1. The easiest to explain to your seasoned coworker
  2. The easiest to explain to a new hire
  3. The most maintainable
  4. The quickest to write
  5. The easiest to test
  6. The most portable
  7. etc.

But here is where the problem shows itself to be hard. It’s not just about avoiding optimizing for speed, or code size, or memory footprint, or flexibility, or future-proofedness. It’s about balance, and about whether what you’re doing is actually in line with your values and goals. It’s completely contextual, and sometimes impossible to measure objectively. It’s an art.

Why is this a good thing? Because life is like this. It’s messy. Our programming-oriented brains sometimes want to create order in the chaos so badly that we just multiply the chaos. It’s like the paradox of trying to force someone to love you. If you think you’ve succeeded at that, it’s no longer love. If you think you’ve found the perfect system for something, well…enjoy the illusion while it lasts, I guess.

Embrace imperfection. Stay focused. Calm. And…

§ Optimize your habits, not your code

As you catch yourself tending to refactor before you even have a working prototype and unit tests going, consider where else you can channel this impulse, besides Sudoku and Mensa, that will actually benefit your project.

  1. Clarity and style
  2. Coding efficiency
  3. Tests
  4. Profiling
  5. Your toolkit/DE
  6. DRY

Just like my last list, which has some overlap with this one, optimizing the heck out of any particular one of these will come at the cost of others. At the very least, it comes at the cost of time.

Here’s where it’s easy to see how much of an art this matter is. For any one of the above, I can tell you stories about how too much or too little of it was thought to be the wrong choice. Who is doing the thinking here is also an important part of the context. For example, regarding DRY: At one job I had, I inherited a codebase that was at least 80% redundant statements, because its author apparently was unaware of how and when to write a function. The other 20% of the code was confusingly self-similar. I was tasked with adding a few features to it. One such feature would need to be repeated throughout all of the code to be implemented, and any future code would have to be carefully copypasta’d to make use of the new feature. Obviously it needed to be refactored just for my own sanity (high value) and for any future work anybody else might do to it. But because I was new to the codebase, I first wrote tests, so that I could make sure my refactoring did not introduce any regressions.

In the end, I thought I had done pretty well. After the refactoring, I impressed my boss with having implemented what had been considered a difficult feature with a few simple lines of code; moreover, the code was overall an order of magnitude more performant. But it wasn’t too long after this that the same boss told me I had been too slow, and that the project should already have been done.

I still think I took the right course there, even if it wasn’t appreciated directly by my boss at the time; I’m sure I could have found a delicate, unslanderous way to communicate the value of what I had accomplished.

Contrast this with some work I did on a small side-project of mine. In the project, I was trying a new templating engine, and wanted to get into good habits from the start, even though trying the new templating engine was not the end-goal of the project. As soon as I noticed that a few blocks I had added were very similar to each other, and furthermore, each block required referring to the same variable 3 times, the DRY bell went off in my head, and I set out to find The Right Way to do what I was trying to do with this templating engine. It turned out, after a couple hours of fruitless debugging, that this was currently not possible with the templating engine in the way that I imagined. There not only was no perfect DRY solution, there was no DRY solution at all. So trying to optimize this one value of mine, I completely derailed my coding efficiency and my own happiness, because this detour cost my project the progress I could have had that day.

Even then, was I entirely wrong? Sometimes it’s worth a bit of investment, especially with a new tech context, to get to know best practices earlier instead of later. Less code to rewrite and bad habits to undo.

I think it was unwise even looking for a way to reduce the repetition in my code–in stark contrast to my attitude in the previous anecdote. The reason is that context is everything: I was exploring a new piece of tech on a tiny play project, not settling in for the long haul. A few extra lines and repetition would not have hurt anyone, but the loss of focus hurt me and my project.

That’s right, somehow I’ve concluded that seeking best practices can be a bad habit. Sometimes true, sometimes not.

And that’s what I meant when I said it’s an art, one whose development would benefit from the reminder, Don’t do it: it at least gets you to consider what values are at play as you work.

§ Let’s obsessively analyze something even more trivial for a second

I’m writing this in Markdown, so for Jackson’s rules above, I prefaced both points with 1. because Markdown just makes the list within an <ol> tag, which in HTML is rendered as an automatically numbered list. Making lists with all 1. is not a terrible habit to be in. In other contexts, you may want to add to your ordered list, and this saves you having to renumber things if you add before the end of the list.

Here, though, it’s clearly quite bonkers. I can’t add to his quote, because it’s a quote.

All the same, there’s no difference between how long it takes me to type 1. and 2., so I might as well always just write 1. to reinforce my good habit, whether it’s prudent in this context or not.

This seems like a good counter-example to the overall theme we’ve been exploring: I needlessly optimized something, but there was no net penalty for it, and some habit-related benefit for future writing. So you could argue that I did the right thing, because I know you love to argue about trivialities, and I know that you’ve got my back.

Umm… (insert funny meme here… right…)

Anyway, how do we know when optimization actually is a good idea?

§ 2. Don’t do it yet: When and how to optimize

Okay, so we want to become better experts, and you don’t really buy my “it’s an art” line, and are thinking that I should exclude myself from the “we are experts” assumption I implied there. That’s OK, I’m not offended. It can be a tough pill to swallow, and you’d rather have some more concrete advice, some that doesn’t lead you to even worse analysis paralysis than you were already prone to (sorry about that.) What are some concrete methods we can follow? Let’s dig in.

§ This isn’t a grass-roots initiative, it’s triple-eh

The TL;DR is: work down from the top. Higher-level optimizations can be made earlier in the project, and lower-level ones should be left later. That’s is all you need to get the full meaning of the phrase “premature optimization”: doing things out of this order has a high probability of wasting your time and being counter-effective.

Common wisdom has it that algorithms and data structures are often the most effective places to optimize, at least where performance is concerned. Keep in mind, though, that architecture sometimes determines which algorithms and data structures can even be used. I once discovered a piece of software doing a financial report by querying an SQL database multiple times, for every single financial transaction, then doing a very basic calculation on the client side. It took the small business using the software only a few months of use before even their relatively small amount of financial data meant that, with brand new desktops and a fairly beefy server, the report generation time was already up to several minutes, and this was one they needed to use fairly frequently. I ended up writing a straightforward SQL statement that contained the summing logic–thwarting their architecture by moving the work to the server to avoid all the duplication and network round-trips–and even several years’ worth of data later, my version could generate the same report in mere milliseconds on the same old hardware.

Sometimes you don’t have influence over the architecture of a project because it’s too late in the project for an architecture change to be feasible. Sometimes you can skirt around it like I did in the example above. But if you are at the start of a project and have some say in its architecture, now is the time to optimize that.

§ Architecture

In a project, the architecture is the most expensive part to change after the fact, so this is a place where it can make sense to optimize at the beginning. If your app is to deliver data via ostriches, for example, you’ll definitely want to structure it towards low-frequency, high-payload packets to avoid making a bad bottleneck even worse. In this case, you’d better have a full implementation of Tetris to entertain your users, because a loading spinner just isn’t going to cut it. (Kidding aside: Years ago I was installing my first Linux distribution, Corel Linux 2.0, and was delighted that the long-running installation process included just that. Having seen the Windows 95 installer’s infomercial screens so many times that I had memorized them, this was a breath of fresh air at the time.)

§ Algorithms and data structures

Check your standard library and ecosystem!

At this point it’s time to break out flame graphs and other profiling tools. Even the most experienced engineers will often guess incorrectly as to which part of their code is the current bottleneck. They may guess better more often than novices, but that’s not the point: The only way to know for sure is to profile.

Strength reduction is a good one here. If you do it, though, at least leave a comment. Not everybody knows or remembers every combinatorics formula. Be careful, though: sometimes what you think might be strength reduction is not in the end. For example, let’s suppose that x * (y + z) has some clear algorithmic meaning. If your brain has been trained at some point, for whatever reason, to automatically ungroup like terms, you might be tempted to rewrite that as x * y + x * z. For one thing, this puts a barrier between the reader and the clear algorithmic meaning that had been there. Worse yet, it’s now actually less efficient because of the extra multiplcation operation required. It’s like loop unrolling just caked its pants.

§ Assembly (micro-optimizations)

I wanted all sections to start with an A, so this is called Assembly, after the technique of optimizing code written in a language like C by including blocks written in assembly. But I also mean it in the sense of putting together the pieces of your code: the rather mechanical process of implementing an algorithm or data structure once it is known. I’m talking about line-by-line optimizations.

§ Some more Don’ts

Re-using a variable for multiple distinct purposes. In terms of maintainability, this is like running a car without oil. Only in the most extreme embedded situations did this ever make sense, and even in those cases, I would argue that it no longer does. This is the job of the compiler to organize. Do it yourself, then move one line of code, and you’ve introduced a bug. Is the illusion of saving memory worth that to you?

Blithe use of macros and inline functions. Yes, function call overhead is a cost. But avoiding it often makes your code harder to debug, and sometimes actually makes it slower.

Hand-unrolling loops. Again, this is something better optimized by an automated process like compilation, not by sacrificing your code’s readability.

The irony in the last two cases is that they can actually be anti-performant. Of course, we can prove or disprove that for your code, because we’re doing benchmarks, right? But even if you see a performance improvement, return to the art side, and see whether the gain is worth the loss in readability and maintainability.

§ Keeping the UX in mind

When improving the data structure or making your code have less boilerplate can worsen the UX. Letting the computer do what it can to help, but approaching UX optimization with a profiling mindset (e.g. saving the user one click on an uncommon process vs several on a very common process.) Hallway testing. Benchmarking e2e tests.

§ How to get better results from $1,400 hardware than from $7,000 hardware

Jeff Atwood of StackOverflow fame once pointed out that it can sometimes (usually, in his opinion) be more cost-effective to just buy better hardware than to spend valuable programmer time on optimization. OK, so suppose you’ve reached a reasonably objective conclusion that your project would fit this scenario. Let’s further assume that what you’re trying to optimize is compilation time, because it’s a hefty Swift project you’re working on, and this has become a rather large developer bottleneck. Hardware shopping time!

What should you buy? Well, obviously, yen for yen, more expensive hardware tends to perform better than cheaper hardware. So a $7,000 Mac Pro should compile your software faster than some mid-range Mac Mini, right?

Wrong!

Turns out that sometimes more cores means more efficient compilation…and in this particular case, LinkedIn found out the hard way that the opposite’s true for their stack.

§ Think before you disrupt

I don’t know about you people, but I don’t wanna live in a world where someone else makes the world a better place… better than we do. -Gavin Belson

As some final food for thought, consider how you can apply the idea of false optimization to a much broader view: your project or company itself. I know how tempting it can be: the thought that technology will save the day, and that we can be the heroes who make it happen. Plus, if we don’t do it, someone else will. But remember that power corrupts, despite the best of intentions. I won’t link to any particular articles here, but if you haven’t wandered across any, it’s worth seeking some out about the wider impact of disrupting the economy, and who this sometimes ultimately serves. You may be suprised at some of the side-effects of trying to save the world through optimization.

§ Conclusion

Well, Optimus, I hope you’ve enjoyed our whirlwind tour. I’m happy if you have come away with an expanded appreciation for any element of the art and science of optimization, like I have. Hopefully this helps us to cast off the notion of writing perfect code from the start, and to write correct code instead. We must remember to optimize from the top down, prove where the bottlenecks lie, and measure before and after fixing them. The optimal, optimum strategy to optimize optimization. Best of luck.