# Don’t ignore naive or "stupid" algorithms — hardware is cheap and fast

I just had a nice reality check. Sort of pleasant in that I realized I could save a LOT of memory usage (like from 35MB down to 9 MB), but also aggravating because I have spent probably 10-20 hours developing a clever algorithm designed for speed.

Lesson learned. I should have built the naive version first. Instead, I wrote up two successively more “brilliant” versions that went through all sorts of hoops to get the most speed out of it. Of course, to do this, they took up all sorts of memory with indexes, and the index creation was starting to take about 10 seconds or longer. I should have just built the naive version.

I just wrote the naive version and realized I could have done that in about 5 minutes and saved many hours of tweaking. The component is a type of indexing component, so there were three metrics: index creation time, lookup time, index size. Here’s a rough comparison just to give an idea:

 Clever Algorithm Naive Algorithm Index Creation Time 10s 0.3s Lookup Time 0.0001s 0.005s Index Size 35MB 9 MB # items ~27,000

Pretty impressive speed numbers aren’t they! That clever algorithm really rocks. And it would be awesome to use if I was doing a lot of searching consecutively, but the searching in my app is tied to the UI, thus to the user, so in reality 0.005 seconds is not that much different than 0.0001 seconds. <sigh>

The numbers above are from my main machine, which is a Core 2 Duo. Just to be safe I tested the naive algorithm on my 4-year-old Pentium 4 laptop to validate that it still has acceptable performance on an older machine. The creation takes 0.05 seconds, but lookup time isn’t much slower, if at all.

And 9MB index is MUCH better than a 35MB index.

In summary, lessons learned:

1. Hardware is cheap and fast. Don’t waste time optimizing for speed if you don’t have to. While there are signs the raw speed of a processor is plateauing as multiple cores become more important, in general, speed is always increasing.
2. If you’re running something when a user inputs something, speed isn’t critical (as long as you have it faster than human response time)
3. Every application is different, so measure and think critically. If my app needed to run the search 100 times per second, the clever algorithm would definitely be better.
4. There is almost always a tradeoff between speed and size. Which is more important depends on the app.
5. Write the dumb algorithm first. It might be good enough and you’ll save yourself hours of development and debugging time.

Technorati Tags: , , , , ,

# ClearType is like a new pair of glasses

Many have said it already, but let me just add my voice: ClearType technology is the most wonderful thing to hit Windows in a long time. I recently received a new computer at work (3.4Ghz hyperthreaded, 1 GB RAM, 80/200 GB disks–a screaming machine, at least compared to what I used to have). and during the setup process (3 versions of Visual Studio, Office, dozens of developer tools) I remembered that I needed to turn ClearType on.

Wow. It’s like the same difference when you’ve been needing glasses for a while and finally get them and realize that the world isn’t that blurry after all.*

It doubles the perceived resolution of LCDs.

(* only a little ironic that ClearType works by deliberately “blurring” edges through antialiasing.)

# The web in a box

I was reading an interview of Gary Flake who works with MSN search. The following quote stood out to me:

Â However, there is an even richer class of algorithms that can only be efficiently built on a 64 bit system because you essentially have to have a significant part of the web stored close to a single CPU. So, 64 bit systems pave the way for entirely new forms of relevance that look at how pages relate to one another.

That is just cool.

Microsoft announced recently that in a few months they would reveal a new search engine that is better than Google. This looks like part of it.