George Kelly Flanagin

Originally published 9 November 2011

At every interview I have been to, there is someone who asks me about optimization, never suggesting optimization of what property, and assumed to be speed of execution. The question is usually asked in a slightly covert way, conspiratorially, and the in a tone of voice I associate with a thirteen year old who has just discovered kissing, and wonders if you, as an adult, may also know of its joys.

My answer is not the one that the interviewers seem to want to hear, but it is the truth: "I attempt no optimization until there is a demonstrated need." Perhaps a case study (or two) would help.

A very short case study

From a friend:

"I had a young web developer working for me. We were checking in some code and I noticed he had changed some of my Python scripts. I asked him why he had done it. He explained that my code was quite inefficient and he had optimized it. So, we ran my inefficient code and timed it; then ran his optimized code and timed it. Zero difference. He had not compared the running time of the two versions of code."

Sigh. My experience is that this kind of thing happens regularly.

A more serious case study

So, how about a detailed look at the process?

Before we begin, let's put the Axiom of Optimization front and center:

" We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

This advice has its origin, at least in print, with Donald Knuth in 1974. I was still five years away from programming at that time, so the advice predates me. But my first serious mentor in the world of programming for money was a guy named Dr. Larry Andrews. "Dr. Larry" put me on the straight and narrow when I was 28 years old, and I have been doing things his way since.

Two months ago I wrote bLaTheR, a Lorem Ipsum replacement. For me was part a learning experience to absorb jQuery, part load testing for a server process, and part entertainment. There is nothing difficult about what is being done; the program searches a database of text, rearranges it, and returns some trashed up text that statistically resembles the input.

The simplicity of bLaTheR made it the ideal program for doing optimization explorations.

With bLaTheR running, it was time to study its performance. It had been written in the QUick-And-Dirty (QUAD) style of most weekend projects, and therefore probably the most unoptimized approach imaginable. But, the unoptimized approach allowed me to clearly instrument the steps:

1. get the text from the database, assemble any multiple shreds, and put the result in a buffer
2. parse the buffer into a trie (single pass) suitable for the derivation
3. navigate the trie to generate the text, and stuff the text into the return message.

As I mentioned, bLaTheR was slipped into the framework of an existing daemon that was known to work well in terms of the basic daemon functionality, so these three steps were the three places to look for improvements rather than the daemon's framework; a key benefit of code reuse.

Instrumentation in the form of a POSIX microsecond stopwatch gave some rough order of magnitudes. I chose the benchmark of a 2K byte shred (typical use) and an analysis depth of 5 using a 20K byte source.

It is clear which step needs the work. One of the first mistakes in optimization is to go after something that is already quick just because you can figure it out or because you suspect it. In the above example, if we could do the text generation in a single CPU cycle, we would still be left with 52/61 of the work. It is frequently tempting to point one's early suspicions toward the I/O, but in this case neither the I nor the O appears to be at fault.

(One other fact of note, step [3] is linear with respect to the amount of bLaTheR that is requested. The other steps take a constant amount of time per request and have nothing to do with how much text is requested.)

I started down the obvious path. There was no need to parse the same text each time to build the trie. The difficult part, of course, was finding a way to store the trie in the database -- a coding adventure sure to pre-bug or re-bug the working code.

But the next day I had a new version of bLaTheR ready to go. I added a trie-table to the database, and put logic in the code to check there first. If the appropriate trie was not found, bLaTheR would go get the text and build the trie, store it, and then try trie again. No text would ever be parsed more than once, so regardless of how slow the parsing operation might be, it was eliminated from the overall performance. Another lesson in optimization: operations that are only done once are usually not worth consideration for performance tuning.

I reworked the instrumentation so that I now had three new steps:

1. get the trie from the database.
2. assemble it in memory.
3. navigate the trie to generate the text, and stuff the text into the return message.

I spun up the new version of bLaTheR expecting a staggering improvement. I was half correct: it was staggering.

Clearly my method of storing the trie in SQLite was ill considered. OK, it wasn't really considered at all; in my haste to look like an expert for Scott and other friends, I had minimized the time spent thinking about the problem rather than the execution time of the code. Another day, another 86,400,000 milliseconds lost to ego.

After yet one more day, I had a much better method of storing the trie, and I got the load time down to 4ms. This system also resulted in fewer steps to assemble the trie in memory, which improved things a bit more. So now I was left with:

There are two things to consider at this point, and as is so often the case there is good news and bad news.