Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The technology behind GitHub’s new code search

github.blog

Post reply on HN
Print view View original

81–90 of 187 posts

Re: The technology behind GitHub’s new code search

#81

Post by 100k »

boyter wrote: post #47

The sparse grams solution to deal with stupidly common ngrams such as for or tes is very interesting. I’d love to see more discussion on how they are dealing with the false positives though. It looks like a positional index is being used to achieve this, but that usually blows out your index size. Additional information about deduplication would be especially interesting to me as well. It seems to solve this quite we…

Thanks! I enjoyed reading your blog posts about building your code search engine. One minor point of clarification, we do not use a positional ngram index, which as you note blows up the index size. Instead, we use the covering sparse ngrams to produce candidate documents and then search the content.

An early version of Blackbird experimented with trigrams plus a bitmask of the next character, but it didn't work well because it wasn't selective enough. This is mentioned in the blog post:

We tried a number of strategies to fix this like adding follow masks, which use bitmasks for the character following the trigram (basically halfway to quad grams), but they saturate too quickly to be useful.

Re: The technology behind GitHub’s new code search

#83

Post by 100k »

andrewmcwatters wrote: post #76

> Just use grep? First though, let’s explore the brute force approach to the problem. We get this question a lot: “Why don’t you just use grep?” To answer that, let’s do a little napkin math using ripgrep on that 115 TB of content. On a machine with an eight core Intel CPU, ripgrep can run an exhaustive regular expression query on a 13 GB file cached in memory in 2.769 seconds, or about 0.6 GB/sec/core. But you don't…

(I work on this.)

If you check out our prior blog post, "A brief history of code search at GitHub" (https://github.blog/2021-12-15-a-brief-history-of-code-searc...), you can learn a bit about the evolution of this feature. And, in fact, we used to use git grep to search repositories.

This doesn't work well at GitHub's scale. We have 100M users and over 200M repositories in a multi-tenant environment. Your git grep is going to be competing for resources with other user's pushes and clones.

Re: The technology behind GitHub’s new code search

#84

Post by chatmasta »

ezekg wrote: post #3

I use their new code search a lot to grok how people use certain features, or implement certain things. But I do wish there was a way to filter out forks. Sometimes I search a string and just get a bunch of forks all with the same result. For example, searching a common class in a Rails app often just shows a bunch of rails/rails forks, which is a lot of noise to sift through when you're trying to see how devs common…

Perhaps it could benefit from something like a "dissimilarity" filter, which ranks the current result set by returning the most unique hits first. You wouldn't always want this, because sometimes you're searching for how something is typically used, and with many duplicative results you can confirm that's the preferred pattern. But other times you're looking for more estoteric usage of a certain function, and it would be nice to filter the "standard usage" from the results (although you can already do this with carefully chosen negated keywords).

Personally, I'm happy with the new code search so far. I stopped using Sourcegraph because I could never get the deeper results I wanted - it would just return the top five repositories including some common code snippet and I couldn't explore further than that. GitHub Code Search doesn't seem to have this problem to such a degree, since I can use negation more naturally, and since my query is not limited to some shallow subset of the corpus before refining it.

Re: The technology behind GitHub’s new code search

#85

Post by chatmasta »

In general, I really recommend code search as a tool for supplementing reading the documentation and source code of your dependencies (you are reading the source code, right?). I reach for it almost every day, and I find it's a reliable tool for identifying "the right way" to use a library, especially one that isn't fully documented.

Re: The technology behind GitHub’s new code search

#86

Post by 100k »

orf wrote: post #77
100k wrote: post #7

Earlier quoted context omitted.

Thanks for the feedback! That's coming, we've been prioritizing scaling the index and ingest process and haven't had a chance got add that yet. There are a bunch of value-add features like this I am looking forward to knocking out soon.

Out of interest, if I have a repo with many millions of files that compress quite nicely down to about a 1.4gb packfile, is it better for the ingestion and/or indexer if I break this down into many smaller pushes or one large push? Because I pushed such a repo yesterday and it’s still not been indexed.

Sorry, there are size limits on the number of files in a repositories that we'll index. That is probably why your repository wasn't indexed. Out of curiosity, what are you storing in this repository?

Re: The technology behind GitHub’s new code search

#87

Post by joshuamorton »

andrewmcwatters wrote: post #76

> Just use grep? First though, let’s explore the brute force approach to the problem. We get this question a lot: “Why don’t you just use grep?” To answer that, let’s do a little napkin math using ripgrep on that 115 TB of content. On a machine with an eight core Intel CPU, ripgrep can run an exhaustive regular expression query on a 13 GB file cached in memory in 2.769 seconds, or about 0.6 GB/sec/core. But you don't…

> I'm ALREADY in a repository, I just don't want to check out, say all of WebKit, I just need to find where a specific reference is defined.

If you're in some repository that uses a webkit api, and you want to know how that api is defined, how do you do that without global cross references or a global lookup?

Even for local lookups, indicies are useful (as any ctags user will tell you!), but for any kind of cross repo xrefs they're ncecessary.

Re: The technology behind GitHub’s new code search

#88

Post by sqs »

chatmasta wrote: post #84
ezekg wrote: post #3

I use their new code search a lot to grok how people use certain features, or implement certain things. But I do wish there was a way to filter out forks. Sometimes I search a string and just get a bunch of forks all with the same result. For example, searching a common class in a Rails app often just shows a bunch of rails/rails forks, which is a lot of noise to sift through when you're trying to see how devs common…

Perhaps it could benefit from something like a "dissimilarity" filter, which ranks the current result set by returning the most unique hits first. You wouldn't always want this, because sometimes you're searching for how something is typically used, and with many duplicative results you can confirm that's the preferred pattern. But other times you're looking for more estoteric usage of a certain function, and it woul…

Re: Sourcegraph, we're working on improving that, and sorry you couldn't get the results you wanted. We primarily build for the code within customers, where this particular problem is less common than across all open-source repositories. But we want it to work really well in every case.

Our new ranking (https://about.sourcegraph.com/blog/new-search-ranking) should help a lot here, and it's live on https://sourcegraph.com. Can you share some of the queries you tried so we can see how much ranking helps and how to handle them better?

Re: The technology behind GitHub’s new code search

#89

Post by orf »

100k wrote: post #86
orf wrote: post #77

Earlier quoted context omitted.

Out of interest, if I have a repo with many millions of files that compress quite nicely down to about a 1.4gb packfile, is it better for the ingestion and/or indexer if I break this down into many smaller pushes or one large push? Because I pushed such a repo yesterday and it’s still not been indexed.

Sorry, there are size limits on the number of files in a repositories that we'll index. That is probably why your repository wasn't indexed. Out of curiosity, what are you storing in this repository?

Sequences of code from Python package releases from pypi, as an experiment I’m working on. They compress quite nicely as the deltas between releases are fairly small.

I thought it would be nice to be able to search through them, but I guess the file limit was reached. That’s a shame.

Re: The technology behind GitHub’s new code search

#90

Post by ZephyrBlu »

100k wrote: post #80
ZephyrBlu wrote: post #46

Search is a fascinating topic because it's such a fundamental problem and every search engine is based around the same extremely simple data structure (Posting list/inverted index). Despite that, search isn't easy and every search engine seems to be quite unique. It also seems to get exponentially harder with scale. You can write your own search engine that will perform very well on a surprisingly large amount of dat…

I agree! Search is so cool. It's interesting that GitHub seems to have quite a few shards. Algolia basically has a monolithic architecture with 3 different hosts I used to work at an Algolia competitor. I don't know for sure, but my guess is that Algolia shards their indices by customer. Algolia does not provide global search. GitHub code search does. That, and the desire to deduplicate data, is what led us to our cu…

I'm not familiar with production search systems at scale (Very curious about them though). How do you think Algolia shards their data given that architecture? Based on their description it seems like the search engine itself is monolithic. Maybe they're running a 3-node cluster with a monolithic index for each customer?

Interesting, do you keep a copy of the index document form of repos or is that done on the fly during indexing? Is your custom index format a binary format? I have no idea whether that's standard practice, or just a compressed text format is enough. I guess that non-binary formats would be enormous though, and given that an index is by definition relatively unique it probably wouldn't compress that well.

I do feel the development velocity thing. I've felt something similar on my smaller scale projects. Being able to fully re-index the corpus in less than a day definitely seems like it would provide a lot of opportunities to experiment and try stuff out without it being too costly.

Scale up in terms of what? Is the current system not indexing all of GitHub, or you mean you want to index on more things (E.g. commits, PRs, etc)?

Post reply on HN