Bestimmten Char aus String entfernen (C)

[Tim T. (tim_taylor)]

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.

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;
}

[MaWin (Gast)]

Viel besser wirds wohl nicht werden.

[Tim T. (tim_taylor)]

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.

[3h (Gast)]

> 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.

[Irgend W. (Firma: egal) (irgendwer)]

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.

[Jemand (Gast)]

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.

[Tim T. (tim_taylor)]

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.

[Klaus W. (mfgkw)]

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.

[Tim T. (tim_taylor)]

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.

[Tim T. (tim_taylor)]

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.

[A. S. (Gast)]

int clean_string(char *buf, int len, char c) {
    char *src=buf;
    while(len-->0 && *src!=c) src++;
    char *dst=src++;
    while(len-->0) {
        if(*src!=c) *dst++=*src;
        src++;
    }
    return dst-buf;
}

[Tim T. (tim_taylor)]

A. S. schrieb:
>

> int clean_string(char *buf, int len, char c) {
>     char *src=buf;
>     while(len-->0 && *src!=c) src++;
>     char *dst=src++;
>     while(len-->0) {
>         if(*src!=c) *dst++=*src;
>         src++;
>     }
>     return dst-buf;
> }
>

Interessant, werde es mal gegen meine überarbeitete Variante testen:

int clean_string(char *buf, int len, char c) {
    int i, j;
    for (i = 0; i < len; i++) if (buf[i] == c) break;
    for (j = i++; i < len; i++) {
        if (buf[i] != c) {
            buf[j++] = buf[i];
        }
    }
    return j;
}

[Dieter H. (kyblord)]

Da kann man nichts mehr rausholen. Du musst über den String iterieren, 
also bist du in O(n).

Das hier wäre halt in place:

int reduce_string(char* str, int len, char c) {
    int j=0;
    
    for(int i=0;i<len;i++) {
        if(j>0) {
            str[i-j]=str[i];
        }
        
        if(str[i] == c) {
            j++;
        }
    }
    
    str[len-j]='\0';
    
    return len-j;
}

[Jemand (Gast)]

Dieter H. schrieb:
> str[len-j]='\0';

int main() {
    char *string = "Ein toller String!";
    size_t len = strlen(string);
    char *data = malloc(len);
    memcpy(data, string, len);

    reduce_string(data, len, '?');
}

=================================================================
==1==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000022 at pc 0x0000004f915d bp 0x7ffd746ac9a0 sp 0x7ffd746ac998
WRITE of size 1 at 0x603000000022 thread T0
    #0 0x4f915c  (/app/output.s+0x4f915c)
    #1 0x7f529bea50b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #2 0x41f2dd  (/app/output.s+0x41f2dd)

0x603000000022 is located 0 bytes to the right of 18-byte region [0x603000000010,0x603000000022)
allocated by thread T0 here:
    #0 0x4b299d  (/app/output.s+0x4b299d)
    #1 0x4f9064  (/app/output.s+0x4f9064)

Gratulation.

[Dieter H. (kyblord)]

wusste dass es jemand schreibt ;-) hatte ich schon bemerkt.

[Tim T. (tim_taylor)]

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.

[Tim T. (tim_taylor)]

Tim T. schrieb:
> A. S. schrieb:
>>

>> int clean_string(char *buf, int len, char c) {
>>     char *src=buf;
>>     while(len-->0 && *src!=c) src++;
>>     char *dst=src++;
>>     while(len-->0) {
>>         if(*src!=c) *dst++=*src;
>>         src++;
>>     }
>>     return dst-buf;
>> }
>>

>
> 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.

[PittyJ (Gast)]

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.

[Oliver S. (oliverso)]

Welche Stringgrößen werden den erwartet? Wenns da in die MB geht, könnte 
man über memcpy nachdenken.

Oliver

[3h (Gast)]

> 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.

[Tim T. (tim_taylor)]

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:

int clean_string(char *buf, int len, char c) {
    char *src, *dst;
    for (src = buf; len-- > 0 && *src != c; src++);
    for (dst = src++; len-- > 0; src++) {
        if (*src != c) *dst++ = *src;
    }
    return (dst - buf);
}

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.

[3h (Gast)]

> 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.

[Oliver S. (oliverso)]

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

[3h (Gast)]

Gerade noch gesehen
> (Messdaten, kein Text)

Da machen Token natuerlich keinen Sinn.

[Tim T. (tim_taylor)]

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.

[Rolf M. (rmagnus)]

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?

[3h (Gast)]

> 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.

[Merker (Gast)]

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 ...

[der Sinn (Gast)]

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

buf

 gar kein

c

 enthält (oder nur am Ende) - dann wird ständig

buf[x]=buf[x]

 ausgeführt?

[Jörg W. (dl8dtl) (Moderator)]

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.

[foobar (Gast)]

>>> "*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.

[foobar (Gast)]

> 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.

[mh (Gast)]

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.

[A. S. (Gast)]

Jörg W. schrieb:
> aber ich würde danach memmove() nehmen

int clean_string(char *buf, int len, char c) {
    char *p, *end=buf+len, *dst=buf, *start=buf;
    if(!(p=memchr(buf,c,len)) return len;
    do {
        memmove(dst, buf, p-buf);
        dst+=p-buf;
        buf=p+1;
    } while(p=memchr(buf,c,end-buf));
    memmove(dst,buf,end-buf);
    return (dst-start) + (end-buf);
}

[Tim T. (tim_taylor)]

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

buf

 gar kein

c

 enthält (oder nur am Ende) - dann wird
> ständig

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. (tim_taylor)]

A. S. schrieb:
> Jörg W. schrieb:
>> aber ich würde danach memmove() nehmen
>

> int clean_string(char *buf, int len, char c) {
>     char *p, *end=buf+len, *dst=buf, *start=buf;
>     if(!(p=memchr(buf,c,len)) return len;
>     do {
>         memmove(dst, buf, p-buf);
>         dst+=p-buf;
>         buf=p+1;
>     } while(p=memchr(buf,c,end-buf));
>     memmove(dst,buf,end-buf);
>     return (dst-start) + (end-buf);
> }
>

Werde es gleich auch mal durchschieben, danke dir.

[mh (Gast)]

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.

[Tim T. (tim_taylor)]

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.

[foobar (Gast)]

> [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²).

[Jörg W. (dl8dtl) (Moderator)]

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.

[Tim T. (tim_taylor)]

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.

[foobar (Gast)]

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.

[A. S. (Gast)]

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) ..."

[Tim T. (tim_taylor)]

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.

[Jörg W. (dl8dtl) (Moderator)]

Tim T. schrieb:
> irgendwie glaube ich die Werte allerdings nicht

Ich auch nicht. ;-)

[A. S. (Gast)]

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. (Gast)]

Suche und verschieben zu trennen ermöglicht es, 8 Byte auf einmal zu 
laden bzw zu verschieben. Sollte also schneller sein können.

[Tim T. (tim_taylor)]

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.

[A. S. (Gast)]

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.

[Tim T. (tim_taylor)]

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...

[Oliver S. (oliverso)]

Tim T. schrieb:
> Habe es jetzt geschafft die Out-of-order execution abzuschalten und die
> Zahlen (Takte) wurden um einiges realistischer:

Komische Sichtweise…

Oliver

[Tim T. (tim_taylor)]

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.

[mh (Gast)]

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?

[Klaus W. (mfgkw)]

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.