Life Hack: Wie man ein Gigabyte Double pro Sekunde analysiert

Wie lese ich einen doppelten Wert aus einer Zeichenfolge in C ++ - Code?

std::stringstream in(mystring);
while(in >> x) {
   sum += x;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Unter Intel Skylake mit GCC 8.3-Compiler analysiert dieser Code 50 MB / s. Festplatten können problemlos sequentielle Lesevorgänge mit einer Geschwindigkeit von mehreren GB / s bereitstellen. Es besteht also kein Zweifel daran, dass nicht die Lesegeschwindigkeit von der Festplatte uns einschränkt, sondern die Geschwindigkeit des Parsens. Wie kann ich es beschleunigen?



Das erste, was sich anbietet, ist, auf die Bequemlichkeit von Streams in C ++ zu verzichten und strtod (3) direkt aufzurufen:

do {
    number = strtod(s, &end);
    if(end == s) break;
    sum += number;
    s = end; 
} while (s < theend);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Die Geschwindigkeit steigt auf 90 MB / s; Die Profilerstellung zeigt, dass beim Lesen aus dem Stream ~ 1600 Anweisungen für jede gelesene Nummer ausgeführt werden, wenn strtod - ~ 1100 Anweisungen pro Nummer verwendet werden. Die C- und C ++ - Standardbibliotheken können durch die Anforderungen an Universalität und Portabilität gerechtfertigt werden. Wenn wir uns jedoch darauf beschränken, nur doppelt und nur auf x64 zu analysieren, können wir viel effizienteren Code schreiben: 280 Anweisungen pro Nummer reichen aus.

Ganzzahlen analysieren

Beginnen wir mit einer Unteraufgabe: Bei einer achtstelligen Dezimalzahl müssen wir sie in int konvertieren. In der Schule wurde uns allen beigebracht, dies in einem Zyklus zu tun:

int sum = 0;
for (int i = 0; i <= 7; i++)
{
	sum = (sum * 10) + (num[i] - '0');
}
return sum;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kompiliertes GCC 9.3.1 -O3, für mich verarbeitet dieser Code 3 GB / s. Der naheliegende Weg, um es zu beschleunigen, besteht darin, die Schleife umzukehren. aber der Compiler macht es selbst.



Beachten Sie, dass die Dezimalschreibweise einer achtstelligen Zahl in die Variable int64_t passt: Beispielsweise wird die Zeichenfolge „87654321“ auf dieselbe Weise wie der int64_t-Wert 0x3132333435363738 gespeichert (das erste Byte enthält die niedrigstwertigen 8 Bits, das letzte - die wichtigsten). Dies bedeutet, dass wir anstelle von acht Speicherzugriffen den Wert jeder Ziffer mit einer Verschiebung zuweisen können:

int64_t sum = *(int64_t*)num;
return (sum      & 15) * 10000000 +
    ((sum >> 8)  & 15) * 1000000 +
    ((sum >> 16) & 15) * 100000 +
    ((sum >> 24) & 15) * 10000 +
    ((sum >> 32) & 15) * 1000 +
    ((sum >> 40) & 15) * 100 +
    ((sum >> 48) & 15) * 10 +
    ((sum >> 56) & 15);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Es gibt noch keine Beschleunigung; im Gegenteil, die Geschwindigkeit sinkt auf 1,7 GB / s! Gehen wir weiter: UND mit der Maske 0x000F000F000F000F erhalten wir 0x0002000400060008 - Dezimalstellen in geraden Positionen. Kombinieren wir jeden von ihnen mit den folgenden:

sum = ((sum & 0x000F000F000F000F) * 10) + 
      ((sum & 0x0F000F000F000F00) >> 8);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Danach wird aus 0x3132333435363738 0x00 (12) 00 (34) 00 (56) 00 (78) - Bytes an geraden Positionen werden auf Null gesetzt, an ungeraden - sie enthalten binäre Darstellungen von zweistelligen Dezimalzahlen.

return (sum        & 255) * 1000000 +
      ((sum >> 16) & 255) * 10000 +
      ((sum >> 32) & 255) * 100 +
      ((sum >> 48) & 255);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- schließt die Konvertierung einer achtstelligen Zahl ab.



Der gleiche Trick kann mit zweistelligen Zahlenpaaren wiederholt werden:

sum = ((sum & 0x0000007F0000007F) * 100) +
      ((sum >> 16) & 0x0000007F0000007F);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 0x00 (12) 00 (34) 00 (56) 00 (78) wird 0x0000 (1234) 0000 (5678);

und mit dem resultierenden vierstelligen Paar:

return ((sum & 0x3FFF) * 10000) + ((sum >> 32) & 0x3FFF);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 0x00 (12) 00 (34) 00 (56) 00 (78) wird 0x00000000 (12345678). Die geringere Hälfte des resultierenden int64_t ist das gewünschte Ergebnis. Trotz der spürbaren Vereinfachung des Codes (drei Multiplikationen statt sieben) bleibt die Parsing-Geschwindigkeit (2,6 GB / s) schlechter als die der naiven Implementierung.



Das Kombinieren von Zahlenpaaren kann jedoch vereinfacht werden, selbst wenn Sie feststellen, dass die folgende Aktion die Maske 0x007F007F007F007F anwendet. Dies bedeutet, dass jeglicher Müll in den nullbaren Bytes verbleiben kann:

sum = ((sum & 0x0?0F0?0F0?0F0?0F) * 10) + ((sum & 0x0F??0F??0F??0F??) >> 8) =
   = (((sum & 0x0F0F0F0F0F0F0F0F) * 2560)+ (sum & 0x0F0F0F0F0F0F0F0F)) >> 8 =
    = ((sum & 0x0F0F0F0F0F0F0F0F) * 2561) >> 8;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Vereinfacht ausgedrückt, eine Maske statt zwei, und es gibt keine Addition. Die beiden verbleibenden Ausdrücke werden auf dieselbe Weise vereinfacht:

sum = ((sum & 0x00FF00FF00FF00FF) * 6553601) >> 16;
return((sum & 0x0000FFFF0000FFFF) * 42949672960001) >> 32;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dieser Trick wird als SIMD innerhalb eines Registers (SWAR) bezeichnet: Mit ihm wird die Parsing-Geschwindigkeit auf 3,6 GB / s erhöht.



Ein ähnlicher SWAR-Trick kann verwendet werden, um zu überprüfen, ob eine achtstellige Zeichenfolge eine achtstellige Dezimalzahl ist:

return ((val & 0xF0F0F0F0F0F0F0F0) |
      (((val + 0x0606060606060606) & 0xF0F0F0F0F0F0F0F0) >> 4))
            == 0x3333333333333333;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Doppelgerät

Der IEEE-Standard hat der Mantisse 52 Bit und dem Exponenten innerhalb dieser Zahlen 11 Bit zugewiesen. Dies bedeutet, dass die Nummer als gespeichert wird $$$\pm1.m\cdot2^e$ , wobei $$$0\le m<2^{52}<10^{16}$ und $$$-1022\le e\le+1023$ . Dies bedeutet insbesondere, dass in der Dezimalschreibweise von double nur die höchstwertigen 17 Stellen von Bedeutung sind; Die niedrigstwertigen Bits können den Doppelwert in keiner Weise beeinflussen. Selbst 17 signifikante Stellen sind viel mehr als für eine praktische Anwendung erforderlich: Denormalisierte Zahlen erschweren die Arbeit ein wenig (von







$$$2^{-1074}$ bis $$$2^{-1022}$ mit einer entsprechend geringeren Anzahl signifikanter Bits in der Mantisse) und Rundungsanforderungen (jede Dezimalzahl muss durch die nächste Binärdatei dargestellt werden, und wenn die Zahl genau in der Mitte zwischen der nächsten Binärdatei liegt, wird die gerade Mantisse bevorzugt ). All dies stellt sicher, dass, wenn Computer A die Zahl X in eine Dezimalzeichenfolge mit 17 signifikanten Ziffern konvertiert, jeder Computer B, der diese Zeichenfolge liest, Bit für Bit dieselbe Nummer X erhält - unabhängig davon, ob A und B gleich sind. Prozessormodelle, Betriebssysteme und Programmiersprachen. (Stellen Sie sich vor, wie viel Spaß es machen würde, Ihren Code zu debuggen, wenn die Rundungsfehler auf verschiedenen Computern unterschiedlich wären.) Aufgrund der Rundungsanforderungen treten diekürzlich erwähntenMissverständnisse auf. auf Habré: Der Dezimalbruch 0,1 wird als der ihm am nächsten liegende binäre Bruch dargestellt $$$7205759403792794\cdot2^{-56}$ , was genau 0,1000000000000000055511151231257827021181583404541015625 entspricht; 0,2 - in der Form $$$7205759403792794\cdot2^{-55}$ , was genau 0,200000000000000011102230246251565404236316680908203125 entspricht; aber ihre Summe ist kein binärer Bruchteil, der 0,3 am nächsten kommt: Annäherung von unten $$$5404319552844595\cdot2^{-54}$ = 0. 2999999999999988897769753748434595763683319091796875 erweist sich als genauer. Dahererfordertder IEEE-Standard das Hinzufügen von 0,1 + 0,2, um ein anderes Ergebnis als 0,3 zu erzielen.

Doppelte Analyse

Eine einfache Verallgemeinerung des Integer-Algorithmus besteht aus iterativen Multiplikationen und Divisionen durch 10.0 - im Gegensatz zum Parsen von Integer ist es hier erforderlich, Ziffern von niedrig nach hoch zu verarbeiten, damit Rundungsfehler in hohen Ziffern Rundungsfehler in niedrigen Ziffern "verbergen". Gleichzeitig lässt sich das Parsen der Mantisse leicht auf das Parsen von ganzen Zahlen reduzieren: Es reicht aus, die Normalisierung so zu ändern, dass der imaginäre Binärpunkt nicht am Anfang der Mantisse, sondern am Ende liegt; die resultierende 53-Bit-Ganzzahl multipliziert oder dividiert durch die gewünschte Zehnerpotenz; und schließlich subtrahiere 52 vom Exponenten, d.h. Verschieben Sie den Punkt 52 Bit nach links - wo er gemäß dem IEEE-Standard sein sollte. Darüber hinaus sind drei wichtige Fakten zu beachten:

1. Es reicht aus zu lernen, wie man mit 5 multipliziert oder dividiert, und Multiplikation oder Division mit 2 ist nur ein Inkrement oder Dekrement eines Exponenten.
2. uint64_t 5 0xcccccccccccccccd 66 , , $$$\frac{\texttt{0xcccccccccccccccd}}{2^{66}} - \frac1 5 = \frac1{5\cdot2^{66}} < 2^{-68}$ 64 ( );
3. – $$$10^{-324} < 2^{-1074}$ $$$2^{1024} < 10^{309}$ ; , 309 , 324 0xcccccccccccccccd, . ( 53 ; 128- , 53- 53- .) 633 double ( , ⅕, 7205759403792794 – 0xcccccccccccccccd, 53 ), double ; 53 , . , , 64 64 , , 128- . .

Die Komplexität der Standardrundung besteht darin, dass wir nicht nur 54 signifikante Bits des Ergebnisses benötigen, um herauszufinden, dass das Ergebnis genau in der Mitte zwischen den nächsten binären Brüchen liegt (das niedrigstwertige Nullbit bedeutet "alles ist in Ordnung"). Das eine bedeutet "Hit the Middle"), aber Sie müssen beobachten, ob es nach dem niedrigstwertigen Bit eine Fortsetzung ungleich Null gab. Dies bedeutet insbesondere, dass es nicht ausreicht, nur die 17 wichtigsten Stellen in der Dezimalschreibweise der Zahl zu berücksichtigen: Sie definieren die binäre Mantisse nur mit einer Genauigkeit von ± 1, und um die gewünschte Rundungsrichtung auszuwählen, müssen Sie berücksichtigen die unteren Ziffern. Beispielsweise sind 10000000000000003 und 10000000000000005 der gleiche Doppelwert (gleich 10000000000000004), und 10000000000000005.00 (viele Nullen) 001 ist ein anderer Wert (gleich 10000000000000006).



Professor Daniel Lemire von der Correspondence University of Quebec (TÉLUQ), der diesen Parser erfunden hat, hat ihn auf Github veröffentlicht . Diese Bibliothek bietet zwei Funktionen from_chars



: Eine analysiert eine Zeichenfolge, um sie zu verdoppeln, die andere, um sie zu schweben. Seine Experimente zeigten, dass es in 99,8% der Fälle ausreicht, 19 signifikante Dezimalstellen (64 Bit) zu berücksichtigen: Wenn für zwei aufeinanderfolgende Werte einer 64-Bit-Mantisse der gleiche endgültige Doppelwert erhalten wird, ist dies der richtige Wert . Nur in 0,2% der Fälle, in denen diese beiden Werte nicht übereinstimmen, wird ein komplexerer und universellerer Code ausgeführt, der eine immer korrekte Rundung implementiert.