28 ms·

The technology behind GitHub’s new code search

750 points by joshbetz 4y ago

loginatnine 4y ago
I'm curious if they'll open source Blackbird, it does not seem mentioned in the post.
- jaza 4y ago
  I'm also curious. Sadly, unless I hear otherwise, I assume that the answer is no.
- yazaddaruvala 4y ago
  From the description, it is just ElasticSearch re-built on top of a Kafka topic. Its not clear what benefit it would brings to open source it.
imadethis 4y ago
Sourcegraph should’ve accepted that offer from GitHub.
- deleted 4y ago
  [deleted]
- pigtailgirl 4y ago
  -- was looking at their glassdoor last night - one of the worst ive seen in tech so far --
  - icelancer 4y ago
    Seems fine to me? I was expecting a bloodbath but the reviews are all pretty balanced, with Yegge getting a pretty good amount of praise.
- mxstbr 4y ago
  I don't think Sourcegraph is in big trouble here. Their whole play is enterprises, who likely have code spread across many different hosts. On top of that, their code search is still miles ahead of GitHub's.
  - tooltitude 4y ago
    It's very useful for enterprises to have one solution like github. Github isn't the best in every fields, but overall it's the best offer (they have git hosting, continuous integration, bug tracking, discussion forums, hosted dev environment, and now code search). It reminds me of a bundling strategy used in MS Office.
  - the_mitsuhiko 4y ago
    The new code search includes private repos. Miles ahead doesn’t matter if you get the search at GitHub for free. GitHub actions started out pretty terrible but they are now dominating hosted CI. SourceGraph likely has challenging times ahead considering the valuation.
    - sqs 4y ago
      Sourcegraph CEO here. “Challenging times” is how it should be all the time. That means competition is forcing both GitHub and us to build better stuff for devs. Devs win. But to be clear, as a company we are doing well and growing nicely inside customers, with a ton of cash in the bank, an awesome team, and a huge opportunity ahead of us. GitHub’s new code search has been out for 14 months now, so this is nothing new. It’s a big market and there’s way more room for differentiation and dev choice in code search/intelligence than in CI. There’s a lot of code intelligence that GitHub won’t support (precise code nav for more languages, comprehensive code ownership, metadata from other dev tools that know things about code outside the GitHub/Microsoft suite, etc.), there’s a need for the ability to fix (with our Batch Changes) not just find, and even in the core search workflow there’s so much room for improvement with AI fine-tuned on your own code, etc. But talk is cheap and only shipping matters. So, watch what we ship, and send any feedback and requests our way!
  - emidoots 4y ago
- lern_too_spel 4y ago
  Sourcegraph had to have known GitHub would do this if they didn't accept the offer. Since this should be expected, the launch of this feature shouldn't change what their decision should have been.
  - sqs 4y ago
    Sourcegraph CEO here. Just to be clear, so internet rumors don’t get started, there was no “offer” here. We started Sourcegraph with the intent of remaining independent because building really good code search and intelligence means working across all code (not just on GitHub), all devs, and all code intelligence sources (code nav plus every dev tool you use that knows stuff about code, not just the ones in the GitHub/Microsoft suite bundle). We’ve never entertained any kind of acquisition interest for this reason. We don’t think any of today’s code host vendors with their current strategies can make truly great code search and intelligence because they’ll be biased toward their own bundled tools and limited to the subset of code hosted on that instance. It’d be kind of like Encyclopedia Britannica or The NY Times building a web search engine: helpful, but so much more limited compared to what the independent Google became. And yes, none of this was a surprise. GitHub’s new code search has been out for 14 months now. OK, hope this puts an internet rumor to rest!
    - lern_too_spel 4y ago
      GitHub's code search product looks limited compared to what Sourcegraph provides, but I don't think being limited to code on their instance is a problem. Even if a company doesn't want to use the full GitHub source code management stack, if GH search becomes good enough, people could mirror their repos onto GitHub or GitHub Enterprise Server just to use its search functionality, and Microsoft will go after that segment if they see a market there.
ezekg 4y ago
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 commonly use a certain feature.
- 100k 4y ago
  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.
  - kowlo 4y ago
    Well done
  - BaculumMeumEst 4y ago
    thanks so much, you guys are doing amazing work
  - orf 4y ago
    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.
    - 100k 4y ago
      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?
      - 4y ago
ZephyrBlu 4y ago
I really hope they release this soon and that it’s actually good. The current search sucks ass, you can’t find anything. I was trying to search for something in the WebKit source the other day and I had to use Sourcegraph because the GitHub search gave me zero results.
- 100k 4y ago
  You can try it right now in our beta. Right now, we are onboarding all signups daily. Sign up here: https://github.com/features/code-search https://github.com/features/code-search Obvious disclaimer because I work on this (and I also worked on the legacy search): It is way better.
  - ZephyrBlu 4y ago
    I just signed up to the beta. Looking forwards to trying it out :).
- bluehatbrit 4y ago
  I've been using it since it entered beta a few months back. It's a huge improvement, still not perfect but it's actually usable now, and I don't just give up with it ever time.
Beefin 4y ago
If you ever want to search binary files (image, video, pdf, etc.) within github repos: https://learn.mixpeek.com/github-search/ https://learn.mixpeek.com/github-search/
Existenceblinks 4y ago
Blackbird written in Rust is a natural approach. Those who try to sell build the whole thing with a whole thing is unwise (look at you isomorphic javascript)
- ZephyrBlu 4y ago
  Isomorphic projects are generally good for full stack apps, but I don’t think anyone would recommend you build a search engine with isomorphic JS.
cozos 4y ago
I have been waiting for this for so long.
kjuulh 4y ago
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
- kibwen 4y ago
  Supporting jump-to-definition natively seems like something that will be table stakes for any code hosting site in the future.
  - jeffbee 4y ago
    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 comment.
    - saagarjha 4y ago
      I can think of zero. Doing go-to-definition statically is very difficult.
    - tjoff 4y ago
      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 magnitude less and with github and others pushing for codespaces it could be the final piece to tie everything together.
solarkraft 4y ago
Damn, it's about time, the current search sucks. What I have found to work very well is SourceGraph; they offer search for public repos. Maybe this'll be an alternative to it.
jd3 4y ago
I was working on a research project awhile ago and every time I searched for something particular it immediately thought I was a bot after like 2-3 particular/exact queries. Ever since then, I've exclusively used sourcegraph.
Scaevolus 4y ago
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 request must be sent to each shard in the cluster.").
- __float 4y ago
  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-search-at-github/ 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.
  - hanwenn 4y ago
    (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?
tonymet 4y ago
This is a great intro / overview of full-text search for those wondering how to build your own search engine. It's a great 101-level exercise to write an inverted index implementation you can do it in an afternoon , and then expand to a leaf /aggregator in follow-up exercises.
- jeffbee 4y ago
  It is indeed Information Retrieval 101 level stuff which leads to the question of why this is the best GitHub can do with all the resources of Microsoft behind them. It's almost useless, at least for C++. It can't tell the difference between foo(int) and foo(double) or this::foo vs. that::foo. If I wanted the kind of search engine I can get a teenager to write in 16 weeks why would I expect my org to be paying $$$ for the service?
  - 100k 4y ago
    Have you tried the new search? Thanks to the variable length ngram indexing mentioned in the post, it can handle all of those cases. Sign up here to try it: https://github.com/features/code-search https://github.com/features/code-search Symbol extraction for C and C++ is currently disabled because we were having problems with the performance of the tree-sitter queries we were using, but we are planning to bring that back.
    - jeffbee 4y ago
      Sorry, it cannot handle any of those cases. You're talking about the ability to find the literal `this::foo` but that's not how it would normally appear. It normally will appear anywhere inside a `namespace this` scope, which cs.github does not grok. And cs.github cannot address finding the definition related to a given call site. It doesn't even try.
      - 100k 4y ago
        You are correct, as I mentioned, we do not analyze symbols for C and C++ at this time.
colin353 4y ago
Hey everyone, I'm Colin from GitHub's code search team: happy to answer any questions people have about it. Also, you can sign up to get access here: https://github.com/features/code-search https://github.com/features/code-search
- Royaljj 4y ago
  Hi Colin, I’m curious as to how you search repeated letters through ngram index? I understand the example search with the string “limits” (find intersection of “lim”, “imi”, “mit” and “its”). However, if the user wants to search the string “aaaaa” how would you go about searching that?
  - colin353 4y ago
    Good question. We still construct ngrams for it, exactly the same way. So for example, we might extract `aaa`, `aaa`, and `aaa`. Or we may extract `aaaa` and `aaaa`, or perhaps `aaaaa`. Then we deduplicate to find the unique ngrams and look them up in the index. So it's possible that a document containing `aaa` might match our ngram search, but we double check after retrieving them and exclude them from the result set.
- Manfred 4y ago
  Have you considered using an index directly on language tokens (eg. the abstract language tree representing the file) instead of ngrams on the source text?
  - colin353 4y ago
    We have not done this yet, but we do intend to. Actually, our search engine is so fast that syntax highlighting the search results is often slower than finding them... so if we store the language tokens directly in the index, we'll be able to directly emit syntax highlighted snippets and make it even faster. It may also enable some interesting search capabilities in the future, like searching within comments or by code structure.
simonw 4y ago
I really appreciate that this includes details about how search permissions work - how they ensure that search results include data from my private repos. I'd always wondered how they implemented that: it turns out they add extra internal filters to their searches along the lines of "RepoIDs(...) or PublicRepo". Question for the team: Do you have an additional permission check in the view layer before the results are shown to the end-user? I worry that if I switch a repo from public to private it may take a while for the code search index to catch up to the new permissions.
- tclem 4y ago
  Yes, we never fully trust the search index so before anything is displayed to the user there are a number of final checks performed to make sure you're actually allowed to see that content. Another fun example is that your SSO session might have expired. While you technically have access to view the result, we can't show it until you go through the refresh dance to get another valid token.
debdut 4y ago
https://grep.app https://grep.app
- napsterbr 4y ago
  I use this one almost daily. It's great to find real world examples of APIs/contracts being used. Also, instant results! The underlying data may be limited (I have no idea how large it is, I doubt it has indexed every public repository out there), but I never failed to find examples of what I was looking for.
- Narushia 4y ago
  Been using this one for well over a year now. Very useful for finding real-world examples of certain implementations or API usage.
Waterluvian 4y ago
This looks delightful! One nit I have about current search: I’ll look something up and find I’m getting results for some obtuse commit in some old branch somewhere. I’d like to be able to optionally say “latest commit on branches only please” or “main branch only please.” Another thing, which might betray that I don’t understand search all that well: language aware searching that knows, for example, that a single or a double quote are syntactically interchangeable. Don’t omit half the results because I used one quote over the other when looking up `interpolation = ‘nearest’`
bjd2385 4y ago
When can we have a usable search in GitLab?
- john_cogs 4y ago
  GitLab team member. Thanks for the question. Our Code Search team is currently working on moving to Zoekt[0] which is expected to be a significant improvement as it is purpose-built for code search. We also shipped an improvement[1] to our existing search functionality at the end of last year. If you haven't used it recently, I'd encourage you to check out code search again to see if the quality has been improved for you. [0] - https://gitlab.com/groups/gitlab-org/-/epics/9404 https://gitlab.com/groups/gitlab-org/-/epics/9404 [1] - https://gitlab.com/gitlab-org/gitlab/-/issues/346914 https://gitlab.com/gitlab-org/gitlab/-/issues/346914
tantalor 4y ago
Why not kythe? https://kythe.io/ https://kythe.io/
- Scaevolus 4y ago
  Kythe is not a regex search engine. It depends on extracting precise semantics of all the code it runs on to compute correct edges like "calls-function". This only works for a few languages, and is extremely difficult to do generically across all of github.
boyter 4y ago
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 well. I usually try a search of Jquery to test this and it does not return multiple copies of different versions of it which is a good indicator that it’s slightly fuzzy. What I find really interesting about all the code search engines I know of is that each one implemented its own index. Nobody is using off the shelf software for this. I suspect that might be down to no off the shelf software providing a decent enough solution, and none providing a solution that scales. At least none that scales with decent costs. I did a small comparison of GitHub code search a while ago https://twitter.com/boyter/status/1480667185475244036?s=61&t=nfND46d9rReCju7-aw457Q https://twitter.com/boyter/status/1480667185475244036?s=61&t... But I should note a lot has improved since then, and it looks like sourcegraph now also does default AND of terms rather than exact match, so my complaints there are resolved. Impressive work by GitHub. I am sure some of the people behind it will read this comment, let me say well done to you all. I am very impressed. Also please post more information like this. There is so little out there.
- ZephyrBlu 4y ago
  Implementing your own index gives you more control over it. I think at this scale you probably want to tweak things specifically to your product rather than using a generic solution. I would guess that what you're indexing on (E.g. language, file, repo, etc) and sharding strategy affects the structure of your index as well.
  - boyter 4y ago
    Believe me I am aware. I am one of those who implemented their own index for a code search engine :) I did it for my own learning, but find it interesting because something like elastic with trigrams can get you very close, albeit at a far greater cost.
    - 4y ago
ZephyrBlu 4y ago
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 data, even doing naive full-text search. A search tool I came across a while back is a great example of something at that scale: https://pagefind.app/ https://pagefind.app/. For anyone who doesn't know anything about search I highly recommend reading this (It's mentioned in the blog post as well): https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html. Algolia also has a series of blog posts describing how their search engine works: https://www.algolia.com/blog/engineering/inside-the-algolia-engine-part-1-indexing-vs-search/ https://www.algolia.com/blog/engineering/inside-the-algolia-.... --- It's interesting that GitHub seems to have quite a few shards. Algolia basically has a monolithic architecture with 3 different hosts which replicate data and they embed their search engine in Nginx: "Our search engine is a C++ module which is directly embedded inside Nginx. So when the query enters Nginx, we directly run it through the search engine and send it back to the client." I'm guessing GitHub probably doesn't store repos in a custom binary format like Algolia does though: "Each index is a binary file in our own format. We put the information in a specific order so that it is very fast to perform queries on it." "Our Nginx C++ module will directly open the index file in memory-mapped mode in order to share memory between the different Nginx processes and will apply the query on the memory-mapped data structure." https://stackshare.io/posts/how-algolia-built-their-realtime-search-as-a-service-product https://stackshare.io/posts/how-algolia-built-their-realtime... 100ms p99 seems pretty good, but I'm curious what the p50 is and how much time is spent searching vs ranking. I've seen Dan Luu say that majority of time should be spent ranking rather than searching and when I've snooped on https://hn.algolia.com https://hn.algolia.com I've seen single digit millisecond search times in the responses, which seems to corroborate this. I'm curious why they chose to optimize ingestion when it only took 36hrs to re-index the entire corpus without optimizations. A 50% speedup is nice, but 36hrs and 18hrs are the same order of magnitude and it sounds like there was a fair amount of engineering effort put into this. An index 1/5 of the size is pretty sweet though, I have to assume that's a bigger win that 50% faster ingestion. Since they're indexing by language I wonder if they have custom indexing/searching for each language, or if their ngram strategy is generic over all languages. Perhaps their "sparse grams" naturally token different for every language. Hard to tell when they leave out the juiciest part of the strategy though: "Assume you have some function that given a bigram gives a weight". Search is so cool. I could talk about it all day.
Daffodils 4y ago
Was looking for more details on the data structure 'Geometric filter' mentioned in the footnotes. Couldn't find anything (a few unrelated papers in object recognition aside). If anybody can share anything that would be great !
- 100k 4y ago
  We hope to share more on this soon!
robertlagrant 4y ago
Not to diminish this excellent work, but: 1) I never want to search all repos globally. At worst I want to search all of my org's repos. 2) the search UI is a little clunky, in a way I'd need to be using it again to remember. Between those two I think there's loads of progress to be made outside of raw search power. Of course it's nice to have that, but that's what I'm really after.
- aeyes 4y ago
  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.
  - robertlagrant 4y ago
    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.
    - dcreager 4y ago
      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/using-files/navigating-code-on-github#cross-repository-precise-code-navigation https://docs.github.com/en/repositories/working-with-files/u... [2] https://news.ycombinator.com/item?id=34693181 https://news.ycombinator.com/item?id=34693181
      - robertlagrant 4y ago
        Thanks! That's a really fascinating search graph.
saagarjha 4y ago
I’ve been using the new code search for a couple of months and I like it, but the UI is kind of antagonistic to how I typically want to search for things. For one, the new experience doesn’t actually load code onto the page, it does some sort of lazy loading thing as you scroll around, so ⌘F doesn’t work. I understand that there’s a custom search box to try to get around this but it’s pretty slow and fiddly and I don’t really want to use it. I also find the layout to be pretty annoying, because invariably there’s a symbol panel on the side that doesn’t work for the code I want to look at, and then it’s just there taking space. If I hit “t” to enter a file name and start typing the text field loses focus after a second and I need to click on it again. I know there are a couple of people on the team in this thread: I search a lot of code on GitHub and I feel like there’s a couple of tweaks that would greatly improve my experience. Like, I think I could even show you a video of all the places where the UI has gotten less usable for me. What would be the best way to get this feedback to you? I’ve posted stuff on the forum or whatever but it’s unclear to me if this is the intended way to raise issues.
- colin353 4y ago
  Hey saagarjha, thanks for the feedback. It's our goal to make the experience as good as possible, and we're aware of shortcomings with cmd+F and `t`, among other things. We're working on it, and your feedback helps us a lot. We read all the feedback on the forum here: https://github.com/orgs/community/discussions/38692 https://github.com/orgs/community/discussions/38692, so please keep providing it. Videos and screenshots are super helpful too. Thanks for bearing with us as we continue to polish the UX!
  - saagarjha 4y ago
    Ah, I see. I'll file future feedback there, then. Thanks!
drcongo 4y ago
With current search, I can search [0] the Django repo for a class that definitely exists [1] in Django, there are 0 code results. Zero. GitHub search is mystifyingly bad, I hope this is a LOT better. [0] https://github.com/django/django/search?q=DeleteView&type=code https://github.com/django/django/search?q=DeleteView&type=co... [1] https://github.com/django/django/blob/main/django/views/generic/edit.py#L268 https://github.com/django/django/blob/main/django/views/gene...
- MapleWalnut 4y ago
  With the new GitHub code search, the first result is the DeleteView class: https://github.com/django/django/blob/bd366ca2aeffa869b7dbc0b0aa01caea75e6dc31/django/views/generic/edit.py#L268 https://github.com/django/django/blob/bd366ca2aeffa869b7dbc0...
PaulHoule 4y ago
My beef with GitHub's code search is that it doesn't distinguish between the definition of a symbol and the uses of the symbol, so you need to wade through 5 pages of results to get the one result you're looking for. I would contrast that to my IDE which usually scores a direct hit if I enter a search in the right box. The indexing they talk about in that article seems like rearranging the deck chairs on the Titanic so far as that is concerned.
- DontchaKnowit 4y ago
  Thank you. This is SUCH an obvious feature that seems super trivial to implement.
  - xavdid 4y ago
    I'm not sure how to read the post and come away thinking any of this is "super trivial", but I'd imagine if it were that easy, they would have done it already.
    - Zuiii 4y ago
      It's simple enough that most IDEs implement it. Take from that what you will.
      - rlt 4y ago
        The fact that most IDEs implement it doesn’t mean it’s trivial. I believe most IDEs leverage “language servers” written ~once per language and used by many IDEs. It’s possible GitHub could also leverage those language servers (which would be super cool) but doing it at GitHub scale is certainly not trivial. Poor man’s version using the new GitHub search would be to construct a regex that matches one but not the other.
        bobbylarrybobby 4y ago
        I think running a language server over a repo would be a reasonable addition to the current index. Should also be pretty small compared to the current index because the number of n grams far exceeds the number of symbols/items.
hbn 4y ago
I've been using this since it was still an email signup beta. I don't do anything too complicated, but man it's been invaluable to do exact-string searches across all of my organization's repos. I use it most days at work
deleted 4y ago
[deleted]
andrewmcwatters 4y ago
> 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 NEED to do this do you? 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. Maybe, maybe on a really serious day do I need to search an entire organization. But hardly ever. I have never, in over a decade ever, wanted sophisticated symbolic searching from GitHub code search, I just need remote grep. Why is the code search not feature bisected into this 99% use case, and then the occasional global repository search, which can behave entirely differently?
- 100k 4y ago
  (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-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.
  - nickysielicki 4y ago
    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.)
    - plugin-baby 4y ago
      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.
mperham 4y ago
On the spectrum of "build vs buy", this is a good example where a business should build it. Scaling code search is their core value.
chatmasta 4y ago
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.
gavinray 4y ago
I just want to say thank-you to the folks who work on Code Search at GitHub. It's the number one way I research and understand new libraries/API's and programming languages. There's a lot more you can learn from usage in the wild than tutorial posts sometimes.
thinking001001 4y ago
Hmm not sure if I should delete my (2nd) Github account again, just thinking about how much data they are getting from users, it could become the Facebook of Git.
tuan 4y ago
I wish they provide short name versions for their filters. For example: instead of "withContext language:python path:tests", I could write "withContext l:python p:tests".
kirillbobyrev 4y ago
This is exciting! I see a lot of familiar pieces here that propagated from Google's Code Search and I know few people from Code Search went to GitHub, probably specifically to work on this. I always wondered why GitHub didn't invest into a decent code searching features, but I'm happy it finally gets to the State of the Art one step at a time. Some of the folks going to GitHub to work on this I know are just incredible and I have no doubt GitHub's code search will be amazing. I also worked on something similar to the search engine that is described here for the purposes of making auto-complete fast for C++ in Clangd. That was my intern project back in 2018 and it was very successful in reducing the delays and latencies in the auto-complete pipeline. That project was a lot of fun and was also based on Russ Cox's original Google Code Search trigram index. My implementation of the index is still largely untouched and is a hot path of Clangd. I made a huge effort to document it as much as I can and the code is, I believe, very readable (although I'm obviously very biased because I spent a loot of time with it). Here is the implementation: https://github.com/llvm/llvm-project/tree/main/clang-tools-extra/clangd/index/dex https://github.com/llvm/llvm-project/tree/main/clang-tools-e... I also wrote a... very long design document about how exactly this works, so if you're interested in understanding the internals of a code search engine, you can check it out: https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiG...
user3939382 4y ago
The cursor position in the free-form query terms in the search input doesn’t align correctly when the input contains tags.
j1elo 4y ago
Will this allow for a happy closure of this question about searching partial words? [0] Like searching for "OPTION" and getting "-DOPTION=TRUE" among the results. Very commonly needed to find all usages of a flag, even instances where the flag is being passed to (at least, that I know of) CMake and Meson. [0]: https://stackoverflow.com/questions/43891605/search-partial-words-in-github-organizations-code https://stackoverflow.com/questions/43891605/search-partial-...
- 100k 4y ago
  Yes. You can also use regular expressions to limit your search. Details: https://docs.github.com/en/search-github/github-code-search/understanding-github-code-search-syntax https://docs.github.com/en/search-github/github-code-search/...
  - j1elo 4y ago
    Great to know! I'll check the docs and see to try it out soon
latchkey 4y ago
I wonder if they've done any work to deal with index pollution, such that one can achieve higher ranking in the results?
WoodenChair 4y ago
The biggest problems I have with their code search are basic usability features, not the search itself. I need a way to exclude private repositories in the result so I’m not clogged by internal instances of what I’m looking for. I need the UI to improve so I don’t have to go to advanced search for every filter I want to do.
webmaven 4y ago
Blackbird? I wonder if the name is coincidence or irony: https://en.m.wikipedia.org/wiki/Blackbird_(online_platform) https://en.m.wikipedia.org/wiki/Blackbird_(online_platform)
- dmurray 4y ago
  There are only so many names, but these days I'd be wary of calling a project BlackAnything.
Royaljj 4y ago
Interesting stuff, was curious how they search repeated letters through ngram index? I understand their example search with the string “limits” (find intersection of “lim”, “imi”, “mit” and “its”. However, if the user wants to search the string “aaaaa” how would they go about searching that?
deleted 4y ago
[deleted]
_pastel 4y ago
So in the sparse grams explanation, what are the bigram weights? Is it inverse frequency, so common bigrams get split last? And the goal is to be able to search on a larger gram that covers the more common trigrams as often as possible?
sidcool 4y ago
I feel search is the most complex domain tech wise. I always feel overwhelmed how people design such systems. Would love to learn more about search. Any books or courses? Right now I can only do binary search.
purkka 4y ago
My biggest feature request would be sorting or filtering by code/commit/repo age, or even repo stars. Most often I end up using code search for figuring out where a piece of code originated, just to find thousands of random projects that have also copied the same code verbatim. Sorting for "relevance" or "latest/oldest indexed" are equally useless.
deleted 4y ago
[deleted]
duckydude20 4y ago
working with this much data is like high voltage engineering. so fascinating...
Cian911 4y ago
> 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?
- 100k 4y ago
  (I edited this post.) Maybe that could have been worded more clearly... What we mean is repositories with atypical activity patterns, for example a busy monorepo with lots of files and continuous pushes. If we sharded by repository, a single shard would be responsible for processing all the updated documents for this busy repository.

750 points by joshbetz 4y ago

loginatnine 4y ago

I'm curious if they'll open source Blackbird, it does not seem mentioned in the post.

jaza 4y ago
I'm also curious. Sadly, unless I hear otherwise, I assume that the answer is no.
yazaddaruvala 4y ago
From the description, it is just ElasticSearch re-built on top of a Kafka topic. Its not clear what benefit it would brings to open source it.

imadethis 4y ago

Sourcegraph should’ve accepted that offer from GitHub.

deleted 4y ago
[deleted]
pigtailgirl 4y ago
-- was looking at their glassdoor last night - one of the worst ive seen in tech so far --
- icelancer 4y ago
  Seems fine to me? I was expecting a bloodbath but the reviews are all pretty balanced, with Yegge getting a pretty good amount of praise.
mxstbr 4y ago
I don't think Sourcegraph is in big trouble here. Their whole play is enterprises, who likely have code spread across many different hosts. On top of that, their code search is still miles ahead of GitHub's.
- tooltitude 4y ago
  It's very useful for enterprises to have one solution like github. Github isn't the best in every fields, but overall it's the best offer (they have git hosting, continuous integration, bug tracking, discussion forums, hosted dev environment, and now code search). It reminds me of a bundling strategy used in MS Office.
- the_mitsuhiko 4y ago
  The new code search includes private repos. Miles ahead doesn’t matter if you get the search at GitHub for free. GitHub actions started out pretty terrible but they are now dominating hosted CI. SourceGraph likely has challenging times ahead considering the valuation.
  - sqs 4y ago
    Sourcegraph CEO here. “Challenging times” is how it should be all the time. That means competition is forcing both GitHub and us to build better stuff for devs. Devs win. But to be clear, as a company we are doing well and growing nicely inside customers, with a ton of cash in the bank, an awesome team, and a huge opportunity ahead of us. GitHub’s new code search has been out for 14 months now, so this is nothing new. It’s a big market and there’s way more room for differentiation and dev choice in code search/intelligence than in CI. There’s a lot of code intelligence that GitHub won’t support (precise code nav for more languages, comprehensive code ownership, metadata from other dev tools that know things about code outside the GitHub/Microsoft suite, etc.), there’s a need for the ability to fix (with our Batch Changes) not just find, and even in the core search workflow there’s so much room for improvement with AI fine-tuned on your own code, etc. But talk is cheap and only shipping matters. So, watch what we ship, and send any feedback and requests our way!
- emidoots 4y ago
lern_too_spel 4y ago
Sourcegraph had to have known GitHub would do this if they didn't accept the offer. Since this should be expected, the launch of this feature shouldn't change what their decision should have been.
- sqs 4y ago
  Sourcegraph CEO here. Just to be clear, so internet rumors don’t get started, there was no “offer” here. We started Sourcegraph with the intent of remaining independent because building really good code search and intelligence means working across all code (not just on GitHub), all devs, and all code intelligence sources (code nav plus every dev tool you use that knows stuff about code, not just the ones in the GitHub/Microsoft suite bundle). We’ve never entertained any kind of acquisition interest for this reason. We don’t think any of today’s code host vendors with their current strategies can make truly great code search and intelligence because they’ll be biased toward their own bundled tools and limited to the subset of code hosted on that instance. It’d be kind of like Encyclopedia Britannica or The NY Times building a web search engine: helpful, but so much more limited compared to what the independent Google became. And yes, none of this was a surprise. GitHub’s new code search has been out for 14 months now. OK, hope this puts an internet rumor to rest!
  - lern_too_spel 4y ago
    GitHub's code search product looks limited compared to what Sourcegraph provides, but I don't think being limited to code on their instance is a problem. Even if a company doesn't want to use the full GitHub source code management stack, if GH search becomes good enough, people could mirror their repos onto GitHub or GitHub Enterprise Server just to use its search functionality, and Microsoft will go after that segment if they see a market there.

ezekg 4y ago

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 commonly use a certain feature.

100k 4y ago
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.
- kowlo 4y ago
  Well done
- BaculumMeumEst 4y ago
  thanks so much, you guys are doing amazing work
- orf 4y ago
  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.
  - 100k 4y ago
    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?
    - 4y ago

ZephyrBlu 4y ago

I really hope they release this soon and that it’s actually good. The current search sucks ass, you can’t find anything. I was trying to search for something in the WebKit source the other day and I had to use Sourcegraph because the GitHub search gave me zero results.

100k 4y ago
You can try it right now in our beta. Right now, we are onboarding all signups daily. Sign up here: https://github.com/features/code-search https://github.com/features/code-search Obvious disclaimer because I work on this (and I also worked on the legacy search): It is way better.
- ZephyrBlu 4y ago
  I just signed up to the beta. Looking forwards to trying it out :).
bluehatbrit 4y ago
I've been using it since it entered beta a few months back. It's a huge improvement, still not perfect but it's actually usable now, and I don't just give up with it ever time.

Beefin 4y ago

If you ever want to search binary files (image, video, pdf, etc.) within github repos: https://learn.mixpeek.com/github-search/ https://learn.mixpeek.com/github-search/

Existenceblinks 4y ago

Blackbird written in Rust is a natural approach. Those who try to sell build the whole thing with a whole thing is unwise (look at you isomorphic javascript)

ZephyrBlu 4y ago
Isomorphic projects are generally good for full stack apps, but I don’t think anyone would recommend you build a search engine with isomorphic JS.

cozos 4y ago

I have been waiting for this for so long.

kjuulh 4y ago

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

kibwen 4y ago
Supporting jump-to-definition natively seems like something that will be table stakes for any code hosting site in the future.
- jeffbee 4y ago
  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 comment.
  - saagarjha 4y ago
    I can think of zero. Doing go-to-definition statically is very difficult.
  - tjoff 4y ago
    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 magnitude less and with github and others pushing for codespaces it could be the final piece to tie everything together.

solarkraft 4y ago

Damn, it's about time, the current search sucks. What I have found to work very well is SourceGraph; they offer search for public repos. Maybe this'll be an alternative to it.

jd3 4y ago

I was working on a research project awhile ago and every time I searched for something particular it immediately thought I was a bot after like 2-3 particular/exact queries. Ever since then, I've exclusively used sourcegraph.

Scaevolus 4y ago

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 request must be sent to each shard in the cluster.").

__float 4y ago
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-search-at-github/ 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.
- hanwenn 4y ago
  (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?

tonymet 4y ago

This is a great intro / overview of full-text search for those wondering how to build your own search engine. It's a great 101-level exercise to write an inverted index implementation you can do it in an afternoon , and then expand to a leaf /aggregator in follow-up exercises.

jeffbee 4y ago
It is indeed Information Retrieval 101 level stuff which leads to the question of why this is the best GitHub can do with all the resources of Microsoft behind them. It's almost useless, at least for C++. It can't tell the difference between foo(int) and foo(double) or this::foo vs. that::foo. If I wanted the kind of search engine I can get a teenager to write in 16 weeks why would I expect my org to be paying $$$ for the service?
- 100k 4y ago
  Have you tried the new search? Thanks to the variable length ngram indexing mentioned in the post, it can handle all of those cases. Sign up here to try it: https://github.com/features/code-search https://github.com/features/code-search Symbol extraction for C and C++ is currently disabled because we were having problems with the performance of the tree-sitter queries we were using, but we are planning to bring that back.
  - jeffbee 4y ago
    Sorry, it cannot handle any of those cases. You're talking about the ability to find the literal `this::foo` but that's not how it would normally appear. It normally will appear anywhere inside a `namespace this` scope, which cs.github does not grok. And cs.github cannot address finding the definition related to a given call site. It doesn't even try.
    - 100k 4y ago
      You are correct, as I mentioned, we do not analyze symbols for C and C++ at this time.

colin353 4y ago

Hey everyone, I'm Colin from GitHub's code search team: happy to answer any questions people have about it. Also, you can sign up to get access here: https://github.com/features/code-search https://github.com/features/code-search

Royaljj 4y ago
Hi Colin, I’m curious as to how you search repeated letters through ngram index? I understand the example search with the string “limits” (find intersection of “lim”, “imi”, “mit” and “its”). However, if the user wants to search the string “aaaaa” how would you go about searching that?
- colin353 4y ago
  Good question. We still construct ngrams for it, exactly the same way. So for example, we might extract `aaa`, `aaa`, and `aaa`. Or we may extract `aaaa` and `aaaa`, or perhaps `aaaaa`. Then we deduplicate to find the unique ngrams and look them up in the index. So it's possible that a document containing `aaa` might match our ngram search, but we double check after retrieving them and exclude them from the result set.
Manfred 4y ago
Have you considered using an index directly on language tokens (eg. the abstract language tree representing the file) instead of ngrams on the source text?
- colin353 4y ago
  We have not done this yet, but we do intend to. Actually, our search engine is so fast that syntax highlighting the search results is often slower than finding them... so if we store the language tokens directly in the index, we'll be able to directly emit syntax highlighted snippets and make it even faster. It may also enable some interesting search capabilities in the future, like searching within comments or by code structure.

simonw 4y ago

I really appreciate that this includes details about how search permissions work - how they ensure that search results include data from my private repos. I'd always wondered how they implemented that: it turns out they add extra internal filters to their searches along the lines of "RepoIDs(...) or PublicRepo". Question for the team: Do you have an additional permission check in the view layer before the results are shown to the end-user? I worry that if I switch a repo from public to private it may take a while for the code search index to catch up to the new permissions.

tclem 4y ago
Yes, we never fully trust the search index so before anything is displayed to the user there are a number of final checks performed to make sure you're actually allowed to see that content. Another fun example is that your SSO session might have expired. While you technically have access to view the result, we can't show it until you go through the refresh dance to get another valid token.

debdut 4y ago

https://grep.app https://grep.app

napsterbr 4y ago
I use this one almost daily. It's great to find real world examples of APIs/contracts being used. Also, instant results! The underlying data may be limited (I have no idea how large it is, I doubt it has indexed every public repository out there), but I never failed to find examples of what I was looking for.
Narushia 4y ago
Been using this one for well over a year now. Very useful for finding real-world examples of certain implementations or API usage.

Waterluvian 4y ago

This looks delightful! One nit I have about current search: I’ll look something up and find I’m getting results for some obtuse commit in some old branch somewhere. I’d like to be able to optionally say “latest commit on branches only please” or “main branch only please.” Another thing, which might betray that I don’t understand search all that well: language aware searching that knows, for example, that a single or a double quote are syntactically interchangeable. Don’t omit half the results because I used one quote over the other when looking up `interpolation = ‘nearest’`

bjd2385 4y ago

When can we have a usable search in GitLab?

john_cogs 4y ago
GitLab team member. Thanks for the question. Our Code Search team is currently working on moving to Zoekt[0] which is expected to be a significant improvement as it is purpose-built for code search. We also shipped an improvement[1] to our existing search functionality at the end of last year. If you haven't used it recently, I'd encourage you to check out code search again to see if the quality has been improved for you. [0] - https://gitlab.com/groups/gitlab-org/-/epics/9404 https://gitlab.com/groups/gitlab-org/-/epics/9404 [1] - https://gitlab.com/gitlab-org/gitlab/-/issues/346914 https://gitlab.com/gitlab-org/gitlab/-/issues/346914

tantalor 4y ago

Why not kythe? https://kythe.io/ https://kythe.io/

Scaevolus 4y ago
Kythe is not a regex search engine. It depends on extracting precise semantics of all the code it runs on to compute correct edges like "calls-function". This only works for a few languages, and is extremely difficult to do generically across all of github.

boyter 4y ago

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 well. I usually try a search of Jquery to test this and it does not return multiple copies of different versions of it which is a good indicator that it’s slightly fuzzy. What I find really interesting about all the code search engines I know of is that each one implemented its own index. Nobody is using off the shelf software for this. I suspect that might be down to no off the shelf software providing a decent enough solution, and none providing a solution that scales. At least none that scales with decent costs. I did a small comparison of GitHub code search a while ago https://twitter.com/boyter/status/1480667185475244036?s=61&t=nfND46d9rReCju7-aw457Q https://twitter.com/boyter/status/1480667185475244036?s=61&t... But I should note a lot has improved since then, and it looks like sourcegraph now also does default AND of terms rather than exact match, so my complaints there are resolved. Impressive work by GitHub. I am sure some of the people behind it will read this comment, let me say well done to you all. I am very impressed. Also please post more information like this. There is so little out there.

ZephyrBlu 4y ago
Implementing your own index gives you more control over it. I think at this scale you probably want to tweak things specifically to your product rather than using a generic solution. I would guess that what you're indexing on (E.g. language, file, repo, etc) and sharding strategy affects the structure of your index as well.
- boyter 4y ago
  Believe me I am aware. I am one of those who implemented their own index for a code search engine :) I did it for my own learning, but find it interesting because something like elastic with trigrams can get you very close, albeit at a far greater cost.
  - 4y ago

ZephyrBlu 4y ago

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 data, even doing naive full-text search. A search tool I came across a while back is a great example of something at that scale: https://pagefind.app/ https://pagefind.app/. For anyone who doesn't know anything about search I highly recommend reading this (It's mentioned in the blog post as well): https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html. Algolia also has a series of blog posts describing how their search engine works: https://www.algolia.com/blog/engineering/inside-the-algolia-engine-part-1-indexing-vs-search/ https://www.algolia.com/blog/engineering/inside-the-algolia-.... --- It's interesting that GitHub seems to have quite a few shards. Algolia basically has a monolithic architecture with 3 different hosts which replicate data and they embed their search engine in Nginx: "Our search engine is a C++ module which is directly embedded inside Nginx. So when the query enters Nginx, we directly run it through the search engine and send it back to the client." I'm guessing GitHub probably doesn't store repos in a custom binary format like Algolia does though: "Each index is a binary file in our own format. We put the information in a specific order so that it is very fast to perform queries on it." "Our Nginx C++ module will directly open the index file in memory-mapped mode in order to share memory between the different Nginx processes and will apply the query on the memory-mapped data structure." https://stackshare.io/posts/how-algolia-built-their-realtime-search-as-a-service-product https://stackshare.io/posts/how-algolia-built-their-realtime... 100ms p99 seems pretty good, but I'm curious what the p50 is and how much time is spent searching vs ranking. I've seen Dan Luu say that majority of time should be spent ranking rather than searching and when I've snooped on https://hn.algolia.com https://hn.algolia.com I've seen single digit millisecond search times in the responses, which seems to corroborate this. I'm curious why they chose to optimize ingestion when it only took 36hrs to re-index the entire corpus without optimizations. A 50% speedup is nice, but 36hrs and 18hrs are the same order of magnitude and it sounds like there was a fair amount of engineering effort put into this. An index 1/5 of the size is pretty sweet though, I have to assume that's a bigger win that 50% faster ingestion. Since they're indexing by language I wonder if they have custom indexing/searching for each language, or if their ngram strategy is generic over all languages. Perhaps their "sparse grams" naturally token different for every language. Hard to tell when they leave out the juiciest part of the strategy though: "Assume you have some function that given a bigram gives a weight". Search is so cool. I could talk about it all day.

Daffodils 4y ago

Was looking for more details on the data structure 'Geometric filter' mentioned in the footnotes. Couldn't find anything (a few unrelated papers in object recognition aside). If anybody can share anything that would be great !

100k 4y ago
We hope to share more on this soon!

robertlagrant 4y ago

Not to diminish this excellent work, but: 1) I never want to search all repos globally. At worst I want to search all of my org's repos. 2) the search UI is a little clunky, in a way I'd need to be using it again to remember. Between those two I think there's loads of progress to be made outside of raw search power. Of course it's nice to have that, but that's what I'm really after.

aeyes 4y ago
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.
- robertlagrant 4y ago
  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.
  - dcreager 4y ago
    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/using-files/navigating-code-on-github#cross-repository-precise-code-navigation https://docs.github.com/en/repositories/working-with-files/u... [2] https://news.ycombinator.com/item?id=34693181 https://news.ycombinator.com/item?id=34693181
    - robertlagrant 4y ago
      Thanks! That's a really fascinating search graph.

saagarjha 4y ago

I’ve been using the new code search for a couple of months and I like it, but the UI is kind of antagonistic to how I typically want to search for things. For one, the new experience doesn’t actually load code onto the page, it does some sort of lazy loading thing as you scroll around, so ⌘F doesn’t work. I understand that there’s a custom search box to try to get around this but it’s pretty slow and fiddly and I don’t really want to use it. I also find the layout to be pretty annoying, because invariably there’s a symbol panel on the side that doesn’t work for the code I want to look at, and then it’s just there taking space. If I hit “t” to enter a file name and start typing the text field loses focus after a second and I need to click on it again. I know there are a couple of people on the team in this thread: I search a lot of code on GitHub and I feel like there’s a couple of tweaks that would greatly improve my experience. Like, I think I could even show you a video of all the places where the UI has gotten less usable for me. What would be the best way to get this feedback to you? I’ve posted stuff on the forum or whatever but it’s unclear to me if this is the intended way to raise issues.

colin353 4y ago
Hey saagarjha, thanks for the feedback. It's our goal to make the experience as good as possible, and we're aware of shortcomings with cmd+F and `t`, among other things. We're working on it, and your feedback helps us a lot. We read all the feedback on the forum here: https://github.com/orgs/community/discussions/38692 https://github.com/orgs/community/discussions/38692, so please keep providing it. Videos and screenshots are super helpful too. Thanks for bearing with us as we continue to polish the UX!
- saagarjha 4y ago
  Ah, I see. I'll file future feedback there, then. Thanks!

drcongo 4y ago

With current search, I can search [0] the Django repo for a class that definitely exists [1] in Django, there are 0 code results. Zero. GitHub search is mystifyingly bad, I hope this is a LOT better. [0] https://github.com/django/django/search?q=DeleteView&type=code https://github.com/django/django/search?q=DeleteView&type=co... [1] https://github.com/django/django/blob/main/django/views/generic/edit.py#L268 https://github.com/django/django/blob/main/django/views/gene...

MapleWalnut 4y ago
With the new GitHub code search, the first result is the DeleteView class: https://github.com/django/django/blob/bd366ca2aeffa869b7dbc0b0aa01caea75e6dc31/django/views/generic/edit.py#L268 https://github.com/django/django/blob/bd366ca2aeffa869b7dbc0...

PaulHoule 4y ago

My beef with GitHub's code search is that it doesn't distinguish between the definition of a symbol and the uses of the symbol, so you need to wade through 5 pages of results to get the one result you're looking for. I would contrast that to my IDE which usually scores a direct hit if I enter a search in the right box. The indexing they talk about in that article seems like rearranging the deck chairs on the Titanic so far as that is concerned.

DontchaKnowit 4y ago
Thank you. This is SUCH an obvious feature that seems super trivial to implement.
- xavdid 4y ago
  I'm not sure how to read the post and come away thinking any of this is "super trivial", but I'd imagine if it were that easy, they would have done it already.
  - Zuiii 4y ago
    It's simple enough that most IDEs implement it. Take from that what you will.
    - rlt 4y ago
      The fact that most IDEs implement it doesn’t mean it’s trivial. I believe most IDEs leverage “language servers” written ~once per language and used by many IDEs. It’s possible GitHub could also leverage those language servers (which would be super cool) but doing it at GitHub scale is certainly not trivial. Poor man’s version using the new GitHub search would be to construct a regex that matches one but not the other.
      - bobbylarrybobby 4y ago
        I think running a language server over a repo would be a reasonable addition to the current index. Should also be pretty small compared to the current index because the number of n grams far exceeds the number of symbols/items.

hbn 4y ago

I've been using this since it was still an email signup beta. I don't do anything too complicated, but man it's been invaluable to do exact-string searches across all of my organization's repos. I use it most days at work

deleted 4y ago

[deleted]

andrewmcwatters 4y ago

> 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 NEED to do this do you? 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. Maybe, maybe on a really serious day do I need to search an entire organization. But hardly ever. I have never, in over a decade ever, wanted sophisticated symbolic searching from GitHub code search, I just need remote grep. Why is the code search not feature bisected into this 99% use case, and then the occasional global repository search, which can behave entirely differently?

100k 4y ago
(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-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.
- nickysielicki 4y ago
  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.)
  - plugin-baby 4y ago
    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.

mperham 4y ago

On the spectrum of "build vs buy", this is a good example where a business should build it. Scaling code search is their core value.

chatmasta 4y ago

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.

gavinray 4y ago

I just want to say thank-you to the folks who work on Code Search at GitHub. It's the number one way I research and understand new libraries/API's and programming languages. There's a lot more you can learn from usage in the wild than tutorial posts sometimes.

thinking001001 4y ago

Hmm not sure if I should delete my (2nd) Github account again, just thinking about how much data they are getting from users, it could become the Facebook of Git.

tuan 4y ago

I wish they provide short name versions for their filters. For example: instead of "withContext language:python path:tests", I could write "withContext l:python p:tests".

kirillbobyrev 4y ago

This is exciting! I see a lot of familiar pieces here that propagated from Google's Code Search and I know few people from Code Search went to GitHub, probably specifically to work on this. I always wondered why GitHub didn't invest into a decent code searching features, but I'm happy it finally gets to the State of the Art one step at a time. Some of the folks going to GitHub to work on this I know are just incredible and I have no doubt GitHub's code search will be amazing. I also worked on something similar to the search engine that is described here for the purposes of making auto-complete fast for C++ in Clangd. That was my intern project back in 2018 and it was very successful in reducing the delays and latencies in the auto-complete pipeline. That project was a lot of fun and was also based on Russ Cox's original Google Code Search trigram index. My implementation of the index is still largely untouched and is a hot path of Clangd. I made a huge effort to document it as much as I can and the code is, I believe, very readable (although I'm obviously very biased because I spent a loot of time with it). Here is the implementation: https://github.com/llvm/llvm-project/tree/main/clang-tools-extra/clangd/index/dex https://github.com/llvm/llvm-project/tree/main/clang-tools-e... I also wrote a... very long design document about how exactly this works, so if you're interested in understanding the internals of a code search engine, you can check it out: https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiG...

user3939382 4y ago

The cursor position in the free-form query terms in the search input doesn’t align correctly when the input contains tags.

j1elo 4y ago

Will this allow for a happy closure of this question about searching partial words? [0] Like searching for "OPTION" and getting "-DOPTION=TRUE" among the results. Very commonly needed to find all usages of a flag, even instances where the flag is being passed to (at least, that I know of) CMake and Meson. [0]: https://stackoverflow.com/questions/43891605/search-partial-words-in-github-organizations-code https://stackoverflow.com/questions/43891605/search-partial-...

100k 4y ago
Yes. You can also use regular expressions to limit your search. Details: https://docs.github.com/en/search-github/github-code-search/understanding-github-code-search-syntax https://docs.github.com/en/search-github/github-code-search/...
- j1elo 4y ago
  Great to know! I'll check the docs and see to try it out soon

latchkey 4y ago

I wonder if they've done any work to deal with index pollution, such that one can achieve higher ranking in the results?

WoodenChair 4y ago

The biggest problems I have with their code search are basic usability features, not the search itself. I need a way to exclude private repositories in the result so I’m not clogged by internal instances of what I’m looking for. I need the UI to improve so I don’t have to go to advanced search for every filter I want to do.

webmaven 4y ago

Blackbird? I wonder if the name is coincidence or irony: https://en.m.wikipedia.org/wiki/Blackbird_(online_platform) https://en.m.wikipedia.org/wiki/Blackbird_(online_platform)

dmurray 4y ago
There are only so many names, but these days I'd be wary of calling a project BlackAnything.

Royaljj 4y ago

Interesting stuff, was curious how they search repeated letters through ngram index? I understand their example search with the string “limits” (find intersection of “lim”, “imi”, “mit” and “its”. However, if the user wants to search the string “aaaaa” how would they go about searching that?

deleted 4y ago

[deleted]

_pastel 4y ago

So in the sparse grams explanation, what are the bigram weights? Is it inverse frequency, so common bigrams get split last? And the goal is to be able to search on a larger gram that covers the more common trigrams as often as possible?

sidcool 4y ago

I feel search is the most complex domain tech wise. I always feel overwhelmed how people design such systems. Would love to learn more about search. Any books or courses? Right now I can only do binary search.

purkka 4y ago

My biggest feature request would be sorting or filtering by code/commit/repo age, or even repo stars. Most often I end up using code search for figuring out where a piece of code originated, just to find thousands of random projects that have also copied the same code verbatim. Sorting for "relevance" or "latest/oldest indexed" are equally useless.

deleted 4y ago

[deleted]

duckydude20 4y ago

working with this much data is like high voltage engineering. so fascinating...

Cian911 4y ago

> 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?

100k 4y ago
(I edited this post.) Maybe that could have been worded more clearly... What we mean is repositories with atypical activity patterns, for example a busy monorepo with lots of files and continuous pushes. If we sharded by repository, a single shard would be responsible for processing all the updated documents for this busy repository.