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.

Debugging 401: Practicum

OK, enough with the generalities, it's time for a concrete example. And yes, I realize that debugging stories are much like fishing stories — and that fishing stories aren't terribly interesting. I've tried to stay focused, but I'll understand if you fall asleep.

A week or so ago, I saw a question on Stack Overflow that let me put all of these techniques to work. In fact, it was a nearly perfect case study of the debugging process, not to mention interesting enough to take an hour out of my day.

The question seemed simple enough: the person posting it was trying to set the F2 key as a menu accelerator in a Swing application (for those not familiar with GUIs, an “accelerator” is a way to invoke a menu item using a single keystroke; for an example, Netscape's “New Window” accelerator is Ctrl-N). On the surface, this seemed like user error, and since I happened to be working on a Swing app at the time, I changed one of my menu items to use F2 so that I could respond with the “correct” code. To my surprise, it didn't work: the F2 keystrokes seemed to vanish.

Other responders had suggested that perhaps the operating system was capturing the keypress event before it got to the program, and this seemed like a reasonable hypotheses: think of Alt-Tab or Ctrl-Alt-Delete under Windows. So, applying Scientific Method, my first task was to falsify that hypothesis, and I created a SSCEP to do so.

This first program was extremely simple: a JFrame with a JLabel as its content, and an event handler that listened for keystrokes and printed them. I ran it, hit F2, and saw that the keystrokes were being reported. Time for a new hypothesis.

My second hypothesis was that the F2 keystroke was being remapped by the operating system, so that it appeared to be some other key. Since my SSCEP was printing the keycodes, and the JDK comes with source code that showed the expected keycodes, I could easily check this. Another hypothesis falsified.

Next hypothesis: the Swing menu system is ignoring F2. Seems unlikely, but I'd apparently exhausted all other answers. So I added a menu to the SSCEP, and printed its invocations. And had another hypothesis shot down: F2 invoked the menu item.

By this point I was hooked: I saw the behavior in my own program, but wasn't able to replicate it in a SSCEP. Time to step back, and think about how my SSCEP differed from my actual application. This was easy: my program's main window was a simple tabular display using a JTable; other than that, just a menu. So I replaced the JLabel in my SSCEP with a JTable, and the F2 key stopped working!

Time for some research, starting with Sun's bug database; nothing there about JTable breaking accelerators. A little more research, and I ended up at the Sun tutorial on key bindings. Oh yeah, I remember that: individual components can intercept keystrokes; it's how the text components implement copy and paste without any program code.

This seemed very promising, so I changed my SSCEP to call getInputMap() on my table, and printed the key bindings. And didn't see a binding for F2. However, I was not yet ready to abandon this hypothesis — largely because I didn't have any others waiting.

So I fired up the debugger. Since I suspected that the table was consuming the keystroke itself, I set my first breakpoint in the processKeyEvent() method. This is a short method, so stepped through it and saw that yes, the event was being consumed due to a key binding.

It took me a little more time, but I discovered that the key binding in question wasn't in the “normal” binding map, which was why I didn't see it when I first examined the bindings. I won't bore you with the details; suffice to say that this discovery came from continued application of the scientific method, along with a little background reading of code and JavaDoc. And led to an answer that the original poster seems to have ignored … oh well, at least I had fun debugging.