|
Registriert seit: 17. Nov 2005
Ort: Hamburg
1.063 Beiträge
Delphi XE2 Professional
|
Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen
7. Dez 2007, 20:38
Zitat von alzaimar:
Zitat von sirius:
Und da gibts nicht viel zu optimieren, ausser dass man alle Variablen in Registern vorhält
Das das nichts bringt, hast Du gut erklärt.
Zitat von sirius:
Edit: Die Sprungtabelle und das Vergleichen des ersten Zeichens sind der Kern. Der Rest ist Zugabe.
Der Vergleich des letzten Zeichen bringt auch nochmal viel, da dadurch der Aufruf von CompareMem nochmals reduziert wird. @alzaimar, sirius:
Ich denke, daß es da sehr wohl einiges zu optimieren gibt.
Deshalb habe ich mir die Mühe gemacht eine etwas schnellere ASM-Routine zu schreiben und die Performance zu testen.
Diese Routine ist ein "PosEx", man kann also auch vorgeben ab welcher Position im String gesucht werden soll.
Für die Performance-Messung wurde der String "SearchIn" auf eine Länge von 1Mio Zeichen gestellt, komplett mit dem Zeichen "a" gefüllt und der String "SearchFor" an das Ende von "SearchIn" gestellt.
Dann wurde für alzaimars, siriuss, meine und die system.pos Routine die Zeit (CPU-Ticks) gemessen.
Und das sind die Ergebnisse, die meines Erachtens für sich sprechen
Code:
SearchFor b ab aba abba abbba abbbba abbbbba
alzaimar 3921148 4668872 145252980 145397708 145417164 87380040 87976592
sirius 3887104 4618452 145108488 145395176 145382700 87022640 86831224
amateurprofi 2845308 4612200 8583452 9482744 9258968 9259532 74201884
system-Pos 4172836 128869200 128814300 129164580 129334480 129133380 128982992
Die drastisch bessere Performance bei den Fällen, in denen SearchFor 3,4,5 oder 6 Zeichen lang ist, ergibt sich daraus, daß
meine Routine für die Fälle Length(SearchFor)<7 jeweils eine eigene Suchroutine benutzt, die nicht das bummelige CompareMem
verwendet.
Ich bin überzeugt, daß meine Routine; die nur ein erster Entwurf ist, durchaus noch einiges Optimierungs-Potenzial beinhaltet und werde mir demnächst noch ein paar Gedanken dazu machen.
Ein kleines simples Testprogramm ist im Anhang, die Beschreibung steht in ReadMe.txt
Und hier die Routine QPosEx
Delphi-Quellcode:
// Version von amateurprofi
FUNCTION QPosEx(SearchFor,SearchIn: String; Start:integer):integer;
asm
pushad // Alle Register auf Stack legen
sub esp,$400 // Platz für Skiptabelle schaffen
// Auf dem Stack liegen folgende Daten
// ESP : Skiptabelle
// ESP+$400..$410 : EDI, ESI, EBP, ESP, EBX
// ESP+$414 : EDX Adresse SearchIn
// ESP+$418 : ECX Start
// ESP+$41C : EAX Adresse SearchFor
// ESP+$420 : EBP
// ESP+$424 : Returnadresse
// Prüfen, ob SearchFor oder SearchIn leer ist, oder Start negativ ist
test eax,eax
je @Fail // SearchFor ist leer
test edx,edx
je @Fail // Searchin ist leer
mov ebx,[eax-4] // Länge SearchFor
test ebx,ebx
je @Fail // SearchFor ist leer
test ecx,ecx
js @Fail // Start ist negative
// Erste und letzte mögliche Fundstelle in ESI bzw. EBP
je @1
sub ecx,1 // =Start 0-basierend
@1: lea esi,[edx+ecx] // Ab hier soll gesucht werden
add edx,[edx-4]
mov ebp,edx
sub ebp,ebx // Bis hier soll gesucht werden
// Prüfen, ob Erste mögliche Fundstelle hinter letzter liegt
cmp esi,ebp
ja @Fail
// Prüfen, ob SearchFor nur 1 Zeichen ist
// Dann ist keine SkipTabelle erforderlich
cmp ebx,1
je @Search1
// Skiptabelle erstellen
// 1) for i:=0 to 255 do Skip[i]:=n+1
mov edi,esp
mov ecx,$100
mov eax,ebx
add eax,1 // Length(Searchfor)+1
rep stosd
// 2) For i:=0 To n-1 Do Skip[SearchFor[i]]:=n-i
mov edi,[esp+$41C] // Adresse SearchFor
mov eax,ebx // Length(Searchfor)
@FillSkip: movzx edx,[edi+ecx] // SearchFor[i]
mov [esp+edx*4],eax // Skip[SearchFor[i]]:=n-i
add ecx,1
sub eax,1
jne @FillSkip
// Erstes und Letztes Zeichen von SearchFor in AL/AH
mov al,[edi] // Erstes Zeichen SearchFor
mov ah,[edi+ebx-1] // Letzes Zeichen SearchFor
// Prüfen, ob Length(SearchFor) > 6 ist
cmp ebx,6
ja @SearchX
jmp @Vector.Pointer[ebx*4-8]
@Vector: dd @Search2
dd @Search3
dd @Search4
dd @Search4 // Länge=5
dd @Search6
// Länge Searchfor > 6
@SearchX: add edi,1 // Auf zweites Zeichen von SearchFor
mov [esp+$41C],edi // Merken für CompareMem
jmp @Search
// Länge SearchFor > 6
@SkipX: mov esi,edx // Aufruf ex CompareMem
@Skip: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search: cmp [esi],al
jne @Skip
cmp [esi+ebx-1],ah
jne @Skip
// Zweites bis vorletzten Zeichen von SearchFor prüfen
mov edx,esi // ESI retten
mov edi,[esp+$41C] // Zeiger zweites Zeichen von SearchFor
add esi,1 // Zeiger Text auf nächstes Zeichen
mov ecx,ebx // Length(SearchFor)
sub ecx,2 // -2 (Erstes und letztes Zeichen)
shr ecx,2 // =Anzahl DWords
repe cmpsd // DWords vergleichen
jne @SkipX // Nicht gleich
mov ecx,ebx // Length(SearchFor)
sub ecx,2 // -2 (Erstes und letztes Zeichen)
and ecx,3 // =Anzahl restliche Bytes
repe cmpsb // Bytes vergleichen
jne @SkipX // Nicht gleich
mov esi,edx // Fundstelle
jmp @Found
// Länge SearchFor=1
@Search1: mov ecx,ebp // Letzte mögliche Fundstelle
sub ecx,esi // - Erste mögliche Fundstelle
add ecx,1 // = Anzahl zu prüfende Zeichen
neg ecx
sub esi,ecx
mov al,[eax] // zu suchendes Zeichen
@Loop: cmp al,[esi+ecx]
je @Found1
add ecx,1
jne @Loop
jmp @Fail
@Found1: lea esi,[esi+ecx] // ESI auf Fundstelle
jmp @Found
// Länge SearchFor=2
@Skip2: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search2: cmp [esi],al
jne @Skip2
cmp [esi+ebx-1],ah
jne @Skip2
jmp @Found
// Länge SearchFor=3
@Skip3: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search3: cmp [esi],al
jne @Skip3
cmp [esi+ebx-1],ah
jne @Skip3
mov dx,[edi]
cmp dx,[esi]
jne @Skip3
jmp @Found
// Länge SearchFor=4 oder 5
@Skip4: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search4: cmp [esi],al
jne @Skip4
cmp [esi+ebx-1],ah
jne @Skip4
mov edx,[edi]
cmp edx,[esi]
jne @Skip4
jmp @Found
// Länge SearchFor=6
@Skip6: movzx edx,[esi+ebx]
add esi,[esp+edx*4]
cmp esi,ebp
ja @Fail
@Search6: cmp [esi],al
jne @Skip6
cmp [esi+ebx-1],ah
jne @Skip6
mov edx,[edi+1]
cmp edx,[esi+1]
jne @Skip6
jmp @Found
@Found: // Gefunden, Index berechnen
sub esi,[esp+$414]
add esi,1
jmp @SetRes
@Fail: // Nicht gefunden, Result=0
xor esi,esi
@SetRes: // Result speichern
mov [esp+$41C],esi
// Skiptabelle vom Stack nehmen
add esp,$400
// Register wieder herstellen, Result in EAX
popad
end;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
|