Eigentlich als Aufgabe für einen Programmieranfänger, haben sich alle mal ausprobiert folgende Aufgabe zu lösen - und zwar möglichst schnell. Alle Beteiligten (bis auf Xin) sehen die Codes der anderen auf dieser Seite zum ersten Mal. Ich (Xin) habe die Auswertung gemacht. Für meinen Algorithmus „xin“ habe canlots Algorithmus genommen und ihn meinen Wünschen angepasst. Der Algorithmus „xin++“ ist mein Algorithmus „xin“, das continue wurde von Dirty Oertis zuerst eingereichten Algorithmus inspiriert. „xinasm“ ist die Umsetzung von „xin++“ nach Assembler.

In jedem Fall ergibt sich eine interessante Auswahl an Lösungideen.

Die Aufgabe ist, eine Funktion zu schreiben, die Wörter zählt, wobei ein Wort alles ist, was kein Leerzeichen ist. Dazu gehören also auch Satzzeichen und das Newline-Zeichen. Leerzeichen - Newline - Leerzeichen ist ein Wort, bla\nbla ist ein (nicht zwei) Worte.

Getestet wird auf einem Intel i7 860 mit 2,80 GHz und 8GB RAM. Hierfür wird eine Textdatei von 3,6GB Größe in den Arbeitsspeicher geladen und anschließend werden die einzelnen Funktionen auf diesen Text losgelassen. Der Algorithmus sollte 598752090 Wörter finden. Die Zeitmessung wird über die Funktion clock() durchgeführt. Das ist alles andere als genau, aber liefert bei der Textgröße durchaus ein Indiz, welcher Algorithmus wie schnell ist. Die Ungenauigkeit liegt bei etwa 5-10%. Aus diesem Grund mache ich 5 Durchläufe und nehme jeweils die schnellste gemessene Zeit. Nach vier Durchläufen ergaben sich keine schnelleren Laufzeiten mehr. Aus Tests, die ich in den Tagen zuvor gemacht habe und im Forum veröffentlicht habe, sind teilweise schnellere Laufzeiten aufgetreten. Diese schnelleren Laufzeiten habe ich in Klammern dazugeschrieben. Diese Laufzeiten werde ich hier nicht mehr berücksichtigen, da sich nach 6 Durchläufen die Zeitunterschiede im Promillebereich (10000-50000 Ticks) bewegen und sich damit keine Verbesserungen mehr ergeben.

Size: 3760664220

canlot  : 598752090 Wörter - Zeit: 21780000  (21580000)
bbbl    : 598752090 Wörter - Zeit: 20500000
nouse   : 598752090 Wörter - Zeit: 19600000
micbac  : 598752090 Wörter - Zeit: 18430000
nouse2  : 598752090 Wörter - Zeit: 18270000
cloid2  : 598752090 Wörter - Zeit: 17850000  (17450000)
cloido  : 598752090 Wörter - Zeit: 17650000
dirty4  : 598752090 Wörter - Zeit: 17580000
bbbl2   : 598752090 Wörter - Zeit: 17110000
cloid   : 598752090 Wörter - Zeit: 16550000  (16290000)
xin     : 598752090 Wörter - Zeit: 16480000
xin++   : 598752090 Wörter - Zeit: 15500000

nufanasm: 598752090 Wörter - Zeit: 11200000
xinasm  : 598752090 Wörter - Zeit: 10220000

Die Codes sind nach ihrer Geschwindigkeit sortiert.

Schauen wir uns den ersten Code an, canlot ist zu diesem Zeitpunkt C-Einsteiger, man sieht es an der Übergabe der Variable counter . Von daher sind 30% Abstand zum schnellsten Algorithmus schon ziemlich gut.

int wordCount_canlot(const char *str, int counter)
    {
        counter = 0;
        int setzen = 0;
        unsigned int i = 0;
        for ( i=0; str[i]!='\0'; i++ )
        {
            if (str[i]==' ')
            {
                setzen = 0;
            }
            else if(str[i]!=' ' && setzen == 0)
            {
                counter++;
                setzen = 1;
            }
        }
        return counter;
    }

Ziel der Aufgabe ist es, dass nicht Leerzeichen gezählt werden, sondern erkannt wird, dass es sich um zwei unterschiedliche Status handelt, nämlich: „Ich befinde mich in einem Wort“ bzw. „Ich befindet mich nicht in einem Wort.“ Wenn ich in den Status „Ich befinde mich in einem Wort“ wechsle, muss ich ein Wort gefunden haben. Dies verdeutlicht der Algorithmus mit der Variable setzen. Die Abfrage if(str[i]!=' ' && setzen == 0) entspricht dem Wechsel des Status. Pro Zeichen sind hier 2 bis 4 Abfragen notwendig: str[i] != 0, str[i] == ' ', str[i] != ' ' und setzen == 0. Die Abfrage str[i] != ' ' ist überflüssig, denn in den Else-Bereich, in dem die Abfrage steht kommt man nur dann, wenn die Bedingung str[i] != ' ' falsch ist.

bbbl benutzt hier keine Status, sondern zählt nur die Wechsel von Leerzeichen zu Nicht-Leerzeichen. Das bedeutet pro Zeichen 2 bis 3 Abfragen: str[i] != 0, str[i] == ' ' und str[i+1] != ' '. Hierbei wird mit str[i+1] zusätzlich noch eine Berechnung durchgeführt, die ebenfalls Zeit kostet.

int wordCount_bbl( const char *str )
{
  unsigned int
    count = 1, // Word count
    i = 0;
 
  const char
    EOL = '\0', // End of line
    SPC = ' ';  // Space
 
  // Return if string is empty
  if ( ! str[0] ) return 0;
 
  // left trim
  while ( str[i++] == SPC )
  {
    if ( str[i] != SPC ) break;
    i++;
  }
 
  // count words
  while ( str[i++] != EOL )
  {
    if ( str[i] == SPC && (str[i+1] != SPC) ) count++;
  }
 
  // dirty: decrease last count if it is caused by a space character
  if ( str[i-2] == SPC ) count--;
 
  return count;
}

Im Aufbau entspricht der Algorithmus dem Algorithmus von canlot, allerdings benutzt er Pointer statt Arrayzugriffe und optimiert das Überspringen von Wörtern und Blöcken von Leerzeichen. Der Status wird wie bei canlot in einer Variablen gespeichert.

unsigned int wordCount_nouse(char const *str)
{
    int wc=0;
    int merker = 0;
 
    while (*str != '\0')
    {
 
        if (*str == ' ' && merker == 1)
        {
            merker = 0;
 
            while (*str == ' ')
                str++;
 
        }
        else if (*str != ' ' && merker == 0)
        {
            merker = 1;
            wc++;
 
            while (*str != ' ')
                str++;
        }
        else
            str++;
    }
 
    return wc;
}

Spät ins Rennen gegangen und dennoch mit einer sehr hübschen Implementierung - nämlich mit dem mit Abstand kürzesten Quelltext - erobert sich micbac seien Platz. Er programmiert C/C++ seit vielen Jahren und hat den Code (in meinem Beisein) ohne einen Test in sein Mailprogramm gehackt und an mich geschickt.

int wordCount_micbac( char* str )
{
   int c = 0;
   while ( *( str++ ))
      *str == ' ' ? 0 : ( *( str-1 ) == ' '&&  c++ );
   return c;
}

Im Aufbau entspricht der Algorithmus dem Code von bbbl, allerdings im Quelltext und Ablaufgeschwindigkeit ist er schneller, was darauf zurückzuführen ist, dass hier mit Pointern statt Arrayzugriffen gearbeitet wird.

Micbac begeistert sich - wie man sieht - für Expressions.

   while ( *( str++ ))
      *str != ' ' && ( *( str-1 ) == ' '&&  c++ );

sollte es ebenso tun und man spart den ?:-Operator.

Nouseforname hat einen zweiten Algorithmus eingereicht. Er entspricht seinem vorherigen Algorithmus, aber ist beschleunigt, da er die Statusvariable merker entfernen konnte.

unsigned int wordCount_nouse2(char const *str)
{
    int wc=0;
 
    while (*str != '\0')
    {
 
        if (*str != ' ')
        {
            wc++;
 
            while (*str != ' ')
                str++;
 
        }
        else
            str++;
    }
 
    return wc;
}

Dies ist cloidnerux zweiter eingereichter Algorithmus. Hier haben wir garantiert nur zwei Abfragen pro Zeichen, allerdings eine Addition aus einer Variablen heraus und es wird pro Zeichen eine Variable gesetzt. Die Idee ist allerdings bemerkenswert klever, denn sie erspart die Frage, ob wir nun am Wortanfang sind oder nicht.

int wordCount_cloidnerux2(char *text)
{
  int space = 1, count = 0;
  for(;*text!='\0';text++)
  {
    if(*text == ' ' /*|| *text == '\n' */ )
    {
      space = 1;
    }
    else
    {
      count += space;
      space = 0;
    }
  }
  return count;
}

cloidnerux war recht fleißig und hat reichlich Codes eingereicht. Dies ist sein optimierter Code (der insgesamt 3. Code). Der Code entspricht fast „cloid2“, lediglich eine Zeile ist hinzugefügt. Bei einem Leerzeichen wird gleich mal das Leerzeichen übersprungen und am Ende der Schleife gleich nochmal. Das ist ein wenig schneller - aber leider falsch, falls am Ende des Textes vor dem Nullbyte ein Leerzeichen ist. Damit ist der optimierte cloidnerux leider disqualifiziert. ^^

int wordCount_cloidnerux_Opti1(char *text)
{
   int space = 1, count = 0;
   for(;*text!='\0';text++)
   {
      if(*text == ' ')
      {
         space = 1;
         text++;            // hinzugefügt
      }
      else
      {
         count += space;
         space = 0;
      }
   }
   return count;
}

Dirty Oerti hat sich viel Mühe gegeben auf Satzzeichen und so weiter zu achten - aber war damit leider nicht konkurrenzfähig. Seine letzte Version löst genau das Problem, das hier verglichen wird und ist damit schon recht flott unterwegs. Hier sieht man auch das continue, das mich zu meinem „xin++“ inspirierte. Dies überspringt Blöcke von Leerzeichen und sorgt dafür, dass man sich um Wörter nicht weiter kümmern muss, solange man in einem Block von Leerzeichen ist. Findet man ein anderes Zeichen, so hat man ein Wort gefunden. Anschließend wird das nächste Leerzeichen gesucht. Hier zeigen die beiden Status - Leerzeichenblock oder innerhalb eines Wortes - im Quelltext, eine zusätzliche Variable wird nicht mehr benötigt und es muss auch kein benachbartes Zeichen zum aktuellen geprüft werden.

unsigned int wordCount_dirty4(char const * const str)
{
    unsigned int words = 0;
    char const * actChar = str;
    while (*actChar != '\0')
    {
        if (*actChar == ' ')
        {
            actChar++;
            continue;
        }
        words++;
        actChar++;
        while (*actChar != ' ' && *actChar != '\0')
        {
            actChar++;
        }
    }
    return words;
}

bbbl optimierte seine Version nochmal mit einem interessanten anderen Ansatz. Zunächst verbrennt er massiv Zeit, in dem er die Länge des Strings ermittelt. Das kostet erstaunlich wenig - vermutlich weil es durch eine moderne CPU gut unterstützt ist und es vereinfacht aber die Abfrage, wann der String durchschritten ist. Statt auf eine Adresse zuzugreifen, ob diese ein Nullbyte enthält, findet hier nur ein Stringvergleich statt. Ansonsten findet sich hier nochmal eine Variable, die den Status speichert: word.

int wordCount_bbl2( const char *str )
{
  unsigned int
    count = 0,
    word = 0; // bool
 
  const char
    *start = str,
    *end = str + strlen(str);
 
  while ( end-- != start )
  {
    if ( ! word && *end != 32 )
    {
      count++;
      word = 1;
    }
    else if ( word && *end == 32 )
    {
      word = 0;
    }
  }
 
  return count;
}

cloidnerux beste Version war die erste Version, die er eingereicht hat, hier heißt die Statusvariable space. Viele Fragen, die jedoch zum Glück aufgrund der Statusvarablen space nicht gestellt werden. In der Zeile if(space && *text > 32 && *text != ' ') wird vermutlich schon direkt vom Compiler die Frage *text != ' ' wegoptimiert, da sie immer wahr sein muss, wenn *text > 32 ist. Somit reduzieren sich die Fragen wieder auf im Schnitt drei pro Zeichen, ohne dass weiteres durchgeführt wird.

int wordCount_cloidnerux(char *text)
{
  int space = 1, count = 0;
  for(;*text!='\0';text++)
  {
    if(space && *text > 32 && *text != ' ')
    {
      count++;
      space = 0;
    }
    else if(*text == ' '/* || *text == '\n'*/)
    {
      space = 1;
    }
  }
  return count;
}

Die folgende Version zeigt die beiden Status durch eine if-Abfrage repräsentiert. Sobald klar ist, ob man sich innerhalb oder außerhalb eines Wortes befindet, wird der Leerzeichenblock bzw. das Wort übersprungen. Das bedeutet, dass in den meisten Fällen nur zwei Abfragen erforderlich sind.

Der Code ist nahezu identisch mit Dirty Oertis Code. Der Unterschied liegt darin, dass ich if ( *(str++) == ' ' ) schreibe, während Dirty Oerti seine Variable actChar erst später erhöht. Die Tatsache, dass der Wert wohl gerade noch im Register ist, führt wohl dazu, dass das Auslesen und Erhöhen der Variable schneller ablaufen.

unsigned int wordCount_xin(const char *str)
{
  unsigned int counter = 0;
 
  while( *str )
    if ( *(str++) == ' ' )
      while( *str == ' ' && *str ) str++;  // Leerzeichen überspringen
    else
    {
      while( *str != ' ' && *str ) str++;  // Wort überspringen
      counter++;
    }
 
  return counter;
}

Als ich Dirty Oertis ersten Code sah (der hier nicht abgedruckt ist), habe ich sein Vorgehen gesehen mit continue den Status Befinde mich in einem Block von Leerzeichen zu vereinfachen. Im Prinzip ändert sich der Algorithmus nicht, aber ich wollte es ausprobieren, ob da noch was geht - und tatsächlich ist diese Fassung schneller. Der Unterschied ergibt sich vermutlich, dass nun str++ nicht mehr alleine dasteht, sondern auch beim Überspringen von Leerzeichen grundsätzlich zusammen mit der Dereferenzierung zusammenfällt, bzw. der Code selbst kürzer wird und so kürzere Sprünge möglich werden, die eventuell so kurz sind, dass sie mit schnelleren Sprungbefehlen optimiert zu werden.

unsigned int wordCount_xin_speed(const char *str)
{
  unsigned int counter = 0;
 
  while( *str )
  {
    if ( *(str++) == ' ' )
      continue;
 
    while( *str != ' ' && *str ) ++str;  // Wort überspringen
    counter++;
  }
 
  return counter;
}

section .text
 
global wordCount_nufan_asm
; counts words in a string on the stack and puts the value in rax
wordCount_nufan_asm:
  mov rax, rdi           ; get parameter address
  push rbx                     ; save callers registers
  push rdx
  mov rbx, 1                   ; says if last character was a space
  mov rdx, 0                   ; number of words
  .Count:
  cmp byte [rax], 0x20         ; check for space on current index
  je .IsSpace
  cmp rbx, 0                   ; check if last character was not a space
  je .InWord
  inc rdx                      ; increment number of words
  mov rbx, 0                   ; character is not a space
  jmp .IsWordStart
  .IsSpace:                    ; current character is a space
  mov rbx, 1
  .InWord:                     ; current character is not a space,
                               ;  but in the middle of a word
  .IsWordStart:                ; current character is not a space,
                               ;  but the start of a new word
  inc rax
  cmp byte [rax], 0x00         ; check if end of string is reached
  jne .Count
  mov rax, rdx                 ; store number of words as "return value"
  pop rdx                      ; restore callers registers
  pop rbx
  ret                          ; leave function

C-Aufruf:

extern unsigned long wordCount_nufan_asm( const char * str );

Zu kompilieren mit

nasm -f elf64 wcnufan.asm

Der Algorithmus entspricht dem C-Algorithmus „xin++“.

.section .data
text: .ascii "Dies ist ein String."
.section .text
.globl wc
 
wc:
  sub %ecx, %ecx
  mov %rdi, %rax
 
  jmp while
continue:
  inc %rax
while:
  cmpb $0, (%rax)
  je exit              # Textende => exit
 
  cmpb $32, (%rax)
  je continue          # Leerzeichen überspringen
 
  inc %ecx             # Wort gefunden
 
skip:
  cmpb $32, (%rax)
  je continue;
 
  cmpb $0, (%rax)
  je exit
 
  inc %rax;
  jmp skip;
 
exit:
  movl %ecx, %eax
  ret

C-Aufruf:

extern unsigned long wc( const char * str );

Zu kompilieren mit

as wordcount.asm -o wordcountAsm.o

Auch einfache Aufgaben können deutlich optimiert werden, es lohnt sich durchaus sich damit zu beschäftigen und die Erfahrungen, die man mit solch einfachen Funktionen sammelt auszuwerten und in die alltägliche Programmierung einfließen zu lassen. Allerdings lohnt es nicht, deswegen gleich Assembler zu lernen. Meistens reicht es vollkommen die Optimierung des Compilers einzuschalten und schon sieht die Welt ganz anders aus, denn kaum ein Assemblerprogrammierer ist in der Lage Optimierungen derart gezielt auszuführen, wie es ein moderner C-Compiler ist. Es zeigt sich, dass Pointerarithmetik - so sehr sie in anderen Sprachen verteufelt wird - einen deutlichen Geschwindigkeitszuwachs bringt. Hier zeigt sich auch, dass ein Optimierer die Reihenfolge nochmal gut durcheinander wirbeln kann:

nufanasm: 598752090 Wörter - Zeit: 12480000              Platz  2 (ASM)
canlot  : 598752090 Wörter - Zeit: 11610000              Platz 11 (C)
xin     : 598752090 Wörter - Zeit: 11240000              Platz  2 (C)
nouse   : 598752090 Wörter - Zeit: 11220000              Platz  9 (C)
dirty   : 598752090 Wörter - Zeit: 10660000              Platz  5 (C)
micbac  : 598752090 Wörter - Zeit: 10480000              Platz  8 (C)
bbbl    : 598752090 Wörter - Zeit: 10470000              Platz 10 (C)
xin++   : 598752090 Wörter - Zeit: 10390000              Platz  1 (C)
cloid2  : 598752090 Wörter - Zeit: 10370000              Platz  6 (C)
bbbl2   : 598752090 Wörter - Zeit: 10290000              Platz  4 (C)
xinasm  : 598752090 Wörter - Zeit: 10280000              Platz  1 (ASM)
cloid   : 598752090 Wörter - Zeit: 9630000               Platz  3 (C)
cloido  : 598752090 Wörter - Zeit: 9400000  (fehlerhaft) 
nouse2  : 598752090 Wörter - Zeit: 8480000               Platz  7 (C)