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.
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
- Der schnellste Verarbeitungsschritt ist häufig jener, den ein Algorithmus beweisbar überspringt.
- Performance entsteht aus Algorithmus, Datenlayout und Betriebssystemschnittstelle gemeinsam.
Fakten
- Der Originalbeitrag wurde am 23. August 2010 auf HN aufgegriffen.
- Die Auswahl vertritt den Monat 08/2010.
- Der verlinkte Originalbeitrag ist weiterhin unmittelbar erreichbar.
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
Der Link zur Originalquelle öffnet einen neuen Tab.