This is a programming war story with a moral that I think is is important for those who care about their code running fast.
Lector · This happened about 1989 or 1990; I was working on a piece of software called Lector that I’ve written about before here. It was a lot like a browser; it displayed marked-up text driven by stylesheets that you could switch at run-time. Importantly, it did multi-column rendering, which was a requirement for our application, displaying dictionary entries. The stylesheets were not entirely unlike modern CSS, allowing you to use multiple fonts and weights and colours.
Lector ran under the X Window system, in its first incarnation as an XLib application, eventually as a Motif application, but with the low-level rendering and interaction still at the XLib level.
Selecting ·
I was adding selection to the system, so you could select a bunch of text
with your mouse just like you can in any program in any modern GUI.
It was really complicated, what with the multi-font display and so on.
The code worked something like this; when the user held the button down and
moved the mouse, your HandleMouseMove routine got called whenever
the OS felt like it, i.e. many times per second.
You could quickly find out if the mouse was over the same character as last
time, but if not, you had to do a lot of work.
There was a big data structure that kept track of where everything was on the
screen, and you had to traverse that whole data structure
figuring out which colum the mouse was in, then which line in that column, then
which character in that line.
Then you had to draw the selection, which involved figuring out the delta
from the current selection, un-reversing some parts and reversing others.
It was really a lot of complicated code and it took considerable
quality time with the debugger to get it actually working.
The Agony and the Ecstacy · Now, I was terrified about performance. This was on a Sun 3/260 or maybe 4/60 or something, the kind of processor you’d use today to run a toaster. In the back of my mind, I had all sorts of optimization schemes like building a tree over the layout and so on, but there was no way this was ever not going to involve plowing through a lot of lines of code.
To my amazement, it ran like a demon, no matter how fast I waved the mouse around the selected region kept right up with it, I never saw a noticeable lag. I dragged all my friends over to look at this magic and they looked blank and said “So you can select text, big deal.”
The Moral of the Story · Computers are amazingly, remarkably, unbelievably fast. When you’re executing compiled code that’s running around structures in memory (and they actually fit in memory), you can do stupendous quantities of computation with no perceptible delay.
It’s easy to forget that now; there are so many layers of database and application server and virtual machine and interface abstraction and method dispatching getting between our code and the metal that we often convince ourselves that the machines are slow. They’re not; and when you need something to run really really fast, you can always make that happen, if you can push the problem down to traversing in-memory data structures with compiled code.
Of course, often you can’t. This way of thinking about things is currently unfashionable, and in modern programming environments sometimes effectively impossible. But sometimes you need to do what seems impossible, and this is one way.
