Alternative zu PosEx

[Amateurprofi]

Zitat:

Zitat von Blup (Beitrag 1543690)

Das anfängliche "SetLength()" bewirkt weniger als erwartet, dafür bingt "inline" deutlich mehr Zeitersparnis:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string; Estimated: Integer = 0): TIntegerDynArray;

  function Search(const SearchFor, SearchIn: string; var Index: Integer): Boolean; inline;
  begin
    Index := Pos(SearchFor, SearchIn, Index + 1);
    Result := (Index > 0);
  end;

begin
  SetLength(Result, Estimated);
  var Count: Integer := 0;
  var Index: Integer := 0;
  while Search(SearchFor, SearchIn, Index) do
  begin
    Inc(Count);
    {Array vergrößern braucht viel Zeit, deshalb gleich etwas mehr Platz reservieren}
    if Estimated < Count then
    begin
      Estimated := Count * 2;
      SetLength(Result, Estimated);
    end;
    Result[Count - 1] := Index;
  end;
  SetLength(Result, Count);
end;

Code:

StrPosEx('7', sRandomString, Positions)
0:00:00.102

Result := MyStrPosEx('7', sRandomString, 0)
0:00:00.168

Result := MyStrPosEx('7', sRandomString, 10000000)
0:00:00.157

Sorry, aber ich kann die Ergebnisse Deiner Zeitmessungen nicht nachvollziehen.
Ich habe SRandomString auf eine Länge von 80 Mio gesetzt und mit Zufallszeichen im Bereich "0".."9" gefüllt.
In Deiner Funktion "Search" habe ich "Pos" durch "PosEx" (aus System.StrUtils) ersetzt, weil bei mir (Delphi XE2) "Pos" keinen Offset unterstützt.
Ergebnisse im Anhang.
Meine Test-Prozedur:

Delphi-Quellcode:

PROCEDURE TMain.Test;
resourcestring
   sFmt='F:%S, R:%D, T:%S ms';
var
  I,R1,R2,R3:Integer;
  T1,T2,T3:Int64;
  DT:TDateTime;
  S1,S2,SRandomString:String;
  Positions:TIntegerDynArray;
begin
   SetLength(SRandomString,80000000);
   for I:=1 to Length(SRandomString) do
      SRandomString[I]:=Char(Random(10)+Ord('0'));
   // Zeitmessung auf Basis TimeStampCounter
   //    StrPosEx
   T1:=TimeStamp;
   SetLength(Positions,8100000);
   R1:=StrPosEx('7',sRandomString,Positions);
   SetLength(Positions,R1);
   T1:=TimeStamp-T1;
   //    MyStrPosEx mit Esrimated=0
   Positions:=Nil;
   T2:=TimeStamp;
   Positions:=MyStrPosEx('7',sRandomString,0);
   R2:=Length(Positions);
   T2:=TimeStamp-T2;
   //    MyStrPosEx mit Esrimated=8100000
   Positions:=Nil;
   T3:=TimeStamp;
   Positions:=MyStrPosEx('7',sRandomString,8100000);
   R3:=Length(Positions);
   T3:=TimeStamp-T3;
   S1:='Zeitmessung auf Basis TimeStampCounter'#13+
       Format(sFmt,['StrPosEx',R1,TicksToStr(T1)])+#13+
       Format(sFmt,['MyStrPosEx 0',R2,TicksToStr(T2)])+#13+
       Format(sFmt,['MyStrPosEx 8100000',R3,TicksToStr(T3)]);
   // Zeitmessung auf Basis TDateTime
   //    StrPosEx
   DT:=Now;
   SetLength(Positions,8100000);
   R1:=StrPosEx('7',sRandomString,Positions);
   SetLength(Positions,R1);
   T1:=MilliSecondsBetween(DT,Now);
   //    MyStrPosEx mit Esrimated=0
   Positions:=Nil;
   DT:=Now;
   Positions:=MyStrPosEx('7',sRandomString,0);
   R2:=Length(Positions);
   T2:=MilliSecondsBetween(DT,Now);
   //    MyStrPosEx mit Esrimated=8100000
   Positions:=Nil;
   DT:=Now;
   Positions:=MyStrPosEx('7',sRandomString,8100000);
   R3:=Length(Positions);
   T3:=MilliSecondsBetween(DT,Now);
   S2:='Zeitmessung auf Basis TDateTime'#13+
       Format(sFmt,['StrPosEx',R1,IntToStr(T1)])+#13+
       Format(sFmt,['MyStrPosEx 0',R2,IntToStr(T2)])+#13+
       Format(sFmt,['MyStrPosEx 8100000',R3,IntToStr(T3)]);
  ShowMessage(S1+#13#13+S2);
end;

[Stevie]

Ich find das ja putzig, wenn Leute Messergebnisse auf höchstwahrscheinlich sehr unterschiedlicher Hardware und Delphi Versionen vergleichen, die mind 10 Jahre auseinander liegen.

[Blup]

Bei mir Delphi 12.
Der Zeitunterschied verschindet bei mir praktisch, wenn statt '7' nach "77" gesucht wird.
Da in beiden Fällen der gesamte String durchsucht wird, meine Vermutung:
Die vielen Aufrufe von Pos bremsen (sind ja nicht inline).
Die Suche selbst innerhalb von Pos scheint optimal (zumindest in Delphi 12).

Eigentlich wollte ich nur die Verwendung von SetLength demonstrieren, damit man die Anzahl der Ergebnisse nicht vorher raten muss.

[Amateurprofi]

Zitat:

Zitat von Stevie (Beitrag 1543761)

Ich find das ja putzig, wenn Leute Messergebnisse auf höchstwahrscheinlich sehr unterschiedlicher Hardware und Delphi Versionen vergleichen, die mind 10 Jahre auseinander liegen.

Du könntest Recht haben, wenn mir um die Zeiten selbst ginge.
Mir geht es aber um folgendes:
Meine "StrPosEx" ist, ich erwähnte es in #1, von "PosEx" aus "System.StrUtils" abgeleitet.
Der Teil, mit dem gesucht wird, ist im Prinzip identisch mit "PosEx".
Unterschied:
Bei der Prüfung, ob die aktuelle Position noch innerhalb des zu durchsuchenden Teil des Strings ist vergleicht "PosEx" mit einem Wert, der auf dem Stack liegt, bei meiner "StrPosEx" mit einem Register, was deutlich schneller ist.
Deshalb erstaunt es mich dass eine Funktion, die wiederholt "Pos" bzw "PosEx" aufruft, deutlich schneller sein soll.
Nun kenne ich die "Pos" aus Delphi 12 nicht, habe aber mal irgendwo gelesen, dass die Identisch ist mit "PosEx" aus Delphi XE2.
Aber selbst wenn das nicht so ist, habe ich Zweifel, dass das etwas Neues ist, das deutlich schneller arbeitet.
Vielleicht kann mal jemand den Code der "Pos" aus Delphi 12 posten.

[Amateurprofi]

Zitat:

Zitat von Blup (Beitrag 1543770)

Bei mir Delphi 12.
Der Zeitunterschied verschindet bei mir praktisch, wenn statt '7' nach "77" gesucht wird.
Da in beiden Fällen der gesamte String durchsucht wird, meine Vermutung:
Die vielen Aufrufe von Pos bremsen (sind ja nicht inline).
Die Suche selbst innerhalb von Pos scheint optimal (zumindest in Delphi 12).

Eigentlich wollte ich nur die Verwendung von SetLength demonstrieren, damit man die Anzahl der Ergebnisse nicht vorher raten muss.

Zu "inline"
Könntest Du mal prüfen, ob bei Dir der Aufruf von "Search" tatsächlich "inline" abgewickelt wird.
Bei mir, obwohl als inline deklariert, jedenfalls nicht.

Code:

Mersenne_Main.pas.7011: while Search(SearchFor, SearchIn, Index) do
005B6B61 55               push ebp
005B6B62 8D4DEC           lea ecx,[ebp-$14]
005B6B65 8B55F8           mov edx,[ebp-$08]
005B6B68 8B45FC           mov eax,[ebp-$04]
005B6B6B E848FFFFFF       call Search
005B6B70 59               pop ecx
005B6B71 84C0             test al,al
005B6B73 75B0             jnz $005b6b25

[Blup]

Bei mir ist da nur der Call von System.Pos().

Code:

Test.View.pas.277: while Search(SearchFor, SearchIn, Index) do
03C55056 8B4DEC           mov ecx,[ebp-$14]
03C55059 8B55F8           mov edx,[ebp-$08]
03C5505C 8B45FC           mov eax,[ebp-$04]
03C5505F E8C88ECAFC       call $008fdf2c
03C55064 8945E0           mov [ebp-$20],eax
03C55067 8B45E0           mov eax,[ebp-$20]
03C5506A 8945EC           mov [ebp-$14],eax
03C5506D 837DEC00         cmp dword ptr [ebp-$14],$00
03C55071 7F93             jnle $03c55006

[himitsu]

Ins Log schauen, normal steht da, wenn Delphi gedenkt das INLINE nicht machen zu wollen.

[Amateurprofi]

Zitat:

Zitat von himitsu (Beitrag 1543794)

Ins Log schauen, normal steht da, wenn Delphi gedenkt das INLINE nicht machen zu wollen.

Danke, himitsu.
Nun, ich schaue mir das einfach im Debugger in der ASM-Ansicht an.
Aber interessehalber: Wo finde ich das Log?
Eventuell das Fenster "Meldungen"? Da steht bei mir nichts dazu.

[Stevie]

Es gibt nur einige Gründe, die geloggt werden, wenn nicht geinlined wird, dieser hier ist keiner davon.
Inlining von Calls, die in einer Loop Bedingung stehen wurde erst jüngst (irgendwann in einer 10er?) implementiert.

Ich würde die Routine deshalb, damit man auch davor davon profitiert, umschreiben:

Delphi-Quellcode:

function MyStrPosEx(const SearchFor, SearchIn: string; Estimated: Integer = 0): TIntegerDynArray;
var
  Count, Index, SearchForLength: Integer;
begin
  SetLength(Result, Estimated);
  Count := 0;
  Index := 1;
  SearchForLength := Length(SearchFor);
  repeat
    Index := Pos(SearchFor, SearchIn, Index);
    if Index = 0 then Break;
    Inc(Count);
    if Estimated < Count then
    begin
      Estimated := Count * 2;
      SetLength(Result, Estimated);
    end;
    Result[Count - 1] := Index;
    Inc(Index, SearchForLength);
  until False;
  SetLength(Result, Count);
end;

Zitat:

Zitat von Amateurprofi (Beitrag 1543778)

Bei der Prüfung, ob die aktuelle Position noch innerhalb des zu durchsuchenden Teil des Strings ist vergleicht "PosEx" mit einem Wert, der auf dem Stack liegt, bei meiner "StrPosEx" mit einem Register, was deutlich schneller ist.

Bevor du solche Behauptungen aufstellst, solltest du nochmal die genauen Timings der entsprechenden Instruktionen zurate ziehen.

Ich zumindest bin immer wieder erstaunt.

[Amateurprofi]

Zitat:

Bevor du solche Behauptungen aufstellst, solltest du nochmal die genauen Timings der entsprechenden Instruktionen zurate ziehen.

Ja ich ziehe deshalb das "IA-32 Intel® Architecture Optimization Reference Manual" zurate.