How Google Code Search Worked • Hacker News Board

Re: How Google Code Search Worked

#21

Post by sciurus » Fri, Jan 20, 2012, 2:36 AM UTC

dennisgorelik wrote: post #11

ajasmin wrote: post #9

Earlier quoted context omitted.

Finding code with the regular Google Search is nearly impossible though.

I'm finding code with regular Google Search all the time. Yes, General Google Search is missing some neat features, but overall these features are not as important as convenience of using familiar general search queries, search speed, and the size of general google search index. BTW, do you have your own explanation of why Google Code Search was cancelled?

Saying "it failed" isn't an explanation.

Re: How Google Code Search Worked

#22

Post by staunch » Fri, Jan 20, 2012, 2:53 AM UTC

I'd love some idea of how large the index was for code search, how many machines it required, and how much total code it was searching.

Re: How Google Code Search Worked

#23

Post by mdwrigh2 » Fri, Jan 20, 2012, 3:36 AM UTC

toddc wrote: post #15

Russ's articles are an excellent write-up and explanation. However, many finite-state automata regex implementations have existed for years (e.g. Java http://cs.au.dk/~amoeller/automaton ) without the backtracking feature, of course. Also of interest is the benchmark data at: http://tusker.org/regex/regex_benchmark.html

> However, many finite-state automata regex implementations have existed for years

If you read his write-up on RegEx matching, you'll see notes that Thompson wrote an implementation in the mid-60s, so he definitely doesn't claim they're new. What he does claim is that most regex libraries don't use them, even when the regex they're matching to doesn't require backtracking.

Re: How Google Code Search Worked

#24

Post by _investigator » Fri, Jan 20, 2012, 3:37 AM UTC

tl;dr

The original basic RE and extended RE (when backreferencing is not used) are significantly faster than implementations that most programmers traditionally rave about, e.g., Perl RE.

Tell me something I didn't know.

He thus used such 30 year old code as a model and easily topped the speeds of the built-in RE capabilities of today's popular scripting languages.

Common sense is underrated.

Re: How Google Code Search Worked

#25

Post by mdwrigh2 » Fri, Jan 20, 2012, 3:38 AM UTC

snprbob86 wrote: post #14

fasdg wrote: post #12

Earlier quoted context omitted.

As Russ points out in his earlier re2-related blog posts, these regex engines still perform non-linearly on inputs which don't involve look-around, look-behind, etc. There's plenty of room for improvement even if they want to keep these features.

Seems like the default should be linear runtime and you should have to explicitly ask for the richer feature set (and opt into the assertion that you trust the input not to DOS your process). Could easily be added as a modifier (see `man perlre`), but should be implemented as two to enable explicit behavior and toggling the default. Randomly picking the letter N: /(\w+) \1/n # Error: look-behind is incompatible with…

I don't think you need to even go as far as adding a modifier. A smart enough regex engine would know when it could use the linear runtime algorithm, and when it needs to fall back.

Re: How Google Code Search Worked

#26

Post by boyter » Fri, Jan 20, 2012, 3:49 AM UTC

gruseom wrote: post #10

Google made a mistake in killing code search. Indexing the world's source code and making it searchable is so obviously part of their core mission that I wonder how this decision even got made. Yeah, code search is a niche market numerically speaking, but intellectually and economically (considering the economic impact of software) it is vital. Google was doing so much better a job of it than anybody else that they c…

You mentioned hoping someone can come along to get this right. I am certainly trying with http://searchco.de/

Its still a long way from being close to Google code search both in terms of code indexed (amending that as I write this) but I hope to get things up-to a par as soon as I possibly can.

Symbolhound http://symbolhound.com/ also has a code index that's worth a look too.

Re: How Google Code Search Worked

#27

Post by dr_rezzy » Fri, Jan 20, 2012, 5:16 AM UTC

I like. Word splitting is very interesting. Today, 2012, I would be hard pressed to provide a reason to use this technique. Splitting an index is a classic complexity/resource trade off (your index has a very predictable compact footprint). Again, today, memory is cheap, wide, uniform, and predictable. Indexes are now cheap and highly specialized. Complexity can be reduced for simplicity. Index specialization now becomes natural. My point here is that this solves a class of very expensive searches with ease, leading wildcard searches et al. Also, couldnt really tell from your code (you may be doing this), but reverse your trigrams in your generated query. If ordered properly, your search will be a lot more efficient.

Re: How Google Code Search Worked

#28

Post by rsc » Fri, Jan 20, 2012, 5:40 AM UTC

_investigator wrote: post #24

tl;dr The original basic RE and extended RE (when backreferencing is not used) are significantly faster than implementations that most programmers traditionally rave about, e.g., Perl RE. Tell me something I didn't know. He thus used such 30 year old code as a model and easily topped the speeds of the built-in RE capabilities of today's popular scripting languages. Common sense is underrated.

Wow, everyone's a cynic. Did you miss the part about the trigram index?

It sounds like you are replying to regexp1.html, not regexp4.html.

Re: How Google Code Search Worked

#29

Post by rsc » Fri, Jan 20, 2012, 5:47 AM UTC

178 wrote: post #19

inerte wrote: post #13

Earlier quoted context omitted.

Did it stop working internally? Do Google employees still get to use it?

http://googlesystem.blogspot.com/2012/01/google-code-search-... —» http://code.google.com/codesearch

In the long term, this will be search only over code.google.com projects, as mentioned in the 'discussion' link on codesearch.google.com.

Re: How Google Code Search Worked

#30

Post by _investigator » Fri, Jan 20, 2012, 5:51 AM UTC

rsc wrote: post #28

_investigator wrote: post #24

tl;dr The original basic RE and extended RE (when backreferencing is not used) are significantly faster than implementations that most programmers traditionally rave about, e.g., Perl RE. Tell me something I didn't know. He thus used such 30 year old code as a model and easily topped the speeds of the built-in RE capabilities of today's popular scripting languages. Common sense is underrated.

Wow, everyone's a cynic. Did you miss the part about the trigram index? It sounds like you are replying to regexp1.html, not regexp4.html.

No. You misread. I love Russ Cox's way of thinking and his continual generosity in sharing his work. I too use the Plan 9 base sed and grep. I'm cynical about the people who rave on about perl/javascript/python/ruby/whatever regexp, who derive some perverse joy in ridiculously complex RE and who often diss sed and all things old school as being slow or deficient in some way.