Problem mit Geschwindigkeit

[himitsu]

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.

[TomyN]

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.

[freimatz]

Wie ist der Vergleich 32-Bit mit 64-Bit?

[TomyN]

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.

[Uwe Raabe]

Zitat von himitsu:

Tja, und wie schon erwähnt, gibt es den in Win64 garnicht mehr.

Zumindest git es noch den TExtended80Rec, mit dem man solche Zahlen auch aus einem Stream lesen kann. Der hat auch ein automatisches Fallback auf Extended unter Win32.

Um die Größe eines Extended festzustellen gibt es auch die Compilerdirektive $EXTENDEDIS10BYTES.

Zitat von TomyN:

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.

Dazu gibt es hier noch ein paar Informationen: Steuerung der Gleitkommagenauigkeit (Delphi für x64)

[TomyN]

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.

[himitsu]

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:

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;

Win64:

Code:

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

gegenüber Win32:

Code:

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;

Noch schlimmer wird es beim Dividieren
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}

[TurboMagic]

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...

[Uwe Raabe]

Zitat von TurboMagic:

Mir ist nochwas eingefallen zu x64 und Gleitkomma:
http://docwiki.embarcadero.com/RADSt..._f%C3%BCr_x64)

Ähemm - siehe #15...

Zitat von Uwe Raabe:

Dazu gibt es hier noch ein paar Informationen: Steuerung der Gleitkommagenauigkeit (Delphi für x64)

[jfheins]

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:

i1:= i+j-1;
i2:= i1+n4;
i3:= i2+n4;
i4:= i3+n4;

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.

Delphi-Quellcode:

                  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;

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.

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.