Warum GNU grep so schnell ist
Zusammenfassung
Mike Haertel erklärt, wie GNU grep Sucharbeit reduziert, Eingaben effizient liest und nur jene Bytes untersucht, die das Ergebnis beeinflussen können. Der schnellste Verarbeitungsschritt ist häufig jener, den ein Algorithmus beweisbar überspringt.
Ideen
- Boyer-Moore-artige Suche überspringt große Bereiche, wenn ein fester Teil des Musters fehlt.
- Große gepufferte Leseoperationen vermeiden unnötige Systemaufrufe und Datenkopien.
- Die Implementierung untersucht Zeilenenden nur dort, wo ein möglicher Treffer liegt.
Einsichten
- Performance entsteht aus Algorithmus, Datenlayout und Betriebssystemschnittstelle gemeinsam.
Empfehlungen
- Miss Suchwerkzeuge mit realen Mustern, Dateigrößen und Cachezuständen.
- Vergleiche Algorithmen anhand der Arbeit, die sie vermeiden, nicht nur ihrer inneren Schleife.
Referenzen
Links zur Originalquelle und zum Webarchiv öffnen einen neuen Tab.