Grep cache

I mentioned in my last post that I’m working for a games company now. I’m also working with the largest code base that I’ve ever seen, or really heard of. To give you an idea, the mainline code base is over 85Mb of text in 14,000 files. If you include the 3rd party packages that we link against, then we have 600+Mb of code text in something like 85k files. I think that this is large by any reasonable standard. Oh, I just did a line count. 18 million lines of text, though I am counting multiple versions of some packages.

Most developers at work use Visual Studio and Visual Assist to edit and navigate their code. I can’t really stand Visual Studio as an editor, so I use Emacs with Vimpulse mode (this is basically Vim key bindings). For a while I was using Visual Assist to navigate the code. On a code base this large I think that the single most useful tool VA provides is Alt+g, which jumps to the definition of the symbol you are on. The context info is quite smart, for instance if the cursor is on something like someVar->SomeFunction() then VA will figure out the type of someVar and put the cursor on typeof_someVar::SomeFunction. Not too shabby, and generating the VA database is not too painful really. But there are two things here, how do I find every place that SomeFunction is used? And, besides I use Emacs.

So I do what any Unix guy in a Windows world would do – install Cygwin and the unix tools for Win32 & try the standard code indexing tools. Tools like ctags, cscope, GNU Global, and source navigator. All of them choke, there are just too many files. I did manage to build a subset database for ctags, which resulted in a 70Mb tags file. Emacs just took too long looking up tags. Using find and grep also takes far too long, something in the order of 5+ minutes. None of this works in a satisfactory manner, and I end up using Visual Studio to navigate the code and Emacs to edit. After much grumbling at my situation I looked at the raw code size numbers and thought to myself “how long does it actually take to grep a 500Mb file?”. I did some tests, and it turns out not that long. On my machine, grepping a single 500Mb file is less than 10 seconds. Grepping an 80Mb file is so fast as to be instant.

Enter Grep Cache

The basic idea of grep cache is that you concatenate all of your code data into one huge file and grep that file instead. Grepping a single file, you will get back the line number of the big file and the matching line of text. The information that you don’t get directly back is the original file that contained that grep hit. My solution to this is to create a dumb index file, which simply has text in the format

<number-of-line-in-file> <filename>\n

Then a Perl script to linear search the index file, as soon as the input line number is greater than the sum of all previous line numbers, we have found the original file. A little bit of text massage to get the Perl script output into a grep format that Emacs expects & we’re done.

How fast is this then? I can grep the smaller (85Mb) code base that I usually work with pretty much instantly. The bigger database takes 10-20 seconds. Most of the time is spent in the Perl script doing the dumb-as-a-rock linear search. If I wanted to grep the bigger file faster I’d write a proper index file where I could use a binary search. But for right now, I’m happy with my new tool. Super fast grepping actually lets me do pretty much everything that a proper tags based system does.

Code

Here’s the code, this runs on Windows with the Unix tools installed. Thanks to Dean for the Perl code.

Bat file to replace grep (fast-grep.bat):
grep -n %* database.txt | perl lookup-file-name.pl

Generate database (gendatabase.bat):

set ROOT=C:\dev\project

del files.lst
del index.txt
del database.txt
ufind %ROOT% -iname *.cpp -or -iname *.h -or -iname *.c | sed s_\\_/_g > %ROOT%\files.lst
for /f %%i in (%ROOT%\files.lst) do @wc -l %%i >> index.txt
for /f %%i in (%ROOT%\files.lst) do @cat %%i >> database.txt

Perl code (lookup-file-name.pl):

#! perl.exe -w

use strict;

my $indexName = “all-index.txt”;
my $index;
open $index, $indexName or die “Can’t open index file $indexName\n”;

my $a = 0;
my @files;

sub addItem {
my ($numLines,$filepath) = @_;

push @files, [$a, $filepath];
$a += $numLines;
}

sub findItem {
my $num = shift;
my $filename;
my $offset;
map { my @a = @{$_}; if ( $a[0] <= $num) { $filename = $a[1]; $offset = $num – $a[0]; } } @files;

($offset,$filename);
}

LINE: while ( ) {
next LINE unless ( /^\s+(\d+) (.*)$/ );

my $numLines = $1;
my $filepath = $2;

#print “$numLines $filepath\n”;
addItem( $numLines, $filepath);
}

#map { print “@{$_}\n”; } @files;
#print findItem( 1000);

FILE: while ( ) {
next FILE unless ( /^(\d+):(.*)/);

my $num = $1;
my $line = $2;

my ($offset,$filepath) = findItem($num);

print “${filepath}:${offset}:$line\n”;
}