Anzahl Buchstaben aus Array C

[Merle]

Ja, das zählen bis \0 dachte ich... (in strlen)
Ist auch latte...

 

[cx01]

du siehst die mehrfache iteration nicht, weil sie durch strlen() versteckt wird. dort findet nämlich auch eine iteration statt.

Ein halbwegs intelligenter Compiler sollte das erkennen können und entsprechend optimieren. GCC kann das wohl: http://stackoverflow.com/questions/2049480/how-many-times-will-strlen-be-called-in-this-for-loop

Möchte man aber auf Nummer sicher gehen, kann man es natürlich explizit machen.

 

[antred]

eine andere methodik, die sogar noch mehr speed liefert ist:

	const char *pos = satz;
	while (*pos != '\0') {
		char c = *pos++;
		...
	}

Also wenn das nicht in die Kategorie "premature optimization" fällt, dann fress ich 'n Besen. Hast Du überhaupt mal gründlich ausgetestet, ob das WIRKLICH einen nennenswerten Unterschied macht? Zumal strlen() ja wahrscheinlich so ziemlich genau das selbe tun wird.

 

[IceMatrix]

Du brauchst nur die Operationen zu zählen, dann siehst du bereits den Unterschied. Dieser Ansatz ist best-practise. So wird es überall dort gemacht, wo es auf Performance ankommt. Man sollte sich grundsätzlich nicht auf den Compiler verlassen, denn der beste Optimierer ist nachwievor der Programmierer selbst.

1:1 übersetzt ist die for-Schleife 1x cmp und 2x add (i++ und satz). Die while-Schleife hat nur 1x add.
Außerdem benötigt die while-Schleife nur ein einzelnes Register um pos zu halten, die for-Schleife muss satz und i halten (also 2).
Zusätzlich reduziert sich die Zahl der Speicherzugriffe, da nur gegen (const)'\0' getestet wird, und nicht gegen die lokale Variable len.

Ein halbwegs intelligenter Compiler sollte das erkennen können und entsprechend optimieren. GCC kann das wohl: http://stackoverflow.com/questions/2...-this-for-loop

Manche Dinge sind nicht so einfach, wie sie auf den ersten Blick erscheinen. Der Compiler kann das strlen() nur in ganz bestimmten Situationen wegoptimieren.
Beispiel: In der Schleife wird eine weitere Funktion XXXX mit dem Parameter "satz" aufgerufen. Schreibt diese Funktion auf die Zeichenkette, dann ist eine Optimierung nicht mehr möglich. Ebenso sieht es aus, wenn die Zeichenkette nicht im Stack liegt, sondern irgendwo global oder im Heap. Dann kann nämlich ein anderer Thread die Zeichenkette manipulieren.
Wie gesagt.. so einfach ist es eben doch nicht. strlen() sollte man in for-Schleifen vermeiden (sofern möglich).

 

[antred]

Ich interpretiere das mal als ein 'nein'.

Du brauchst nur die Operationen zu zählen, dann siehst du bereits den Unterschied. Dieser Ansatz ist best-practise. So wird es überall dort gemacht, wo es auf Performance ankommt. Man sollte sich grundsätzlich nicht auf den Compiler verlassen, denn der beste Optimierer ist nachwievor der Programmierer selbst.

1:1 übersetzt ist die for-Schleife 1x cmp und 2x add (i++ und satz). Die while-Schleife hat nur 1x add.
Außerdem benötigt die while-Schleife nur ein einzelnes Register um pos zu halten, die for-Schleife muss satz und i halten (also 2).
Zusätzlich reduziert sich die Zahl der Speicherzugriffe, da nur gegen (const)'\0' getestet wird, und nicht gegen die lokale Variable len.

Best practice? Etwas so triviales wie ein strlen() durch ein selbst gerolltes strlen()-Imitat zu ersetzen in der vagen Hoffnung, daß es "etwas mehr speed" liefert, nennst du "best practice"??

 

[IceMatrix]

Wo bitte ist hier ein strlen()-Immitat? Wenn du keine Ahnung hast, dann halt dich einfach raus!

Ergänzung (10. März 2011)

Aber für alle die es mal genau haben wollen.. hier die for-Variante (jeweils gcc -O2)

.text:080484EF mov [esp+0A0h+var_A0], esi
.text:080484F2 call _strlen ; Unnötiger strlen(), allerdings aus Loop heraus optimiert
.text:080484F7 xor edx, edx
.text:080484F9 mov edi, eax
.text:080484FB jmp short loc_804852B
Belegte Register: esi, edx, edi -> 3 Register!
.text:080484FB ; ---------------------------------------------------------------------------
.text:080484FD align 10h
.text:08048500
.text:08048500 loc_8048500: ; CODE XREF: main+ADj
.text:08048500 movzx ecx, byte ptr [esi+edx] Index-Berechnung
.text:08048504 lea eax, [ecx-61h]
.text:08048507 cmp al, 19h
.text:08048509 ja short loc_8048516
.text:0804850B movsx eax, cl
.text:0804850E add [esp+eax*4+0A0h+var_214], 1
.text:08048516
.text:08048516 loc_8048516: ; CODE XREF: main+89j
.text:08048516 lea eax, [ecx-41h]
.text:08048519 cmp al, 19h
.text:0804851B ja short loc_8048528
.text:0804851D movsx ecx, cl
.text:08048520 add [esp+ecx*4+0A0h+var_194], 1
.text:08048528
.text:08048528 loc_8048528: ; CODE XREF: main+9Bj
.text:08048528 add edx, 1
.text:0804852B
.text:0804852B loc_804852B: ; CODE XREF: main+7Bj
.text:0804852B cmp edx, edi
.text:0804852D jnz short loc_8048500
.text:0804852F mov esi, 61h
.text:08048534 lea esi, [esi+0]
.text:08048538

Jetzt leg da nochmal bisschen Register Pressure drauf, dann haste Spilling und die Performance geht nochmal deutlich in die Knie.

Variante mit while:
; Kein strlen(), somit nur ein einzelnes Durchlaufen des Arrays,
Belegte Register: esi -> 1 Register!
.text:080484BF jmp short loc_80484F1
.text:080484BF ; ---------------------------------------------------------------------------
.text:080484C1 align 8
.text:080484C8
.text:080484C8 loc_80484C8: ; CODE XREF: main+A6j
.text:080484C8 lea edx, [eax-61h]
.text:080484CB cmp dl, 19h
.text:080484CE ja short loc_80484DB
.text:080484D0 movsx edx, al
.text:080484D3 add [esp+edx*4+0A0h+var_214], 1
.text:080484DB
.text:080484DB loc_80484DB: ; CODE XREF: main+7Ej
.text:080484DB lea edx, [eax-41h]
.text:080484DE cmp dl, 19h
.text:080484E1 ja short loc_80484EE
.text:080484E3 movsx eax, al
.text:080484E6 add [esp+eax*4+0A0h+var_194], 1
.text:080484EE
.text:080484EE loc_80484EE: ; CODE XREF: main+91j
.text:080484EE add esi, 1
.text:080484F1
.text:080484F1 loc_80484F1: ; CODE XREF: main+6Fj
.text:080484F1 movzx eax, byte ptr [esi] Keine Indexberechnung nötig!
.text:080484F4 test al, al
.text:080484F6 jnz short loc_80484C8
.text:080484F8 mov esi, 61h
.text:080484FD lea esi, [esi+0]
.text:08048500


Und jetzt noch ein Paar Worte zur GCC-Optimierung von strlen() aus der for-Schleife heraus:
Änder doch mal den Quellcode etwa so:

// buchstaben zählen
for(i = 0; i < strlen(satz); i++) {
char c = satz;

if(c >= 'a' && c <='z')
anzahl[c-'a']++;

usleep(1);

if(c >= 'A' && c <='Z')
anzahl[c-'A']++;
}

Ich habe hier ein usleep() eingebaut. Es könnte aber auch irgendwas anderes sein, was nicht Teil der aktuellen C-Datei ist. Dann passiert nämlich wie oben beschrieben das hier:

.text:08048521 jmp short loc_8048564
.text:08048521 ; ---------------------------------------------------------------------------
.text:08048523 align 8
.text:08048528
.text:08048528 loc_8048528: ; CODE XREF: main+C2j
.text:08048528 movzx edi, byte ptr [esp+esi+0A0h+var_26]
.text:0804852D lea eax, [edi-61h]
.text:08048530 cmp al, 19h
.text:08048532 ja short loc_8048541
.text:08048534 mov edx, edi
.text:08048536 movsx eax, dl
.text:08048539 add [esp+eax*4+0A0h+var_214], 1
.text:08048541
.text:08048541 loc_8048541: ; CODE XREF: main+82j
.text:08048541 mov [esp+0A0h+var_A0], 1
.text:08048548 call _usleep
.text:0804854D lea eax, [edi-41h]
.text:08048550 cmp al, 19h
.text:08048552 ja short loc_8048561
.text:08048554 mov eax, edi
.text:08048556 movsx edi, al
.text:08048559 add [esp+edi*4+0A0h+var_194], 1
.text:08048561
.text:08048561 loc_8048561: ; CODE XREF: main+A2j
.text:08048561 add esi, 1
.text:08048564
.text:08048564 loc_8048564: ; CODE XREF: main+71j
.text:08048564 lea edx, [esp+0A0h+var_26]
.text:08048568 mov [esp+0A0h+var_A0], edx
.text:0804856B call _strlen ; strlen() jetzt _innerhalb_ der Schleife!!
.text:08048570 cmp eax, esi
.text:08048572 ja short loc_8048528
.text:08048574 mov esi, 61h
.text:08048579 lea esi, [esi+0]



Eine kleine Anmerkung noch:
Es macht Sinn nicht
char c = satz;
sondern
unsigned char c = (unsigned char)satz;


Macht hier im konkreten Fall zwar keinen Unterschied, da die Buchstaben alle kleiner als 0x80 sind, aber wenn man andere Zeichen >=0x80 zählen will gibts
hier Probleme! Der Array-Index kann dann nämlich negativ werden (integer overflow)!!

Beispiel: c = 0x80 -> movsx eax, dl ergibt 0xffffff80 -> kleiner als 0!

 

[antred]

Das

const char *pos = satz;

while (*pos != '\0') {
    char c = *pos++;
    ....           
}

ist semantisch das gleiche wie das

const int length = strlen( satz );
for ( int i = 0; i < length; ++i )
{
      char c = satz[i];
}

Nur daß die untere Variante deutlich lesbarer ist als deine Lösung mit dem selbstgerollten strlen()-Ersatz. Und dein ganzes Register-Rumgeeiere kannst du dir stecken. Schreib mal ein sinnvolles Programm, und dann beweis mal mittels eines Profilers, daß diese "Optimierung" einen relevanten Performance-Gewinn bringt. Ohne das vorher mit einem Profiler verifiziert zu haben, sind solche tollen Optimierungsversuche nichts weiter als Zeitverschwendung.

Im übrigen habe ich mich nie zu der 1. Variante (strlen() innerhalb der Schleife) bekannt. Daß das nicht die eleganteste Lösung ist, erkennt man auch ohne hier groß mit seinem Assemblerwissen Eindruck schinden zu wollen.

 

[IceMatrix]

Manche Leute sind halt beratungsresistent.. du bist das beste Beispiel dafür. Deine Versuche hier Gift zu spucken kannst du dir übrigens sparen.

Thread bitte schließen!