Die Zeit ist ein flacher Kreis. Als 1973 die erste Version von grep veröffentlicht wurde, war es ein einfaches Hilfsprogramm, um reguläre Ausdrücke mit Textdateien in einem Dateisystem abzugleichen. Im Laufe der Jahre wurden Entwickler-Tools immer fortschrittlicher, und grep wurde nach und nach von spezialisierteren Tools verdrängt. Zuerst durch grob syntaktische Indizes wie ctags. Später wechselten viele Entwickler zu spezialisierten IDEs für bestimmte Programmiersprachen, mit denen sie sich durch das Parsen und Erstellen syntaktischer Indizes sehr effizient in Codebasen bewegen konnten, oft ergänzt durch Typinformationen. Schließlich wurde dies im Language Server Protocol (LSP) standardisiert, das diese Indizes in alle Texteditoren brachte, ob alt oder neu. Und genau als sich LSP als Standard etablierte, kam agentisches Programmieren auf — und siehe da: Agenten lieben es einfach, grep zu nutzen.

Es gibt auch andere moderne Verfahren, um Kontext für Agenten zu sammeln. Wir haben früher schon darüber gesprochen, wie stark sich die Leistung von Agenten bei vielen Aufgaben durch semantische Indizes verbessern lässt, aber es gibt bestimmte Anfragen, die das Modell nur durch Suchen mit regulären Ausdrücken auflösen kann. Das bedeutet, ins Jahr 1973 zurückzugehen, auch wenn sich das Feld seitdem ein wenig weiterentwickelt hat.

Die meisten Agent-Harnesses, auch unsere, verwenden standardmäßig ripgrep, wenn sie ein Such-Tool bereitstellen. Es ist eine eigenständige ausführbare Datei, entwickelt von Andrew Gallant, die eine Alternative zum klassischen grep bietet, aber mit sinnvolleren Standardeinstellungen (z. B. beim Ignorieren von Dateien) und mit deutlich besserer Leistung. ripgrep ist bekanntlich schnell, weil Andrew viel Zeit darauf verwendet hat, über Geschwindigkeit nachzudenken, wenn es um das Abgleichen regulärer Ausdrücke geht.

Egal wie schnell ripgrep Inhalte in einer Datei abgleichen kann, es hat eine ernsthafte Einschränkung: Es muss die Inhalte von allen Dateien abgleichen. Das ist bei kleinen Projekten in Ordnung, aber viele Benutzer von Cursor, insbesondere große Enterprise-Kunden, arbeiten in sehr großen Monorepos. Schmerzhaft großen. Wir sehen regelmäßig rg-Aufrufe, die mehr als 15 Sekunden dauern, und das bremst den Workflow derjenigen spürbar aus, die aktiv mit dem Agent interagieren, um ihn beim Schreiben von Code anzuleiten.

Das Abgleichen regulärer Ausdrücke ist heute ein zentraler Bestandteil agentischer Entwicklung, und wir glauben, dass es entscheidend ist, es gezielt anzugehen: So wie eine traditionelle IDE lokal syntaktische Indizes für Operationen wie Go To Definition erstellt, erstellen wir Indizes für die zentrale Operation, die moderne Agenten beim Nachschlagen von Text ausführen.

#Der klassische Algorithmus

Die Idee der Indizierung textueller Daten zur Beschleunigung von Abgleichen mit regulären Ausdrücken ist keineswegs neu. Sie wurde erstmals 1993 von Zobel, Moffat und Sacks-Davis in einer Arbeit mit dem Titel "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" veröffentlicht. Darin stellen sie einen Ansatz vor, der n-Gramme (Segmente einer Zeichenkette mit einer Breite von n Zeichen) zum Erstellen eines invertierten Indexes sowie Heuristiken zur Zerlegung regulärer Ausdrücke in einen Baum aus n-Grammen nutzt, die im Index nachgeschlagen werden können.

Wenn du von diesem Konzept schon einmal gehört hast, dann wahrscheinlich nicht aus dieser Arbeit, sondern aus einem Blogbeitrag, den Russ Cox 2012 kurz nach der Einstellung von Google Code Search veröffentlicht hat. Schauen wir uns die Bausteine dieser Indizes kurz noch einmal an, denn sie gelten im Grunde für fast jeden anderen Ansatz zur Indizierung, der seitdem entwickelt wurde.

#Invertierte Indizes

Ein invertierter Index ist die grundlegende Datenstruktur hinter einer Suchmaschine. Ausgehend von einer Menge zu indexierender Dokumente erstellst du einen invertierten Index, indem du jedes Dokument in Tokens zerlegst. Das nennt man Tokenisierung, und dafür gibt es viele verschiedene Verfahren — für dieses Beispiel nutzen wir den denkbar einfachsten Ansatz: einzelne Wörter als Tokens. Die Tokens werden dann zu den Schlüsseln einer wörterbuchähnlichen Datenstruktur, während die Werte für jeden Token die Liste aller Dokumente sind, in denen er vorkommt. Diese Liste wird üblicherweise als Posting-Liste bezeichnet, weil jedes Dokument eindeutig durch einen numerischen Wert oder ein „Posting“ identifiziert wird. Wenn du nach einem oder mehreren Tokens suchst, laden wir ihre Posting-Listen; gibt es mehr als eine Posting-Liste, bilden wir ihre Schnittmenge, um die Dokumente zu finden, die in allen vorkommen.

Dieses Design (mit viel zusätzlicher Komplexität obendrauf) ist die Grundlage der meisten heute verfügbaren Suchmaschinen. Aber das sind Suchmaschinen für natürliche Sprache, und wir versuchen, nach regulären Ausdrücken zu suchen und sie auf Quellcode anzuwenden. Das funktioniert so nicht wirklich.

Du kannst versuchen, hier etwas Nützliches zu erstellen, indem du sehr gründlich über die Tokenisierung nachdenkst — also die Syntax jeder Programmiersprache berücksichtigst, Bezeichner im Quellcode aufteilst und so weiter. Das ist sehr schwer, richtig umzusetzen. In den Anfangstagen von GitHub funktionierte das Code Search Feature genau so: mit einem sehr komplexen Tokenizer für Programmiersprachen und einem sehr großen ElasticSearch-Cluster. Die Ergebnisse waren nicht gut, und die Leute hatten eine sehr schlechte Meinung von dem Feature. Du konntest nach Bezeichnern suchen (mehr oder weniger), aber keine regulären Ausdrücke abgleichen. Dafür brauchst du eine bessere Art der Tokenisierung.

#Trigramm-Zerlegung

Eine naive Tokenisierung von Quellcode ist für den Abgleich regulärer Ausdrücke nicht sinnvoll. Wir müssen die Dokumente in grundlegendere Einheiten aufteilen. Der klassische Algorithmus wählt Trigramme: Ein Token ist jeder überlappende Abschnitt von drei Zeichen in der Eingabezeichenfolge.

Warum drei? Wir speichern diese Trigramme als Schlüssel in unserem invertierten Index. Würden wir Bigramme (Abschnitte aus 2 Zeichen) wählen, hätten wir nur sehr wenige Schlüssel im Index, höchstens 64k, aber die Posting-Listen zu jedem Schlüssel wären riesig — zu groß, um effizient damit zu arbeiten. Würden wir Quadgramme (Abschnitte aus 4 Zeichen) wählen, wären die Posting-Listen winzig, was sehr gut ist, aber wir hätten Milliarden von Schlüsseln in unserem invertierten Index, und auch damit lässt sich nur schwer effizient arbeiten.

Trigramme sind also ein ziemlich guter Mittelweg. Dadurch wird die Tokenisierung bei der Indizierung von Dokumenten sehr einfach: Extrahiere jede überlappende Folge von 3 Zeichen aus dem Dokument, das indiziert wird, und nutze sie als Tokens im invertierten Index.

Die eigentliche Komplexität entsteht bei der Tokenisierung eines regulären Ausdrucks, damit er mit dem Index abgeglichen werden kann. Reguläre Ausdrücke haben Syntax, daher musst du sie parsen und Heuristiken nutzen, um herauszufinden, welche Trigramme sich aus den Teilen des Ausdrucks extrahieren lassen, die tatsächlich Text darstellen.

Die Zerlegung einer Literalzeichenfolge in Trigramme ist unkompliziert, da dabei derselbe Algorithmus verwendet wird wie bei der Indizierung eines Dokuments. Extrahiere jedes überlappende Trigramm, das in der Zeichenfolge enthalten ist; ein Dokument, das alle diese Trigramme enthält, enthält wahrscheinlich auch das Literal (aber nicht zwingend!). Alternationen werden separat zerlegt, sodass zwei Zweige entstehen, von denen einer in einem Dokument enthalten sein muss, damit es übereinstimmt. Im invertierten Index fragen wir das ab, indem wir die Posting-Listen vereinigen, statt ihre Schnittmenge zu bilden. Zeichenklassen können in viele Trigramme zerlegt werden. Kleine Klassen wie [rbc]at ergeben ein Trigramm für jedes Element der Klasse. Bei allgemeineren Zeichenklassen überspringen wir einfach die Extraktion solcher Trigramme über diese Grenzen hinweg.

#Alles zusammengeführt

Wir wissen, dass Trigramme die richtige Methode sind, um diese Dokumente zu tokenisieren. Wir wissen, wie Dokumente beim Erstellen des Index tokenisiert werden und wie Abfragen beim Suchen tokenisiert werden. All das können wir nun zu einem echten Suchindex zusammenführen, der reguläre Ausdrücke sehr effizient abgleichen kann. Indem wir jeden regulären Ausdruck in eine Menge von Trigrammen zerlegen und alle relevanten Posting-Listen aus dem invertierten Index laden, erhalten wir eine Liste von Dokumenten, die potenziell zu unserem regulären Ausdruck passen. Das ist wichtig! Die endgültige Ergebnismenge erhalten wir erst, indem wir alle potenziellen Dokumente tatsächlich laden und den regulären Ausdruck „auf die altmodische Art“ abgleichen. Aber diese Teilmenge von Dokumenten ist immer noch schneller, als die gesamte Codebasis Datei für Datei zu scannen und abzugleichen.

Dieser Ansatz ist grundsätzlich vollkommen funktionsfähig. Projekte wie google/codesearch und sourcegraph/zoekt liefern gute Performance für große Indizes mit einem invertierten Index aus Trigrammen (und wie alle Suchmaschinen setzen sie noch deutlich mehr Komplexität obendrauf). Aber es gibt hier klare Schwächen: Die Indexgrößen sind nicht klein, und die Zerlegung zur Abfragezeit erfordert einen Kompromiss. Wenn du einfache Heuristiken nutzt, zerlegst du Abfragen in nur wenige Trigramme, und das führt zu vielen potenziellen Dokumenten, die abgeglichen werden müssen. Wenn du komplexe Heuristiken nutzt, kannst du bei Dutzenden — vielleicht Hunderten — von Trigrammen landen, und all diese aus dem invertierten Index zu laden kann genauso langsam werden, wie einfach alles von Grund auf zu durchsuchen.

Das geht besser.

#Suffix-Arrays: ein Exkurs

Da wir uns mit der Geschichte der Indizierung von Textdaten für Suchen mit regulären Ausdrücken beschäftigen, möchte ich einen Exkurs machen und diese Implementierung besprechen, die Nelson Elhage 2015 für seinen livegrep-Webdienst entwickelt hat. Im Vergleich zu anderen großen Initiativen der Branche ist livegrep winzig — es indiziert nur die neueste Version des Linux-Kernels —, aber gerade wegen dieses kleineren Umfangs unterscheidet sich seine Implementierung stark von allem anderen, und genau das macht sie so interessant und erwähnenswert.

Nelson ging das Problem von Grund auf an: Diese Suchmaschine basiert auf keinem invertierten Index. Stattdessen wird der gesamte Quellcode in einem Suffix-Array indiziert.

Wo liegen hier die Schwächen? Ein Suffix-Array muss aus einer Eingabezeichenkette konstruiert werden. Das ist eine große Einschränkung. Wenn du versuchst, eine große Codebasis (oder vielleicht viele verschiedene Codebasen) zu indizieren, musst du zunächst den gesamten Inhalt zu einer einzigen Zeichenkette verketten und daraus das Suffix-Array konstruieren. Beim Abgleich im Suffix-Array benötigst du außerdem eine zusätzliche Datenstruktur, um die Trefferposition der ursprünglichen Datei zuzuordnen, die sie enthält. Das ist keine unüberwindbare Komplexität, aber es macht das dynamische Aktualisieren des Index sehr teuer. Diese Lösung lässt sich nur schwer skalieren.

#Trigramm-Abfragen mit probabilistischen Masken

Kehren wir zu etwas traditionelleren Ansätzen zurück: Hier ist ein Ansatz, der ursprünglich bei GitHub für Project Blackbird entwickelt wurde. Das war ein Forschungsprojekt mit dem Ziel, das alte Code-Search-Feature zu ersetzen. Wie wir bereits besprochen haben, wurde die alte Suche durch die Tokenisierung von Quellcode umgesetzt und konnte keine regulären Ausdrücke abgleichen. Das Ziel dieser neuen Implementierung war es, etwas zu entwickeln, das genau das konnte.

Die ersten Iterationen versuchten, den klassischen invertierten Index mit Trigrammen als Schlüsseln zu nutzen, stießen aber schnell auf Kapazitätsprobleme. Auf GitHub gibt es sehr viel Code, und Trigramme für die Indexierung zu nutzen führte zu Posting-Listen, die für die Suche schlicht zu groß waren.

Da Trigramme nicht wirklich funktionierten, bestand der nächste Schritt darin, eine bessere Größe für die n-Gramme zu finden, die indexiert werden sollten. Wir haben gesehen, dass Bigramme zu allgemein sind, weil ihre Posting-Listen unhandlich groß werden, und dass Quadgramme zu spezifisch sind, weil wir am Ende zu viele Schlüssel in unserem Index haben. Trigramme sind ein Sweet Spot zwischen beidem, aber in der Praxis liegt die ideale Größe eher bei ... 3,5-Grammen. Aber wir können ein Zeichen ja nicht in zwei Hälften teilen, oder?

Tatsächlich können wir etwas tun, das dem ziemlich nahekommt: Dieses Design schlägt vor, Trigramme als Schlüssel für den invertierten Index zu nutzen und die Posting-Listen um zusätzliche Informationen über das „vierte Zeichen“ zu erweitern, das in diesem spezifischen Dokument auf das Trigramm folgt. Dazu könnten wir dieses vierte Zeichen einfach als zusätzliches Byte speichern, aber damit würde unser Index zu einem Quadgramm-Index, und wir haben bereits gesehen, dass diese schlicht zu groß zum Speichern sind. Stattdessen speichern wir einen Bloom-Filter, der alle Zeichen enthält, die auf dieses spezifische Trigramm folgen.

Die resultierenden Indizes sind extrem effizient, aber sie haben einen großen Nachteil. Bloom-Filter können gesättigt werden. Das ist eine bedauerliche Eigenschaft von Bloom-Filtern: Sie lassen sich aktualisieren, aber wenn du zu viele Daten hinzufügst, werden irgendwann alle Bits im Filter gesetzt. Und sobald der Bloom-Filter gesättigt ist, passt er auf alles, sodass wir wieder bei der Performance des allerersten Index sind, über den wir gesprochen haben.

Dies ist ein Index, der den Speicherbedarf minimiert, aber er wird unerquicklich, wenn du ihn direkt an Ort und Stelle aktualisieren musst.

#Sparse N-Gramme: Intelligentere Trigramm-Auswahl

Hier ist noch eine ziemlich clevere Idee. Vielleicht hast du sie in ClickHouse beim Operator für reguläre Ausdrücke gesehen, und auch bei GitHub, im neuen Code Search Feature, das vor ein paar Jahren eingeführt wurde und reguläre Ausdrücke tatsächlich unterstützt. Sie heißt Sparse N-grams und ist ein besonders gelungener Mittelweg.

Ein traditioneller Trigramm-Index extrahiert jede aufeinanderfolgende Folge aus 3 Zeichen, aber du siehst schnell, dass das eine Menge Redundanz erzeugt. Die Zeichen in jedem Trigramm tauchen in den benachbarten erneut auf! In diesem Algorithmus extrahieren wir eine zufällige Anzahl von N-Grammen, wobei jedes N-Gramm eine zufällige Länge hat.

Natürlich kann zufällig hier nicht wirklich zufällig bedeuten, weil der Index sonst nicht abgefragt werden könnte. Wir weisen jedem Zeichenpaar im Dokument ein „Gewicht“ zu. Dieses Gewicht kann beliebig gewählt werden, solange es deterministisch ist (ClickHouse nutzt den crc32-Hash der beiden Zeichen). Unsere Sparse N-Gramme sind dann alle Teilzeichenfolgen, bei denen die Gewichte an beiden Enden strikt größer sind als alle Gewichte im Inneren.

Entscheidend ist, dass Sparse N-Gramme beliebige Längen haben können. Sie sind also nicht einheitlich. Das bedeutet auch, dass wir am Ende viele davon erzeugen können — mehr, als wenn wir einfach Trigramme extrahieren würden. Aber weil die N-Gramme deterministisch erzeugt werden, können wir zur Abfragezeit einige sehr wichtige Optimierungen vornehmen. Sehen wir uns an, wie.

Können wir das besser machen? Ja! Sogar deutlich besser. In unserem Beispiel haben wir crc32 bisher als Gewichtsfunktion im Algorithmus genutzt. Tatsächlich würde hier aber jede Hash-Funktion funktionieren, solange sie deterministisch ist. Nehmen wir also etwas sehr Clevere: eine Hash-Funktion, die jedem Zeichenpaar, das tatsächlich sehr selten ist, ein hohes Gewicht gibt, und jedem Paar, das sehr häufig ist, ein niedriges Gewicht.

Diese Hash-Funktion lässt sich leicht berechnen. Da wir Quellcode indizieren, können wir ein paar Terabyte Open-Source-Code aus dem Internet holen und eine Häufigkeitstabelle für alle Zeichenpaare erstellen, die wir darin finden. Diese Häufigkeitstabelle ist unsere Hash-Funktion. Sehen Sie, was passiert, wenn wir sie auf unseren Algorithmus anwenden: Die höchsten Gewichte liegen jetzt auf den seltensten Zeichenpaaren, und dadurch führt der Covering-Modus zu noch weniger N-Grammen, die nachgeschlagen werden müssen, und zu weniger Dokumenten, die überhaupt infrage kommen.

Dieser Ansatz, der die Anzahl der Posting-Lookups minimiert, ist der perfekte Ausgangspunkt, um Indizes zu konstruieren, die auf den Maschinen der Benutzer effizient abgefragt werden können.

#All das auf deinem Rechner

Indizes zur Beschleunigung der Suche mit regulären Ausdrücken müssen irgendwo liegen. Alle Ansätze, die wir bisher gesehen haben, werden serverseitig eingesetzt, und auch die semantischen Indizes, über die wir gesprochen haben, werden auf dem Server verwaltet und abgefragt. Trotzdem gehen wir hier bewusst einen anderen Weg: Wir erstellen und durchsuchen die Indizes auf den Rechnern der Benutzer.

Es gibt mehrere Gründe, warum es sinnvoll ist, diese Indizes lokal zu halten. Erstens sind die Indizes nur ein Teil dessen, was für einen Treffer auf einen regulären Ausdruck nötig ist. Sie liefern eine eingegrenzte Teilmenge von Dokumenten, in denen die regulären Ausdrücke passen könnten, aber du musst trotzdem jede Datei einzeln durchsuchen. Das auf dem Server zu tun würde entweder bedeuten, alle Dateien zu synchronisieren, oder teure Roundtrips zwischen Client und Server zu verursachen. Auf dem Client ist das trivial und umgeht außerdem viele Sicherheits- und Datenschutzbedenken rund um die Datenspeicherung.

Auch die Latenz ist für diese Funktion extrem wichtig. Unser Composer-Modell hat einen der schnellsten Token-pro-Sekunde-Werte (TPS) der Branche, und wir arbeiten hart daran, es sowohl intelligenter als auch schneller zu machen. Netzwerk-Roundtrips zu einem so kritischen Vorgang hinzuzufügen, den das Modell ständig nutzt (oft parallel), sorgt nur für Reibung, Verzögerungen und führt uns genau in die entgegengesetzte Richtung von dem, was wir bei der Interaktion mit Agents erreichen wollen.

Anders als bei semantischen Indizes muss ein Index für die Suche mit regulären Ausdrücken außerdem sehr aktuell sein, insbesondere wenn es darum geht, dass das Modell seine eigenen Schreibvorgänge wieder einliest. Wir müssen unseren semantischen Index nicht fortlaufend aktualisieren, weil das Neuberechnen der Embeddings für eine Datei nach einer Änderung nicht dazu führt, dass sich das neue Embedding im mehrdimensionalen Raum stark verschiebt. Die von uns verwendete Nearest-Neighbor-Suche wird den Agent trotzdem in die richtige Richtung lenken. Wenn der Agent jedoch nach einem bestimmten Text sucht und ihn nicht findet, gerät er oft auf eine falsche Fährte, verschwendet Tokens und macht damit den Zweck unserer Leistungsoptimierung von vornherein zunichte.

Diese Indizes auf den Client zu verlagern, bringt allerdings eigene Herausforderungen mit sich. Das Synchronisieren von Daten auf dem Datenträger kann komplex und aufwendig sein, aber wir machen es in der Praxis sehr effizient: Wir steuern den Zustand des Index, indem wir ihn auf einen Commit im zugrunde liegenden Git-Repository stützen. Änderungen von Benutzern und Agents werden als zusätzliche Schicht darüber gespeichert. Dadurch lässt sich der Index sehr schnell aktualisieren und beim Start sehr schnell laden und synchronisieren.

Damit die Speichernutzung im Editor minimal bleibt, speichern wir unsere Indizes in zwei separaten Dateien. Die erste Datei enthält alle Posting-Listen des Index, eine nach der anderen — wir schreiben sie während der Erstellung direkt auf den Datenträger. Die andere Datei enthält eine sortierte Tabelle mit den Hashes aller n-Gramme und dem Offset ihrer jeweiligen Posting-Liste in der Postings-Datei. Dass wir hier Hashes speichern, ohne die vollständigen n-Gramme abzulegen, ist unproblematisch: Wenn zwei Hashes kollidieren, kann eine Posting-Liste dadurch allgemeiner werden (in der Praxis extrem unwahrscheinlich), aber es kann keine falschen Ergebnisse geben. Außerdem erhalten wir so ein sehr kompaktes Layout für die Lookup-Tabelle. Anschließend mmapen wir diese Tabelle, und nur diese Tabelle, im Editor-Prozess und nutzen sie, um Abfragen per binärer Suche zu bedienen. Die Suche gibt einen Offset zurück, und wir lesen in der Postings-Datei direkt an diesem Offset.

#Fazit

Wir haben festgestellt, dass die Bereitstellung von Textsuchindizes für schnelle Modelle, wie unser eigenes Composer 2, einen qualitativen Unterschied für agentenbasierte Workflows schafft. In größeren Enterprise-Repositories ist dieser Effekt deutlich stärker ausgeprägt, denn grep ist eine der wenigen Agent-Operationen, deren Latenz mit der Größe und Komplexität des bearbeiteten Codes skaliert. Schau dir diese Beispiel-Workflows mit Composer 2 an: Wenn die Zeit für die Suche in der Codebasis komplett entfällt, spart das spürbar Zeit — insbesondere dann, wenn der Agent Bugs untersucht — und ermöglicht eine deutlich effektivere Iteration.

Und was kommt als Nächstes? Wer weiß! Rund um die Bereitstellung von Kontext für Agenten gibt es viele spannende Entwicklungen, und viele Forschende arbeiten in diesem Bereich — auch bei uns. Wir werden die Performance aktueller Ansätze weiter optimieren, darunter semantische Indizes, und wir hoffen, schon bald völlig neue Wege zu erschließen, um die Performance von Agenten noch weiter zu verbessern, und dabei stets sicherzustellen, dass sie dort einsatzfähig sind, wo es wirklich darauf ankommt: in den größten Repositories der Welt, wo die Zukunft der agentenbasierten Entwicklung wirklich an Fahrt gewinnt.