The 30-Second Mistake

When I think back to my early days at Xerox working on the Star (Daybreak), I remember how different the world was. Computers were slow, memory was scarce, and if you wanted to learn something, you hoped the right book on the shelf actually covered it. It was during that time that I learned one of the most important lessons of my career about optimization.

I was working on a Geographic Information System where drawing a map took around thirty seconds. The code did this using brute force. It checked the axis-aligned bounding box of every polyvector in the database against the current field of view. It was slow and didn’t scale.

The engineer who originally wrote the system was a brilliant guy with a Master’s in Computer Science from Stanford. He insisted this was optimal. I was skeptical, and hearing that only made me want to prove otherwise.

For the next couple of months, I became obsessed with speeding this up. Information was hard to come by. The closest reference I found was a small example of range searching in the first edition of Sedgewick’s algorithms book. It covered points, not regions, but it planted a seed. I kept whiteboarding with my office mate late at night, trying to reason my way through the bigger problem.

A lot of my thinking came from a simple intuition. If binary search partitions a one-dimensional space with a small decision tree, then a two-dimensional space could be tamed with something one dimension higher. That led me to build a three-dimensional tree that avoided most unnecessary comparisons.

I left Xerox before the project was finished, but I licensed a similar dataset and completed the work around a year later. My search ran about 10x faster than the brute-force version in my tests, which felt like a real breakthrough.
Then reality hit.

I had made the classic mistake. I never measured the real bottleneck. I had optimized the part of the system that interested me the most, not the part that actually mattered. The search accounted for only about 10% of the total time. So even with a tenfold speedup, the overall gain was just a couple of seconds.

The other twenty-plus seconds came from drawing the vectors to video memory. My clever data structure did nothing to help with that. I shelved the work and felt embarrassed. A few years later, I came across an article describing this spatial indexing structure that looked nearly identical to what I had built. That felt good, and it told me the intuition wasn’t entirely off.

But the real lesson had nothing to do with the structure itself. It was much simpler. The most innovative solution in the world is worthless if you solve the wrong problem. Measure first. Figure out where the real time is going. Then decide what to optimize.

It’s a lesson I learned the hard way and have carried with me ever since.