Welche Funktion ist schneller: strcmp oder strlen?

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?

hustbaer

Was genau willst du addieren? Addition wird ja bei der DWORD Variante eh schon verwendet.

Und die einzelnen Bytes addieren bringt nix, aus dem Ergebnis kann man nicht rauslesen ob eines davon Null gewesen sein könnte.
Verunden ginge, nur bei Verunden hätte man noch viel mehr False Positives. Und man würde nach wir vor viel rumshiften müssen, also wieder viele Instructions-per-DWORD.

Was ist mit if (!str[0] + !str[1] + !str[2] + !str[3] + !str[4] + !str[5] + !str[6] + !str[7] != 8) ?

hustbaer

Jo. Sollte gehen.
Nur wird das ziemlich sicher nicht schneller sein als jedes Byte einzeln zu prüfen.
Und auf jeden Fall nicht schneller als ein DWORD pro Durchlauf zu prüfen.