|
Problem mit Geschwindigkeit
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:
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?
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; |
AW: Problem mit Geschwindigkeit
Vielleicht übersteigen die Instruktionen innerhalb der Schleife die Größe des Befehlscache der CPU?
|
AW: Problem mit Geschwindigkeit
Guter Gedanke. Gibt es eine Möglichkeit das irgendwie zu überprüfen ('COMMAND_QEUE_OVERFLOW_CALLBACK' oder so?)
|
AW: Problem mit Geschwindigkeit
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.
|
AW: Problem mit Geschwindigkeit
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 |
AW: Problem mit Geschwindigkeit
Wie sind datenA und datenB denn definiert?
|
AW: Problem mit Geschwindigkeit - Erledigt
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. :thumb: Zur meiner Verwirrung hat der Start mit $10 00 00 beigetragen, da der Effekt auch bei $08 00 00 da war. |
AW: Problem mit Geschwindigkeit
Zitat:
Code:
Anzahl siehe den Post darüber.
TAE = Array of Extended
|
AW: Problem mit Geschwindigkeit
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.
|
AW: Problem mit Geschwindigkeit
Intel VTune oder AMD μProf (je nach CPU) zur Hand nehmen und schauen, wo der Flaschenhals liegt.
|
AW: Problem mit Geschwindigkeit
Extended war "eigentlich" nie zur Speicherung gedacht, sondern nur kurz während der Berechnung (drum kennen/kannten viele Programmiersprachen diesen Typ garnicht erst)
Tja, und wie schon erwähnt, gibt es den in Win64 garnicht mehr. Extended außerhalb von Win32 ist im Delphi daher ein Alias für Double (Abwärtskompatibilität, damit Programme/Komponenten/Quellcodes von Programmierern, die es nicht besser wussten, dennoch kompilierbar bleiben) Und dieses 10 Byte-Align vom Extended ist für das Caching auch nicht grade optimal. |
AW: Problem mit Geschwindigkeit
Hi,
Erstmal Danke für Euere Antworten. Zuerst wollte ich nur verstehen, warum die Doppel-FFT teilweise langsamer ist als zwei einzelne FFTs, obwohl dabei deutlich weniger Berechnungen nötig sind. Da war die erste Antwort 'CPU-Cache' eigentlich schon die 'Lösung'. Durch die weiteren Antworten bin ich aber etwas neugierig geworden und habe noch ein wenig rumgespielt. Ich habe jeweils 100 Durchläufe berechnen lassen (jeweils mit den gleichen Startdaten). Wenn ich nach Windows 64 kompiliere, wird Extended wohl einfach in Double umgewandelt. Daher meine irrige Meinung, dass Extended mehr Präzision 'ohne Aufpreis' bringt (und daher die Umstellung von double auf Extended). Bei den Tests war jedenfalls kein Unterschied bei der Geschwindigkeit feststellbar. Bei Win32 als Target ist ein Unterschied zwischen Extended und Double feststellbar, dieser ist in den meisten Fällen aber relativ gering, nur bei einer FFT-Größe fällt auf, dass der CPU Cache mit double noch zurecht kommt, mit Extended aber nicht mehr so gut (oder der Compiler deutlich unterschiedlich kompiliert). Da beträgt die Verbesserung fast 50%. Single als Datentyp bringt bei Win64 keinerlei Vorteile sondern ist sogar etwas langsamer, speziell bei kleineren FFT Größen. Vermutlich wird da erstmal alles 'verdoubled' und zurück 'gesinglet', was auch etwas Zeit kostet. Bei Win32 bringt single eine deutliche Verbesserung. Bei single ist Win64 als Target deutlich langsamer als die Win32, ansonsten ca. 1/3 schneller. Für mich habe ich aktuell entschieden auf double zu gehen und das Thema 'Abwärtskompatibilität zu 32Bit Windows' nochmals zu überdenken. |
AW: Problem mit Geschwindigkeit
Wie ist der Vergleich 32-Bit mit 64-Bit?
|
AW: Problem mit Geschwindigkeit
Hier mal ein paar Zahlen
(A): Berechnung zweier FFTs hintereinander. (B): Berechnung einer 'Dualen' FFT. Kompiliert für win64 (Daten: double) 1024k FFT -> A: 289ms, B: 331ms 512k FFT -> A: 88ms, B: 139ms (!!) 256k FFT -> A: 29ms, B: 40ms (!!) 128k FFT -> A: 13ms, B: 13ms 64k FFT -> A: 6ms, B: 6ms 32k FFT -> A: 2,5ms, B: 2,4ms Kompiliert für win32 (Daten: double) 1024k FFT -> A: 309ms, B: 350ms 512k FFT -> A: 96ms, B: 142ms (!!) 256k FFT -> A: 34ms, B: 38ms 128k FFT -> A: 16ms, B: 14ms 64k FFT -> A: 7ms, B: 6ms 32k FFT -> A: 3,0ms, B: 2,7ms Irgendwie hängt das anscheinend sehr von der Umgebung ab. Wenn ich das Programm im VTune ausführe, dann bekomme ich (win32 + win64) bessere Werte bei der größten FFT (1024k FFT -> A: 286ms, B: 332ms, win32 und A:269ms, B: 315ms in win64), ab 512k sind die Resultate bei 32bit gleich, bei win64 gibt's bei 512k / 'dual' ein besseres Resultat ( 126ms zu 139ms). Insgesamt sind die Unterschiede anscheinend sehr von der Umgebung abhängig, so dass ich das alles nur als große Richtung verstehe. Interessant war und ist es aber schon. |
AW: Problem mit Geschwindigkeit
Zitat:
Um die Größe eines Extended festzustellen gibt es auch die Compilerdirektive $EXTENDEDIS10BYTES. Zitat:
 Steuerung der Gleitkommagenauigkeit (Delphi für x64) |
AW: Problem mit Geschwindigkeit
Danke für die Infos.
Interessant finde ich auch, dass der Einsatz von Int64 für die Indizes die Performance sowohl für win32 (da hätte ich es erwartet) aber auch für win64 (was mich überrascht) deutlich verschlechtert. |
AW: Problem mit Geschwindigkeit
Bei Int64 kommt es drauf an.
Die Operationen werden unter Win32 "manuell" auf zwei Int32 aufgeteilt und per ProgrammCode berechnet, was im Win64 die CPU erledigen kann. Dieses ergab auch shcon nette Bugs, wo in älteren Delphis auch schonmal die Funktionen für Int64 und UInt64 durcheinandergekommen waren und dann das Ergebnis nicht stimmte.
Delphi-Quellcode:
Win64:
var
A, B, C: Int64; begin A := 3; B := 4; C := A * B; // hier wird im Win32 das System.__llmul ausgeführt if C <> 0 then Beep; end;
Code:
gegenüber Win32:
Unit7.pas.29: A := 3;
000000000070AD9C 48C7453803000000 mov qword ptr [rbp+$38],$0000000000000003 Unit7.pas.30: B := 4; 000000000070ADA4 48C7453004000000 mov qword ptr [rbp+$30],$0000000000000004 Unit7.pas.31: C := A * B; 000000000070ADAC 488B4538 mov rax,[rbp+$38] 000000000070ADB0 480FAF4530 imul rax,[rbp+$30] 000000000070ADB5 48894528 mov [rbp+$28],rax Unit7.pas.32: if C <> 0 then 000000000070ADB9 48837D2800 cmp qword ptr [rbp+$28],$00 000000000070ADBE 7407 jz TForm7.FormCreate + $37 Unit7.pas.33: Beep; 000000000070ADC0 33C9 xor ecx,ecx 000000000070ADC2 E8696DD1FF call MessageBeep
Code:
Noch schlimmer wird es beim Dividieren :stupid:
Unit7.pas.29: A := 3;
0060E39C C745F003000000 mov [ebp-$10],$00000003 0060E3A3 C745F400000000 mov [ebp-$0c],$00000000 Unit7.pas.30: B := 4; 0060E3AA C745E804000000 mov [ebp-$18],$00000004 0060E3B1 C745EC00000000 mov [ebp-$14],$00000000 Unit7.pas.31: C := A * B; // hier wird im Win32 das System.__llmul ausgeführt 0060E3B8 FF75EC push dword ptr [ebp-$14] 0060E3BB FF75E8 push dword ptr [ebp-$18] 0060E3BE 8B45F0 mov eax,[ebp-$10] 0060E3C1 8B55F4 mov edx,[ebp-$0c] 0060E3C4 E81BDEDFFF call @_llmul 0060E3C9 8945E0 mov [ebp-$20],eax 0060E3CC 8955E4 mov [ebp-$1c],edx Unit7.pas.32: if C <> 0 then 0060E3CF 837DE400 cmp dword ptr [ebp-$1c],$00 0060E3D3 7504 jnz $0060e3d9 0060E3D5 837DE000 cmp dword ptr [ebp-$20],$00 0060E3D9 7407 jz $0060e3e2 Unit7.pas.33: Beep; 0060E3DB 6A00 push $00 0060E3DD E8BA79E0FF call MessageBeep // ------------------------------------------------------------------------------ // 64-bit signed multiply // ------------------------------------------------------------------------------ // // Param 1(EDX:EAX), Param 2([ESP+8]:[ESP+4]) ; before reg pushing // procedure __llmul; asm //StackAlignSafe PUSH EDX PUSH EAX // Param2 : [ESP+16]:[ESP+12] (hi:lo) // Param1 : [ESP+4]:[ESP] (hi:lo) MOV EAX, [ESP+16] MUL DWORD PTR [ESP] MOV ECX, EAX MOV EAX, [ESP+4] MUL DWORD PTR [ESP+12] ADD ECX, EAX MOV EAX, [ESP] MUL DWORD PTR [ESP+12] ADD EDX, ECX POP ECX POP ECX RET 8 end; Und das ist schon die schnelle Version vom Fastcode (da hatte Delphi früher noch "schlimmeres" drin)
Code:
(* ***** BEGIN LICENSE BLOCK *****
* * The function __lldiv is licensed under the CodeGear license terms. * * The initial developer of the original code is Fastcode * * Portions created by the initial developer are Copyright (C) 2002-2004 * the initial developer. All Rights Reserved. * * Contributor(s): AMD, John O'Harrow and Dennis Christensen * * ***** END LICENSE BLOCK ***** *) // ------------------------------------------------------------------------------ // 64-bit signed division // ------------------------------------------------------------------------------ // // Dividend = Numerator, Divisor = Denominator // // Dividend(EDX:EAX), Divisor([ESP+8]:[ESP+4]) ; before reg pushing // // procedure __lldiv; //JOH Version asm //StackAlignSafe {$IFDEF PC_MAPPED_EXCEPTIONS} PUSH EBP MOV EBP, ESP {$ENDIF} PUSH EBX PUSH ESI PUSH EDI {$IFDEF PC_MAPPED_EXCEPTIONS} MOV EBX, [ESP+20] MOV ECX, [ESP+24] {$ELSE !PC_MAPPED_EXCEPTIONS} MOV EBX, [ESP+16] MOV ECX, [ESP+20] {$ENDIF !PC_MAPPED_EXCEPTIONS} MOV ESI, EDX MOV EDI, ECX SAR ESI, 31 XOR EAX, ESI XOR EDX, ESI SUB EAX, ESI SBB EDX, ESI // EDX:EAX := abs(Dividend) SAR EDI, 31 XOR ESI, EDI // 0 if X and Y have same sign XOR EBX, EDI XOR ECX, EDI SUB EBX, EDI SBB ECX, EDI // ECX:EBX := abs(Divisor) JNZ @@BigDivisor // divisor > 32^32-1 CMP EDX, EBX // only one division needed ? (ecx = 0) JB @@OneDiv // yes, one division sufficient MOV ECX, EAX // save dividend-lo in ecx MOV EAX, EDX // get dividend-hi XOR EDX, EDX // zero extend it into edx:eax DIV EBX // quotient-hi in eax XCHG EAX, ECX // ecx = quotient-hi, eax =dividend-lo @@OneDiv: DIV EBX // eax = quotient-lo MOV EDX, ECX // edx = quotient-hi(quotient in edx:eax) JMP @SetSign @@BigDivisor: SUB ESP, 12 // Create three local variables. MOV [ESP ], EAX // dividend_lo MOV [ESP+4], EBX // divisor_lo MOV [ESP+8], EDX // dividend_hi MOV EDI, ECX // edi:ebx and ecx:esi SHR EDX, 1 // shift both RCR EAX, 1 // divisor and ROR EDI, 1 // and dividend RCR EBX, 1 // right by 1 bit BSR ECX, ECX // ecx = number of remaining shifts SHRD EBX, EDI, CL // scale down divisor and SHRD EAX, EDX, CL // dividend such that divisor SHR EDX, CL // less than 2^32 (i.e. fits in ebx) ROL EDI, 1 // restore original divisor (edi:esi) DIV EBX // compute quotient MOV EBX, [ESP] // dividend_lo MOV ECX, EAX // save quotient IMUL EDI, EAX // quotient * divisor hi-word (low only) MUL DWORD PTR [ESP+4] // quotient * divisor low word ADD EDX, EDI // edx:eax = quotient * divisor SUB EBX, EAX // dividend-lo - (quot.*divisor)-lo MOV EAX, ECX // get quotient MOV ECX, [ESP+8] // dividend_hi SBB ECX, EDX // subtract divisor * quot. from dividend SBB EAX, 0 // Adjust quotient if remainder is negative. XOR EDX, EDX // clear hi-word of quot (eax<=FFFFFFFFh) ADD ESP, 12 // Remove local variables. @SetSign: XOR EAX, ESI // If (quotient < 0), XOR EDX, ESI // compute 1's complement of result. SUB EAX, ESI // If (quotient < 0), SBB EDX, ESI // compute 2's complement of result. @Done: POP EDI POP ESI POP EBX {$IFDEF PC_MAPPED_EXCEPTIONS} POP EBP {$ENDIF} RET 8 end; siehe System.pas
Delphi-Quellcode:
{ 64-bit Integer helper routines }
{$IF defined(CPU386) and defined(ASSEMBLER)} procedure __llmul; procedure __lldiv; procedure __lludiv; procedure __llmod; procedure __llmulo; procedure __llumulo; procedure __lldivo; procedure __llmodo; procedure __llumod; procedure __llshl; procedure __llushr; {$ENDIF} |
AW: Problem mit Geschwindigkeit
Mir ist nochwas eingefallen zu x64 und Gleitkomma:
http://docwiki.embarcadero.com/RADSt..._f%C3%BCr_x64)Mal testen ob damit Single Berechnungen nicht doch gehörig schneller werden... |
AW: Problem mit Geschwindigkeit
Zitat:
Zitat:
|
AW: Problem mit Geschwindigkeit
Also ich habe nochmal rein geschaut ... und mir sind da ein paar Sachen aufgefallen:
Zunächst das duale: Du greift abwechselnd auf das Array datenA und datenB zu - das ist sehr ungünstig! Weil die CPU ja annimmt, wenn du Daten liest, dass du vermutlich kurz darauf die Folgedaten auch brauchst, werden spekulativ weitere Daten geladen. Es kann auch gut sein, dass ein array in den Cache passen würde, aber 2 nicht. Dann sowas:
Delphi-Quellcode:
Auf unterster Ebene suboptimal. Die CPU könnte i1 und i2 parallel ausrechnen, wenn i2 nicht von i1 abhängen würde => Probiere mal, die Sachen mehrfach ausrechnen als die Berechnungen zu sequenzieren.
i1:= i+j-1;
i2:= i1+n4; i3:= i2+n4; i4:= i3+n4;
Delphi-Quellcode:
Sowas müsstest du versuchen, mit SIMD zu lösen. Also SSE2 oder AVX Anweisungen, um gleich alle 4 Werte in einem Schritt zu ermitteln.
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; Schlussendlich: Wenn du eh 2 Rechnungen machen möchtest, probiere auch mal 2 Threads zu nutzen. Bei 100ms wird es sich vermutlich nicht lohnen, extra einen Thread zu erzeugen, aber wenn es den Thread schon gibt, kannst du einfach parallel rechnen. |
AW: Problem mit Geschwindigkeit
Hi,
Danke für alle Tipps. Das ganze macht immer mehr Spaß, obwohl es eigentlich relativ irrelevant ist, da die FFT durchaus schnell genug ist (und eigentlich sollte ich schon seit zwei Tagen Doku machen :-) Eine Änderung im Bereich der Indices (danke für den Tipp) bringt bei großen FFTs eine signifikante Beschleunigung ( bis zu 10%), bei kleinen Größe eher eine Tendenz zu einer etwas geringeren Rechendauer denn eine messbare Beschleunigung (aber keinenfalls eine Verlangsamung). Es ist schon sehr interessant zu sehen, wie sich die Umgruppierung einer Inc Anweisung gleich mal deutliche Auswirkungen hat. Aktuell schauen die Indices so aus
Code:
Das Inc(i,id) an der aktuelle Stelle liefert für kurze FFTs eine etwas höhere Geschwindigkeit (1-2%), während bei langen FFTs eine Position direkt am Ende der Schleife einen bessere Performance liefert. Für spezielle Sachen (SSE oder Rechnen auf der Grafikkarte etc.. ) fehlt mir das Basiswissen. Dann würde ich auch eher auf fertig Lösungen (Intel, FFTm(?)) o.ä. gehen.//Schleife Anfang i5:= Succ(i + n4 -j); //+1; i1:= i + j - 1; Inc(i, id); //Hier gut für kurze FFT i2:= i1 + n4; i3:= i1 + n4 + n4; // i2 + n4; i4:= i1 + n4 + n4 + n4; // i3 + n4; i6:= i5 + n4; i7:= i5 + n4 + n4; // i6+n4; i8:= i5 + n4 + n4 + n4; // i7+n4; //Berechnung der Daten // Inc(i,id); Hier gut für lange FFT //Schleife Ende |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 01:35 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz