Nabend,
ich habe eine kurze Frage zum Ausschneiden eines bestimmten Zeichens aus
einem nicht null terminierten String. Hat dafür Jemand eine bessere Idee
als diese hier? Es soll also das Zeichen nicht ersetzt, sondern
überschrieben werden. Der String wird dabei natürlich auch kürzer.
Wichtig, es geht nur Standard C, kein C++ oder sonstwas. Danke schonmal.
MaWin schrieb:> Viel besser wirds wohl nicht werden.
Ja, aber fragen kann man ja mal. Bin am überlegen ob es was bringen
könnte wenn man nur dann kopiert wenn i != j ist. Wird dann aber wohl
auf den use-case ankommen. Aktuell geht es mir hauptsächlich darum aus
einem CR+LF ("\r\n") ein reines LF ("\n") zu machen, nur empfange ich
Zeichen nicht immer bis zum Zeilenende, sondern auch mal mehr oder
weniger pro Datenpaket. Es kann also vorkommen das direkt das erste
Zeichen ein verworfen werden müsste und in dem Fall eine Prüfung i != j
praktisch vollständig unnötig wäre.
> Ja, aber fragen kann man ja mal.
Nimm Pointer statt der haessilichen Indexe.
C ist doch kein BASIC. Dafuer sind Pointer schliesslich da.
Und quasi jede aktuelle CPU kann Indirekt+Postinkrement
in einem Zyklus.
Und die Zaehlschleife dann auch von len-1 to 0.
Wofuer die meissten CPUs auch etwas spezielles in petto haben.
Tim T. schrieb:> Der String wird dabei natürlich auch kürzer.> Wichtig
Wenn es ein Null-Terminierter String ist solltest du dir darüber mal
Gedanken manchen wo dieses steht wenn du den String verkürzt.
Tim T. schrieb:> Hat dafür Jemand eine bessere Idee> als diese hier?
Wenn du eine Schleife aus "Länge bis nächstes \r oder Ende" und "Block
nach vorne kopieren" machst, kann der Compiler die Geschichte besser
(oder überhaupt erst) vektorisieren, was ggf. schneller ist, je nach
Plattform und typischen Daten.
Würde aber mutmaßen, dass die Funktion schlicht keinen Flaschenhals
darstellt.
Tim T. schrieb:> Es kann also vorkommen das direkt das erste> Zeichen ein verworfen werden müsste und in dem Fall eine Prüfung i != j> praktisch vollständig unnötig wäre.
Einen winzigen Spezialfall zu prüfen ist häufig langsamer als die
redundante Rechnung selbst, besonders auf Architekturen mit Branch
Prediction, etc.
Irgend W. schrieb:> Tim T. schrieb:>> Der String wird dabei natürlich auch kürzer.>> Wichtig>> Wenn es ein Null-Terminierter String ist solltest du dir darüber mal> Gedanken manchen wo dieses steht wenn du den String verkürzt.Tim T. schrieb:> einem nicht null terminierten String.
Es ist eben kein null terminierter String und selbst wenn, wäre es noch
einfacher, da die Terminierung dann natürlich auch vorgezogen werden
würde.
Die Länge wird, wie man zweifelsfrei erkennen kann, von der Funktion
zurück gegeben.
Tim T. schrieb:> Bin am überlegen ob es was bringen> könnte wenn man nur dann kopiert wenn i != j ist.
Dafür jeden Schleifendurchlauf zu bremsen mit der zusätzlichen Abfrage
wird unterm Strich eher langsamer sein.
Wenn überhaupt, dann wäre es höchstens schneller eine Schleife davor zu
setzen, die nur hochrennt solange das Zeichen nicht gefunden wird.
Danach dann deine Schleife wie gehabt, ohne zusätzliche Tests.
Jemand schrieb:> Tim T. schrieb:>> Hat dafür Jemand eine bessere Idee>> als diese hier?>> Wenn du eine Schleife aus "Länge bis nächstes \r oder Ende" und "Block> nach vorne kopieren" machst, kann der Compiler die Geschichte besser> (oder überhaupt erst) vektorisieren, was ggf. schneller ist, je nach> Plattform und typischen Daten.> Würde aber mutmaßen, dass die Funktion schlicht keinen Flaschenhals> darstellt.
Ja, das war es ja was mich primär gestört hat, einen Flaschenhals hab
ich da nicht wirklich aber ich habe, wenn auch subjektiv, gemerkt das
ich dem Compiler das leben schwerer mache als nötig und darum kam ich
auf die Idee, das es eventuell dafür eine simple Standardvariante gibt.
> Tim T. schrieb:>> Es kann also vorkommen das direkt das erste>> Zeichen ein verworfen werden müsste und in dem Fall eine Prüfung i != j>> praktisch vollständig unnötig wäre.>> Einen winzigen Spezialfall zu prüfen ist häufig langsamer als die> redundante Rechnung selbst, besonders auf Architekturen mit Branch> Prediction, etc.
Ja, hatte ich mir schon ungefähr gedacht. Habs auch mal spaßeshalber auf
Pointer umgeschrieben aber am assembly hat sich garnichts verändert.
Klaus W. schrieb:> Tim T. schrieb:>> Bin am überlegen ob es was bringen>> könnte wenn man nur dann kopiert wenn i != j ist.>> Dafür jeden Schleifendurchlauf zu bremsen mit der zusätzlichen Abfrage> wird unterm Strich eher langsamer sein.>> Wenn überhaupt, dann wäre es höchstens schneller eine Schleife davor zu> setzen, die nur hochrennt solange das Zeichen nicht gefunden wird.> Danach dann deine Schleife wie gehabt, ohne zusätzliche Tests.
Ja, das würde etwas sparen, zumindest wenn das Zeichen erstmals spät im
String vorkommt.
Dieter H. schrieb:> Da kann man nichts mehr rausholen. Du musst über den String iterieren,> also bist du in O(n).
Ja, das war schon von Anfang an klar, hier geht es eher darum "wie sage
ich es meinem Compiler das er sich etwas cleverer anstellt".
Null terminiert ist der String auch immer noch nicht... Den restlichen
Senf spare ich mir einfach, kommt vor.
>> Interessant, werde es mal gegen meine überarbeitete Variante testen:
Habs jetzt mal getestet (x86_64, gcc 10.2.1), die Variante von achs ist
schneller (141 Takte) gegenüber meiner (193 Takte). Aus Interesse habe
ich auch noch die Variante von kyblord getestet und die war mit 258
Takten am langsamsten. Mit Optimierung O3 kommen die Varianten von achs
und mir auf 90 Takte und die von kyblord auf 159 Takte.
Braucht man das wirklich so oft?
Ich bin zwar kein Massstab, doch die letzten 20 Jahre habe ich das nicht
gebraucht. Ich habe einiges an Stringoperationen, doch diese Anforderung
hatte ich nie.
Und wenn ich es ab und zu mal brauche, warum muss ich das dann bis auf
den letzten Takt optimieren?
Also mein Frage: ihr braucht diese Funktion sehr oft, und seid deshalb
auf die 141 Takte angewiesen?
Beim meinem kleinem 48Mhz Arm M0, könnte ich 340425 String pro Sekunde
bearbeiten. Da wüßte ich gar nicht, wo ich so viele Strings her bekomme.
> die Variante von achs ist schneller
Ja sicher. Pointer statt Indize!
> und seid deshalb auf die 141 Takte angewiesen?
Bei Stringoperationen ist niemand auf 141 Takte angewiesen.
Sonst haette er die Strings schon lange gehasht oder anderweitig
fuer eine schnellere Verarbeitung gesorgt.
Es ist der grundsaetzliche geistige Habitus, wie man so etwas
in C formuliert.
Mit C-Programmen im BASIC-Style eben nicht.
3h schrieb:>> die Variante von achs ist schneller>> Ja sicher. Pointer statt Indize!>>> und seid deshalb auf die 141 Takte angewiesen?>> Bei Stringoperationen ist niemand auf 141 Takte angewiesen.>> Sonst haette er die Strings schon lange gehasht oder anderweitig> fuer eine schnellere Verarbeitung gesorgt.
Jein, es geht darum das ein "dauerhafter" Strom an Datenpaketen
(Messdaten, kein Text) über Netzwerk reinkommt, UDP mit Sequenzierung,
ohne Wiederholung (nicht im änderbaren Einflussbereich), weiter für
Steuerungszwecke verarbeitet wird. Bislang wurde der Datenstrom einfach
stumpf ins RAM geschrieben und von dort aus weiter verarbeitet. Jetzt
war die Überlegung vor dem Schreiben ins RAM diese Daten schon teilweise
aufzuarbeiten um die zeitnahe, spätere Auswertung zu vereinfachen. Das
Entfernen von '\r' war dabei nur, damit ich was zum testen habe (und
damit die geschriebenen Daten netter aussehen). Aber wie gesagt, eng ist
es an der Stelle nicht, eher war es das Gefühl es irgendwie suboptimal
zu machen. Der erste Schritt war da die Idee von Klaus W. die Prüfung
auf vorkommen des ersten zu entfernenden Zeichens vor die kopier
Schleife zu ziehen und der zweite Schritt war dann das Umstellen von
Indexen auf Pointer.
> Es ist der grundsaetzliche geistige Habitus, wie man so etwas> in C formuliert.> Mit C-Programmen im BASIC-Style eben nicht.
Bislang hatte ich damit keine Probleme, ich mag die Index Schreibweise
nur irgendwie lieber, genau so wie ich lieber for-Schleifen als while
benutze.
Habe aus dem Grund auch die Variante von achs auf for-Schleifen
umgeschrieben und dabei gemerkt das schon die Reihenfolge der
Schleifenbedingungen einen Unterschied in der Laufzeit macht, jedenfalls
ohne Optimierung. Ab O2 war es grundsätzlich egal ob man mit Indexen
oder Pointern geschrieben hat, es kam das Gleiche am Ende heraus.
Aktueller Stand:
1
intclean_string(char*buf,intlen,charc){
2
char*src,*dst;
3
for(src=buf;len-->0&&*src!=c;src++);
4
for(dst=src++;len-->0;src++){
5
if(*src!=c)*dst++=*src;
6
}
7
return(dst-buf);
8
}
Interessanterweise bewirkt schon ein Umkehrung von "len-- > 0 && *src !=
c" in "*src != c && len-- > 0" eine Verschlechterung der Laufzeit (ohne
Optimierung). Oder wenn man das Dekrementieren von len in die Anweisung
oder Fortsetzung schreibt.
Oliver S. schrieb:> Welche Stringgrößen werden den erwartet? Wenns da in die MB geht, könnte> man über memcpy nachdenken.
Die Stringgrößen sind jeweils maximal in der Größe der Payload eines
garantiert unfragmentierten UDP Paketes abzüglich einer Sequenznummer,
etc. also <= 500 Byte.
> diese Daten schon teilweise aufzuarbeiten
Dann mach es doch gleich richtig und tokenisiere die Eingabe
wenn das bei deinen Daten geht. Die Token wollen natuerlich
mit Bedacht gewaehlt werden.
Wenn man die Strings los ist, braucht man auch nicht mehr
darueber iterieren.
> Bislang hatte ich damit keine Probleme
Man muss immer mit Compilern rechnen, bei denen die
Optimierung nicht besonders gut ist.
Nebenbei wird auch das Debugging erleichtert.
Denn der aus der Indexrechnung optimierte (Pointer-)Code
hat nicht mehr viel mit der Quelle zu tun.
> Da kann man nichts mehr rausholen. Du musst über den String iterieren,> also bist du in O(n).
Lach, ja da spricht der typische Informatiker.
Theoretisch korrekt, praktisch aber abgeschlagen daneben.
Tim T. schrieb:> Interessanterweise bewirkt schon ein Umkehrung von "len-- > 0 && *src !=> c" in "*src != c && len-- > 0" eine Verschlechterung der Laufzeit
Das bewirkt halt, daß du ein Zeichen mehr (= zu viel) vergleichst, auch
wenn das dank der am Stringende stehenden 0 kein ernsthaftes Problem
ist.
Oliver
Oliver S. schrieb:> Tim T. schrieb:>> Interessanterweise bewirkt schon ein Umkehrung von "len-- > 0 && *src !=>> c" in "*src != c && len-- > 0" eine Verschlechterung der Laufzeit>> Das bewirkt halt, daß du ein Zeichen mehr (= zu viel) vergleichst, auch> wenn das dank der am Stringende stehenden 0 kein ernsthaftes Problem> ist.>> Oliver
Oh mann, ja da hatte ich wirklich ein Brett vorm Kopf aber jetzt wo du
es sagst, klar. Am Stringende steht aber auch kein '\0', aber zum
Problem wirds ja trotzdem nicht.
3h schrieb:> Bei Stringoperationen ist niemand auf 141 Takte angewiesen.>> Sonst haette er die Strings schon lange gehasht oder anderweitig> fuer eine schnellere Verarbeitung gesorgt.
Was haben Hashes mit der Entfernung einzelner Zeichen aus einem String
zu tun?
> Was haben Hashes mit der Entfernung einzelner Zeichen aus einem String> zu tun?
Du nimmst als Weg zur Stadtmitte immer eine Spirale? Oder?
Kleinteiliges Arbeiten und kleinteiliges Denken.
Man kann Stringoperationen sukzsessive auf Eingabedaten anwenden.
Man kann aber auch nur einmal parsen und dabei gleichzeitig
Whitespaces entfernen und den nachfolgenden Funktionen z.B.
ein Array mit Pointern auf die relevanten Bestandteile hinterlassen.
Und eben erkannte Schluesselworte durch Hashes oder Token ersetzen.
Wenn man will, und das fuer das Resultat nuetzlich ist.
Und nun rate mal, was im (Gesamt-)Ergebnis schneller ist.
Läuft das programm auf einem Rechner welcher noch mit Relais arbeitet?
Oder warum werden Takte bei so einer Pipifunktion gezählt?
Ich fasse es nicht ...
Tim T. schrieb:> int clean_string(char *buf, int len, char c) {> int i, j;> for (i = 0, j = 0; i < len; i++) {> if (buf[i] != c) buf[j++] = buf[i];> }> return j;> }
wenn
Tim T. schrieb:> Jemand eine bessere Idee als diese hier?
Iterieren musst du natürlich, aber ich würde danach memmove() nehmen. Es
könnte sein, dass der Compiler das vielleicht besser optimieren kann als
händisches Zeiger- oder Index-Gefummel.
>>> "*src != c && len-- > 0">>>> Das bewirkt halt, daß du ein Zeichen mehr (= zu viel) vergleichst, auch>> wenn das dank der am Stringende stehenden 0 kein ernsthaftes Problem>> ist.>> Oh mann, ja da hatte ich wirklich ein Brett vorm Kopf aber jetzt wo du> es sagst, klar. Am Stringende steht aber auch kein '\0', aber zum> Problem wirds ja trotzdem nicht.
Doch, das ist ein Problem - du liest über den Buffer hinaus und das gibt
u.U. einen Segfault.
> Iterieren musst du natürlich, aber ich würde danach memmove() nehmen.
Wenn man nur das erste "c" löschen möchte, ok. Wenn man aber alle "c"
entfernen will, geht das den O(n²)-Bach runter.
Merker schrieb:> Läuft das programm auf einem Rechner welcher noch mit Relais> arbeitet?> Oder warum werden Takte bei so einer Pipifunktion gezählt?> Ich fasse es nicht ...
Ich frage mich eher was das für eine x86 Cpu ist, bei der die Angabe von
"Takten" eine brauchbare größe ist, um Mikrooptimierungen zu testen,
oder wie man diese Takte bestimmt.
Merker schrieb:> Läuft das programm auf einem Rechner welcher noch mit Relais arbeitet?> Oder warum werden Takte bei so einer Pipifunktion gezählt?> Ich fasse es nicht ...
Nein, es sind nur Datenströme im Bereich von einigen MBit/s und es ist
nur ein ARM, kein PC. Aber auch sonst, habe ich gerne eine Gute Lösung
für schwächere Systeme im Fundus und muss nicht immer alles mit mehr
Leistung erschlagen.
der Sinn schrieb:> Tim T. schrieb:>> int clean_string(char *buf, int len, char c) {>> int i, j;>> for (i = 0, j = 0; i < len; i++) {>> if (buf[i] != c) buf[j++] = buf[i];>> }>> return j;>> }>> wenn
1
buf
gar kein
1
c
enthält (oder nur am Ende) - dann wird
> ständig
1
buf[x]=buf[x]
ausgeführt?
Ja, darum ja auch das Vorziehen der Prüfung auf das erste Vorkommen vor
die Schleife in der späteren Version.
Jörg W. schrieb:> Tim T. schrieb:>> Jemand eine bessere Idee als diese hier?>> Iterieren musst du natürlich, aber ich würde danach memmove() nehmen. Es> könnte sein, dass der Compiler das vielleicht besser optimieren kann als> händisches Zeiger- oder Index-Gefummel.
Werde ich mir spaßeshalber mal anschauen aber was ich noch von der
memmove() Implementierung im Kopf habe, zweifel ich da dran dass es
wirklich was bringt. Bin da bei foobar, dass es spätestens bei mehreren
Vorkommnissen einfach nur langsamer sein wird.
foobar schrieb:>>>> "*src != c && len-- > 0">>>>>> Das bewirkt halt, daß du ein Zeichen mehr (= zu viel) vergleichst, auch>>> wenn das dank der am Stringende stehenden 0 kein ernsthaftes Problem>>> ist.>>>> Oh mann, ja da hatte ich wirklich ein Brett vorm Kopf aber jetzt wo du>> es sagst, klar. Am Stringende steht aber auch kein '\0', aber zum>> Problem wirds ja trotzdem nicht.>> Doch, das ist ein Problem - du liest über den Buffer hinaus und das gibt> u.U. einen Segfault.
Nein, zum Einen ist der Buffer etwas größer als maximal nötig, zum
Anderen kann ich, da der Buffer auf dem Stack liegt, mit Sicherheit
sagen das der Speicher hinter dem Buffer ebenfalls zum Programm gehört,
nur liefert die Prüfung nichts Sinnvolles. Entweder ist der "Müll"
hinter dem Buffer zufällig c und die Schleife endet oder die Schleife
endet weil len bei 0 angekommen ist. Was aber alles nichts daran ändert
das es Unsinn von mir war es andersherum zu probieren.
mh schrieb:> Merker schrieb:>> Läuft das programm auf einem Rechner welcher noch mit Relais>> arbeitet?>> Oder warum werden Takte bei so einer Pipifunktion gezählt?>> Ich fasse es nicht ...>> Ich frage mich eher was das für eine x86 Cpu ist, bei der die Angabe von> "Takten" eine brauchbare größe ist, um Mikrooptimierungen zu testen,> oder wie man diese Takte bestimmt.
Ist keine x86 CPU, hatte es dort nur auf die Schnelle gemacht um zu
testen ob der Umstieg von Indexen auf Pointer wirklich was bringen
könnte. Die eigentliche Implementierung läuft dann auf einem älteren ARM
Cortex A8, der aber ausreichend schnell für die Aufgaben ist.
Tim T. schrieb:> mh schrieb:>> Ich frage mich eher was das für eine x86 Cpu ist, bei der die Angabe von>> "Takten" eine brauchbare größe ist, um Mikrooptimierungen zu testen,>> oder wie man diese Takte bestimmt.>> Ist keine x86 CPU, hatte es dort nur auf die Schnelle gemacht um zu> testen ob der Umstieg von Indexen auf Pointer wirklich was bringen> könnte. Die eigentliche Implementierung läuft dann auf einem älteren ARM> Cortex A8, der aber ausreichend schnell für die Aufgaben ist.
Und du glaubst, dass die Ergebnisse übertragbar sind? Und die Antwort
auf die Frage, wie du diese Takte mit dem x86_64 gcc bestimmt hast,
würde mich noch immer interessieren.
mh schrieb:> Tim T. schrieb:>> mh schrieb:>>> Ich frage mich eher was das für eine x86 Cpu ist, bei der die Angabe von>>> "Takten" eine brauchbare größe ist, um Mikrooptimierungen zu testen,>>> oder wie man diese Takte bestimmt.>>>> Ist keine x86 CPU, hatte es dort nur auf die Schnelle gemacht um zu>> testen ob der Umstieg von Indexen auf Pointer wirklich was bringen>> könnte. Die eigentliche Implementierung läuft dann auf einem älteren ARM>> Cortex A8, der aber ausreichend schnell für die Aufgaben ist.> Und du glaubst, dass die Ergebnisse übertragbar sind?
Absolut, es ging mir ja nur um die Frage ob Indexe oder Pointer
schneller sind und die Optimierung fürs Vorkommen des ersten Zeichens
ist logischerweise auf dem ARM auch anwendbar. Zusätzlich habe ich mir
noch das assembly angeschaut und es sah auch nicht wirklich anders aus,
also nicht so besondere Optimierung auf den Befehlssatz. Natürlich ist
mir bewusst das die Takte nicht 1:1 übertragbar sind, aber für eine
einfache Abschätzung reicht es allemal.
Und die Antwort
> auf die Frage, wie du diese Takte mit dem x86_64 gcc bestimmt hast,> würde mich noch immer interessieren.
Achso, hatte das nicht wirklich als Frage aufgefasst. Ich hab einfach
rdtsc genutzt. Den Prozess auf exklusiv einen Kern begrenzt,
Hyperthreading, Turbo und Hibernating abgeschaltet und die Funktion mit
den Testdaten 10.000.000 mal durchlaufen lassen und dann gemittelt. War
einfach zu faul Takte im assembly zu zählen und das Ergebnis war für
mich genau genug und reproduzierbar.
> [memmove-Variante]
Die Implementation ist nicht korrekt - buf und dst sind der gleiche
Buffer, durch den memmove wird also auch buf geändert. Statt "buf=p+1"
müsste wohl sowas wie "buf=p; end--" da stehen. Und wie gesagt, O(n²).
Tim T. schrieb:> ob Indexe oder Pointer schneller sind
Weder noch. Je nach konkreter Aufgabe kann ein Compiler gut und gern für
beide Schreibweisen das gleiche produzieren.
Jörg W. schrieb:> Tim T. schrieb:>> ob Indexe oder Pointer schneller sind>> Weder noch. Je nach konkreter Aufgabe kann ein Compiler gut und gern für> beide Schreibweisen das gleiche produzieren.
Was ja auch in diesem Fall ab O2 eingetreten ist.
Ich schrieb:
> Die Implementation ist nicht korrekt
Sorry, hab mich vertan - ist doch korrekt. Du kopierst nur den
übersprungenen Bereich, nicht den Rest bis zum Ende. Und das mit dem n²
stimmt dann auch nicht.
foobar schrieb:> Die Implementation ist nicht korrekt -
hab sie nur hier im Browser runtergetippt. Weder Editor noch kompiliert
geschweige denn laufen gelassen. Also vermutlich ein paar Fehler drin.
Absicht sind aber (mögliche, unnötige) Aufrufe mit Länge 0 wenn das
letzte Zeichen das gesuchte ist. Keine Ahnung, ob das erlaubt ist, aber
(für mich) more straight als ein "if(end-buf>0) ..."
Habs jetzt auch mal getestet und diese Variante braucht bei gleichen
Testdaten ohne Optimierung 53 Takte, mit O1 und O2 sind es 50 und bei O3
sind es 42.
Hmm, irgendwie glaube ich die Werte allerdings nicht, muss nochmal
drüber schauen.
Tim T. schrieb:> Funktion mit den Testdaten 10.000.000 mal durchlaufen lassen und dann> gemittelt.
Was bedeutet "Takte" bei Dir? Bezogen auf ein Byte oder je Telegramm?
Tim T. schrieb:> und bei O3 sind es 42.> Hmm, irgendwie glaube ich die Werte allerdings nicht, muss nochmal> drüber schauen.
Die memfunktionen können schon deutlich besser sein als handgestrickt.
Es wird ja nicht eine Funktion aufgerufen (so mit Adresse und Parameter
auf den Stack) sondern dem Compiler sehr formal gesagt: das will ich
machen. Er kann dann die wildesten Bit-, Byte- und Ptr-tricks dort
Inline ausrollen. Beim hangedengelten Code muss er erstmal erkennen,
dass er dafür 2 höchstoptimierte Strategien hat.
A. S. schrieb:> Tim T. schrieb:>> Funktion mit den Testdaten 10.000.000 mal durchlaufen lassen und dann>> gemittelt.>> Was bedeutet "Takte" bei Dir? Bezogen auf ein Byte oder je Telegramm?
Eben einfach die Differenz der CPU Zyklen seit dem letzten Reset, vor
und nach der Funktion. Diese Differenzen habe ich über 10.000.000
Funktionsaufrufe summiert und dann durch die Anzahl der Aufrufe geteilt.
>> Tim T. schrieb:>> und bei O3 sind es 42.>> Hmm, irgendwie glaube ich die Werte allerdings nicht, muss nochmal>> drüber schauen.>> Die memfunktionen können schon deutlich besser sein als handgestrickt.>> Es wird ja nicht eine Funktion aufgerufen (so mit Adresse und Parameter> auf den Stack) sondern dem Compiler sehr formal gesagt: das will ich> machen. Er kann dann die wildesten Bit-, Byte- und Ptr-tricks dort> Inline ausrollen. Beim hangedengelten Code muss er erstmal erkennen,> dass er dafür 2 höchstoptimierte Strategien hat.
Ja, aber trotzdem erscheinen die Takte dafür etwas sehr wenig, werde ich
mir aber noch anschauen. Habe die Testroutine jetzt schon 2 mal
umgeschrieben, jetzt messe ich die Zyklen für das Zurücksetzen des
Puffers zwar mit, aber trotzdem geht es immer noch doppelt so schnell
wie in der schnellsten händischen Version (ebenfalls mit Zyklen fürs
Zurücksetzen gerechnet). Werde mich morgen mal dransetzen und die
Testbench komplett überarbeiten damit die Ergebnisse sauberer werden.
Tim T. schrieb:> aber trotzdem geht es immer noch doppelt so schnell> wie in der schnellsten händischen Version
Da könnten auch cache-Effekte eine Rolle spielen.
Ggf. mal die Daten per rnd immer wieder neu erzeugen. Dürfte ja bei
gleichem seed immer gleich sein.
Wie sehen die Daten denn im Mittel aus? 500 Byte und 2-3 Suchzeichen wie
mit dem Schrottgewehr darüber verteilt? Also wenn im Mittel 20 oder mehr
Zeichen nacheinander kein c enthalten, könnte das gut passen.
A. S. schrieb:> Tim T. schrieb:>> aber trotzdem geht es immer noch doppelt so schnell>> wie in der schnellsten händischen Version>> Da könnten auch cache-Effekte eine Rolle spielen.
Jop, das war auch mein Verdacht, darum wollte ich den Test verändern.
> Wie sehen die Daten denn im Mittel aus? 500 Byte und 2-3 Suchzeichen wie> mit dem Schrottgewehr darüber verteilt? Also wenn im Mittel 20 oder mehr> Zeichen nacheinander kein c enthalten, könnte das gut passen.
Prinzipiell sind in jedem Paket (String) mehrere Suchzeichen vorhanden
aber eigentlich seltener als jedes 20. Zeichen, eher so jedes 60., eine
genaue Statistik da drüber habe ich allerdings nicht. Aber die sind
schon relativ gleichmäßig verteilt.
Habe es jetzt geschafft die Out-of-order execution abzuschalten und die
Zahlen (Takte) wurden um einiges realistischer:
Indexe: 2160 (O0), 770 (O1), 639 (O2), 639 (O3)
Pointer: 1357 (O0), 793 (O1), 726 (O2), 726 (O3)
Memmove: 410 (O0), 374 (O1), 374 (O2), 374 (O3)
Interessant dabei ist, dass ohne OOO die Pointer Variante bei
Optimierung wieder etwas langsamer als die mit Indexen ist...
Tim T. schrieb:> Habe es jetzt geschafft die Out-of-order execution abzuschalten und die> Zahlen (Takte) wurden um einiges realistischer:
Komische Sichtweise…
Oliver
Oliver S. schrieb:> Tim T. schrieb:>> Habe es jetzt geschafft die Out-of-order execution abzuschalten und die>> Zahlen (Takte) wurden um einiges realistischer:>> Komische Sichtweise…
Ja, ohne den Kontext kann das wirklich so wirken.
Es ging mir einfach darum eine Abwägung zwischen verschiedenen
Implementierungen zu machen. Leider ist die Laufzeit der Funktion aber
so kurz das es nicht brauchbar möglich ist diese bei einem
Funktionsaufruf auch nur halbwegs zu bestimmen. Also habe ich die
Variante gewählt die entsprechende Funktion einfach mehrere Millionen
mal auszuführen und dann die Laufzeit eines Aufrufs zu mitteln. Bei
diesen wiederholten Aufrufen kann es aber durch OOO dazu kommen, dass
bestimmte Teile der zu messenden Funktion bereits vor dem Ermitteln des
Startzeitstempels ausgeführt werden und somit nicht mit gemessen werden.
Die einzige Alternative hierzu wäre die komplette Zeit, inklusive des
Schleifenkonstrukts und der Datengenerierung mit zu messen, was aber das
Ergebnis weiter verfälschen würde.
Mir ging es dabei weniger um eine exakte Abschätzung der
Funktionslaufzeit als vielmehr um eine realistische Abschätzung der
Laufzeitunterschiede. Die Zahlen ansich, können dabei eher als
Obergrenze gesehen werden.
Tim T. schrieb:> Mir ging es dabei weniger um eine exakte Abschätzung der> Funktionslaufzeit als vielmehr um eine realistische Abschätzung der> Laufzeitunterschiede.
Und, OOO bei der Abschätzung der Laufzeitunterschiede zu ignorieren, ist
realistisch?
foobar schrieb:> Die Implementation ist nicht korrekt - buf und dst sind der gleiche> Buffer, durch den memmove wird also auch buf geändert.
Bei memmove() ist es ok, wenn Quelle und Ziel überlappen.
Bei memcpy() ist es verboten.