Fragen? Antworten! Siehe auch: Alternativlos
Update: Graz, nicht Wien.
Update: Ich hoffe ja insgeheim auf den Twist, dass die offiziell einen Lizenzdeal mit Facebook haben. Facebook lässt sich im Kleingedruckten ja kommerzielle Verwertungsrechte einräumen.
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) {
size_t i,r;
for (i=r=0; i<l; ++i)
if (s[i]==n) ++r;
return r;
}Das ist die naive Implementation. Die braucht für eine 5k-Datei ca. 15000 CPU-Zyklen auf einem 4000er i7.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.
Die Telematikinfrastruktur soll demnach »für weitere Anwendungen im Gesundheitswesen und für weitere Leistungserbringer« geöffnet werden. Damit setzen Lobbyisten der IT-Industrie eines ihrer zentralen Anliegen durch. Bleibt dieser Punkt im Gesetz, könnten künftig private Firmen wie Apple mit den Produkten iHealth oder Apple Watch Patientendaten nutzen, um damit Profite zu machen.Ja super! (Danke, Dirk)
Die schlechte Nachricht: Komasaufen gerät aus der Mode – aus Angst vor Crystal Meth. (Danke, Simon)
Bei einer Unterbringung von Wohnungslosen und Flüchtlingen in der vorgesehenen Weise handele es sich zudem nicht um eine Wohnnutzung im engeren Sinne, befanden die Richter. Dazu fehle es an der auf Dauer angelegten Häuslichkeit und an der Freiwilligkeit des Aufenthalts. Eine Wohnnutzung setze ferner ein Mindestmaß an Intimität voraus.m(
So müssten zum Beispiel Gesetze für neue Umweltstandards in NRW darauf überprüft werden, welche Kosten für die Industrie entstehen.Ja wo kämen wir da auch hin, wenn der erhalt einer menschliches Leben ermöglichenden Umwelt Priorität vor den Interessen der Industriebosse hätte!1!! (Danke, Sarah)
Zur digitalen Welt gehöre auch, dass es keine geheimen Winkel in der Welt gebe. „Wir wollen versuchen, nicht immer zuerst über die Risiken zu sprechen.“Noch nicht zynisch genug? Im Text steht dieser Satz davor:
Zu der Forderung nach Transparenz sagte die Kanzlerin, sie begrüße diese.Prost! (Danke, Stefan)
In zwei kürzlich ergangenen Urteilen hat der EuGH entschieden, dass Umweltverbände nur unter engen Voraussetzungen gegen EU-Institutionen klagen dürfen.Die Schranken für Klage gegen Mitgliedstaaten sind deutlich niedriger. (Danke, Frank)
Wir reden hier vom Kampf um die letzten stehenden Trümmer unserer Demokratie, soviel sollte aber allen klar sein an der Stelle.
Update: Money Quote aus dem Text:
Aus den Ermittlungsakten ergibt sich, dass von Edathys Laptop am 1. November 2013 ein Programm zum Entpacken von Dateien heruntergeladen wurde. Ein solches Programm ist gewöhnlich nur bei großen Datenmengen erforderlich, die etwa durch Videodateien anfallen.Hat hier jemand unzip auf der Platte? Das begründet offensichtlich heutzutage schon einen Anfangsverdacht. Weia.
Die schlechte Nachricht: Gegen die Türkei. Die Amis, Briten, Kanadier, Neuseeländer und Australier dürfen weiter ungestört alles abschnorcheln.
Update: Das sind keine 1700 Jets sondern 1700 Flüge, wobei Flüge mit Zwischenlandungen als mehrere Flüge zählen.
