Schnellstes Entfernen von Chars aus einem String?

[Namenloser]

Zitat von Amateurprofi:

Zitat von Namenloser:

Meine ist also nicht nur einfacher, sondern auch durchweg schneller. (CPU i7 4790K, 64 Bit)
Was sagst du nun?

Dazu sage ich, dass ich das nicht nachvollziehen kann.
Auf meinem Rechner (I7 2600K) sind die Ergebnisse so:

32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 141756 Max 358172
T2 Min 18144 Max 137786

64 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 165112 Max 377076
T2 Min 19936 Max 146812

Min/Max find ich jetzt nicht so glücklich, da kriegst du gerade die größten Schwankungen. Median oder Durchschnitt wären aussagekräftiger.

Wie dem auch sei, ich kann mir den Unterschied nur so erklären, dass entweder Delphis Pos-Routine wesentlich langsamer ist als das Freepascal-Äquivalent oder erhebliche Unterschiede zwischen den CPUs bestehen.

Probier es doch mal mit einer anders definierten Pos-Funktion:

Delphi-Quellcode:

function Pos(const Needle: MyChar; const Haystack: MyString): integer; inline;
var
  i: integer;
begin
  for i := 1 to length(Haystack) do
    if Haystack[i] = Needle then
    begin
      Result := i;
      exit;
    end;
  Result := 0;
end;

Bei mir ändert sich dadurch nicht wirklich was:

Code:

[dev]$ ./test
Ergebnisse gleich
35883
69671
[dev]$ ./test
Ergebnisse gleich
44440
85332
[dev]$ ./test
Ergebnisse gleich
34680
71640

Allerdings interessanterweise nur im WideChar-Fall. Im 8-Bit-Fall ist meine Routine damit nun leicht langsamer als deine. Ich vermute daher, dass Freepascals Pos-Routine im 8-Bit-Fall irgendwelche SSE-Instructions verwendet.

Edit: Okay, letzteres lag wohl nur an der Optimierungsstufe:

AnsiString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
38464
46625
fpc -O3 test.pas
Ergebnisse gleich
36628
40034

AnsiString, mit eigener Pos-Funktion:
fpc test.pas
Ergebnisse gleich
58889
46354
fpc -O3 test.pas
Ergebnisse gleich
39852
42474

WideString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
41160
73345
fpc -O3 test.pas
Ergebnisse gleich
39369
67631

WideString, mit eigener Pos-Funktion:
fpc test.pas
Ergebnisse gleich
62403
73024
fpc -O3 test.pas
Ergebnisse gleich
34298
64443


(Sorry, bin zu faul, herauszufinden, wie man hier eine Tabelle formatiert)

[Mavarik]

hmm...

Also ohne es getestet zu haben... Aber wenn ich einen 1GB langen String habe...
Wie sieht das Zeitverhalten aus, wenn ich den String in

Anzahlzeichen/Cores vorher per Pointer auf mehrere Threads aufteile?

Mavarik

[Amateurprofi]

Zitat von Namenloser:

Min/Max find ich jetzt nicht so glücklich, da kriegst du gerade die größten Schwankungen. Median oder Durchschnitt wären aussagekräftiger.

Wie dem auch sei, ich kann mir den Unterschied nur so erklären, dass entweder Delphis Pos-Routine wesentlich langsamer ist als das Freepascal-Äquivalent oder erhebliche Unterschiede zwischen den CPUs bestehen.

Probier es doch mal mit einer anders definierten Pos-Funktion:

Delphi-Quellcode:

function Pos(const Needle: MyChar; const Haystack: MyString): integer; inline;
var
  i: integer;
begin
  for i := 1 to length(Haystack) do
    if Haystack[i] = Needle then
    begin
      Result := i;
      exit;
    end;
  Result := 0;
end;

Mit der obigen Pos Funktion habe ich folgende Ergebnisse gekriegt:
32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 53844 Max 592624
T2 Min 20512 Max 749712

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

[Namenloser]

Zitat von Amateurprofi:

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

Allerdings ist das Handicap durch Interrupts für beide Funktionen gleich, und es sind meistens nur weniger Ausreißer vorhanden, von daher sind die Durchschnittswerte schon einigermaßen repräsentativ. Median wäre natürlich besser, aber umständlicher zu implementieren.

Die Min-Werte sind auch nicht unbedingt verlässlich. Der Tick-Counter ist nämlich zwischen den CPU-Kernen nicht synchron. Falls das Programm also während der Ausführung auf einen Kern verschoben wird, kriegst du inkonsistente Ergebnisse. Im Internet findest du Fälle, wo der Vergleich zweier aufeinanderfolgender Timestamps deshalb sogar negative Werte ergab. Du wirst also nach unten genau so Ausreißer kriegen wie nach oben.

[Amateurprofi]

Zitat von Namenloser:

Zitat von Amateurprofi:

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

Allerdings ist das Handicap durch Interrupts für beide Funktionen gleich, und es sind meistens nur weniger Ausreißer vorhanden, von daher sind die Durchschnittswerte schon einigermaßen repräsentativ. Median wäre natürlich besser, aber umständlicher zu implementieren.

Die Min-Werte sind auch nicht unbedingt verlässlich. Der Tick-Counter ist nämlich zwischen den CPU-Kernen nicht synchron. Falls das Programm also während der Ausführung auf einen Kern verschoben wird, kriegst du inkonsistente Ergebnisse. Im Internet findest du Fälle, wo der Vergleich zweier aufeinanderfolgender Timestamps deshalb sogar negative Werte ergab. Du wirst also nach unten genau so Ausreißer kriegen wie nach oben.

Ja, das kenne ich dass gelegentlich bei zwei direkt aufeinander folgenden RDTSC der zweite Wert kleiner ist, als der erste.
Jedoch erfolgen bei dem Test keine RTDSC direkt hintereinander.
Und selbst wenn: Dann würde ich einen MinWert < 0 sehen, der natürlich nicht plausibel ist.
Bei Durchschnittswerten würde das in der Masse anderer Messungen untergehen.
So gesehen ist das ein weiteres Argument für MinWert Betrachtung.

Und unterschiedliche TSC auf verschiedenen Kernen lassen sich doch ganz einfach in den Griff kriegen.
Bei ernsthafteren Tests mache ich das in etwa so:

Delphi-Quellcode:

var PriorityClass,Priority:Integer; SaMask,PaMask,TaMask:NativeUInt;
begin
   // Thread auf eine CPU fixieren
   GetProcessAffinityMask(GetCurrentProcess,PaMask,SaMask);
   TaMask:=1;
   while TaMask and PaMask=0 do TaMask:=TaMask shl 1;
   SetThreadAffinityMask(GetCurrentThread,TaMask);
   // Thread auf höchste Priorität setzen
   PriorityClass:=GetPriorityClass(GetCurrentProcess);
   Priority:=GetThreadPriority(GetCurrentThread);
   SetPriorityClass(GetCurrentProcess,REALTIME_PRIORITY_CLASS);
   SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
   // Zeitmessungen durchführen


   // Thread für alle CPUs freigeben und Priorität auf alten Wert stellen
   SetThreadAffinityMask(GetCurrentThread,PaMask);
   SetThreadPriority(GetCurrentThread,Priority);
   SetPriorityClass(GetCurrentProcess,PriorityClass);
end;

[Harry Stahl]

Also ich hatte es gestern auch erst einmal mit dem Debugger verfolgt, bevor ich mein posting gemacht hatte. Und da war es so, dass mit

Result := s; neuer Speicher angefordert wurde. Anscheinend greift die String-Referenzierung nicht bei Rückgabe von String-Funktionsresultaten. Würde auch einen gewissen Sinn machen, da die Funktion ja direkt nach Rückkehr quasi nicht mehr existiert und insofern dazu keine Verwaltung stattfinden kann, ob ein referenzierender String (= die Funktion) sich verändert hat.

Dennoch ist es natürlich viel schneller, eine Zuweisung auf einen Rutsch zu machen, als Charweise in einer For-Schleife.