GitHub claims source code search engine is a game changer
(2023/02/07)
- Reference: 1675805413
- News link: https://www.theregister.co.uk/2023/02/07/github_code_search/
- Source link:
GitHub has a lot of code to search – more than 200 million repositories – and says last November's beta version of a search engine optimized for source code that has caused a "flurry of innovation."
GitHub engineer Timothy Clem explained that the company has had problems getting existing technology to work well. "The truth is from Solr to Elasticsearch, we haven't had a lot of luck using general text search products to power code search," he [1]said in a GitHub Universe video presentation. "The user experience is poor. It's very, very expensive to host and it's slow to index."
In a [2]blog post on Monday, Clem delved into the technology used to scour just a quarter of those repos, a code search engine built in Rust called Blackbird.
[3]
Blackbird currently provides access to almost 45 million GitHub repositories, which together amount to 115TB of code and 15.5 billion documents. Shifting through that many lines of code requires something stronger than grep, a common command line tool on Unix-like systems for searching through text data.
[4]
[5]
Using [6]ripgrep on an 8-core Intel CPU to run an exhaustive regular expression query on a 13GB file in memory, Clem explained, takes about 2.769 seconds, or 0.6GB/sec/core.
"We can see pretty quickly that this really isn’t going to work for the larger amount of data we have," he said. "Code search runs on 64 core, 32 machine clusters. Even if we managed to put 115TB of code in memory and assume we can perfectly parallelize the work, we’re going to saturate 2,048 CPU cores for 96 seconds to serve a single query! Only that one query can run. Everybody else has to get in line."
[7]GitHub CEO says EU AI Act shouldn't apply to open source devs
[8]Mozilla, like Google, is looking ahead to the end of Apple's WebKit rule
[9]Microsoft, GitHub, OpenAI urge judge to bin Copilot code rip-off case
[10]ChatGPT (sigh) the fastest-growing web app in history (sigh) claim analysts
At 0.01 queries per second, grep was not an option. So GitHub front-loaded much of the work into precomputed search indices. These are essentially maps of key-value pairs. This approach makes it less computationally demanding to search for document characteristics like the programming language or word sequences by using a numeric key rather than a text string.
Even so, these indices are too large to fit in memory, so GitHub built iterators for each index it needed to access. According to Clem, these lazily return sorted document IDs that represent the rank of the associated document and meet the query criteria.
[11]
To keep the search index manageable, GitHub relies on sharding – breaking the data up into multiple pieces using Git's content addressable hashing scheme and on delta encoding – storing data differences (deltas) to reduce the data and metadata to be crawled. This works well because GitHub has a lot of redundant data (e.g. forks) – its 115TB of data can be boiled down to 25TB through deduplication data-shaving techniques.
The resulting system works much faster than grep – 640 queries per second compared to 0.01 queries per second. And indexing occurs at a rate of about 120,000 documents per second, so processing 15.5 billion documents takes about 36 hours, or 18 for re-indexing since delta (change) indexing reduces the number of documents to be crawled.
GitHub Code Search is presently [12]in beta testing . ®
Get our [13]Tech Resources
[1] https://youtu.be/QCs76SC1ZZ0?t=68
[2] https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[4] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[5] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[6] https://github.com/BurntSushi/ripgrep
[7] https://www.theregister.com/2023/02/07/github_ceo_ai_act/
[8] https://www.theregister.com/2023/02/07/mozilla_google_apple_webkit/
[9] https://www.theregister.com/2023/01/31/microsoft_github_openai_copilot/
[10] https://www.theregister.com/2023/02/03/chatgpt_most_popular_apps/
[11] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[12] https://github.com/features/code-search
[13] https://whitepapers.theregister.com/
GitHub engineer Timothy Clem explained that the company has had problems getting existing technology to work well. "The truth is from Solr to Elasticsearch, we haven't had a lot of luck using general text search products to power code search," he [1]said in a GitHub Universe video presentation. "The user experience is poor. It's very, very expensive to host and it's slow to index."
In a [2]blog post on Monday, Clem delved into the technology used to scour just a quarter of those repos, a code search engine built in Rust called Blackbird.
[3]
Blackbird currently provides access to almost 45 million GitHub repositories, which together amount to 115TB of code and 15.5 billion documents. Shifting through that many lines of code requires something stronger than grep, a common command line tool on Unix-like systems for searching through text data.
[4]
[5]
Using [6]ripgrep on an 8-core Intel CPU to run an exhaustive regular expression query on a 13GB file in memory, Clem explained, takes about 2.769 seconds, or 0.6GB/sec/core.
"We can see pretty quickly that this really isn’t going to work for the larger amount of data we have," he said. "Code search runs on 64 core, 32 machine clusters. Even if we managed to put 115TB of code in memory and assume we can perfectly parallelize the work, we’re going to saturate 2,048 CPU cores for 96 seconds to serve a single query! Only that one query can run. Everybody else has to get in line."
[7]GitHub CEO says EU AI Act shouldn't apply to open source devs
[8]Mozilla, like Google, is looking ahead to the end of Apple's WebKit rule
[9]Microsoft, GitHub, OpenAI urge judge to bin Copilot code rip-off case
[10]ChatGPT (sigh) the fastest-growing web app in history (sigh) claim analysts
At 0.01 queries per second, grep was not an option. So GitHub front-loaded much of the work into precomputed search indices. These are essentially maps of key-value pairs. This approach makes it less computationally demanding to search for document characteristics like the programming language or word sequences by using a numeric key rather than a text string.
Even so, these indices are too large to fit in memory, so GitHub built iterators for each index it needed to access. According to Clem, these lazily return sorted document IDs that represent the rank of the associated document and meet the query criteria.
[11]
To keep the search index manageable, GitHub relies on sharding – breaking the data up into multiple pieces using Git's content addressable hashing scheme and on delta encoding – storing data differences (deltas) to reduce the data and metadata to be crawled. This works well because GitHub has a lot of redundant data (e.g. forks) – its 115TB of data can be boiled down to 25TB through deduplication data-shaving techniques.
The resulting system works much faster than grep – 640 queries per second compared to 0.01 queries per second. And indexing occurs at a rate of about 120,000 documents per second, so processing 15.5 billion documents takes about 36 hours, or 18 for re-indexing since delta (change) indexing reduces the number of documents to be crawled.
GitHub Code Search is presently [12]in beta testing . ®
Get our [13]Tech Resources
[1] https://youtu.be/QCs76SC1ZZ0?t=68
[2] https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[4] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[5] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[6] https://github.com/BurntSushi/ripgrep
[7] https://www.theregister.com/2023/02/07/github_ceo_ai_act/
[8] https://www.theregister.com/2023/02/07/mozilla_google_apple_webkit/
[9] https://www.theregister.com/2023/01/31/microsoft_github_openai_copilot/
[10] https://www.theregister.com/2023/02/03/chatgpt_most_popular_apps/
[11] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_software/devops&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44Y@LYEYyvsElKGuObagdGXAAAAE8&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[12] https://github.com/features/code-search
[13] https://whitepapers.theregister.com/
Re: Why?
b0llchit
It is a "look at us!" project. The "we can do this" adventure of a "see how good we are" endeavour.
There is no point to any literal textual search in code of that size. If you want to find illicit copying you need to do a lot more than simple-words-and-phrases comparisons. Algorithms and solutions cannot be found on word basis. This type of search also discards any code structure and context.
And, if you really need to find your own code in 15e9 lines of community code... well, you should have kept your copy. Alternatively, it would be much faster to use a search engine.
So we are clearly left with the "look at us!" explanation.
Why?
Why would you want to search code?
I mean, why would you want to perform a textual search of a horde of strangers' code, the intention of which is unknown to you?
If for a solution to an actual problem then, without some knowledge of how to solve that problem you can't know what to search for.
Unless, of course, you're relying on comments to describe what the code does, or is intended to do. Which is eminently subvertible, whether for lolz or for nefarious pursuit of illicit profit.
-A.