====== WordCount Contest ======
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 =====
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.
===== Die Testauswertung =====
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 [[c:lib:time: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.
===== Die C-Programme =====
==== Platz 11: canlot - Zeit: 21780000 ====
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.
==== Platz 10: bbbl - Zeit: 20500000 =====
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;
}
==== Platz 9: nouse - Zeit: 19600000 =====
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;
}
==== Platz 8: micbac - Zeit: 18430000 ====
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.
==== Platz 7: nouse2 - Zeit: 18270000 ====
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;
}
==== Platz 6: cloid2 - Zeit: 17850000 (17450000) ====
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;
}
==== Platz -: cloido: Zeit: 17650000 ====
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;
}
==== Platz 5: dirty - Zeit: 17580000 ====
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;
}
==== Platz 4: bbbl2 - Zeit: 17110000 ====
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;
}
==== Platz 3: cloid: 16550000 (16290000) ====
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;
}
==== Platz 2: xin - Zeit: 16480000 ====
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;
}
==== Platz 1: xin++ : 598752090 Wörter - Zeit: 15500000 ====
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;
}
===== Die Assemblerversionen =====
==== Platz 2: nufanasm - Zeit: 11200000 ====
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
==== Platz 1: xinasm - Zeit: 10220000 ====
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
===== Fazit =====
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)