C Laufzeit meiner modifizierten memcmp()-implementierung

[asdfman]

Schönengutenabend. Hab da mal eine Frage!

strcmp(), memcmp() undsoweiter brechen normalerweise beim Auftreten des ersten Unterschieds ab. Ich möchte das vermeiden, deshalb habe ich eine eigene Version von memcmp gebastelt:

int my_memcmp(const void *buf1, const void *buf2, size_t len) {
	size_t index;
	uint8_t *cbuf1 = buf1, *cbuf2 = buf2;
	int diff, ret = 0;

	for(index = 0; index < len; index++) {
		diff = cbuf1[index] - cbuf2[index];
		if(diff && !ret)
			ret = diff;
		else
			diff = ret;
	}

	return ret;
}

Ich bin nun wirklich kein Experte für Compiler und Optimierung und andere Lowlevel-Sachen. Deshalb meine Frage an diejenigen, die sich damit auskennen:
Kann ich davon ausgehen, dass die Laufzeit dieser Funktion ausschließlich von len abhängt?
Wenn nein: Bitte erklärt mir, warum. Finde solche Dinge sehr interessant. Bonuspunkte für Verbesserungsvorschläge :3

 

[antred]

Ich bin nun wirklich kein Experte für Compiler und Optimierung und andere Lowlevel-Sachen.

Ich auch ned. Aber was mich wundert ....

strcmp(), memcmp() undsoweiter brechen normalerweise beim Auftreten des ersten Unterschieds ab. Ich möchte das vermeiden [...]

Warum? Mit dem Auftreten des ersten Unterschiedes ist doch das Ergebnis bereits klar. Weshalb also weitermachen?

 

[Miuwa]

Was ist der Sinn von demhier:

if(diff && !ret)
     ret = diff;
else
    diff = ret;

Was die genaue Laufzeit angeht: auf welcher Platform soll der Code denn laufen?

EDIT:
Und ist dir eine konstante Laufzeit wichtiger als eine geringere maximale Laufzeit?

 

[aroxx]

also ein experte bin ich auch nicht. aber mal meine amateuranalyse:

ich gehe davon aus, dass die laufzeit tatsächlich ausschließlich von len abhängt.
begründung: in der schleife hast du nur eine subtraktion und einen if-block. subtraktionen gehen alle gleich schnell sage ich jetzt mal.

(if könnte ein problem sein, wenn du häufig zwischen dem if und dem else wechselst, das heißt dass die sprungvorhersage oft versagen würde und die pipeline wieder neu befüllt werden müsste.
aber da du in der if und in der else anweisung die selben variablen in den registern haben musst gehe ich davon aus, dass es völlig egal ist welche arten von strings du vergleichst. )
edith findet, dass das sehr an den haaren herbeigezogen ist, weil du höchstens 1x im if teil sein kannst und sonst eh im else bist.

achja: mir hat sich natürlich auch die frage nach dem warum (???) gestellt
der return wert wird ja nicht mehr überschrieben, sobald er einmal gesetzt wurde... warum also nicht abbrechen?

 

[nbzklr]

Die Laufzeit ist linear und hängt von len ab.
Wovon solltes es denn sonst abhängen?
Mit compiler Optimierung hat das auch nichts zu tun.
Die Laufzeit eines Algorithmus ist immer nur eine Abschätzung (nach oben), wobei solche Details wie die Anzahl der Taktzyklen ignoriert werden.

 

[-Razzer-]

Welchen Sinn hat der else Fall?
So wie dein Code aussieht kannst du den Else Fall löschen und im Then Fall gibst du direkt ret zurück wenn er da reinspringt.
Fall er durchläuft ohne einmal im Then Fall gewesen zu sein gibst du ja den Initialwert von ret = 0 zurück.

 

[Miuwa]

@noobzkillor: Je nach Platform kann das von allem Möglichen abhängen: Sprungvorhersage, Speicherlayout, Cache...
Und da ret sich nichtmehr ändert, sobald zum ersten mal einen Unterschied auftritt darf der Compiler danach theoretisch sogar eine break Anweisung einfügen.

 

[asdfman]

Warum? Mit dem Auftreten des ersten Unterschiedes ist doch das Ergebnis bereits klar. Weshalb also weitermachen?

Damit ein potentieller Angreifer keine Information darüber erhält, an welcher Stelle ein untergeschobenes Paket vom erwarteten Inhalt abweicht.

Welchen Sinn hat der else Fall?

Die Idee ist, dass wenn der Ausdruck wahr ist, eine Zuweisung durchgeführt wird. der Elsefall führt eine (unnötige) Zuweisung durch, damit beides gleich lang dauert.

Und da ret sich nichtmehr ändert, sobald zum ersten mal einen Unterschied auftritt darf der Compiler danach theoretisch sogar eine break Anweisung einfügen.

Ganz schlecht. Hast du einen Vorschlag, wie ich dafür sorgen kann, dass das Ergebnis erst feststeht, wenn beide Puffer komplett durchlaufen wurden?

 

[aroxx]

@noobzkillor: Je nach Platform kann das von allem Möglichen abhängen: Sprungvorhersage, Speicherlayout, Cache...
Und da ret sich nichtmehr ändert, sobald zum ersten mal einen Unterschied auftritt darf der Compiler danach theoretisch sogar eine break Anweisung einfügen.

ich bin neugierig... hast du sowas schonmal in der praxis gesehen?

 

[kuddlmuddl]

Bonuspunkte für Verbesserungsvorschläge

Es scheint keinen Unterschied zu machen Quelle C++, Quelle C aber ich finde index += 1 oder ++index intuitiver zu lesen als index++.. evtl. nur Geschmackssache. Hab mich da immer nach diesem hier gerichtet: Google C++ StyleGuide

Kann ich davon ausgehen, dass die Laufzeit dieser Funktion ausschließlich von len abhängt?
Wenn nein: Bitte erklärt mir, warum. Finde solche Dinge sehr interessant.

Ich fürchte die Frage ist komplizierter zu beantworten als man denkt. Erstmal ist natürlich die Frage: Was genau für eine Laufzeit interessiert dich. Es gibt ja verschiede Landau-Symbole und oft betrachtet man O, also worst case auch wenn average-case in der Realität interessanter ist. Aber auch unabhängig davon ist es komplizierter als Aroxx schreibt eben weil das Ergebnis schnell feststehen kann. Es könnte also gut sein, dass der Compiler äquivalenten Code erzeugt, der tatsächlich wieder beim ersten Auftreten eines Unterschieds abbricht und dann hängt die Laufzeit eben nicht mehr nur von len sondern auch vom Inhalt deiner Arrays ab!

Selbst wenn diese Äquivalenz nicht erkannt wird, schlägt die Branche-Prediction natürlich sehr stark ins Gewicht. Dh wenn früh ein Duplikat erkannt wurde ist ja !ret nie mehr erfüllt und das ganze if-else kostet keine Laufzeit mehr. Siehe auch hier: Why is processing a sorted array faster than an unsorted array?

Wenn der Compiler erkennt, dass das Ergebnis schon feststeht, könnte er ja tatsächlich sowas draus machen, oder nicht?

int my_memcmp(const void *buf1, const void *buf2, size_t len) {
    size_t index;
    uint8_t *cbuf1 = buf1, *cbuf2 = buf2;
    
    for(index = 0; index < len; index++)
        if(cbuf1[index] != cbuf2[index])
            return cbuf1[index] - cbuf2[index];
    return 0;
}

Auf Stackoverflow würde jetzt sofort jemand mit -s compilieren und zeigen ob und ab welchem Optimierungsstufe O(1,2,3) und für welchen Compiler diese Optimierung tatsächlich stattfindet weil der Assembler-Code identisch ist, aber Assembler ist wirklich nicht meine Welt.

 

[Simpson474]

Die Idee ist, dass wenn der Ausdruck wahr ist, eine Zuweisung durchgeführt wird. der Elsefall führt eine (unnötige) Zuweisung durch, damit beides gleich lang dauert.

Den Else-Zweig sollte so gut wie jeder brauchbare Compiler entfernen: theoretisch könnte ein sehr guter Compiler sogar bei der ersten Abweichung abbrechen, da eine weitere Ausführung der Funktion zu keiner Änderung führen kann.

 

[asdfman]

Erstmal ist natürlich die Frage: Was genau für eine Laufzeit interessiert dich. Es gibt ja verschiede Landau-Symbole

Mich interessiert die Zeit, die auf einer Stoppuhr vergeht, die beim Sprung in die Funktion gestartet wird. Worst, best und average case sollen identisch sein und ausschließlich von len abhängen.

€: Huch, ganz übersehen!

Was die genaue Laufzeit angeht: auf welcher Platform soll der Code denn laufen?

asdf@chelloveck:~/src$ uname -m
i686

Und die generischen x86 und x64 Targets von Visual Studio.

 

[calav3ra_de]

Die Laufzeit ist linear/n (=len)

Was der TE hier macht ist die Funktion memcmp() zu ändern, denn in der Dokumentation von memcmp heißt es zB: "<0: the first byte that does not match in both memory blocks has a lower value in ptr1 than in ptr2 (if evaluated as unsigned char values)"

Das heißt wenn das erste zu vergleichende Byte kleiner ist, wird ein negativer Wert zurück gegeben. Das ist zuerst mal wichtig, falls man sich auf so einen return-Wert verlassen möchte. Es liefert übrigens auch den Unterschied als Zahl zurück.

Wen man das nicht benötigt, und unbedingt (wie der TE), ohne Vergleich durchlaufen will, dann kann man das ganze IF Gedöns weglassen und einfach nur schreiben:

diff = (bool)(cbuf1[index] != cbuf2[index]); // diff als bool deklarieren

und dann eben diff zurückgeben, entweder 0/1 je nachdem ob es einen unterschied gibt.

Wenn man jetzt weiß, das die zu prüfenden Speicherblöcke alle sehr kurz sind, dann könnte man ohne das IF möglicherweise schnelleren Code erhalten, da ein Sprung natürlich die ganze Pipeline verhageln kann.

Man kann sich natürlich aber auch vorstellen, das ein vorzeitiges return, Unmengen an Zeit sparen kann, falls len eine sehr sehr große Zahl ist.

Also. Optimieren je nach Situation und vorliegenden Daten, und dann auch testen und vergleichen. Ansonsten ist Optimierung reinste Zeitverschwendung.

 

[kuddlmuddl]

Oha da sind ja nun noch mehr Beiträge gekommen als ich anfangs gesehen habe. Ein Beispiel wo es eben nicht nur von len abhängt selbst wenn der Compiler nicht das else weg-optimiert ist meine oben gepostete branch-prediction. Wer also immer noch sagt die Laufzeit hängt nur von len ab liegt hier definitiv falsch! Der Inhalt der Arrays kann locker Faktor 10 ausmachen. (da asdfman ja nicht nur worst-case sondern auch best und average-case abdecken will)

Mich interessiert die Zeit, die auf einer Stoppuhr vergeht, die beim Sprung in die Funktion gestartet wird. Worst, best und average case sollen identisch sein und ausschließlich von len abhängen.

Wenn du den Compiler zu konstanter Laufzeit zwingen willst solltest du mit volatile arbeiten. Das kann für große len messbar bremsen aber verhindert, dass so eine Optimierung dir die erhoffte Laufzeit ruiniert.

volatile int ret;
int my_memcmp(const void *buf1, const void *buf2, size_t len) {
    size_t index;
    uint8_t *cbuf1 = buf1, *cbuf2 = buf2;
    ret = 0;
    for(index = 0; index < len; index++) {
        int diff = cbuf1[index] - cbuf2[index];
        if (diff != 0 && ret == 0)
            ret = diff;
    }
    return ret;
}

volatile1, volatile2

Volatile sorgt dafür, dass der compiler bei jeder Verwendung der Variable erneut prüft welchen Wert sie hat.
Dh nur weil in einer Zeile ret auf diff gesetzt wird und somit zB != 0 ist, heißt das noch lange nicht, dass er sich darauf verlässt dass beim if (diff != 0 && ret == 0) ret !=0 immernoch angenommen wird.

Das hört sich zwar komisch aber aber wird sofort klar, wenn man erkennt wo Volatile verwendet wird: Bei Interrupt-Service-Routinen in der µC Welt. Es kann nämlich sein, dass vor dem if aber nach dem ret= ein IRQ reinkommt, eine ISR abläuft und daher der Wert dieser Variablen geändert wird. Damit dies aber überhaupt möglich ist (damit ret von außerhalb des Funktions-Scopes erreicht werden kann) habe ich ret außerhalb der Funktion deklariert, weil der Compiler sonst evtl wieder optimieren darf.

 

[calav3ra_de]

Die durschnittliche Laufzeit in seinem Testlauf hängt (ursprünglich) davon ab, was für Daten er verwendet. Er kann also nur ein memcmp verwenden, das wie von mir oben erwähnt gar keine Sprünge nutzt und nur (nach dem vollständigen Durchlauf) zurückgibt ob es einen Unterschied (bool) gibt.

Damit sind alle Laufzeiten wie gefordert gleich. Schöne Hausaufgabe! ;-)

Und übrigens: Wegoptimiert wird bei C++ nicts zur Laufzeit, nur bei Kompilierung.

 

[antred]

Damit ein potentieller Angreifer keine Information darüber erhält, an welcher Stelle ein untergeschobenes Paket vom erwarteten Inhalt abweicht.

Damit ein Angreifer überhaupt die Laufzeit eines isolierten memcmp()-Aufrufes mit solch einer hohen Genauigkeit messen kann, braucht er aber doch ohnehin nahezu uneingeschränkten Zugriff aus das System - Debuggen / Profilen muß möglich sein. Und wann er das tun kann, dann kann er doch wahrscheinlich ohnehin direkt auf die 2 Speicherbatzen schauen, die verglichen werden.

Oder sehe ich das komplett falsch?

 

[asdfman]

Die durschnittliche Laufzeit in seinem Testlauf hängt davon ab, was für Daten er verwendet. Er kann also nur ein memcmp verwenden, das wie von mir oben erwähnt gar keine Sprünge nutzt und nur zurückgibt ob es einen Unterschied (bool) gibt.

Ich werde gern in der zweiten Person angesprochen. Ist eine kleine Macke von mir und das kann man natürlich nicht wissen, wenn man mich nicht kennt.
Es ist im Moment sogar tatsächlich so, dass die Art des Unterschieds für mich keine Rolle spielt. Es ist egal wo und wie sich die Puffer unterscheiden, ich will nur wissen, ob sie gleich sind oder nicht.
Ich habe das erstmal so implementiert, dass man die Funktion komplett als Ersatz für memcmp() benutzen kann. Wenn mein Ziel sich aber nicht mit einer Funktion erreichen lässt, die das Selbe
Verhalten wie memcmp() hat, kann ich das natürlich auch beliebig anders machen.

Damit sind alle Laufzeiten wie gefordert gleich. Schöne Hausaufgabe! ;-)

Die Uni habe ich lange hinter mir und wie man vielleicht an diesem Thread erkennen kann, hatte meine Ausbildung nichts mit Programmieren zu tun.

Und übrigens: Wegoptimiert wird bei C++ nicts zur Laufzeit, nur bei Kompilierung.

Habe ich nie behauptet. Die Bemerkung über Optimierung zielte darauf, dass mir z.B. das Else weggemacht wird, mit dem ich die Originalzuweisung zeitlich ausgleichen will.

 

[Miuwa]

@aroxx:
Die Gelegenheiten, bei denen ich mir den generierten Assemblercode ansehen musste kann ich an meinen zehn Fingern abzählen und es ging nie darum sicherzustellen, dass unnötiger Code auch wirklich ausgeführt wird. Von daher: nein, habe ich noch nie erlebt und es ist sicher keine Optimierung, die ich erwarten würde. Wenn man sich allerdings schon um solche Sidechannelattacken Gedanken machen muss, dann muss man auch darüber nachdenken, was möglich ist und nicht nur, was wahrscheinlich ist. Compiler werden ja auch weiterentwickelt.

Worst, best und average case sollen identisch sein und ausschließlich von len abhängen.

Da du wohl kein Echtzeit Betriebssystem nutzt und der Code auf x86 Prozessoren laufen soll ist das praktisch unmöglich .
Falls es dir reicht, dass es keinen vorhersehbaren Zusammenhang zwischen Pufferinhalt und Ausführungszeit gibt, würde ich wohl auch auf volatile zurückgreifen, obwohl ich nicht behaupten kann alle Implikationen genau zu kennen - bisher habe ich es nur für Registerzugriffe benutzt (wofür sie ja auch gedacht sind).
Generell würde ich aber vorschlagen: Prüfe den Assemblercode und messe selbst nach. Und wiederhole das ganze jedes Mal, wenn du Änderungen am Code vornimmst oder den Compiler updatest.

Einen alternativen Algorithmus, den man ausprobieren könnte, wäre die Absolutwerte der Differenzen aufzusummieren und am Ende auf Null zu prüfen. Das dürfte der Compiler zwar genause optimieren, aber ich fände es verständlicher, als deine Konstruktion.

 

[Nai]

Wenn die Laufzeit gar nicht von der Eingabe abhängen soll, würde ich folgenden Trick machen:
-Laufzeit extrem worst case abschätzen (z.B. 1 ms pro 10 kbyte)
-so lnage die worst case Laufzeit unterschritten ist wird am Ende der Funktion gewartet.

 

[Freezedevil]

Es hängt natürlich auch stark vom O-flag ab was von deinem, aus funktioneller Sicht überflüssigem, Code übrig bleibt. Ich hab die Funktion mal disassembliert.
-O0

================ B E G I N N I N G   O F   P R O C E D U R E ================



                                       ; 
                                       ; Section __text
                                       ; 
                                       ; Range 0x100000ed0 - 0x100000f92 (194 bytes)
                                       ; File offset 3792 (194 bytes)
                                       ; Flags : 0x80000400
                                       ; 
                     _my_memcmp:
0000000100000ed0         push       rbp                                         ; XREF=0x1000000d0
0000000100000ed1         mov        rbp, rsp
0000000100000ed4         mov        qword [ss:rbp+var_8], rdi
0000000100000ed8         mov        qword [ss:rbp+var_10], rsi
0000000100000edc         mov        qword [ss:rbp+var_18], rdx
0000000100000ee0         mov        rdx, qword [ss:rbp+var_8]
0000000100000ee4         mov        qword [ss:rbp+var_28], rdx
0000000100000ee8         mov        rdx, qword [ss:rbp+var_10]
0000000100000eec         mov        qword [ss:rbp+var_30], rdx
0000000100000ef0         mov        dword [ss:rbp+var_38], 0x0
0000000100000ef7         mov        qword [ss:rbp+var_20], 0x0

0000000100000eff         mov        rax, qword [ss:rbp+var_20]                  ; XREF=_my_memcmp+152
0000000100000f03         cmp        rax, qword [ss:rbp+var_18]
0000000100000f07         jae        0x100000f6d

0000000100000f0d         mov        rax, qword [ss:rbp+var_20]
0000000100000f11         mov        rcx, qword [ss:rbp+var_28]
0000000100000f15         movzx      edx, byte [ds:rcx+rax]
0000000100000f19         mov        rax, qword [ss:rbp+var_20]
0000000100000f1d         mov        rcx, qword [ss:rbp+var_30]
0000000100000f21         movzx      esi, byte [ds:rcx+rax]
0000000100000f25         sub        edx, esi
0000000100000f27         mov        dword [ss:rbp+var_34], edx
0000000100000f2a         cmp        dword [ss:rbp+var_34], 0x0
0000000100000f31         je         0x100000f4f

0000000100000f37         cmp        dword [ss:rbp+var_38], 0x0
0000000100000f3e         jne        0x100000f4f

0000000100000f44         mov        eax, dword [ss:rbp+var_34]
0000000100000f47         mov        dword [ss:rbp+var_38], eax
0000000100000f4a         jmp        0x100000f55

0000000100000f4f         mov        eax, dword [ss:rbp+var_38]                  ; XREF=_my_memcmp+97, _my_memcmp+110
0000000100000f52         mov        dword [ss:rbp+var_34], eax

0000000100000f55         jmp        0x100000f5a                                 ; XREF=_my_memcmp+122

0000000100000f5a         mov        rax, qword [ss:rbp+var_20]                  ; XREF=_my_memcmp+133
0000000100000f5e         add        rax, 0x1
0000000100000f64         mov        qword [ss:rbp+var_20], rax
0000000100000f68         jmp        0x100000eff

0000000100000f6d         mov        eax, dword [ss:rbp+var_38]                  ; XREF=_my_memcmp+55
0000000100000f70         pop        rbp
0000000100000f71         ret        
                        ; endp

-O3

================ B E G I N N I N G   O F   P R O C E D U R E ================



                                       ; 
                                       ; Section __text
                                       ; 
                                       ; Range 0x100000f60 - 0x100000f98 (56 bytes)
                                       ; File offset 3936 (56 bytes)
                                       ; Flags : 0x80000400
                                       ; 
                     _my_memcmp:
0000000100000f60         push       rbp                                         ; XREF=0x1000000d0
0000000100000f61         mov        rbp, rsp
0000000100000f64         xor        eax, eax
0000000100000f66         test       rdx, rdx
0000000100000f69         je         0x100000f8e

0000000100000f6b         nop        qword [ds:rax+rax+0x0]

0000000100000f70         movzx      r8d, byte [ds:rdi]                          ; XREF=_my_memcmp+44
0000000100000f74         movzx      ecx, byte [ds:rsi]
0000000100000f77         sub        r8d, ecx
0000000100000f7a         je         0x100000f83

0000000100000f7c         test       eax, eax
0000000100000f7e         jne        0x100000f83

0000000100000f80         mov        eax, r8d

0000000100000f83         inc        rdi                                         ; XREF=_my_memcmp+26, _my_memcmp+30
0000000100000f86         inc        rsi
0000000100000f89         dec        rdx
0000000100000f8c         jne        0x100000f70

0000000100000f8e         pop        rbp                                         ; XREF=_my_memcmp+9
0000000100000f8f         ret        
                        ; endp

Ich hab jetzt um diese Uhrzeit keine Lust mehr den ASM Code zu parsen, aber O3 streicht das schon ziemlich zusammen.