Fragen? Antworten! Siehe auch: Alternativlos
Heute zeige ich euch mal, wie sich ein Hacker einen perfekten Sonntagnachmittag vorstellt. Der erdgeist und ich, wir haben uns im Chat hingesetzt und wollten diesen Code hier optimieren:
for (i=0; i+1<l; ++i) {Der Code kommt aus gatling und soll feststellen, ob die bisher reingekommenen Daten schon einen fertigen HTTP-Header ergeben. erdgeist interessiert sich dafür, weil er den Opentracker hackt, der ja eh schon der mit Abstand schnellste Torrent-Tracker ist, und jetzt soll der eben auch Keep-Alive kriegen, und dafür muss er dann auch mal die Header richtig parsen. Nun ist das aus praktischen Erwägungen heraus nicht sonderlich sinnvoll, an so einer Stelle die letzten Taktzyklen heraus zu optimieren, weil der Bulk der Last eh im TCP Stack anfällt. gatling und opentracker sind I/O-bound, nicht CPU-bound. Aber hey, als zwei alte Bitfrickler haben wir uns mal hingesetzt und das optimiert.
if (c[i]=='\n' && c[i+1]=='\n')
return i+2;
if (i+3<l &&
c[i]=='\r' && c[i+1]=='\n' &&
c[i+2]=='\r' && c[i+3]=='\n')
return i+4;
}
Der offensichtliche Ansatz ist an der Stelle, dass man die Speicherzugriffe reduzieren will. Die überwiegende Mehrheit an Daten wird zwar weder CR noch LF sein, und insofern wird es auch im Normalfall nicht vorkommen, dass der alte Code zu viele unnötige Speicherzugriffe macht, aber hey, es ist Sonntag, da muss man nicht rational entscheiden. Das generelle Problem heißt String Matching und ist in der Informatik an sich gut untersucht. Das Buch der Wahl dazu habe ich vor ein paar Jahren gelesen und finde es gerade nicht wieder. Es ist jedenfalls von diesem Chilenen hier, nur sah bei meinem das Cover gelb aus. Egal. Es gibt mehrere schöne Verfahren, um einen bestimmten String schnell zu finden, aber die meisten schnelleren brauchen eine Tabelle, in der sie dann pro einkommendem Zeichen was nachgucken. Das ist zwar in der theoretischen Informatik schnell, aber in der Praxis habe ich dann sogar mehr Speicherzugriffe als ich jetzt habe. Insbesondere bei einem so kurzen Muster wie CR-LF-CR-LF. Das Verfahren, das ich einsetzen wollte, heißt Shift-Or und ist durch agrep populär gemacht worden. Auch Shift-Or braucht eine Tabelle pro Zeichen, aber dadurch dass mein Muster nur aus zwei Zeichen besteht, kann man das auch inline machen. Zur Veranschaulichung der Idee paste ich mal ein Stück Code, das ich mal für ein altes Kommerz-Projekt gehackt habe:
int detect_magic(const unsigned char c) {Kurz gesagt hat man ein Array, in dem pro Zeichen im Muster eine 0 oder 1 steht. An Position 0 steht eine 1, wenn das letzte reinkommende Zeichen das erste Zeichen im Muster ist. An Position 1 steht eine 1, wenn das letzte reinkommende Zeichen das zweite Zeichen im Muster ist und das vorige Zeichen das erste im Muster war. Pro reinkommendem Zeichen schiebt man das Array einmal durch und setzt die ausscheidenden Varianten auf 0. Das Muster ist in der Eingabe erkannt worden, wenn der letzte Eintrag im Array 1 ist. Nun ist das natürlich auch alles andere als speichereffizient, da ein Array zu verschieben pro reinkommendem Zeichen, aber wenn man sich das Verfahren mal genau anguckt, kann man auch statt eines Array einen Integer nehmen und pro Eintrag im Array ein Bit in diesem Integer. Solange das Muster höchstens so viele Zeichen wie der Integer Bits hat. Das ist dann genau das Shift-Or Verfahren, weil man pro reinkommendem Zeichen den Integer um eins shiftet und eine 1 hinten dran packt, wenn das Zeichen passt. Dann muss man jeweils mit einer von der Eingabe abhängenden Maske ANDen. In unserem Falle, wenn ein CR reinkommt, ist die Maske (1+4), weil CR in dem Muster an Position 0 und 2 vorkommt, also setzt man Bit 0 und 2 und da kommt dann eben 5 raus. Der traditionelle Shift-Or Algorithmus sieht an der Stelle wieder eine Tabelle vor, aber weil ich ja nach CR-LF-CR-LF matchen will, und da nur CR und LF vorkommen, kann ich die beiden Werte auch inline hinschreiben. Für alle Zeichen, die nicht im Muster vorkommen, ist die Maske 0, d.h. man löscht alle Bits im Integer.
#define my_magic "fnord";
static char* magic = my_magic;
static char maybe[sizeof(my_magic)];
int i;
for (i=sizeof(my_magic)-2; i>=1; --i)
maybe[i]=(maybe[i-1] && (c==magic[i]));
maybe[0] = (c==magic[0]);
return maybe[sizeof(my_magic)-2];
}
Der Code, wie ich ihn eingecheckt habe, sieht so aus:
int state=0;Euch wird auffallen, dass ich beim Newline-Fall erst 1 ORe und dann mit einem Wert ANDe, bei dem die 1 dann wieder rausfällt. Ja, stimmt, das soll so. Man könnte die 1 da jetzt rausnehmen, aber das spart keine Zyklen, also lasse ich das drinnen, damit man dem Algorithmus folgen kann.
for (i=0; i<l; ++i) {
switch (c[i]) {
case '\r':
state=((state<<1)|1)&(1+4);
break;
case '\n':
state=((state<<1)|(1+16))&(2+8+16+32);
break;
default:
state=0;
}
if (state==26 || state==48) return i+1;
So, nun wären wir keine Hacker, wenn wir uns damit zufrieden geben würden. Hier ist die Endversion:
int state;Ihr könnt ja mal gucken, ob ihr das versteht, was da vor sich geht. Wie ihr sehen könnt, shiften wir jetzt nicht mehr einen nach links sondern zwei nach rechts. Hach, ich liebe C! :-)
for (i=state=0; i<l; ++i)
if ((state = (c[i]=='\r' || c[i]=='\n') ?
(state >> 2) | (( c[i] << 6) & 0xc0 ) : 0) >= 0xa0 ||
state == 0x99)
return i+1;
Abgesehen davon: wenn ihr Rotwein mögt, probiert doch mal einen Refosco. Ich habe gestern einen 2003er Refosco bei meinem lokalen Weinhändler gekauft, und das war einer der besten Rotweine, die ich je hatte. Die Rebenart kennt keine Sau, die Flasche kostete nur knapp 7 Euro. Den Wein muss man in einen Dekanter tun und eine halbe Stunde atmen lassen. Dann zieht er einem die Schuhe aus. Oh und falls ihr Rum mögt: den Diplomatico aus Venezuela kann ich wärmstens empfehlen. Wenn der Andreas seinen Rausch ausgeschlafen hat, wird er euch das sicher bestätigen.
Update: Der eine oder andere Spezialist auf dem Gebiet wird jetzt einwenden wollen, dass wir besser einen Boyer-Moore benutzen sollen. Stimmt, ist auch trotz des kurzen Musters schneller. Aber ergibt keinen so schön eindrucksvollen Blogpost.