5 ms·

AFAIK, Google Code Search was written by Russ Cox, who also wrote this: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html My

by wooster 17y ago

AFAIK, Google Code Search was written by Russ Cox, who also wrote this: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html My guess, back when I was doing code search at Apple, was that he was actually scanning all the docs with his fast regexp, which would be do-able with the number of machines at his disposal + the expected traffic. If anyone knows any differently, I'm all ears. :)

nostrademons 17y ago
If anyone knows any differently, I doubt they'd be able to tell you. ;-)
Retric 17y ago
I agree that Google probably just throws HW at the problem, but you could also build something custom if it really needed to scale. Just record what people look for and keep an index for the common chunks of logic. So, if people often search for someones name or date you keep a list of what satisfies that so you can quickly eliminate large numbers of documents without doing a full text search. You could also reduce the document to a list of tokens and search that list before the file etc.
deleted 17y ago
[deleted]
fizx 17y ago
That does searching of text, without generating an index. While this is fast, you are still have search time linear in the size of your searchable text. If you used a suffix tree as an index, you'd get time complexity strongly sublinear in text length. In summary, if the regex matching complexity dwarfs the corpus size, you want Thompson NFA. If your corpus size dwarfs the regex complexity, you want suffix tree indexes. It's not clear to me if the two approaches can be combined, but if they are, I'd like to know.
bravura 17y ago
If Russell Cox wrote it, it must be good. I programmed competitively with him at USACO and in college (we got to 8th best college team in the world), and he was a consistent ass-kicker. Hardcore and disciplined and fast.
- uriel 17y ago
  Other (open source) projects by Russ people might find interesting: * Plan 9 from User Space - http://plan9.us http://plan9.us * vx32/9vx - http://pdos.csail.mit.edu/~baford/vm/ http://pdos.csail.mit.edu/~baford/vm/ * libtask - http://swtch.com/libtask/ http://swtch.com/libtask/ (Plus quite a few bits of Plan 9 itself, obviously.) Edit: forgot this really cool storage system: http://doc.cat-v.org/plan_9/misc/foundation/ http://doc.cat-v.org/plan_9/misc/foundation/

by wooster 17y ago

nostrademons 17y ago

If anyone knows any differently, I doubt they'd be able to tell you. ;-)

Retric 17y ago

I agree that Google probably just throws HW at the problem, but you could also build something custom if it really needed to scale. Just record what people look for and keep an index for the common chunks of logic. So, if people often search for someones name or date you keep a list of what satisfies that so you can quickly eliminate large numbers of documents without doing a full text search. You could also reduce the document to a list of tokens and search that list before the file etc.

deleted 17y ago

[deleted]

fizx 17y ago

That does searching of text, without generating an index. While this is fast, you are still have search time linear in the size of your searchable text. If you used a suffix tree as an index, you'd get time complexity strongly sublinear in text length. In summary, if the regex matching complexity dwarfs the corpus size, you want Thompson NFA. If your corpus size dwarfs the regex complexity, you want suffix tree indexes. It's not clear to me if the two approaches can be combined, but if they are, I'd like to know.

bravura 17y ago

If Russell Cox wrote it, it must be good. I programmed competitively with him at USACO and in college (we got to 8th best college team in the world), and he was a consistent ass-kicker. Hardcore and disciplined and fast.

uriel 17y ago
Other (open source) projects by Russ people might find interesting: * Plan 9 from User Space - http://plan9.us http://plan9.us * vx32/9vx - http://pdos.csail.mit.edu/~baford/vm/ http://pdos.csail.mit.edu/~baford/vm/ * libtask - http://swtch.com/libtask/ http://swtch.com/libtask/ (Plus quite a few bits of Plan 9 itself, obviously.) Edit: forgot this really cool storage system: http://doc.cat-v.org/plan_9/misc/foundation/ http://doc.cat-v.org/plan_9/misc/foundation/