Testprogramm zur prozessorspezifischen X86-Codeoptimierung

[mschnell]

64 Bit

Hast Du die Test-Schleifen auch in 64 Bit Assembler mitgeliefert ?

Sonst ginge das doch gar nicht ...

Zweite Idee: Du arbeitest mit CodeTyphoon.

Bei Assembler-Teilen darf doch das Compile-System (genau wie das Betriebssystem) keinerlei Einfluss auf ein solches Programm haben ?!?!?!?!?

-Michael

[Horst_h]

Hallo,

ich habe mal meine Pascal Variante eingebaut und das Programm gestartet, sie ist schneller als alle Assembler-Varianten. Das sollte doch zu denken geben.

Code: Alles auswählen

 
Function OwnPascal_NoAlign                   Verified   1,253 s  ( 67,4 %)  =    30 ns / Call
    Run 2                                    Verified   1,250 s  ( 67,2 %)  =    30 ns / Call
    Run 3                                    Verified   1,259 s  ( 67,7 %)  =    30 ns / Call
    Run 4                                    Verified   1,252 s  ( 67,3 %)  =    30 ns / Call
...
die zeitlich nächste Variante:
Function CharPos_Asm3c_InsideLoop_9          Verified   1,257 s  ( 67,6 %)  =    30 ns / Call  =    25 ns Loop time / Call
    Run 2                                    Verified   1,253 s  ( 67,4 %)  =    30 ns / Call  =    25 ns Loop time / Call
    Run 3                                    Verified   1,251 s  ( 67,3 %)  =    30 ns / Call  =    25 ns Loop time / Call
    Run 4                                    Verified   1,255 s  ( 67,5 %)  =    30 ns / Call  =    25 ns Loop time / Call 

Was mich auch sehr wunderte, dass normalerweise ( Delphi 32 Bit ) die Daten in den Register EAX dann EDX dann ECX übergeben werden, dies könnte man in assembler auch ausnutzen.
Der Pascal Schnipsel in der Assemblerausgabe

Code: Alles auswählen

# Temps allocated between esp+0 and esp+12
# [71] begin
	subl	$12,%esp
.Lc14:
# Var c located in register al
# Var s located in register edx
# Var $result located in register ebx
# Var cntS located in register edi
# Var LenS located in register esi
# Var PS located in register edx
	movl	%ebx,(%esp)
	movl	%esi,4(%esp)
	movl	%edi,8(%esp)
# [72] result := 0;
	movl	$0,%ebx
# [73] LenS   := Length(S);
	movzbl	(%edx),%esi
# [74] if LenS = 0 then
	testl	%esi,%esi
	je	.Lj72
# [76] CntS := 1;
	movl	$1,%edi
# [78] while PS[Cnts] <> c do
	jmp	.Lj85
	.balign 2,0x90
.Lj84:
# [80] Inc(CntS);
	incl	%edi
# [81] if CntS > LenS then
	cmpl	%esi,%edi
	jg	.Lj72
.Lj85:
	movb	(%edx,%edi,1),%cl
	cmpb	%al,%cl
	jne	.Lj84
.Lj86:
# [84] result := cntS;
	movl	%edi,%ebx
.Lj72:
# [85] end;
	movl	%ebx,%eax
	movl	(%esp),%ebx
	movl	4(%esp),%esi
	movl	8(%esp),%edi
	addl	$12,%esp
	ret

Gruß Horst

[marcov]

Und wie geht das mit ein Indexbyte() basierter Lösung?

Code: Alles auswählen

 
Function Pos(c : AnsiChar; Const s : RawByteString) : SizeInt;
begin
  pos:=0;
  if length(s)>0 then
      pos:=indexbyte(s[1],length(s),c)+1;
end;
 

[mschnell]

ich habe mal meine Pascal Variante eingebaut und das Programm gestartet, sie ist schneller als alle Assembler-Varianten. Das sollte doch zu denken geben.

(Falls es nicht doch ausschließlich an der Test-Umgebung liegt...)

Die Assembler-Varianten sind somit offensichtlich schlecht optimiert.

Entweder bezüglich der "normalen" Arbeitsweise eines "old-School" Prozessors, oder bezüglich der (hier ja zu testenden) Empfindlichkeit moderner Prozessoren (mit breiten Datenpfaden zum 1st Level Cache,Jump-Prediction, usw.)

Meiner Ansicht nach ist die vernünftigste Art mit Assembler (zu Optimierungs-Zwecken) umzugehen sich zunächst anzusehen was der Compiler (fpc oder - meist besser - gcc ) für Code erzeugt und dann versuchen von Hand zu optimieren. Und natürlich testen ob das tatsächlich was bringt.

Der von fpc erzeugte Code ist doch völlig geradeaus. Man würde in ASM doch - wenn man sich keine weiteren Gedanken macht - ziemlich dasselbe schreiben.

fpc macht hier kein Loop-Enrolling. gcc würde das vermutlich tun. Das könnte einen erheblichen Unterschied machen.

-Michael

[ruewa]

"Versuch" ist völlig in Ordnung und natürlich sinnvoll. Er gibt Hinweise, wie man weiter vorgehen kann.

Michael, ganz genau so, und keinen Deut anders, hatte ich das vor Tagen schon geschrieben. Diskussionen werden ziemlich zäh, wenn sie ignorieren, was einer sagt, und sich stattdessen bequemlichkeitshalber nur noch darum drehen, was man felsenfest erwarten würde, vorzufinden, wenn man sich denn die Mühe machte, es zu lesen, was sich aber schon deshalb erübrigt, weil man's doch eh schon kennt...

Hast Du die Test-Schleifen auch in 64 Bit Assembler mitgeliefert ?

Sonst ginge das doch gar nicht ...

Wäre Runterladen und im Dateimanager einen kurzen Blick auf die Dateinamen im Zipfile werfen schon zuviel des Aufwands? Oder hält sowas bloß von den wichtigeren Dingen im Leben ab, z.B. im Forum Verrisse zu formulieren?

Um ein signifikantes Ergebnis einer Messung unter Störeinflüssen zu bestimmen muss die Messanordnung (inklusive statistischer Auswertung) so geartet sein dass der Einfluss der Störfaktoren als klein genug (statistisch "nicht signifikant") bewertet werden kann.

Richtig. Und ob die dem Testdesign zugrundeliegende Annahme, daß dieses hinreichend trennscharf sein würde, berechtigt ist oder nicht, läßt sich letztlich erst anhand einer hinreichend großen Anzahl von Ergebnis-Rückmeldungen beurteilen. Die müßten halt erstmal zustandekommen, anstatt bräsig zerredet zu werden. Michael, wie wäre es denn, wenn Du mir bei der statistisch sauberen Anlage der Auswertung helfen würdest, z.B. mit Tips, wie man mit stochastischen Peaks am besten umgeht (rausschmeißen, gewichten, Standardabweichungen, das ganze Zeug), statt ziemlich unbesehen alles in Bausch und Bogen zu verdammen, was von anderen kommt? Wenn wir zusammenarbeiten würden, statt uns zu bekriegen, hätten alle mehr davon!

ich habe mal meine Pascal Variante eingebaut und das Programm gestartet, sie ist schneller als alle Assembler-Varianten. Das sollte doch zu denken geben.

Horst, genau diese Beobachtung hat mich monatelang umgetrieben! Die logische Konsequenz ist klar: Es muß also noch effizientere Assembler-Codevarianten geben! Aber gilt das dann nur für Deinen einen Prozessor, oder läßt sich das verallgemeinern? Funktioniert das, was bei Dir superschnell läuft, auch auf anderen Rechnern richtig gut? Irgendjemand sollte vielleicht mal ein Programm schreiben, das die Performance Deiner optimalen Routine mißt, es veröffentlichen und andere bitten, diesen Test auch auf ihren Rechnern laufen zu lassen und die Ergebnisse mitzuteilen...

Ähem... Merkst Du was?

Wie wäre es denn, Horst, wenn Du auch mal den originalen, unveränderte AlignTest laufen lassen und Deine Ergebnisse durchreichen würdest? Zum basteln haben wir dann alle Zeit der Welt.

Gruß Rüdiger

PS: Schade, daß die einfachen Dinge so gnadenlos untergehen, wenn Deutsche über Prinzipien debattieren... Nochmals meine Bitte: Könnte einer der Windows-Nutzer mir bitte einen Vorschlag machen, welches Unterverzeichnis als Default eingestellt werden müßte, um nur die Bibliotheksdateien von Lazarus zu erfassen (so daß man auf etwa 4.000 Dateien kommt)? Ich würde das Programm wirklich gerne dahingehend ändern, daß es auch unter Windows tatsächlich die versprochenen 12 Minuten plusminus läuft, anstatt wohlmeinende Nutzer mit Laufzeiten von einer Dreiviertelstunde zu verärgern.

[Horst_h]

Hallo,

wie Du schon gelesen hast, tut sich bei Intel i3/i5/i7 nicht viel.Mein erster Test passt damit recht genau.

Code: Alles auswählen

{$IFDEF FPC}
  {$MODE objFPC}
  {$OPTIMIZATION ON,REGVAR,PEEPHOLE,CSE,ASMCSE}
  {$CODEALIGN proc=16,Loop=16}
{$ENDIF}
uses
  sysutils;
const 
  //searching cUnknown characters in string of cMylen 
  // cMyLen+cUnknown < 256 !
  cMyLen   =  38; 
  //searching cUnknown characters in string of cMylen 
  //Number of matches per function:                6,535,345   =  29.50 % 
  cUnknown =  round(cMyLen*(1/0.295-1));
 
  //memory occupied by strings 
  cSpeicher = 32*32*32*1024;// 32*32*32*1024; 32 MB/1 Mb / 32 Kb
  // count of strings
  cMax = cSpeicher div SizeOf(shortstring);
  NumberOfPosCheck =  22*1024*1024;
  RUNDEN = (NumberOfPosCheck-1) DIV (cMax*(cMyLen+cUnknown));      
type
  tshortStringArray = array [0..cMax-1] of ShortString;  
  tmyF = function (c : Char; const s : ShortString):NativeInt;  
 
var
  dt : tDateTime;
  ShortStringArray: tshortStringArray;
  sMix :shortString;
  sumPos : NativeUint;
 
procedure ShuffleS(var s:shortString);
var
  i,j: NativeInt;
  c : char;  
begin
  For i := length(s) downto 2 do
  Begin
    j := random(i)+1;
    c := s[j];s[j]:= s[i];s[i]:= c;
  end;
end;    
 
procedure Init(var sFeld:tshortStringArray);
//create cmax shuffled strings of length cMyLen
//search for cMyLen+cUnknown characters in sMix 
var
  s : shortString;
  i : NativeInt;
begin
  setLength(s,cMyLen);
  For i := 1 to length(s) do
    s[i] := chr(i+31); 
  For i := Low(ShortStringArray) to High(ShortStringArray) do
  Begin
    sFeld[i] := s;
    ShuffleS(sFeld[i]);
  end;
 
  //string of characters searched for
  smix := s;
  setlength(smix,cMyLen+cUnknown);
  For i := length(s)+1 to length(sMix) do
    sMix[i] := chr(i+31); 
  ShuffleS(sMix);  
 
  writeln(s);  
  writeln(sMix);    
  writeln;
end;  
 
function SmallTest(myF:tmyF;const s: shortString): NativeUint;
var
  i : integer;
  pc : pChar;
Begin
  pc := @sMix[0];  
  result := 0;
  For i := 1 to Length(sMix) do
    inc(result,myF(pc[i],s));
end;
 
procedure Test(myF:tmyF);
var
  t1,t0: TDateTime;
  i,j,k,r: NativeUInt;
 
Begin  
  For i := 0 to 3 do
  Begin
    t0:= now;
    r := 0;
    For k := Runden-1 downto 0 do
      For j := Low(ShortStringArray) to High(ShortStringArray) do
        inc(r,SmallTest(myF,ShortStringArray[j]));
    t1:= now;        
    if r <> sumPos then
      write('Error  ') 
    else
      write((t1-t0)/dt*100.0:8:3,'% ');
  end;
  writeln;    
end;  
 
function SmallOrgPos(const s: shortString):NativeUint;
var
 i : integer;
  pc : pChar;
Begin
  result := 0;
  pc := @sMix[0]; 
  For i := Length(sMix) downto 1 do
    result := result+Pos(pc[i],s);
end;
 
procedure OrgPos;
var
  j,k: NativeInt;
Begin  
  sumPos := 0;
  For k := Runden-1 downto 0 do
    For j := Low(ShortStringArray) to High(ShortStringArray) do
      inc(sumPos,SmallOrgPos(ShortStringArray[j]));
end;
 
function CharPos_Pascal(c : Char; const s : ShortString):NativeInt;
var  
  cntS,     
  LenS : NativeInt;
  PS   : PChar;
begin
  result := 0;  
  LenS   := Length(S);
  if LenS = 0 then
    exit;
  CntS := 1;
  PS := @S[0];
  while PS[Cnts] <> c do
  begin
    Inc(CntS);
    if CntS > LenS then 
      exit;
  end;
  result := cntS;
end;
 
Function MarcovPos(c : AnsiChar; Const s : ShortString) : SizeInt;
begin
  MarcovPos:=0;
  if length(s)>0 then
    MarcovPos:=indexbyte(s[1],length(s),Ord(c))+1;
end;
//use it, if you like it
function CharPos_AsmX(c : Char; const s : ShortString): NativeInt; assembler; register; nostackframe;
asm
            xorl   %ecx,%ecx
            pushl  %esi               // Save ESI
            addb   (%edx),%cl        
            jz     .LExit0            // if Length(s) = 0 then exit with result = 0 in AX
            xorl   %esi,%esi
            jmp   .LLoop
            .balign 16
  .LLoop:   
            incl   %esi  
            cmp    %esi,%ecx   
            jb     .LExit0
          	cmpb  (%edx,%esi,1),%al
            jne     .LLoop
  .LExit:   mov    %esi,%eax
            popl   %esi   
            ret
 
  .LExit0:  xorl   %eax,%eax
            popl   %esi 
end;
//Copyright (C) 2015 Ruediger Walter <rue.walter@web.de>
//CharPosAsmFuncs_i386.inc
function CharPos_Asm3c_InsideLoop_0(c : Char; const s : ShortString): NativeInt; assembler; register; nostackframe;
asm
            pushl  %esi               // Save ESI
            movl   s, %esi            // @s -> ESI (s handed over in EDX)
            movzbl c, %edx            // c -> DL   (c handed over in AL)
            xorl   %eax, %eax         // Clear EAX
            xorl   %ecx, %ecx         // Clear ECX
            addb  (%esi), %cl         // Length(s) -> CL   (XOR/ADD is faster than MOVZx/TEST sequence)
            jz     .LExit             // if Length(s) = 0 then exit with result = 0 in AX
            movw   %cx, %ax           // copy Length(s) -> AX
            incw   %ax                // CntDownS in AX := Length(s)+1  ( not used in Version 1)
            jmp    .LLoop
    .balign 16                        // aligned to 16
  .LLoop:   subw   $1, %ax            // 4 Byte code 662d0100
            jz     .LExit             // 2 Byte code 74xx
            incl   %esi               // 1 Byte code 46
            cmpb   (%esi), %dl        // 2 Byte code 3a16
            jne    .LLoop             // 2 Byte code 75xx
            jmp    .LResult           // 2 Byte code ebxx
    .balign 16
  .LResult: subw   %ax, %cx           // Match result := LenS in CX - CntDownS in AX + 1 -> AX
            movw   %cx, %ax
            incw   %ax
  .LExit:   popl   %esi               // Restore ESI
end;
//Copyright (C) 2015 Ruediger Walter <rue.walter@web.de>
//CharPosAsmFuncs_i386.inc
function CharPos_Asm3b_LoopStart_9(c : Char; const s : ShortString): NativeInt; assembler; register; nostackframe;
asm
            pushl  %esi
            movl   s, %esi
            movzbl c, %edx
            xorl   %eax, %eax
            xorl   %ecx, %ecx
            addb  (%esi), %cl
            jz     .LExit
            movw   %cx, %ax
            incw   %ax
            jmp    .LLoop
    .balign 16                        // 0 + 9 byte NOP (never reached)
    .byte   0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00                //  9 x NOP
  .LLoop:   decw   %ax
            jz     .LExit
            incl   %esi
            cmpb   (%esi), %dl
            jne    .LLoop
            jmp    .LResult
    .balign 16
  .LResult: subw   %ax, %cx
            movw   %cx, %ax
            incw   %ax
  .LExit:   popl   %esi
end;
 
var
  T0,T1 : TDateTime;
 
begin
  randomize;
  Init(ShortStringArray);
  writeln(' Runden :',runden,' pos checked ',runden *(cMax*(cMyLen+cUnknown)));
  OrgPos;  
  t0:= time;
  OrgPos;
  t1:= time;
  dt := t1-t0;  
  IF dt = 0 then 
    dt := 0.00001;
  writeln('Original Pos ',FormatDateTime('NN:SS.ZZZ   ',dt),sumPos:10);
  Test(@MarcovPos);  
  Test(@CharPos_Pascal);
  Test(@CharPos_AsmX);
  Test(@CharPos_Asm3b_LoopStart_9);
  Test(@CharPos_Asm3c_InsideLoop_0);
end.
(*
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDE
rxvNz!jwIp>(nuhSRO|{g~Q"t@a9`d[LK }'0mf=&e;+<F.HAkl#siTq,c-2b?_BE$86/1yG%JZ PMoUDV7:^X\45YW]*3C)
 
 Runden :1397 pos checked 23067264 // 32 kByte Daten
Original Pos 00:00.759    132502656
 116.864%  116.996%  116.996%  116.601% 
  62.319%   62.451%   62.319%   62.451% 
  59.684%   59.552%   59.289%   59.157% 
  64.295%   64.163%   64.163%   64.032% 
  62.055%   62.451%   62.187%   61.924% 
 
real	0m12.617s
 
  !"#$%&'()*+,-./0123456789:;<=>?@ABCDE
6|0%f(Iu3&HeB~L_kx5l*a]W}RsTq7=yJ).8"dwimbn9jZh1-#X/F`CcU;Y MP2EKo[{S:OVN4Q'+?t!,vr>^G\ <zDpg@A$
 
 Runden :43 pos checked 22720512
Original Pos 00:00.794    130510848 // 1 Mb Daten
 113.350%  113.980%  113.476%  113.224% 
  57.683%   57.305%   57.683%   57.431% 
  54.156%   54.156%   54.030%   53.904% 
  80.730%   80.227%   80.605%   80.856% 
  57.809%   57.431%   58.816%   58.186% 
 
real	0m13.162s
 
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDE
So=%&l/eWNa$!BcF4bYOUmQx9+Csjh3-n]LVD5J0\[^@P>X}A?pRf#8Z `{t2_<wd*;girq7~HM)|u6,GT'z.:EyKk vI"(1
 
 Runden :1 pos checked 16908288    // 32 Mb Daten
Original Pos 00:00.592     97124352
 113.345%  113.514%  112.500%  114.020% 
  57.432%   57.939%   57.432%   58.108% 
  54.392%   54.223%   53.885%   54.561% 
  80.912%   81.419%   81.419%   81.081% 
  56.757%   56.757%   56.588%   56.926% 
 
real	0m9.908s
 
*)

Gruß Horst

EDIT:
Die Zeichenkette aus dem die Zeichen gesucht werden auch durchmischt, sonst werden ja zum Ende immer nur Zeichen nicht gefunden, damit klappt die Sprungvorhersage unrealistisch gut,

[h-elsner]

1. Teil mit Win7 und Lazarus 1.3, SVN revision 44761.
2. Teil mit WinXP Notebook kommt bald. Der muss sich erstmal vom Schrecken des Einschaltens erholen. Windoofs-typisch ist der erstmal eine ganze Weile mit sich selber beschäftigt.

Gruß HE

[h-elsner]

Teil 2 des Testlaufs mit WinXP und Lazarus 1.1, SVN 37469.

Gruß HE

[ruewa]

Danke, HE!

@Horst_h: Ich kann Dein Ergebnisfile leider nicht verwenden! Um sicherzustellen, daß die Meßwerte den Original-Funktionen entsprechen, protokolliert AlignTest auch die MD5-Summen der relevanten Units zum Zeitpunkt der Kompilation. Aus Deinen Daten geht hervor, daß Du sowohl die Unit "TestFunctions.pas" als auch die "CharPosAsmFuncs_i386.inc" vor dem Testlauf verändert hast. Ich will weder darüber spekulieren, ob das relevante Änderungen waren oder triviale (ein zusätzliches Space genügt), noch will ich Dir Böswilligkeit unterstellen. Aber es ist nicht nachvollziehbar, was du da gemessen hast. Deshalb muß der Datensatz rausfliegen.

Selbstverständlich steht es Dir frei, an dem Programm nach Herzenslust rumzubasteln, und Du kannst gerne Dein eigenes Testprogramm schreiben. Aber dann würde ich Dich dringend darum bitten, dies in einem getrennten Thread zu kommunizieren: Hier geht es um das Projekt AlignTest. Ich werde mich in dieser Phase nicht an der Diskussion um alternative Funktionsvarianten beteiligen - und vor allem werde ich auf keinen Fall all den anderen, die hier dankenswerterweise ihre (validen) Ergebnisse beigesteuert haben, den Vogel zeigen und sagen "Ach, ich hab's mir anders überlegt, ich trete Eure Mitarbeit in die Tonne und messe doch lieber was anderes..."

Wie gesagt: Ich habe nichts dagegen, was Du da machst, aber bitte sorge für eine saubere Trennung der Thematiken!

Gruß Rüdiger

[Horst_h]

Hallo,

Nochmals meine Bitte: Könnte einer der Windows-Nutzer mir bitte einen Vorschlag machen, welches Unterverzeichnis als Default eingestellt werden müßte, um nur die Bibliotheksdateien von Lazarus zu erfassen (so daß man auf etwa 4.000 Dateien kommt)? Ich würde das Programm wirklich gerne dahingehend ändern, daß es auch unter Windows tatsächlich die versprochenen 12 Minuten plusminus läuft, anstatt wohlmeinende Nutzer mit Laufzeiten von einer Dreiviertelstunde zu verärgern.

Das war es doch hauptsächlich, worum es in dem Schnipsel ein paar Zeilen hier drüber ging,Selbst die Strings erzeugen, in denen, wie beim Original nur 29,5 % Treffer sind und die mittlere Länge 38 Zeichen ist. ( Lazarus 1.2.6 unter Windows), denn jede Version von Unterverzeichnis wird etwas anderes enthalten.
Man kann ja seinen Zufallsgenerator einbauen, und randseed setzen, damit sogar die Startbedingungen für alle gleich sind.
Was der Schnipsel auch zeigen sollte, welche Anzahl günstig ist.
Wenn alle Daten im Level II Cache sind, ist bei mir die Laufzeit am gleichmäßigsten.

Gruß Horst

[mschnell]

Rüdiger,

Falls es Dir um eine Wissenschaftliche Gegenüberstellung der verschiedenen Prozessor-Chips geht, ignoriere das Folgende bitte.

Falls es Dir um die Optimierung z.B. der Funktion "Suche Character in String" geht, noch ein Vorschlag.

Es könnte sein, dass alle oder auch nur manche Chips bei langen Strings schneller arbeiten, wenn nicht jedes Byte einzeln aus dem Speicher geholt wird, sonder die Wortbreite beim Speicherzugriff explizit durch den Assembler-Code ausgenutzt wird.

Es könnte also z.B. bei 32 Bit die Schleife über 4-Byte-Gruppen laufen und dann die 4 Bytes in einem 32 Bit Register gecheckt werden.

(Bei 64 Bit Mode entsprechend.)

-Michael

[mschnell]

Man kann ja seinen Zufallsgenerator einbauen, und randseed setzen, damit sogar die Startbedingungen für alle gleich sind.

Das halte ich für sehr sinnvoll !

Danke,
-Michael

[ruewa]

@Horst_h: Nein, ich werde die Testbedingungen jetzt NICHT ändern, während täglich neue Ergebnisse hereinkommen! Punkt!

Falls es Dir um die Optimierung z.B. der Funktion "Suche Character in String" geht, noch ein Vorschlag.

Es könnte sein, dass alle oder auch nur manche Chips bei langen Strings schneller arbeiten, wenn nicht jedes Byte einzeln aus dem Speicher geholt wird, sonder die Wortbreite beim Speicherzugriff explizit durch den Assembler-Code ausgenutzt wird.

Es könnte also z.B. bei 32 Bit die Schleife über 4-Byte-Gruppen laufen und dann die 4 Bytes in einem 32 Bit Register gecheckt werden.

(Bei 64 Bit Mode entsprechend.)

Michael, Du hast recht! Aber das ist keineswegs trivial.

Schau Dir doch bitte mal die Unit SortableHashList.pas genauer an (die ist in den Sourcen von AlignTest). Dort gibt es zwei Funktionen "ShortCompareSensitive" und "ShortCompareInsensitive" jeweils in Assembler-Fassungen für x86_64 und i386 sowie als Pascal-Variante für nicht-x86er-Prozessoren (übrigens handelt es sich um zwei unterschiedliche Algorithmen, die x86_64-Funktionen sind eine Entwicklungsgeneration weiter und nochmal ein paar Prozent schneller - ich hatte einfach noch nicht die Zeit gefunden, die 32-Bit-Versionen entsprechend anzupassen und zu testen). Dort geschieht genau das, was Du vorschlägst: Einlesen in Long- bzw. Quadbreite in die Register. Es ist nicht ganz trivial, denn man muß ja auch kontrollieren, wie oft man entsprechende Register-Shifts und Vergleiche unternimmt. Also wird der Quelltext entweder quälend lang (Abfolge mit vielen Wiederholungen statt Schleife pro Registerblock) oder man codiert entsprechende Schleifen, die schnell mehr Zeit verbrauchen, als das Ganze einbringt. Da das richtige Maß zu finden ist nicht ganz leicht.

Damit bei einer CharPos-Funktion noch etwas zu gewinnen, wird allerdings sehr schwer werden. Denn die ist schon von sich aus so eng, daß das gesamte Einsparpotential pro Char (bei 32-Bit) gerade mal (3 * mov(mem,reg) - 1 * shr($16,reg)) / 4 beträgt. Das ist schnell wieder verbraten, wenn es den Algorithmus verkompliziert! Ich bin in diesem Zusammenhang übrigens noch auf ein anderes Problem gestoßen, bei dem ich nicht weitergekommen bin: Gerade hier wäre es nämlich sehr viel einfacher, immer blockweise einzulesen, ohne zu kontrollieren, ob man damit schon über das Ende des Strings hinausliest. Ich habe mir das nicht getraut, weil ich mir nicht sicher bin, ob man damit nicht (in sehr seltenen Fällen) eine Memory-Zugriffsverletzung riskiert. Vielleicht weiß jemand darauf eine Antwort?

Hier bei AlignTest ging es mir gerade nicht darum, ein allgemeinverbindliches Optimum zu finden. Das hatte ich mit den Pos(String, String)-Funktionen monatelang versucht und es ist mir immer mehr entglitten, was überhaupt allgemeingültig sein könnte. An der Stelle habe ich dann einen Schnitt gemacht, bewußt die denkbar minimalistischste Funktion genommen und diese variiert. Und jetzt ist die spannende Frage: Kann man auf niedrigster (Assembler-) Ebene überhaupt Codefolgen finden, die auf (nahezu) allen Rechnern gut bis perfekt laufen, oder sieht man da kein Land und muß sich damit abfinden, daß alles, was auch immer man macht, auf dem einen Rechner eben super läuft und auf dem nächsten ggfls. quälend langsam (ich rede von der Micro-Code-Ebene, nicht von Algorithmen-Optimierung). Mit welcher Unschärfe müssen wir leben? Auf diese Frage versuche ich, eine Antwort zu finden. Nein, besser gesagt: Einer Antwort näherzukommen.

Die CharPos-Funktionen, die im Test verwendet werden, sind mit einiger Wahrscheinlichkeit noch nicht das Ende der Fahnenstange. Aber diese Frage habe ich im Moment zurückgestellt. Stattdessen möchte ich derzeit erstmal wissen: Gibt es denn soetwas wie ein verbindliches "Ende der Fahnenstange" überhaupt? Oder rennt man da einer Fata Morgana hinterher?

Gruß Rüdiger

[mschnell]

Also wird der Quelltext entweder quälend lang (Abfolge mit vielen Wiederholungen statt Schleife pro Registerblock) oder man codiert entsprechende Schleifen, die schnell mehr Zeit verbrauchen, als das Ganze einbringt. Da das richtige Maß zu finden ist nicht ganz leicht.

Kann auch sehr Chip-abhängig sein. Idealer Weise hat der Chip einen "Micro-Cash" für ein Datenwort, das über den Bus eingelesen wird, dann kann so eine Maßnahme nichts bringen. Umgekehrt kann ein Daten-Zugriff nach außerhalb des Cores auch wesentlich länger als die Ausführung eines Befehls dauern. Ob mehr Loop-Sprünge oder ein größerer Code besser ist, ist ebenfalls Chip-abhängig.

Gibt es denn soetwas wie ein verbindliches "Ende der Fahnenstange" überhaupt?

Wohl kaum. Dafür sind die in Frage kommenden Chips zu unterschiedlich.

Hast Du übrigens mal einen von den damals viel diskutierten Chips getestet, die (um möglichst wenig Energie zu brauchen), den Intel-Code in RISC übersetzen und von einer ganz anderen CPU ausführen lassen, und das BIOS vor dem Start den Übersetzer in die der CPU laden musste? Ich habe den Namen vergessen. (Intel-Chips machen so etwas teilweise auch, aber anscheinend noch verdeckter und sie müssen nicht geladen werden.)

-Michael

[Horst_h]

Hallo,

bei x64 kann man doch XMM Befehle nutzen, dort kann man zwei Werte direkt byte-weise vergleichen und eine Bitmaske mit der Position wird erstellt.
Das ist dann erheblich schneller.

Gruß Horst
P.S: @ruewa
Noch eine kleine Bemerkung zu

Nein, ich werde die Testbedingungen jetzt NICHT ändern,

soll ich NICHT als genervt auffassen?
Eigentlich zeigt doch die Vorgehensweise der Teststrings Generierung, dass Du Dich nicht damit auseinandergesetzt hast.Ich habe was Tolles, das nehme ich mal.
Aber es funktioniert ja.