If this interests you, I recommend The History of English podcast. The episodes on Old English cover similar linguistic evolution that happened due the influence of Old Norse.
3,186 karma · joined July 11, 2008
Minneapolitan in exile. My blog is http://recursion.org.
I usually go by "look" online but that was taken at HN when I registered.
If anyone else is curious about why the cracked window didn't cause an implosion, I found the answer in an interview: it was a plexiglass window on the entrance tunnel, not the viewport that was part of the sphere.
"A Plexiglas window in the flooded entrance tunnel had cracked under the pressure. But Walsh and Piccard were safe inside their cabin, separated from the tunnel by a thick steel hatch."
https://spectrum.ieee.org/don-walsh-describes-the-trip-to-th...
It's not as old, but in Wernor Herzog's documentary "Cave of Forgotten Dreams", an archeologist plays a 30,000 year old vulture bone flute. It even uses the pentatonic scale!
Some links about it:
https://www.youtube.com/watch?v=yUCBBDV2Tzk https://www.ethanhein.com/wp/2011/flute-of-forgotten-dreams/ https://www.npr.org/2009/06/24/105823127/a-little-flute-musi...
The current GitHub code search is based on Elasticsearch and indexes more than 100M repositories. Its tokenization is based on whitespace, case changes (like CamelCase) and punctuation (like kebab-case) and strips out non-letter characters like < or { which is why it can't do exact match search.
Our new code search, currently in beta and indexing about 45 million repositories, uses an search engine we built in house that indexes content using a technique we call sparse ngrams. This allows us to execute searches faster than a trigrams index, while also being smaller than a positional trigram index. My teammate discussed some of the technology behind it in our blog post that was published yesterday: https://github.blog/2023-02-06-the-technology-behind-githubs...
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 DAGs) into a list of documents to index (the prior state is diffed for changes).
Is your custom index format a binary format? I have no idea whether that's standard practice, or just a compressed text format is enough. I guess that non-binary formats would be enormous though, and given that an index is by definition relatively unique it probably wouldn't compress that well.
Binary formats are normal, posting lists are giant sorted blocks of numbers, so there are a lot of techniques that can be used to compress them. Lucene's index format is pretty well documented if you're interested in learning more (interestingly, Lucene has a text format for debugging: https://lucene.apache.org/core/8_6_3/codecs/org/apache/lucen...).
Scale up in terms of what? Is the current system not indexing all of GitHub, or you mean you want to index on more things (E.g. commits, PRs, etc)?
It's not indexing all of GitHub yet, nor do all users have access yet. Those are the things we are focusing on now. In the future, we want to support indexing branches.
If you check out our prior blog post, "A brief history of code search at GitHub" (https://github.blog/2021-12-15-a-brief-history-of-code-searc...), you can learn a bit about the evolution of this feature. And, in fact, we used to use git grep to search repositories.
This doesn't work well at GitHub's scale. We have 100M users and over 200M repositories in a multi-tenant environment. Your git grep is going to be competing for resources with other user's pushes and clones.
An early version of Blackbird experimented with trigrams plus a bitmask of the next character, but it didn't work well because it wasn't selective enough. This is mentioned in the blog post:
We tried a number of strategies to fix this like adding follow masks, which use bitmasks for the character following the trigram (basically halfway to quad grams), but they saturate too quickly to be useful.
It's interesting that GitHub seems to have quite a few shards. Algolia basically has a monolithic architecture with 3 different hosts
I used to work at an Algolia competitor. I don't know for sure, but my guess is that Algolia shards their indices by customer. Algolia does not provide global search. GitHub code search does. That, and the desire to deduplicate data, is what led us to our current sharding strategy (notably, it is different than the old GitHub code search's sharding.).
I'm guessing GitHub probably doesn't store repos in a custom binary format like Algolia does though:
We have a custom index format, so I would say this is the same, unless you mean something different. We of course translate repos from their Git form to our index document form for indexing.
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.
The index size is a bigger win, but being able to reindex quickly is huge for our development velocity and trying things out. We really feel it when things are slow. This is also not our final goal, we want to scale the system up considerably.
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.
Obvious disclaimer because I work on this (and I also worked on the legacy search): It is way better.
"Introduction to Information Retrieval" is a textbook which is available online https://nlp.stanford.edu/IR-book/ Here's a review: http://glinden.blogspot.com/2009/02/book-review-introduction...
Another textbook which IMHO is a bit lower level is "Information Retrieval: Implementing and Evaluating Search Engines". The book website is down for me right now, but you can find it on Amazon here: https://www.amazon.com/Information-Retrieval-Implementing-Ev...
Another commenter linked to "Relevant Search", which is great if you want to learn how to effectively use a search engine to improve relevance (as opposed to how to implement a search engine). It's old, but another book in that vein that was really helpful for me earlier in my career is Lucene in Action: https://www.amazon.com/Lucene-Action-Second-Covers-Apache/dp...
Yes, the new code search and navigation experience is powered by React for the frontend. We decided to use that because we wanted to build a stateful, rich navigation experience.
If you want to try it, please sign up for our beta https://github.com/features/code-search (we have been clearing the waitlist daily.)