Optimierung der Codeausführungsgeschwindigkeit



    In diesem Artikel geht es darum, wie klassische Algorithmen unseren Code beschleunigen. Wir werden den Null-Bit-Suchalgorithmus betrachten und wie er uns helfen kann, die Effizienz des Suchalgorithmus für ein Zeichen aus einem Bereich zu erhöhen (z. B. das erste Auftreten eines Zeichens aus einem Bereich von 0 bis 9 in einer Zeichenfolge zu finden).
    Das heißt, Nur ein kugelförmiges Pferd im Vakuum ist eine ziemlich häufige Situation bei der Verarbeitung von Text, wenn es notwendig ist, die Position der ersten Ziffer in einem beliebigen Text zu finden. So beginnen viele, reguläre Ausdrücke zu lernen.
    Der Artikel beschreibt die Verwendung von gcc. Auf Wunsch kann alles mit kleinen Änderungen für andere Compiler und Sprachen wiederholt werden. Achtung, unter dem Schnitt befindet sich ein Assembler!

    Um dieses Problem zu lösen, können wir die folgenden Methoden verwenden:
    1) Verwenden Sie die Bibliothek für reguläre Ausdrücke.
    2) Schreiben Sie eine Funktion, um nach sich selbst zu suchen.
    Wenn die Linien klein sind, stellt sich die Frage der Optimierung nicht. Diese Aufgabe wird interessant, wenn die Länge der Zeilen zunimmt oder eine große Anzahl von Überprüfungen stattfindet.
    Wir werden die Ausführungszeit mit der Funktion clock () aus der verbundenen Datei messen.

    Wir verwenden REGEX

    Betrachten Sie eine Methode mit regulären Ausdrücken. Eine der ersten Methoden, die mir in den Sinn kommt, ist die Verwendung der REGEX-Bibliothek. Der reguläre Ausdruck sieht folgendermaßen aus:
    "[[: digit:]]"
    Der Code für die Verwendung dieser Bibliothek kann folgendermaßen aussehen:
    clock_t tbefore;
        long i;    
        double eplased;    
        int pmatch[1];
        regex_t regex;
        int reti;
    ….
    /*REGEXP usage*/
       tbefore = clock();
       reti = regcomp( & regex, "[[:digit:]]", 0);   
       for (i=1;i<100000;i++){
            reti = regexec(& regex, test_string, 1, pmatch, 0);	
       }   
       eplased=clock()-tbefore;
       printf("Function strchr used %.3f seconds %d\n", eplased/CLOCKS_PER_SEC, pmatch[0]);    
       regfree( & regex);
    /**************/
    

    Ausführungsgeschwindigkeit: 1,74 Sek.
    In diesem Code habe ich absichtlich Überprüfungen des Erfolgs der Kompilierung und Suche entfernt, dh es ist unmöglich, diesen Code zur Lösung realer Probleme zu verwenden. Aber um die Geschwindigkeit unter "Gewächshaus" -Bedingungen zu überprüfen - das war's. Außerdem messe ich die Laufzeit, indem ich einen regulären Ausdruck kompiliere und nach dessen Verwendung Speicher freigebe.

    Seine Funktion für die Suche

    Versuchen wir, den traditionellen Ansatz zu verwenden - Stirn. Die Suchfunktion
    sieht folgendermaßen aus ( Algorithmus 1 ):
    int search1(char *str){
      int l=0;
      int i;
      l = strlen(str);
      for (i=0;i= '0') && (str[i] <= '9')){
          return (i);
        }
      }  
      return (-1);
    }
    

    Ausführungsgeschwindigkeit: 7,19 Sek.
    Und die Messergebnisse zeigen eine mehr als viermal niedrigere Ausführungsgeschwindigkeit! Welches ist zu erwarten.

    Optimierter Algorithmus

    Versuchen wir zu optimieren. Es war einmal das Buch "Algorithmic Tricks for Programmers" von G. Warren. In diesem Buch wurden Algorithmen zum Auffinden des Nullzeichens in einer Zeichenfolge beschrieben. Diese Algorithmen werden beispielsweise in C verwendet, um das Ende einer Zeile zu finden. In einem der Absätze wird auch eine Verallgemeinerung eines dieser Algorithmen für eine Bereichsbeschreibung vorgeschlagen.
    Die Idee des Algorithmus ist, dass zum Suchen nach dem Index eines Zeichens in einer Zeichenfolge nicht eines nach dem anderen, sondern vier Zeichen gleichzeitig durchlaufen werden und doppelte Wörter aus dem Array gelesen werden (dword = 4 Byte). Das heißt, In Bezug auf C lesen wir lange Ganzzahlen ohne Vorzeichen aus einem Zeichenarray (char).
    Danach werden arithmetische Operationen mit dem Wort ausgeführt. Für einen Bereich von null bis neun sieht es so aus:
    int zbytel3(unsigned z) {
       unsigned y;
       x = z ^ 0x30303030;  
                             				// Original byte: 00 80 other
       y = (x & 0x7F7F7F7F) + 0x76767676; // 7F 7F 1xxxxxxx
       y = ~(y | x | 0x7F7F7F7F);         // 80 00 00000000
                                          // These steps map:
       if (y == 0) return 4;              // 00000000 ==> 4,
       else if (y > 0x0000FFFF)           // 80xxxxxx ==> 0,
          return (y >> 31) ^ 1;           // 0080xxxx ==> 1,
       else                               // 000080xx ==> 2,
          return (y >> 15) ^ 3;           // 00000080 ==> 3.
    }
        


    das heißt, x = z ^ 0x30303030 - eine exklusive Operation oder die minimale Anzahl des Bereichs "0" - 0x30 auf 0 ändert. 0x76 = 0x7F-9, wobei 9 = n-1, wobei n die Anzahl der Zeichen im Bereich ist.
    Als nächstes einfache Byte-Arithmetik, wodurch wir eine Zahl erhalten können, die in der Verzweigung verarbeitet wird, und als Ergebnis erhalten wir die Zahlen von 1 bis 4. Das heißt Wenn das Symbol nicht gefunden wird - dann 4.
    Nun hat unsere Funktion die folgende Form:
    int search2( char *str){
      int n, j = 0;  
      unsigned x, y, *r;
      const char *c_ptr;
      //Проверяем посимвольно первые байты, пока не выровняем.
       for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr)
        if ((*c_ptr >= '0') && (*c_ptr <= '9'))
          return c_ptr - str;
      r = (unsigned *) c_ptr;
      j = c_ptr - str ;  
      while (1){            
          x = *r ^ 0x30303030;                                           	    
          y = (x & 0x7F7F7F7F) + 0x76767676;
          y = ~(y | x | 0x7F7F7F7F);         
          // These steps map:
          if (y == 0) n = 4;              // 00000000 ==> 4,
          else if (y > 0x0000FFFF)        // 80xxxxxx ==> 0,
          n= (y >> 31) ^ 1;               // 0080xxxx ==> 1,
          else                            // 000080xx ==> 2,
          n= (y >> 15) ^ 3;               // 00000080 ==> 3.            
          j=j+n ;
          if (n<4) {j =j +3 -2*n; break;}      
          r++;
      }        
      return (j);
    }
    

    Ausführungsgeschwindigkeit: 1,71 Sek.
    Die Messergebnisse zeigen eine Geschwindigkeit nahe dem regulären Ausdruck. Können wir es schneller machen? Ja!
    Wir verwenden Assembler-Einsätze. Die Stärke der beschriebenen Methode besteht darin, dass Sie die Anzahl der Taktzyklen, die der Prozessor für die Ausführung ausgibt, mithilfe elementarer arithmetischer Operationen reduzieren können. Das Programmieren in einer Hochsprache ermöglicht es uns nicht, die Fähigkeiten dieses Algorithmus vollständig zu realisieren.
    Und deshalb wird unsere Funktion jetzt die folgende Form annehmen:
    int search3( char *str){
      int n, j = 0;
      unsigned x, y, *r;
      const char *c_ptr;    
      for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr)
        if ((*c_ptr >= '0') && (*c_ptr <= '9'))
          return c_ptr - str;
      r = (unsigned *) c_ptr;
      j = c_ptr - str ;
      while (1){
          __asm__(
           "movl $5, %%edx\n"
           "movl (%%ebx), %%eax\n"
           "xor $0x30303030, %%eax\n" //
           "and $0x7F7F7F7F, %%eax\n"
           "add $0x76767676, %%eax\n"
           "movl %%eax, %%ecx\n"
           "or %%eax, %%ecx\n"
           "or $0x7F7F7F7F, %%ecx\n"
           "notl %%ecx\n"                   
          :"=c"(y)
          :"b"( r )
          );
           // These steps map:
          if (y == 0) n = 4;              // 00000000 ==> 4,
          else if (y > 0x0000FFFF)        // 80xxxxxx ==> 0,
          n= (y >> 31) ^ 1;               // 0080xxxx ==> 1,
          else                            // 000080xx ==> 2,
          n= (y >> 15) ^ 3;               // 00000080 ==> 3.            
          j=j+n ;
          if (n<4) {j =j +3 -2*n; break;}      
          r++;
      }        
      return (j);
    }
    

    Ausführungsgeschwindigkeit: 1,23 Sek.
    Ich habe die Baugruppe nur durch arithmetische Operationen ersetzt. Die Verzweigung kann auch durch Assembler-Code ersetzt werden, aber ich bin mir nicht sicher, ob ein signifikanter Gewinn erzielt werden kann, aber mehrere Verzweigungen mit Beschriftungen erschweren den Debugging-Prozess erheblich.
    Gewinnen ist vorhanden, aber manchmal nicht im Vergleich zu regulären Ausdrücken. Wenn Sie mit Assembler-Einfügungen optimieren, können Sie den Code zwar noch verbessern, dies führt jedoch zu einer Komplikation des Debugging-Prozesses. Wenn Sie die Verzweigung und die Schleife optimieren, können Sie eine anderthalbfache Geschwindigkeitssteigerung erzielen. Das Debuggen des Codes wird jedoch viel schwieriger. Sie können diesen Algorithmus auch für 64 statt 32 Bit optimieren und versuchen, den Prozess zu parallelisieren.

    Insgesamt erhalten wir:
    Regex 1,74
    Algorithmus 1 7.19
    Algorithmus 2 1,71
    Algorithmus 2 + asm 1.23


    Die Schlussfolgerung liegt auf der Hand: Die Erfindung von Fahrrädern ist nicht erwünscht, und nicht immer kann der Gewinn aus der Montageoptimierung so bedeutend sein.

    Link zum
    Quellarchiv : webfile.ru/5706721

    UPD: Die
    Optimierung für die Prozessorarchitektur wurde angezeigt. Ich füge den Parameter -O 2 hinzu. Ich
    füge auch eine Summierung innerhalb der Testfunktionen hinzu, um das Ergebnis auf irgendeine Weise zu verwenden.
    Ergebnis:

    Regex 4.56
    Algorithmus 1 2,99
    Algorithmus 2 1
    Algorithmus 2 + asm 1,7 *


    * Da der -O2-Schalter nicht mehr richtig funktioniert, hat __volatile_ nicht geholfen, das Ergebnis mit dem -O1-Schalter, aber mit zusätzlicher Summierung.

    UPD 2: Maratyszcza-

    Benutzer (danke an ihn!) Bietet eine noch schnellere Option mit SIMD-Erweiterungen .

    #include 
    const char* find_digit(const char* str) {
        static const __m128i str_mask[16] = {
            _mm_set_epi32(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x00FFFFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x0000FFFF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x000000FF, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x00FFFFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x0000FFFF),
            _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x000000FF)
        };
        static const __m128i str_offset = _mm_set1_epi8(127 - '9');
        static const __m128i str_threshold = _mm_set1_epi8(127 - 10);
        const size_t str_misalignment = ((size_t)str) & ((size_t)15);
        const __m128i* str_aligned = (const __m128i*)(((size_t)str) - str_misalignment);
        __m128i str_vector = _mm_load_si128(str_aligned);
        str_vector = _mm_and_si128(str_vector, str_mask[str_misalignment]);
        str_vector = _mm_add_epi8(str_vector, str_offset);
        int str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold));
        unsigned long index;
        _BitScanForward(&index, str_bitmask);
        while (str_bitmask == 0) {
            str_aligned += 1;
            str_vector = _mm_load_si128(str_aligned);
            str_vector = _mm_add_epi8(str_vector, str_offset);
            str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold));
            _BitScanForward(&index, str_bitmask);
        }
        return ((const char*)str_aligned) + index;
    }
    


    Dies ist die bisher schnellste Option.

    Jetzt auch beliebt: