Problem mit Geschwindigkeit

[TomyN]

Hallo,

Ich habe hier eine seltsames Phänomen, das ich nicht einsortieren kann.
Ich nutze Delphi 10.3
In meiner Software brauche ich oft eine FFT und da gerade etwas Zeit ist, habe ich mich seit Jahren wieder mal damit beschäftigt und ein kleines Testprogramm für die FFT Unit geschrieben. Das läuft soweit alles recht schön.
Aber: Da ich oft zwei FFTs mit der gleichen Auflösung gleichzeitig brauche, hab ich mir gedacht, ich erweitere die Procedure so, dass ich die Berechnung der Indexe sowie der Sin und Cos werter nur einmal mache und damit Zeit spare. Soweit so gut, nur dauert die neue Procedure deutlich länger als wenn ich zweimal die 'normale' FFT mache.

Ich habe nur den Code aus der 'Single FFT' kopiert und führe dann die Berechnungen anstelle mit einem Array mit zwei Arrays aus. Hier mal der Ausschnitt, auf den sich der 'Geschwindigkeitsverlust' reduzieren lässt.

Code:

a:= e;
       For j:=2 to n8 do begin
          Math.SinCos(a, ss1, cc1);
          Math.SinCos(3.0 * a, ss3, cc3);
           a:= j * e;
           i:= 0;
           id:= n2 shl 1;
           while i< Anzahl do begin
              While i < Anzahl do begin
                  i1:= i+j-1;
                  i2:= i1+n4;
                  i3:= i2+n4;
                  i4:= i3+n4;
                  i5:= i+n4-j+1;
                  i6:= i5+n4;
                  i7:= i6+n4;
                  i8:= i7+n4;
//Alter Teil
                  t1:= datenA[i3]*cc1+datenA[i7]*ss1;
                  t2:= datenA[i7]*cc1-datenA[i3]*ss1;
                  t3:= datenA[i4]*cc3+datenA[i8]*ss3;
                  t4:= datenA[i8]*cc3-datenA[i4]*ss3;
                  t5:= t1+t3;
                  t6:= t2+t4;
                  t3:= t1-t3;
                  t4:= t2-t4;
                  t2:= datenA[i6]+t6;
                  datenA[i3]:= t6-datenA[i6];
                  datenA[i8]:= t2;
                  t2:= datenA[i2]-t3;
                  datenA[i7]:= - datenA[i2]-T3;
                  datenA[i4]:= T2;
                  t1:= datenA[i1]+T5;
                  datenA[i6]:= datenA[i1]-t5;
                  datenA[i1]:= T1;
                  t1:= datenA[i5]+t4;
                  datenA[i5]:= datenA[i5]-t4;
                  datenA[i2]:= t1;
//Neuer Teil
                  t1:= datenB[i3] * cc1 + datenB[i7] * ss1;
                  t2:= datenB[i7] * cc1 - datenB[i3] * ss1;
                  t3:= datenB[i4] * cc3 + datenB[i8] * ss3;
                  t4:= datenB[i8] * cc3 - datenB[i4] * ss3;
                  t5:= t1+t3;
                  t6:= t2+t4;
                  t3:= t1-t3;
                  t4:= t2-t4;
                  t2:= datenB[i6]+t6;
                  datenB[i3]:= t6-datenB[i6];
                  datenB[i8]:= t2;
                  t2:= datenB[i2]-t3;
                  datenB[i7]:= - datenB[i2]-T3;
                  datenB[i4]:= T2;
                  t1:= datenB[i1]+T5;
                  datenB[i6]:= datenB[i1]-t5;
                  datenB[i1]:= T1;
                  t1:= datenB[i5]+t4;
                  datenB[i5]:= datenB[i5]-t4;
                  datenB[i2]:= t1;
//Ende Einschub
                  Inc(i, id);
              end;
              id:= id shl 1;
              i:= id-n2;
              id:= id shl 1;
           end;
       end;
       k:= k Shr 1;

Ich habe schon verschiedene FFT Größen und auch 32Bit oder 64Bit Kompilierung probiert, die 'Duale' Version ist immer um ca. 25% langsamer als zweimal die 'Single' Version. Und das kann ich mir einfach nicht erklären. Irgendwelche Ideen?

[Uwe Raabe]

Vielleicht übersteigen die Instruktionen innerhalb der Schleife die Größe des Befehlscache der CPU?

[TomyN]

Guter Gedanke. Gibt es eine Möglichkeit das irgendwie zu überprüfen ('COMMAND_QEUE_OVERFLOW_CALLBACK' oder so?)

[Sailor]

Wie groß sind denn die Felder? Kann es sein, daß da andauernd im SecondLevelCache nachgeladen werden muß? Ich hatte mal einen ähnlichen Fall, ein 2-dimensionales Feld mit random access versus eine verteilte Implementierung mit Indexfeldern. Erstaunlicherweise war die letztere, programmtechnisch aufwändigere Implementierung schneller als der simple Zugriff über x[i,j]. Die Empfehlung war, flache Datenstrukturen zu verwenden, von denen der Teil unter Zugriff länger im SLC verbleibt.

[TomyN]

Hi,

Den Gedanken hatte ich auch schon. Dann habe ich die Datensatzgröße halbiert, leider ohne Verbesserung, d.h. der Effekt bleibt genauso.
Leider hab ich bei dem Thema 'Caching' keine Ahnung, da ich Programmieren gelernt habe, als man noch strukturiert Programmiert hat ..

Tomy

[Uwe Raabe]

Wie sind datenA und datenB denn definiert?

[TomyN]

So, nun hab ich mich nochmal von 'unten' ran getestet.
Der 'Break' kommt, wenn ich die Arraygröße von $04 00 00 auf $08 00 00 erhöhe, bleibt interessanterweise bei $10 00 00 erhalten und verschwindet wieder bei $20 00 00.
Damit kann ich gut leben, da die zeitkritischen FFTs alle < $04 00 00 sind. Und Caching als Ursache erscheint mir plausibel.

Zur meiner Verwirrung hat der Start mit $10 00 00 beigetragen, da der Effekt auch bei $08 00 00 da war.

[TomyN]

Zitat von Uwe Raabe:

Wie sind datenA und datenB denn definiert?

Code:

TAE = Array of Extended

Anzahl siehe den Post darüber.

[TurboMagic]

Hinweis: Extended wird bei x64 auf Double gekappt da der 64 Bit Compiler nicht die FPU sondern SSE2 benutzt. Evtl. könnte ein Wechsel auf Single noch signifikant was bringen, falls das genau genug ist.

[Stevie]

Intel VTune oder AMD μProf (je nach CPU) zur Hand nehmen und schauen, wo der Flaschenhals liegt.