Boyer Moore Algorithmus

[Amateurprofi]

Zitat von Horst_:

Ich würde in der ASM Version mal an repne scasb //scasw in Betracht ziehen.

Ich nicht!
Zumindest bei mir ist das langsamer, als konventionelles Cmp
Und das war bei mir schon immer so, beim 80486,Pentium, Pentium II, Core 2 und jetzt Core I7.
Bei anderen CPUs mag das anders sein.
Ich meide all diese schönen Super-Instrutionen wie Cmps, Lods, Scas, Stos, Loop.
Die sind zwar schön bequem, aber langsamer.

Hier mal ein kleines Test-Szenario, das in 800 Bytes erfolglos sucht.
Es wird 1000 Mal getestet wie viel CPU-Ticks Repne Scasb und Cmp brauchen.
Die jeweiligen Minimum-Ticks werden gegenübergestellt.
Bei mir ergab sich für Repne Scasb 3526 Ticks, für konventionelles Cmp 3468 Ticks.
Kein großer Unterschied, aber jedenfalls ein Unterschied zu Gunsten Cmp.

Delphi-Quellcode:

PROCEDURE TestRepneScas(var T1,T2:Int64);
const len=800;
asm
         // Register sichern
         push     ebp
         push     ebx
         push     edi
         push     esi
         // Parameter sichern
         push     eax                     // @T1
         push     edx                     // @T2
         // Len Bytes auf Stack reservieren und mit 0 füllen
         sub      esp,len
         mov      ecx,len
         lea      edx,[esp+ecx]
         neg      ecx
@L1:     mov      byte[edx+ecx],0
         add      ecx,1
         jl       @L1
         // repnw Scasb testen
         rdtsc
         mov      ebp,eax                 // TSC.Lo
         mov      ebx,edx                 // TSC.Hi
         mov      ecx,len                 // Anzahl Bytes
         mov      edi,esp                 // Ab hier prüfen
         mov      al,1                    // 1 suchen (wird nicht gefunden
         repne    scasb
         rdtsc
         sub      eax,ebp
         sbb      edx,ebx
         mov      ebp,eax                 // Ticks für Repne Scas byte
         mov      ebx,edx
         // konventionelle Schleife
         rdtsc
         mov      edi,eax
         mov      esi,edx
         mov      ecx,len                 // Anzahl Bytes
         lea      edx,[esp+ecx]
         neg      ecx
         mov      al,1
@L2:     cmp      [edx+ecx],al
         je       @Found                  // wird nicht eintreten
         add      ecx,1
         jl       @L2
@Found:  rdtsc
         sub      eax,edi                 // Ticks für konventionelles cmp byte
         sbb      edx,esi
         // Len Bytes auf Stack freigeben
         add      esp,len
         pop      ecx                     // @T2
         mov      [ecx],eax               // T2.Lo
         mov      [ecx+4],edx             // T2.Hi
         pop      ecx                     // @T1
         mov      [ecx],ebp               // T1.Lo
         mov      [ecx+4],ebx             // T1.Hi
         // Register wiederherstellen
         pop      esi
         pop      edi
         pop      ebx
         pop      ebp
end;

Delphi-Quellcode:

PROCEDURE TMain.Test;
const count=1000;
var samask,pamask,tamask:NativeUInt;
    t1,t2,ticks1,ticks2:Int64; i:integer; s:string;
begin
   i:=Pos('a',s);
   // Thread auf 1 CPU fixieren
   GetProcessAffinityMask(GetCurrentProcess,pamask,samask);
   if pamask=0 then exit;
   tamask:=1;
   while tamask and pamask=0 do tamask:=tamask shl 1;
   SetThreadAffinityMask(GetCurrentThread,tamask);
   ticks1:=High(Int64);
   ticks2:=High(Int64);
   for i:=1 to count do begin
      TestRepneScas(t1,t2);
      if t1<ticks1 then ticks1:=t1;
      if t2<ticks2 then ticks2:=t2;
   end;
   ShowMessage('Repne Scas: '+IntToStr(ticks1)+' Ticks'#13+
               'Konv. CMP: '+IntToStr(ticks2)+' Ticks'#13+
               'Delta: '+IntToStr(ticks1-ticks2)+' Ticks');
end;