Cursor-Trigramm-Indizes für schnelle Regex-Suche

Cursors lokale Trigramm-Indizes beschleunigen Regex-Suche in großen Repositories

Cursor hat lokale Indizes für die Regex-Suche direkt in der IDE implementiert. Das löst das Problem langsamer Scans in großen Monorepos, wo klassische ripgrep-Aufrufe 15+ Sekunden dauern und der AI-Agent Dutzende solcher Abfragen erzeugt.

Die Technologie basiert auf dem Trigramm-Inverted-Index aus dem Jahr 1993. Der Text wird in alle 3-Zeichen-Sequenzen (Trigramme) zerlegt, die als Schlüssel in einem Dictionary dienen. Jeder Schlüssel entspricht einer Liste von Dateien, die diese Sequenz enthalten. Die Regex-Abfrage wird in eine Menge von Trigrammen zerlegt, Posting-Listen werden intersectiert, um Kandidaten auszuwählen. Dann wird grep nur auf ein Dutzend Dateien statt Tausender angewendet.

Sparse n-Gramme für präzise Abgrenzung

Aufbauend auf dem Basis-Index werden sparse n-Gramme hinzugefügt. Die Länge jedes n-Grams wird deterministisch berechnet: unter Verwendung von Gewichten für Zeichenpaare basierend auf crc32 oder einer Häufigkeitstabelle, die aus Terabytes Open-Source-Code erstellt wurde.

Während der Indizierung werden alle möglichen n-Gramme erzeugt; bei der Suche ein minimales Überdeckungs-Set. Das reduziert die Anzahl der Lookups und verbessert die Filtergenauigkeit.

// Example dekompozitsii regex in n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...]  // sparse pokryodkrycie
candidates = intersect(postings(ngrams))

Lokaler Speicher und Commit-Bindung

Der Index wird lokal auf dem Benutzergerät in zwei mmap-Dateien gespeichert. Gründe:

• Der AI-Agent liest Dateien ohnehin lokal für die finale Verifikation.
• Netzwerk-Roundtrips zerstören den Geschwindigkeitsvorteil.

Der Index ist an einen spezifischen git-Commit gebunden. Uncommittete Änderungen werden darüber gelegt, ohne Neubau.

• mmap-Vorteile: null Overhead beim Laden, schnelle Navigation durch Posting-Listen.
• Update: ausgelöst durch git pull/push oder manuellen Rebuild.
• Größe: proportional zum Codebase; für 10M LoC — ~500MB.

Leistungsvergleich

| Ansatz | Zeit pro Abfrage (10k Dateien) | Kandidaten für grep |

|--------------|-------------------------------|---------------------|

| ripgrep | 15–20 sec | 10k |

| Cursor index | 50–200 ms | 10–50 |

In realen Szenarien mit 100+ Abfragen vom Agenten erreicht die Gesamtbeschleunigung 100-fach.

Trigramme gewährleisten Vollständigkeit (Recall=1 für exakte Substrings), während sparse n-Gramme Präzision hinzufügen, ohne False Positives.

Wichtige Punkte

• Trigramm-Index reduziert Kandidaten von Tausenden auf Dutzende Dateien.
• Sparse n-Gramme minimieren Lookups durch minimales Überdeckungs-Set.
• Lokaler mmap-Speicher eliminiert Netzwerkverzögerungen.
• Bindung an git-Commit mit Overlay uncommitteter Änderungen.
• 100-fache Beschleunigung für Regex-Suche von AI-Agenten in großen Monorepos.

— Editorial Team