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

161–170 of 187 posts

Re: The technology behind GitHub’s new code search

#161

Post by hanwenn »

__float wrote: post #147
Scaevolus wrote: post #20

As a comparison to Sourcegraph: Sourcegraph shards and indexes a repository at a time, and uses trigrams and bloom filters (to skip shards). Github shards and indexes individual files according to their hashes. It also uses variable length ngrams (neat!). This makes horizontal scaling simpler, but also means more of the index needs to be scanned for org/repo-scoped queries ("Due to our sharding strategy, a query requ…

Sourcegraph's underlying code search server is the Zoekt project (which started as a Google open sourced project that Sourcegraph recently took over). They mention in a blog post linked to this one ( https://github.blog/2021-12-15-a-brief-history-of-code-searc... ) that Zoekt indexes much bigger than the corpus size, so they don't work at GitHub scale.

(I wrote most of Zoekt)

The github code search looks like an impressive piece work (congrats!).

That said, I'm curious about the nuances regarding corpus size. Their blog post claims they have 115 Tb of source code, but that a positional index is "too expensive". A positional index is a 3.5x blow-up, which is ~500 Tb of data. A 1 Tb SSD retails for $50, so that's $25,000 for storing a positional index. 500T of GCP local SSD is also ~25 k$/year. Even if you factor in replication/redundancy, the resource cost is far less than hiring a software engineer. I guess they think machines with local SSD are too much overhead to manage?

Re: The technology behind GitHub’s new code search

#162

Post by plugin-baby »

nickysielicki wrote: post #145
100k wrote: post #83

Earlier quoted context omitted.

(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…

From a resource utilization perspective, is it easier on your servers if I just clone the repo and do the grep myself? Because when the search doesn’t show me what I’m looking for on the first page, this is exactly what I do. (And I can never remember if it’s —shallow or —depth=1, so they’re not shallow clones, either.)

Same. In addition:

> when the search doesn’t show me what I’m looking for on the first page, this is exactly what I do

This is pretty much always.

Re: The technology behind GitHub’s new code search

#163

Post by ygra »

userbinator wrote: post #132
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…

or about 0.6 GB/sec/core. That seems very slow by today's standards. There's a rather... eccentric guy who easily beat that almost 10 years ago with his implementations of string search: https://news.ycombinator.com/item?id=6954298

The difference may be regex matching. This can often be optimized to an impressive degree, depending on the regex, but unless it's a simple substring search without any metacharacters, I'm not sure those approaches are comparable.

Re: The technology behind GitHub’s new code search

#164

Post by bspammer »

joshuawarner32 wrote: post #131
orf wrote: post #89

Earlier quoted context omitted.

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.

Oooh that sounds really useful, would you mind dropping a link?

Sorry for the cyber-stalking orf, but I'm guessing it's this: https://github.com/orf/pypi-data

Re: The technology behind GitHub’s new code search

#165

Post by ZephyrBlu »

100k wrote: post #120
ZephyrBlu wrote: post #90

Earlier quoted context omitted.

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 dur…

How do you think Algolia shards their data given that architecture? My guess is that Algolia's indices are sharded by customer and each cluster probably has multiple customer indices. do you keep a copy of the index document form of repos or is that done on the fly during indexing? As mentioned in the post, the index contains the full content. Our ingest process essentially flattens git repos (which are stored as DAG…

Cool, thanks for all your answers!

Re: The technology behind GitHub’s new code search

#166

Post by dcreager »

tjoff wrote: post #36
jeffbee wrote: post #25

Earlier quoted context omitted.

I can only think of one hosted repo service that provides a working go-to-definition feature and it is not github or sourcegraph. What makes you think this will suddenly become widespread? Github spent years doing this and their new thing is strictly non-semantic. It doesn't have the faintest idea where the name is defined, or if there's even a difference between a function name, a parameter name, or a word in a comm…

The rise and popularity of LSP and projects such as treesitter are a superb foundation for features such as this. Both support a wealth of languages, it is still and will be quite hard to assume the toolchain and settings required for producing accurate information though. But this could be tied into CI, especially for projects utilizing runners for building the code. So the barrier to entry now is orders of magnitud…

> But this could be tied into CI, especially for projects utilizing runners for building the code.

One often overlooked drawback of generating this data during CI is that you, the project owner, are now paying for the compute. Of course, maybe you qualify for a free tier. And if not, if you're already running a CI job for testing/linting/etc, the marginal cost of also generating code nav symbols might not be too bad. But one benefit of the stack graphs approach mentioned up-thread (and the code search indexing described in OP) is that all of the analysis and extraction work is done in dedicated server-side jobs that GitHub is footing the bill for.

Re: The technology behind GitHub’s new code search

#167

Post by dcreager »

kjuulh wrote: post #15

I really like the new search. Though sometimes it is a bit deceptive. I.e. when searching for a function name by clicking on a piece of code and suddenly you are in an entitely different code base with an unrelated function though it shares the name. It feels like github code browsing is a step between a full editor with lsp and a static site. I Hope they work out the Kinks and make it more smooth

It sounds like you are navigating in a language where we currently only support "fuzzy" or "search-based" Code Navigation, which only uses the _unqualified_ symbol name as the search target. As you point out, this can be very imprecise when there are particular symbol names that are used a lot. (Think `render` in a Rails codebase, for instance.)

We also have Precise Code Navigation — still currently only for Python [1], but we're working on other languages as fast as we can. As mentioned down-thread, that is built on our new stack graphs framework [2]. We're often asked why we're not leaning on something LSP-shaped for this. I go into a built of detail about that in a FOSDEM talk from a couple years back [3], and also in the Related Work section of a paper that we just published [4].

[1] https://docs.github.com/en/repositories/working-with-files/u...

[2] https://dcreager.net/talks/stack-graphs/

[3] https://dcreager.net/talks/2020-fosdem/

[4] https://dcreager.net/publications/016-stack-graphs/

Re: The technology behind GitHub’s new code search

#168

Post by dcreager »

robertlagrant wrote: post #67
aeyes wrote: post #63

Earlier quoted context omitted.

I use global search from time to time to see how other projects use certain libraries. When the documentation of said libraries is sparse this can sometimes be a good timesaver.

The other big thing that works well is being able to jump directly into the source of an open source library from your code. That is powerful, but again, possibly doesn't need a giant ultra search. Just some clever linking.

This sounds like Cross-Repo Code Navigation [1], which we do support, though only for Python at the moment. And you're right that it does not use the same search index under the covers — OP is specifically describing the index for "search box"-style code search across a large set of repositories (org-scoped, global-scoped, me-scoped, etc). For Code Navigation, we have a _different_ set of interesting and bespoke indexers and storage formats. I've posted some links here if you want to learn more: [2]

[1] https://docs.github.com/en/repositories/working-with-files/u...

[2] https://news.ycombinator.com/item?id=34693181

Re: The technology behind GitHub’s new code search

#169

Post by Cian911 »

> Shard by Git blob object ID which gives us a nice way of evenly distributing documents between the shards while avoiding any duplication. There won’t be any hot servers due to special repositories and we can easily scale the number of shards as necessary.

What exactly do they mean by "special repositories" here?

Re: The technology behind GitHub’s new code search

#170

Post by PaulHoule »

kgeist wrote: post #153
Zuiii wrote: post #136

Earlier quoted context omitted.

It's simple enough that most IDEs implement it. Take from that what you will.

GitHub hosts 28 million public repositories. Do you think your IDE can open 28 million projects at once and search there "trivially" without hanging? Unless you're talking about searching inside a single repository?

I am talking about searching in a single repository, who would expect to get useful results otherwise? I have no idea how you’re going to rank 28 million repos in a way that matches my perception of relevance.

To be specific, I was looking for the definition of one method in Highcharts so I could understand what it does and override it, GitHub gave 6 pages of results. I was able to find the function immediately in my IDE once I checked out the 100mb+ repository and it indexed it. If I’d been able to the same w/ the search on GitHub it would have saved me considerable time and hassle.

This search could be implemented by something that compiles and indexes like the IDE (sourcegraph) or maybe some kind of shallower parsing. Highcharts is in typescript which I’d don’t know well but in JavaScript the later might be a little tricky because there are so many ways to define a function (one hell of a regency.). I’d contrast to Java where is would be very easy to write a rule that would turn up a class definition if not a method definition, in my case finding the class would have solved my problem.

Post reply on HN