Searching 20 GB/sec: Systems Engineering Before Algorithms

One can name thousands of examples (literally) where the simple code doesn't beat the fancy algorithm. What's your point?

I wrote a simple code search tool a number of years ago that had the ability to run arbitrary regex queries on a codebase, much like a recursive grep. I was working on a medium sized codebase and our primary platform was Windows. The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. If the file cache was cold, a simple search could turn into minutes of waiting.

My approach was to, essentially, concatenate all files into a single blob. The search tool would then let the regex loose on the contents of that single file. I had a simple index on the side to map byte positions to filenames. To get a line number from the position I would simply count the number of newlines from the start of the file to the regex match position.

Add some smarts to avoid duplicating work, compression and multithreading and I had a tool that could find all lines that contained "int(8|16|32|64)_t" in the Linux kernel source in a third of a second. This was about 20 times faster than grep (with a hot file cache).

It was a simple solution that scaled well enough to handle the codebases I was working on at the time without problems. I later read Russ Cox's article[1] on how Google code search worked. I recommend that article to anyone who's interested in running regular expressions on a large corpus.

Edit: The source[2] is available on github. Tested on Linux and Windows.

[1] http://swtch.com/~rsc/regexp/regexp4.html

[2] https://github.com/kalven/CodeDB

This randomly reminded me of an ancient kuro5hin article that I found interesting back in the day. Where the proposal was to use brute force to implement comment search on kuro5hin.

http://www.kuro5hin.org/story/2004/5/1/154819/1324

In BI, a similar tradeoff between lots of fancy preaggregation, versus optimizing search across the raw, un- (or lightly-) processed base data comes up quite frequently.

Commonly, the choice of approach is dictated by the number of end users querying the same data. If it's relatively specific queries ran frequently by many users, the aggregation approach can be made snappier and save lots of processing power.

But for power users, it becomes a nuisance real fast to be limited not only by stored base data, but also by the somewhat arbitrarily chosen aggregate structures. I'm assuming people doing log analyses of server logs fall within "power users" in most shops. At least I'd hope so :)

As an aside, the Go language (that I'm currently flapping between loving and not so much), versus Python at al., seems to be born of somewhat similar thinking.

    I’d certainly seen this at Google, where they’re 
    pretty good at that kind of thing. But at Scalyr, 
    we settled on a much more brute-force approach: a 
    linear scan through the log

Art of Computer Programming mentions this methodology, and the importance of learning about it. There are entire sections of "Tape Algorithms" that maximize the "brute force linear scan" of tape drives, complete with diagrams on how a hypothetical tape drives work in the situation.

Few "fancy algorithms" books actually get into the low level stuff. But Knuth knows: modern computers are extremely fast at linear data, and accessing data linearly (as well as learning algorithms that access data linearly) is a good idea.

I'll bet you that a B-tree approach would be fastest actually. B-Trees are usually good at balancing "massive linear performance" with "theoretical asymptotic complexity". IIRC, there is some research into this area: (look up cache sensitive search trees)