Welche Funktion ist schneller: strcmp oder strlen?

Mr X

Da grundsätzlich erstmal die gleichen (lowlevel-)Mittel (zuzüglich weiterer; Ausnahme ist "restrict") zur Verfügung stehen wie bei C und beides (oft vom gleichen Compiler) zu Maschinencode kompiliert wird, gibt es keinen prinzipiellen Geschwindigkeitsunterschied. Wenn ein Programm dadurch langsamer wird, dass man es als C++-Code übersetzt, würde ich das auf den Compiler schieben.

Swordfish

...

hustbaer

@Mr X
Was einem bei C++ ein wenig reinscheissen kann sind Aufrufe über Funktionszeiger bzw. Aufrufe von Code in DLLs/SOs.

Wenn man es dem Compiler nämlich nicht anders sagt, gehen die meisten Compiler davon aus dass die so aufgerufenen Funktionen Exceptions werfen können, und müssen dementsprechend den nötigen Verwaltungscode in die aufrufende Funktion einbauen.
Weil halt, soweit ich weiss, noch kein Compiler das Suchen des zuständigen Handlers und das Stack-Unwinding 100% table-driven erledigen kann.

So lange man reinen C-Style Code schreibt, also keine Destruktoren etc. verwendet, sollte es allerdings wirklich egal sein. Weil ja dann auch kein Exception-Verwaltungscode in den aufrufenden Funktionen anfällt.

volkard

hustbaer schrieb:

@Mr X
Was einem bei C++ ein wenig reinscheissen kann sind Aufrufe über Funktionszeiger bzw. Aufrufe von Code in DLLs/SOs.

Wenn man es dem Compiler nämlich nicht anders sagt, gehen die meisten Compiler davon aus dass die so aufgerufenen Funktionen Exceptions werfen können, und müssen dementsprechend den nötigen Verwaltungscode in die aufrufende Funktion einbauen.
Weil halt, soweit ich weiss, noch kein Compiler das Suchen des zuständigen Handlers und das Stack-Unwinding 100% table-driven erledigen kann.

So lange man reinen C-Style Code schreibt, also keine Destruktoren etc. verwendet, sollte es allerdings wirklich egal sein. Weil ja dann auch kein Exception-Verwaltungscode in den aufrufenden Funktionen anfällt.

Daß richtig verwendete Exceptions den Code schneller machen, hatten wir doch schonmal festgetellt.
Weil man anderenfalls jeden einzelnen Funktionsaufruf, der mißlingen könnte (egal wie unwahrscheinlich), mit if prüfen müßte, ob er geklappt hat.

hustbaer

@volkard
Lies meinen Beitrag nochmal.

Ich spreche von Code der keine Exceptions verwendet (ausser vielleicht das was C++ von sich aus wirft + ein catch ganz aussen in main() ), dafür aber Exception-Handling aufgedreht hat und viele indirekte Funktionsaufrufe verwendet.

Und genau in so einem Fall stimmt die Annahme "you only pay for what you use" bei C++ eben nicht.

Natürlich könnte man solchen Code umschreiben auf schönen Exceptions-verwendenden C++ Code, und in vielen Fällen wird der dann auch schneller sein als das was man vorher hatte. Darum gings mir aber nicht.

Ethon

Muss halt der Autor der DLL in die Funktionsdeklerationen noexcept, throw(), eine Compiler-Extension oder was weiß ich packen.

Erhard Henkes

..
strlen sollte eigentlich schneller sein. Kannst ja in den Code eine Stopp-Uhr einbauen.

hustbaer

@Erhard Henkes
strcmp kann vorzeitig (=beim ersten gefundenen Mismatch) abbrechen.
strlen nicht.

Daher ist - abgesehen von Spezialfällen - strcmp schneller.

volkard

Erhard Henkes schrieb:

size_t strlen(const char* str)
{
    size_t retval = 0;
    for (; *str != '\0'; ++str)
        ++retval;
    return retval;
}

int strcmp(const char* s1, const char* s2)
{
    while ((*s1) && (*s1 == *s2))
    {
        ++s1;
        ++s2;
    }
    return (*s1 - *s2);
}

strlen sollte eigentlich schneller sein. Kannst ja in obigen Code eine Stopp-Uhr einbauen.

Hab seit 15 Jahren kein Compilat gesehen, wo der strlen-Aufruf ohne bit twiddeling abging, außer natürlich der Compiler wußte, daß er sehr kurz, oder sowas war und haute ein REP rein, um den Funktionsaufruf zu sparen oder so.
http://stackoverflow.com/questions/14041750/how-the-magic-bits-are-improving-the-strlen-function-in-glibc

und diese methode ist wirklich schneller? mir erscheints unnötig kompiliziert.

warum ist diese bitgeschichte jetzt schneller als einfaches byte-zählen?

volkard

asi schrieb:

und diese methode ist wirklich schneller? mir erscheints unnötig kompiliziert.

warum ist diese bitgeschichte jetzt schneller als einfaches byte-zählen?

Weil man dabei weniger Schleifen-Sachen machen muss. Nicht für jedes elende Byte testen und prüfen und springen, sondern nur für jedes vierte Byte. Dafür halt am Ende eine kleine Nachlese machen.
In der Schleife ist eine 4-Byte-Operation nicht teurer als eine Byte-Operation. So simple Sachen kann der Prozzi in einem Takt, egal, ob 8 oder 32 Bits.

volkard schrieb:

In der Schleife ist eine 4-Byte-Operation nicht teurer als eine Byte-Operation. So simple Sachen kann der Prozzi in einem Takt, egal, ob 8 oder 32 Bits.

Der Algorithmus hat einen Haken, bei einem bestimmten Muster tritt ein "misfire" auf, dann kostet einen das den Bithack + 4 ifs. Wenn der ganze String so aufgebaut ist, dürfte das naive strlen() besser sein.

strlen ist wieder ein Beispiel dafür, dass ifs gar nicht so langsam sind (scheinbar ein Lieblings-Dogma von volkard).
Man könnte ja testen

for (;; str += 4)
  if ((long)str[0] * str[1] * str[2] * str[3] == 0)
    // Nachauslese

aber da ist einem Branch-Prediction lieber.

volkard

prozzi schrieb:

volkard schrieb:

In der Schleife ist eine 4-Byte-Operation nicht teurer als eine Byte-Operation. So simple Sachen kann der Prozzi in einem Takt, egal, ob 8 oder 32 Bits.

Der Algorithmus hat einen Haken, bei einem bestimmten Muster tritt ein "misfire" auf, dann kostet einen das den Bithack + 4 ifs. Wenn der ganze String so aufgebaut ist, dürfte das naive strlen() besser sein.

Jo, und? Trotzdem sollte der Compilerbauer als default den nehmen, der fast immer schneller ist, oder?
Oh, er kann jetzt "gehackt" werden, mit einem DOS-Angriff, wo er viermal so lahm wird. Das nehmen wir mal in Kauf.

volkard

prozzi schrieb:

strlen ist wieder ein Beispiel dafür, dass ifs gar nicht so langsam sind (scheinbar ein Lieblings-Dogma von volkard).
Man könnte ja testen
for (;; str += 4)
  if ((long)str[0] * str[1] * str[2] * str[3] == 0)
    // Nachauslese
aber da ist einem Branch-Prediction lieber.

Das ist eine gute Idee. Da das Multiplizieren nur noch 6 Takte kostet, vielleicht sollte man so unrollen. Die Idee hast Du verstanden.
Naja, 6 reicht dann wieder nicht, weil die Schleifen von supersubsklalaren I7s durchgewürkst werden. Da muss man halt flexibel sein. Mag sein, daß man in 15 Jahren strlen am besten mit Divisionen durchführt. Oder wieder mit gant schlichten Schleifen auf char*.

hustbaer

@prozzi
"ifs" sind lahm, wenn sie oft unterschiedlich ausgehen und/oder man keine gute Branch-Prediction hat.
Wenn sie dagegen wie in strlen fast immer gleich ausgehen, dann sind sie nicht so schlimm.

Ethon

Da ist zb das __builtin_expect von GCC sehr praktisch - Denn man liegt sowieso nur 1x falsch und n-1x richtig damit.

volkard schrieb:

prozzi schrieb:
strlen ist wieder ein Beispiel dafür, dass ifs gar nicht so langsam sind (scheinbar ein Lieblings-Dogma von volkard).
Man könnte ja testen
for (;; str += 4)
  if ((long)str[0] * str[1] * str[2] * str[3] == 0)
    // Nachauslese
aber da ist einem Branch-Prediction lieber.
Das ist eine gute Idee. Da das Multiplizieren nur noch 6 Takte kostet, vielleicht sollte man so unrollen. Die Idee hast Du verstanden.
Naja, 6 reicht dann wieder nicht, weil die Schleifen von supersubsklalaren I7s durchgewürkst werden. Da muss man halt flexibel sein. Mag sein, daß man in 15 Jahren strlen am besten mit Divisionen durchführt. Oder wieder mit gant schlichten Schleifen auf char*.

6 Takte für ne Multiplikation? Oder meinst du die 3? Das hört sich extrem langsam an.

hustbaer

Was zu den Multiplikationskosten noch dazukommt sind die "unpack" Kosten. Also aus einem DWORD 4 Ints zu machen.

Ohne MMX/SSE/... ist das nämlich auch ziemlich langsam, weil man halt viele Befehle dafür braucht.
Mit MMX/SSE/... könnte man aber vermutlich irgendwas machen was noch schneller als die DWORD Variante ist.

Und... müsste sich das "false positive" nicht sogar vermeiden lassen indem man das Carry- bzw. Overflow-Flag prüft? Ich hab die i386 Befehle und welche Flags die jeweils modifizieren bzw. prüfen nicht im Kopf - könnte sein dass es sogar ohne zusätzlichen bedingten Sprung geht.

Wäre es vielleicht schneller, sie zu addieren oder zu ver-UND-en?