Fragen? Antworten! Siehe auch: Alternativlos
Eines meiner Projekte ist eine Suchmaschine für Code. Damit indiziere ich dann den Quellcode bei Kundenprojekten, damit ich schnell darin herumnavigieren kann. Für kleinere Codebasen lohnt sich das nicht, da macht man lieber grep -r und hat die Quellen in einer Ramdisk. Aber bei manchen Kunden ist der Quellcode im höheren zweistelligen Gigabytebereich. Da braucht man dann schon einen Index.
Wenn ich in meinem Index jetzt nach einem Wort sucht, und im Allgemeinfall ist das ein Bezeichner aus dem Quellcode, d.h. ein längeres Wort, dann sagt mir mein Index die Namen der Dateien, in denen das Wort vorkommt. Aber ich will ja nicht nur wissen, in welchen Dateien es ist, sondern auch die Zeilennummer, damit ich da schön hinnavigieren kann.
Mein Code muss daher die Datei öffnen und darin nach dem Wort suchen und mir dann die Trefferzeilen mit Zeilennummer ausgeben. Wenn ich die Zeilennummer ausgeben will, kann ich aber nicht Boyer-Moore verwenden und dann Zeichen in der Mitte überspringen. Daher wird die Suche langsamer.
Das war der Grund, wieso ich gestern mal mit der Frage verbracht habe, wie man möglichst schnell die Newlines in einem Speicherblock zählen kann. Wenn es nämlich gelingt, die Newlines in einem Speicherblock effizienter als durch zeichenweises Lesen zu zählen, dann ist es möglicherweise effizienter, erst mit Boyer Moore nach dem Match zu suchen und dann im Speicher davor nochmal die Newlines zu zählen.
Damit das klappt, müsste man deutlich effizienter zählen. Um zu verstehen, wie man effizienter sein kann, als jedes Byte einmal kurz anzugucken, muss man die Speicherhierarchie in CPUs verstehen. Die CPUs sind heutzutage rasend schnell, aber der Speicher ist vergleichsweise langsam. CPUs haben mehrere Hierarchien von Zwischenspeichern, aber selbst die sind noch langsam. Wenn man ein Byte aus dem schnellsten (und kleinsten) Cache liest, dem Level 1-Cache, dann hat man immer noch pro Zugriff eine Straflatenz zu erdulden, bis der Wert vorliegt. Auf meinem etwas älteren AMD-Desktop war es ein Taktzyklus, bei einem modernen i7 ist es offenbar eher 2 oder 3. Wie sich rausstellt ist diese Latenz aber nicht pro Byte sondern pro Zugriff. Wenn man also mehr als ein Byte auf einmal liest, dann zahlt man diese Strafsteuer nur einmal. Auf einer 64-bit-Architektur passen in ein Maschinen-Register 8 Bytes rein. Die Kosten für Newlinezählen wären damit also potentiell ein Achtel dessen, was man für die naive Implementation zahlt. Zum Vergleich:
size_t byfoot(const char* s,size_t l) {Das ist die naive Implementation. Die braucht für eine 5k-Datei ca. 15000 CPU-Zyklen auf einem 4000er i7.
size_t i,r;
for (i=r=0; i<l; ++i)
if (s[i]==n) ++r;
return r;
}
Der erste Verbesserungsansatz wäre, dass man wortweise liest und dann innerhalb des Wortes die Bytes einzeln rausmaskiert zum Vergleichen.
size_t byfoot2(const char* s,size_t l) { size_t i,r; for (i=r=0; i+sizeof(i)<=l; i+=sizeof(i)) { size_t x=*(size_t*)(s+i); while (x) { r += ((x&0xff) == 0x0a); x >>= 8; } } for (; i<l; ++i) if (s[i]==n) ++r; return r; }Hier haben wir pro Byte deutlich mehr Operationen, aber die laufen alle innerhalb der CPU asynchron ab, und es bleibt noch Zeit übrig, um auf den Speicher zu warten. Hiermit bin ich schon runter auf 11800 CPU-Zyklen.
Wenn man noch mehr Performance will, muss man tricksen. Die beste Variante, die ich dafür gestern gefunden habe, ist die hier:
static size_t fold(size_t v) { return (v * (size_t)0x0101010101010101) >> (sizeof(v)*8-8); } static size_t nlto1(size_t v) { v ^= (size_t)0x0a0a0a0a0a0a0a0a; v |= (v & (size_t)0x0101010101010101ull) << 1; v = ((v - (size_t)0x0101010101010101ull) & ~v & (size_t)0x8080808080808080ull); return v >> 7; } size_t newlines(const char* s,size_t l) { size_t i,n=0,r=0,max=l/sizeof(n); size_t* S=(size_t*)s; int o=255; for (i=0; i<max; ++i) { n += nlto1(S[i]); if (!--o) { r += fold(n); n=0; o=255; } } r += fold(n); if (l %= sizeof(i)) { s += i*sizeof(n); for (; l; --l) r += (*s++=='\n'); } return r; }Ich habe mal die Kommentare entfernt, weil ich mir dachte, dass vielleicht der eine oder andere von euch Spaß daran haben könnte, zu verstehen, wie das funktioniert, und warum jeder einzelne Schritt davon da ist und nötig ist. Mit diesem Code bin ich für die selben Daten schon runter auf 5200 Zyklen. Nicht schlecht! Geht aber noch besser. Moderne CPUs haben Vektorinstruktionen für sowas, und mit SSE komme ich auf 2500 Zyklen. Ich vermute, dass auch damit noch nicht das Ende der Fahnenstange erreicht ist.
Wenn jemand eine klarere oder schnellere Variante des portablen Codestücks findet, bitte ich um eine Email mit den Details!
Die mir wichtige Lektion an der Stelle ist jedenfalls, dass Performance auf heutigen CPUs fast ausschließlich eine Frage von "wieviel Speicherzugriffe habe ich" ist. Unter dem Gesichtspunkt muss man auch Datenstrukturen bewerten.
Update: Oh, einer noch. Das da oben ist im 64-bit-Modus. Im 32-bit-Modus lohnt sich das Bitgefrickel nur wenig bis gar nicht, da ist in meinem Messungen die zweite Variante von oben sogar geringfügig schneller als die dritte. Dafür braucht spannenderweise der selbe SSE-Code nur noch 1800 Zyklen. Keine Ahnung, wie das kommt.
Es gibt übrigens auch noch eine Bitfrickel-Variante von fold:
static size_t fold(size_t v) {
v=(v & (size_t)0x00ff00ff00ff00ff) + ((v>>8) & (size_t)0x00ff00ff00ff00ff);
v=(v & (size_t)0x0000ffff0000ffff) + ((v>>16) & (size_t)0x0000ffff0000ffff);
if (sizeof(v)>4)
v = (v & 0xffffffff) + (v>>32);
return v;
}
Die ist aber geringfügig langsamer bei mir. Das hängt von der Performance der Integer-Multiplikationseinheit ab. Auf anderen CPUs ist möglicherweise das Bitfrickeln schneller.
Update: Wie das erste Adlerauge (Glückwunsch!) schon gemerkt hat, hat die Nicht-Bitfrickel-Fold-Funktion ein Overflow-Problem, wenn zu viele Newlines auf einmal reinkommen. Das ist leider nicht so einfach zu fixen. Ich verwendet daher gerade die Bitfrickel-Funktion, auch wenn das in der Praxis so gut wie nicht vorkommt in Code. Ich wollte euch den Fold-Code trotzdem nicht vorenthalten, weil er so schön bewusstseinserweiternd ist.