Faster Than Grep

Es war wie ein langweiliger Tag suchen. Ich habe in spät, fast 11 (BAD, ich arbeiten in der Regel von 10.30 bis 18.30 Uhr) und um 11:30 hatten alle die tägliche Wartung Zeug genagelt und wurde bei einer Reihe von festgefahrenen suchen und warten-für-andere-Jungs Arbeitsplätze. Und ein paar epische Arbeitsplätze, die nicht wirklich sein könnte gefördert heute. Dann wird die ops-Manager kam auf mich zu ...

"Was ist schneller als grep?"

Wenn Sie nicht ein Aussenseiter sind, ist grep ein wirklich vielseitiges und sehr schnell, was Sie suchen Textdateien mit. Wenn jemand wichtige will etwas schneller als grep, sind sie entweder in einer unheiligen Eile, oder haben eine Wagenladung von Daten.

Oder schlimmsten Fall, wie dieser Fall beides.

Vierundvierzig Gig von Daten alles in allem, ein 180k Liste von rund 13.000 Datensätze zu ziehen. Variabler Länge Textdaten, ein Worst-Case-Szenario. Und wir brauchen die Informationen bis morgen früh extrahiert. Oh, und Sie müssen zwei verschiedene Felder übereinstimmen.

Great.

Die gute Nachricht? Das erste Feld hat eine Menge von Duplikaten. Es ist 13.000 Datensätze, aber nur 220 einmalig in das erste Feld. Ich kennzeichnen, dass als "interessant".

Das Problem mit einer Schleife grep ist, Sie drehen die Big Wheel schnell und das kleine Rad langsam. Du durchstöberst 44gig von Daten 13.000 mal Radfahren. Nichts wird im RAM (dies ist 2006, und ich habe noch nicht eine Kiste mit 64 GB RAM Darnit .. Ich steckte ein in bei meinem letzten Job mit 32 though). So komme ich es aus der anderen Richtung. Eine wiederholte grep Befehl wurde buchstäblich Tag (es wurde versucht, bevor sie mir reichte das Problem)

Ich habe etwas schneller als grep vorher geschrieben. Aber ich betrogen dann und indexiert die Daten mit etwas namens CDB, die die schnellste Datenbank-System, das ich je gesehen habe (schauen Sie, es ist wirklich annihilative) ist. Aber heute hatte ich keine Zeit zu indizieren nichts ..... ein Pass war zu haben, um genug sein. Woher ich das tun?

Ich schrieb es in C kein Scherz, dass Datenvolumen brauche ich die schnellste _performing_ Tool, das ich finden kann, oder es wird Wochen dauern. Kompilieren mit-O3! PHP würde viel weniger Zeit, um Code zu nehmen, spart eine Stunde oder zwei sogar, aber Tage dauern, mehr zu laufen.

Das erste, was ich tat, war laden die 13.000 Sätze von zwei Felder in einem Array. Dies bedeutete, dass die Daten den Großteil der Arbeit im RAM steckte, und wir hatten nur um durch die 44DE von Junk einmal. Dies ist eine gute Sache.

Viele Bugs folgte. Die übliche C stuff ... Sie hacken etwas zusammen und es Segfaults die ersten 100 Male Sie laufen lassen, während Sie rund setzen print-Anweisungen überall versuchen, herauszufinden, wo das Feuer ist toll laufen. Unterdessen tickt die Uhr und mein Chef Chef neben mir sitzt oder Stimulation in seinem Büro suchen besorgt. Tick ​​Tock.

Ich bekomme das Ding funktioniert, und verschieben Sie es über den HPUX-Box, die alle Daten auf sich hat. Ich hatte noch nicht einmal vim auf diesem Feld, so dass ich kodiert es zunächst auf meinem Linux-Desktop. Ich beginne es dort auf einer kleinen Stichprobe der Daten, die auf meinem Desktop gearbeitet hatte.

Er stürzt. Und stürzt ab. Und stürzt ab. Ich laufe in Fehler nach Fehler in den schrecklichen HP Bibliotheken. sscanf nicht funktioniert alles wie es funktioniert unter der GNU libc. Ich bin bereit, über die Daten zu verschieben off auf eine schwere Linux-Server, wenn mein Boss (nicht mein Boss Boss) erwähnt, dass er die GNU-Compiler und Bibliotheken ist auf der hpux Maschine installiert. Sweet! Kompiliert zuerst gehen, läuft erst jetzt gehen.

Außer es ist zu langsam.

"Was cpu ist in dieser Sache der Mensch?"

"Uhhh Ich denke, es ist 4x 360MHz"

"$% #%!"

Ich beginne die Übertragung der Daten auf den genannten schweren Linux-Server. Es hat etwa 10 mal die Prozessor-Leistung. Ich habe eine kurze Diskussion mit IP Engineering Über lasse mich durch die Firewall NOW PLZ. Dann beginnt es ..... 5MB a sec anyone? Dies ist die Art von Dingen, ich erwähne es sinnvoll sein, auf Gigabit-Ethernet für ein Upgrade wäre. Tick ​​Tock.

Stunden später .... Die Stunden sind gut in einer Weise, sie geben mir Zeit, um ein wenig andere Arbeit zu erledigen und darüber nachdenken, wie man meinen hacked-together Programm schneller gehen.

Die erste Sache ist, ich merke, Schmatzen mir in den Kopf, dass ich passende Sachen und dann weiter den Rest der 13.000 vergleichen wollte Datensätze der Linie, nachdem sie abgestimmt ist! Ich dieses Problem beheben, und dann erinnere ich mich das "interessant", was von früher.

220 eindeutige Datensätze im ersten Feld nur. Ich schreibe eine Schleife (ich hasse C, würde dies eine weitere one-liner in php sein:.. (), Um diese zu finden und sie in einem Array ich dieses Array "screen" jeden Datensatz vor dem Scannen es Wenn das erste Feld isn 't in der 220, ist die Leitung nicht an den 13.000 im Vergleich zu bekommen - wir lassen es aus und ziehen weiter.

Diese tatsächlich verlangsamt meinen Sample-Daten merklich. Aber ich weiß, dass meine Sample-Daten eine ungewöhnlich hohe Anzahl von Spielen hat - ich meine, mein Programm ist nur tun, eine zusätzliche 220-Vergleiche in jeder Zeile für diese Daten, während der Großteil der REAL Daten werden schnell vorbei durch diesen Code übersprungen werden. Wie teste ich diese Theorie? Ich bin in der Lage, das Programm auf die unvollständige Datei, wie sie Downloads laufen. Versuchen Sie nicht, diese auf Windows :) ich immer, was aussieht wie gute Ergebnisse werde. Es ist schnell, und es ist immer die Daten.

Ich laufe von Stunden. Die erste Hälfte der Daten (froh, dass es in zwei separaten Dateien jetzt!) Ist fertig heruntergeladen und ich bekomme auf es für real zu arbeiten. Sieht gut aus ... es passende Sachen, und der Zähler I im Programm, die eine Zeile gedruckt wird, wenn es um eine Million bekommt bekommen habe ist Clipping ziemlich schnell. Die tote Punkte in den Daten ohne Datensätze in der 220-Liste fliegen vorbei, und ich schätze, es wird nur 90 Minuten dauern, bis die erste Datei zu erhalten! 285 Millionen Datensätze in 90 Minuten nur für mich in Ordnung.

Wir werden gewinnen.

Der Rest ist einfach. Ein paar Stunden später, endet die zweite Datei herunterladen. Ich fange sie auf und gehen nach Hause. Es ist von der Zeit, die ich dorthin und VPN in. Süße getan. Home von 9.00, und die Arbeit getan!

Heute erinnerte mich, warum ich meinen Job liebe....