Re:Livegrep: Live searching the Linux kernel source code
by durin42 on Friday April 20, 2012 @07:25PM
(#3870232)
Do you use anything like a trigram index (see rsc's wonderful posts about how Google Code Search worked, and https://code.google.com/p/codesearch/ for a Go implementation) to speed up the regex codepath?
Re:Livegrep: Live searching the Linux kernel source code
by nelhage on Friday April 20, 2012 @07:31PM
(#3870243)
I'm using a different data structure -- a suffix array -- but the concept is pretty similar. I started work on this before Russ released his codesearch implementation, but I did read his blog posts while I was working on this.
So they can efficiently answer questions like "Give me all documents containing the word 'Linus'", but not necessarily "All documents containing the string '#def'".
That said, I am indexing -- I have my own custom backend that stores an in-memory index that lets me do arbitrary substring search (and more complicated queries, such as most character classes) much faster than a full search.
That said, the backend will fall back on a full regex search if necessary.