Entwickler-Ecke

Algorithmen, Optimierung und Assembler - CompareText Optimierung


Flamefire - Mo 27.10.08 15:19
Titel: CompareText Optimierung
Ich möchte einen Textvergleich optimieren. Mir geht es dabei um keine logische Anordnung sondern um eine schnelle Aussage, ob ein Text vor einem anderen kommt oder danach oder gleich ist. Geht um eine Vergleichsfunktion.
Also die Folgende Funktion:
//TOrdner ist ein Objekt. FName ein String und FNameL die Länge davon

Delphi-Quelltext
1:
2:
3:
function Compare(o1,o2:Pointer):Integer;
begin
CompareText(TOrdner(o1).FName,TOrdner(o1).FName);

1.Optimierung (Zeitgewinn ca. 15%)

Delphi-Quelltext
1:
2:
3:
4:
function Compare(o1,o2:Pointer):Integer;
begin
Result:=TOrdner(o1).FNameL-TOrdner(o1).FNameL;
If(Result=0then CompareText(TOrdner(o1).FName,TOrdner(o1).FName);


Optimierungsansatz nach feststellen gleicher länge:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
var lcomp:Integer;
    p1,p2:Pointer;
begin
//l ist die Länge
p1:=Ptr(String1); //richtig so?
p2:=Ptr(String2);
lcomp:=0;
while(lcomp+4<=l) do begin //so weit wie möglich 4B-Weiser vergleich
Result:=PInteger(p1)-PInteger(p2);
If(Result<>0then exit;
Inc(p1,4);Inc(p2,4);Inc(lcomp,4);
end;
while(lcomp+1<=l) do begin //rest dann byteweise
Result:=PByte(p1)-PByte(p2);
If(Result<>0then exit;
Inc(p1);Inc(p2);Inc(lcomp);
end;


würde das so gehen? Könnten Integerüberläufe auftreten und Fehler verursachen? (Besonders bei dem Byte-Vergleich)
Gibt es noch bessere Optimierungen oder Vorschläge?
z.b. könnte man die +4 noch iwie nur einmal ausführen lassen. weiß aber nicht wie.

Und ja solche optimierungen lohnen, da der code SEHR häufig ausgeführt wird.


alzaimar - Mo 27.10.08 15:52

http://fastcode.sourceforge.net/

Da solltest Du fündig werden.


Gammatester - Mo 27.10.08 16:08

Wenn Du keinen Fastcode nehmen willst, mußt Du die Fälle behandeln, in denen durch den Typecast die Integers negativ werden können. Das kann zB die Vergleichsreihenfolge umkehren, wenn Integer positiv, der andere negativ ist. Außerdem wird's Probleme mit overflows geben (selbst dann wenn $Q-, $R- gesetzt wurde).

Gruß Gammatester


Flamefire - Mo 27.10.08 17:33

selbst der fastcode wird langsamer sein, da er alle fälle behandeln muss und logisch sortieren muss!

ok ich guck mal wo was mit den integern nicht klappt


alzaimar - Mo 27.10.08 22:07

In einer Stringmatch-Implementierung habe ich eine Prüfung der jeweils ersten und letzten Zeichen einer CompareText-Prüfung vorgeschaltet. Die Verbesserungen sind drastisch. Aber Vorsicht: Das lohnt sich nur bei relativ langen Strings. Erstell doch mal ein Beispielprojekt mit Zeitmessung und stelle das hier rein. Dann können Alle mithelfen.


Flamefire - Mi 29.10.08 11:05

Bsp-Projekt: 1 Button + 1 Memo

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
function CompStr(const String1,String2:String;const l:Integer):Integer;
var lcomp:Integer;
    p1,p2:Cardinal;
begin
//l ist die Länge
p1:=Cardinal(Pointer(String1)); //richtig so?
p2:=Cardinal(Pointer(String2));
lcomp:=4;
if(lcomp<=l) then begin //so weit wie möglich 4B-Weiser vergleich
  Repeat
    Result:=PInteger(p1)^-PInteger(p2)^;
    If(Result<>0then exit;
    If(lcomp=l) then exit;
    Inc(p1,4);Inc(p2,4);
    Inc(lcomp,4);
    If(lcomp>l) then begin
      Dec(lcomp,4);
      break;
    end;
  Until false;
end else lcomp:=0;
  Inc(lcomp);
  Repeat
    Result:=PByte(p1)^-PByte(p2)^;
    If(Result<>0then exit;
    If(lcomp=l) then exit;
    Inc(p1);Inc(p2);
    Inc(lcomp);
  Until false;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  freq,startTime,endTime: Int64;
  i:Integer;
  s1,s2,s3,s4,s5,s6:String;
  l1,l2,l3,l4,l5,l6:Integer;
  arrayB:Integer;
  b:Integer;
begin
  Memo1.Clear;
  s1:='Btdfu%&6554787BGHBtzbTuzGT';
  s2:='Btdfu%&6554787BGHBtzbTuzGT';
  s3:='Btdfu%&6554787BGHBtzbTuzG';
  s4:='Btdfu%&6554787BGHBtzbTuzGA';
  s5:='Btdfu%&6554787BGHBtzbTuzGt';
  s6:='Atdfu%&6554787BGHBtzbTuzGt';
  l1:=Length(s1);
  l2:=Length(s2);
  l3:=Length(s3);
  l4:=Length(s4);
  l5:=Length(s5);
  l6:=Length(s6);
  arrayB:=0;
  QueryPerformanceFrequency(freq);
  QueryPerformanceCounter(startTime);

  //Befehlesfolge deren Zeitdauer bestimmt werden soll
  for i:=0 to 9999999 do begin
    b:=l1-l2;
    if(b=0then b:=CompStr(s1,s2,l1);
    b:=l1-l3;
    if(b=0then b:=CompStr(s1,s3,l1);
    b:=l1-l4;
    if(b=0then b:=CompStr(s1,s4,l1);
    b:=l1-l5;
    if(b=0then b:=CompStr(s1,s5,l1);
    b:=l1-l6;
    if(b=0then b:=CompStr(s1,s6,l1);
  end;

  QueryPerformanceCounter(endTime);

  Memo1.Lines.Add('1.Variante: ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
  Memo1.Lines.Add(inttostr(arrayB));

  arrayB:=0;
  QueryPerformanceFrequency(freq);
  QueryPerformanceCounter(startTime);

  //Befehlesfolge deren Zeitdauer bestimmt werden soll
  for i:=0 to 9999999 do begin
    b:=CompareText(s1,s2);
    b:=CompareText(s1,s3);
    b:=CompareText(s1,s4);
    b:=CompareText(s1,s5);
    b:=CompareText(s1,s6);
  end;

  QueryPerformanceCounter(endTime);

  Memo1.Lines.Add('2.Variante: ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
  Memo1.Lines.Add(inttostr(arrayB));
end;


Aktuelle Zeiten:
(Variante1;Variante2)
Normal: 1169;4389
FastMM4: 1096;4470
FastMM4+FastCode: 1089;1363

Auskommentieren von s3-->Alle Strings haben gleiche Länge-->1.Variante hat Nachteil
FastMM4: 1090;3620
FastMM4+FastCode: 1073;901

Nur Vergleich von s1 und s2-->Gleiche Strings
FastMM4+FastCode: 196;45

-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller

Kann Jemand meine Funktion in ASM übersetzen und optimieren? Sollte einiges bringen


SvenAbeln - Mi 29.10.08 14:29

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:

-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller


Und in den anderen Fällen ist dein Vergleich etwas unfair.

Die Länge der Strings wird nur einmal zu Beginn bestimmt und dies geht noch nicht einmal in die gemessene Zeit mit ein.

Bei verschiedenen Längen macht deine Variante 1 in der Schleife nur noch einen Vergleich von L1 und L3 ohne die Längen aber jeweils neu zu berechnen.
Die eigentliche Vergleichfunktion CompStr(s1,s3,l1) wird dann gar nicht mehr aufgerufen.

Wenn der Längenvergleich Teil deiner Optimierung sein soll, dann müssen die Zeiten zum bestimmen der Länge aber auch mit in deine Zeitmessung eingehen.

Ansonsten hätte ich eine schneller Lösung : :twisted: :wink:

Delphi-Quelltext
1:
2:
3:
4:
  b3 := CompareText(s1,s3); 
  for i:=0 to 9999999 do begin
    b:= b3;
  end;


Flamefire - Mi 29.10.08 18:21

es geht aber darum, dass die längenberechnung nur einmal ausgeführt wird, außerhalb der vergleichsmethode...
um genau zu sein, könnte ich aber die längenmessungen mit unter das queryperformance... setzen
ist aber ebn nur einmal! und da es ne simple kopierfunktion von 4 Byte ist sollte das nur 1ms ausmachen


SvenAbeln - Mi 29.10.08 18:54

Aber du willst doch in der Realität doch verschiedene Strings vergleichen und nicht 9999999 mal immer wieder die selben. Daher wirst du dann auch jedesmal die Längenmessungen machen müssen.

Was dein Vergleich im Moment für ungleiche Stringlängen aussagt ist:
9999999 mal
b:=l1-l3;
und prüfen ob b=0 // was es in diesem Fall ja nicht ist

ist schneller als:
9999999 mal compareText

Aber wie sieht es aus wenn du nun 9999999 mal verschiedene Strings vergleichen willst?


alzaimar - Mi 29.10.08 19:01

Nochmal für mich als Hausfrau, zum Mitschreiben: Du willst eine Ordnung auf Strings. Nicht notwendigerweise eine lexikalische Ordnung, aber zumindest eine (totale) Ordnung. Als Performancetrick definierst du, das kürzere Strings stets "kleiner" und längere Strings stets "größer" als ein Referenzstring ist. Soweit richtig?

Wie lautet der Funktionsaufruf (bevor irgendetwas verglichen wird)? Ich schlage vor:

Delphi-Quelltext
1:
Function FastCompareStrings (Const s1, s2 : String) : integer;                    


Wenn Du jedoch z.B. einen String 'X' hast, den Du gegen 1.000.000 andere Strings vergleichen willst, sieht die Sache anders aus. Also?


Flamefire - Mi 29.10.08 19:21

ok es geht um listen von strings
diese listen wird einmal erstellt und muss dann (möglicherweise) sehr oft gegeneinander abgeglichen werden

darum nur einmal die längenberechnung aber der häufige vergleich

trotzdem ist selbst mit längenberechnung jedesmal der stringvergleich über die länge vorher um 100-200ms schneller

was fehlt ist also eine optimierte version meines vergleichs


SvenAbeln - Mi 29.10.08 19:40

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:

trotzdem ist selbst mit längenberechnung jedesmal der stringvergleich über die länge vorher um 100-200ms schneller

was fehlt ist also eine optimierte version meines vergleichs


Du hattest doch oben schon geschrieben:
user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:

-->Nur bei gleich Langen Strings oder gleichen Strings ist Fastcode schneller

Warum kombinierst du dann nicht beide Varianten?
Deinen Vergleich rufst du ja auch nur bei gleich langen Strings auf.

Also erst Vergleich über die Länge und dann Fastcode.

Delphi-Quelltext
1:
2:
    b:=l1-l2;
    if(b=0then b:=FastCode ;


Flamefire - Mi 29.10.08 19:57

weils es mir am liebsten wäre, den FastCode noch weiter zu optimieren, da die Länge ja schon feststeht


alzaimar - Mi 29.10.08 20:13

Das hier ist eh schneller:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
Function FastCompare (Const s1, s2 : String) : Integer;
Var
  l1, i : Integer;

Begin
  l1 := Length(s1);
  Result := l1 - Length(s2);
  if Result=0 then
    For i := 1 to l1 do
      if s1[i]<>s2[i] then begin
        Result := Ord(s1[i])-Ord(s2[i]);
        Exit;
      End;
End;

Vorteil: Die ganze Optimierungslogik ist in einer Routine gekapselt.


SvenAbeln - Mi 29.10.08 20:27

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
weils es mir am liebsten wäre, den FastCode noch weiter zu optimieren, da die Länge ja schon feststeht


Wenn du die Länge schon hast, dann benutze diese Information doch auch beim Fastcode.
Wie eben schon geschrieben, erst die Länge prüfen und nur wenn die gleich ist den Fastcode benutzen, der ja gerade bei gleich langen Strings schneller ist.


Flamefire - Mi 29.10.08 21:09

@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen

@sven: ja hab ich auch vor, aber den fastcode kann man ja weiter optimieren, da der die länge nicht mehr beachten muss


alzaimar - Mi 29.10.08 23:14

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen

Hast Du es auch getestet? :wink: Ich würde nicht behaupten, es sei schneller, wenn ich es nicht selbst... aber was red ich, gegen solch geballtes Fundamentalwissen bin ich machtlos.


Gammatester - Mi 29.10.08 23:17

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
@alzaimar: diese methode ist auf jeden fall langsamer, da byteweise verglichen wird. bei mir wird 4-byte weise verglichen


Irgendwann mußt Du allerdings mal sagen, wie Du nun die 4-Byte-Problematik lösen willst. Mit dem Integervergleich ist zb 'ÄÄÄÄ' kleiner als 'aaaa', aber zb nicht 'XXXXÄ' kleiner als 'XXXXa' wenn der letzte Vergleich über ord('Ä') und ord('a') geht. Also insgesamt ziemlich unbefriedigend.

Gammatester


Flamefire - Mi 29.10.08 23:39

mir geht es ja (wie oben beschrieben) nicht um eine lexikalische ordnung sondern nur um irgendeine Ordnung
und da reicht es einen string in 4-byte-pakete zu zerlegen und sich zu nutze zu machen dass der prozessor sowieso mit 4 byte (32bit) arbeitet. sollte um den faktor 3-5 schneller sein (je nachdem wie er intern die byteumwandlung macht)

Fastcode arbeitet ja in gewissem sinne mit dieser methode. allerdings hat er ein paar umwandlungen und rechnerein drin, die für mich nicht nötig sind (groß/kleinschreibung) und eben der lexikalische teil
meine asm kenntniss sind leider nicht so gut um da wirklich durchzusehen


alzaimar - Do 30.10.08 10:42

Also mein Code ist auf meinem Laptop schneller, auf einem AMD64 dagegen viel langsamer... Na ja, ich rudere also 50% zurück.

Egal. Geh nochmal auf die FastCode-Seite und lade Dir die Ergebnisse von 'CompareStr' (nicht CompareText). Hier meine Ergebnisse mit deinem Benchmark:

CompStr: 1465ms
CompareText: 2538ms
Fastcode_CompareStr: 1046ms


Flamefire - Do 30.10.08 12:05

verdammt...ja hab übersehn, dass bei groß/kleinschreibung es langsamer wird, wenn es ignoriert werden soll...
compareStr mit längen-überprüfung vorher ist demnach das schnellste...doppelt so schnell, wie meine bisherige methode


Motzi - Mo 10.11.08 19:38

Du solltest für der Optimierung nicht bei der Implementierung ansetzen, sondern beim Algorithmus..! Ein schlecht implementierter Quicksort ist immer noch um Größenordnungen schneller als ein perfekt implementiert und hochoptimierter Bubblesort - und so ähnlich ist es hier auch.

Daher werfe ich einfach mal Suffix-Trees [http://en.wikipedia.org/wiki/Suffix_tree] in die Runde. Ist zwar sicher etwas mehr Implementierungsaufwand, aber dafür baust du diese genau einmal auf (in linearer Zeit) und kannst dann in ebenfalls linearer Zeit darin suchen!

Gruß, Motzi