Micro-Optimization is Easy and Feels Good

Have you ever seen code like this?

private String foo(String arg1, int arg2)
{
    StringBuilder buf = new StringBuilder();
    buf.append(arg1).append(" = ").append(arg2);
    return buf.toString();
}

If you ask the person who wrote this why s/he used a StringBuilder rather than simply concatenating the strings, you'll probably hear a long lecture about how it's more efficient. If you're a bytecode geek, you can respond by demonstrating that the compiler generate exactly the same code. But then the argument changes: it's more efficient in some cases, and is never less efficient, so is still a Good Thing. At that point it's usually easiest to (snarkily) say “well, you should at least pre-allocate a reasonable buffer size,” and walk away.

These arguments are not caused by the time quantum fallacy. The StringBuilder fan recognizes that different operations take differing amounts of time, and is actively trying to minimize the overall time of his/her code. Never mind that, in context, string concatenation is rarely a significant time sink. The rationale is always “it can't hurt, and might help.”

This is the same attitude that drives curbside recycling. It feels good to put an aluminum can in the bin: the can can be melted down and reused, saving much of the energy needed to smelt the aluminum from ore. Doing so, however, avoids the bigger questions of whether aluminum is the most environmentally sound packaging material in the first place, or whether you should even be drinking the contents of that can.

In the same way, micro-optimizations let you feel good while avoiding the bigger question of what parts of your code should be optimized. Experienced programmers know that not all code should be optimized: there's an 80-20 (or more likely 90-10) rule at work. But finding the 10% that should be optimized is, quite frankly, hard.

It's not that we don't have tools: profilers of one form or another have been around since before I started working with computers. Java has had a built-in profiler since at least JDK 1.2, and a good profiler since (I think) 1.4. For that matter, some carefully placed logging statements can give you a good idea of what parts of your code take the longest (just be sure to use a logging guard so that you're not wasting CPU cycles!).

The real barrier to profiling — and by extension, intelligent optimization — is coming up with a representative workload. “Representative” is the key word here: you can write a performance test that spends all of its time doing things that your real users never do. Even when you think that you know what the users will do, it's tempting to take shortcuts: to profile an eCommerce application, you might add 10,000 items to a single cart. But the optimizations that you make after this test could be meaningless if the real world has 10,000 carts containing one item. And even if you get that right, there may be different implications running on an empty database versus one that has lots of data.

So yes, it's hard. But ultimately, the brain cycles that you spend thinking about representative workloads will have a greater payoff than those you spend thinking about micro-optimizations. And the end result feels better too, much like foregoing a can of soda for a glass of water.

The Time Quantum Fallacy

So why would someone who's writing a servlet worry about the time taken for a cast? I can't believe it's due to a fear of software bloat, simply because the relative impact is so minimal: a person truly concerned about bloat would think of replacing HTTP with a raw TCP connection. Or maybe UDP, to avoid all the overhead of ack/nack.

However, what if the questioner has a fundamental misunderstanding of how long it takes a computer to do anything? To be more specific, a belief that all operations take the same time, so removing a cast is just as good as removing a database lookup.

Experienced programmers will scoff at that idea. But think about it: on a human scale, all computer operations do seem to take the same amount of time. Google can come up with search suggestions in the time it takes you to type a single character; that involves a round-trip web request and some sort of database call.

Computer science classes reinforce this idea, with their emphasis on “Big O” analysis. The implications of such analysis is that an O(n²) algorithm is worse than an O(n log_n) algorithm, regardless of what the code actually does — or the context in which the code is executed.

In the real world, of course, context is everything. If I need to do lookups on thousands of items, a hashed lookup (O(1)) seems far more appropriate than a linear lookup (O(N)). But what if I only have a few items? Say, 10 or 20? Or if I only occasionally do a lookup? In this case, the O(1) versus O(N) analysis just doesn't matter. And a linear structure may be easier to construct and use than a hashed structure.

This brings me back to Mel. Mel's genius was not so much in understanding the instruction set, but understanding overall context. Of knowing how long each instruction took, how quickly the memory drum spun, and most important, when this knowledge made a difference. Perhaps that understanding only comes with experience, but I find that even experienced programmers fall into the micro-optimization trap, so there must be yet another factor at work.

The Urge to Optimize

I've a Servlet filter which performs the following type cast [...] What is the performance impact of such a cast? Is it worth to accept this performance degradation for a better architecture?

That's an exact quote from an online Q&A forum. The first response starts with an incredulous “As compared to handling a HTTP request?” (emphasis as written). To an experienced programmer, the questioner's concern is ridiculous: a cast takes nanoseconds, processing a request takes milliseconds; the difference is six orders of magnitude.

But questions like this aren't rare: on the same day, another user wanted to know the “exact” CPU difference, for allocating byte arrays in Java versus pooling them. Another was concerned about the performance of unsigned versus signed integers in C++. And yet another wondered how best to translate a Python program (not a module, a program) into C, “so that it can be smaller (and faster).”

Most of the answers to such questions involve platitudes about premature optimization; a few suggest profiling. Both of which are valid answers. And more important, well-publicized answers: a Google search on “software profiling” returns 5½ million results. And yet the micro-optimization questions keep coming. Why?

Part of the answer, I think, is that there are also an enormous number of pages devoted to “software bloat” — and an equally large fear that one's own software is bloated. Every culture has its creation myths, and The Story of Mel is a powerful myth for the software industry. Who wouldn't want to be Mel, a person who knew his machine so well that he laid out instructions according to the characteristics of its memory device?

I was one of the “new generation of programmers” that was the audience for that story; I started my professional career at about the same time the story was posted. At the time, I was doing a lot of low-level programming: one job involved inserting NOPs into an 8086 interrupt handler to ensure real-time response characteristics (real-time means predictable, not necessarily fast). Another job involved porting a windowing system that provided Macintosh-level capabilities for the Apple 2e.

To understand the latter project, recognize that this was 1984, the Macintosh had most of its windowing library in ROM, yet developers still struggled to fit a complex program (and user data) into its 128k of RAM. The Apple 2e had 64k of memory, which would have to hold this windowing library and a real program. The person who developed the library was perhaps the equal of Mel. I was nowhere close, and just porting the library was at the limits of my ability. I came into the project thinking I understood how to cram code into limited memory, I left with a much better understanding of the things I knew, and vague hints that there was a whole realm that I didn't.

I don't remember much of it now. With multiple gigabytes of RAM and megabytes of L2 cache, it just doesn't seem to matter. But one thing that I do remember is that it had nothing whatsoever to do with debates over the performance implications of a cast. You can find that lesson in the Story of Mel, if you look closely enough, yet somehow it always seems to be missed.