5 ms·

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 wor

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 http://swtch.com/~rsc/regexp/regexp4.html [2] https://github.com/kalven/CodeDB https://github.com/kalven/CodeDB

justin66 12y ago
> The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. It's something hard disk drives were not optimized for.
- barrkel 12y ago
  He says hot cache - hdd is out of the loop, it should just be between the FS implementation and the cache implementation.
- vinkelhake 12y ago
  Windows is (or at least was) a dog when it comes to this even if the files are in the cache. Like barrkel said, the number I quoted was for the case when the OS doesn't hit the drive.
  - to3m 12y ago
    Random rant time! You have to code for Windows just so. Dear POSIX people in general, there is more to cross platform coding than being able to build it with cygwin. Every grep I've used on Windows handles wildcards, so it must be doing the expansion itself. The right way to do this sort of thing on Windows is to call FindFirstFile/FindNextFile, which is a cross between readdir and stat in that each call returns not only the name of one directory entry that matches the pattern (as per readdir+fnmatch) but also its metadata (as per stat). So, if you were going to call readdir (to get the names) and then stat each name (to get the metadata), you should really be doing all of it in just this one loop so that each bit of data is retrieved just the once. But this is exactly what POSIX programmers would seemingly never, ever do. Probably because doing it that way would involve calling a Win32 function. Well, more fool them, because getting this data from FindFirstFile/FindNextFile seems pretty quick, and getting it any other way seems comparatively slow. I cobbled together a native Win32 port of the_silver_searcher a while ago and it was about twice as fast as the stock EXE thanks to retrieving all the file data in one pass. In this case the readdir wrapper just needed to fill in the file type in the dirent struct; luckily it seems that some POSIX-style systems do this, so there was already code to handle this and it just needed the right #define adding. (I have absolutely no idea why MingW32 doesn't do this already.) Prior to switching to the_silver_searcher, I used to use grep; the grep I usually used is the GNU-Win32 one (http://gnuwin32.sourceforge.net/packages/grep.htm http://gnuwin32.sourceforge.net/packages/grep.htm), and it looks to call readdir to get the names, and then stat to get each name's details. I checked that just now, and after all those years I can finally imagine why it's so slow. GNU-Win32 find is really slow, too.
    - lucian1900 12y ago
      Perhaps it'd be less bad if Windows wasn't so gratuitously different. On a more serious note, there's a pretty large gulf between the Windows and Unix development worlds. Try getting a game developer to use curl ...
- sitkack 12y ago
  HDD don't care about opening files. If the FS supported the same operations, I could send grep directly to the block level and have it scan contiguous lists of blocks that cover files I care about. You will get false positives for the overscan (potentially), but you will also achieve the raw rate of the disk (150MB/s for spinning and 500MB/s for solid sate). So in effect, these big data serialization systems are attempting to lift the file system into userland so they can make just that optimization.
hvidgaard 12y ago
It's not unlike how we do free text search at my work. We collect all aggregate information for an item, concatenate it and store it in one table. Searching is amazingly fast. So fast in fact that we've had several clients open a ticket claiming that the search is broken. "There is no way you can search for a random text string in our million documents database this fast".

justin66 12y ago

> The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. It's something hard disk drives were not optimized for.

barrkel 12y ago
He says hot cache - hdd is out of the loop, it should just be between the FS implementation and the cache implementation.
vinkelhake 12y ago
Windows is (or at least was) a dog when it comes to this even if the files are in the cache. Like barrkel said, the number I quoted was for the case when the OS doesn't hit the drive.
- to3m 12y ago
  Random rant time! You have to code for Windows just so. Dear POSIX people in general, there is more to cross platform coding than being able to build it with cygwin. Every grep I've used on Windows handles wildcards, so it must be doing the expansion itself. The right way to do this sort of thing on Windows is to call FindFirstFile/FindNextFile, which is a cross between readdir and stat in that each call returns not only the name of one directory entry that matches the pattern (as per readdir+fnmatch) but also its metadata (as per stat). So, if you were going to call readdir (to get the names) and then stat each name (to get the metadata), you should really be doing all of it in just this one loop so that each bit of data is retrieved just the once. But this is exactly what POSIX programmers would seemingly never, ever do. Probably because doing it that way would involve calling a Win32 function. Well, more fool them, because getting this data from FindFirstFile/FindNextFile seems pretty quick, and getting it any other way seems comparatively slow. I cobbled together a native Win32 port of the_silver_searcher a while ago and it was about twice as fast as the stock EXE thanks to retrieving all the file data in one pass. In this case the readdir wrapper just needed to fill in the file type in the dirent struct; luckily it seems that some POSIX-style systems do this, so there was already code to handle this and it just needed the right #define adding. (I have absolutely no idea why MingW32 doesn't do this already.) Prior to switching to the_silver_searcher, I used to use grep; the grep I usually used is the GNU-Win32 one (http://gnuwin32.sourceforge.net/packages/grep.htm http://gnuwin32.sourceforge.net/packages/grep.htm), and it looks to call readdir to get the names, and then stat to get each name's details. I checked that just now, and after all those years I can finally imagine why it's so slow. GNU-Win32 find is really slow, too.
  - lucian1900 12y ago
    Perhaps it'd be less bad if Windows wasn't so gratuitously different. On a more serious note, there's a pretty large gulf between the Windows and Unix development worlds. Try getting a game developer to use curl ...
sitkack 12y ago
HDD don't care about opening files. If the FS supported the same operations, I could send grep directly to the block level and have it scan contiguous lists of blocks that cover files I care about. You will get false positives for the overscan (potentially), but you will also achieve the raw rate of the disk (150MB/s for spinning and 500MB/s for solid sate). So in effect, these big data serialization systems are attempting to lift the file system into userland so they can make just that optimization.

hvidgaard 12y ago

It's not unlike how we do free text search at my work. We collect all aggregate information for an item, concatenate it and store it in one table. Searching is amazingly fast. So fast in fact that we've had several clients open a ticket claiming that the search is broken. "There is no way you can search for a random text string in our million documents database this fast".