Performance Problem mit GNU MP

Swordfish

Könnt' mir mal jemand verraten, warum

unsigned long __stdcall draw_apfel( void *data )
{
    thread_data_t *d = reinterpret_cast< thread_data_t* >( data );

    mpf_t g;
    mpf_init2( g, PRECISION );

    mpf_t ix, iy;
    mpf_init2( ix, PRECISION );
    mpf_init2( iy, PRECISION );

    mpf_t nix, niy;
    mpf_init2( nix, PRECISION );
    mpf_init2( niy, PRECISION );

    mpf_t min_x, min_y;
    mpf_init2( min_x, PRECISION );
    mpf_init2( min_y, PRECISION );

    mpf_t tmp_1, tmp_2;
    mpf_init2( tmp_1, PRECISION );
    mpf_init2( tmp_2, PRECISION );

    mpf_set_d( tmp_1, double( DOCUMENT_X / 2 ) );
    mpf_mul( tmp_1, tmp_1, d->dx );
    mpf_sub( min_x, d->mid_x, tmp_1 );

    mpf_set_d( tmp_1, double( DOCUMENT_Y / 2 ) );
    mpf_mul( tmp_1, tmp_1, d->dy );
    mpf_sub( min_y, d->mid_y, tmp_1 );

    mpf_t x, y;
    mpf_init2( x, PRECISION );
    mpf_init2( y, PRECISION );
    mpf_set( y, min_y );

    unsigned long iter;
    unsigned long max_iter = 100;

    register int pix_x, pix_y;

    unsigned __int64 start = 0, end = 0;
    QueryPerformanceCounter( reinterpret_cast< LARGE_INTEGER* >( &start ) );

    for( pix_y = 0; pix_y < DOCUMENT_Y; mpf_add( y, y, d->dy ), ++pix_y ) {

        mpf_set( x, min_x );

        for( pix_x = 0; pix_x < DOCUMENT_X; mpf_add( x, x, d->dx), ++pix_x ) {

            mpf_set_ui( g, 0 );
            mpf_set_ui( ix, 0 );
            mpf_set_ui( iy, 0 );

            for( iter = 0; ( iter < max_iter ) && ( mpf_cmp_ui( g, 8 ) < 0 ); ++iter ) {

                mpf_mul( tmp_1, ix, ix );
                mpf_mul( tmp_2, iy, iy );
                mpf_sub( tmp_1, tmp_1, tmp_2 );
                mpf_add( nix, tmp_1, x );

                mpf_mul( tmp_1, ix, iy );
                mpf_mul_ui( tmp_1, tmp_1, 2 );
                mpf_add( niy, tmp_1, y );

                mpf_set( ix, nix );
                mpf_set( iy, niy );

                mpf_mul( tmp_1, ix, ix );
                mpf_mul( tmp_2, iy, iy );
                mpf_add( g, tmp_1, tmp_2 );
            }

            if( iter < max_iter )
                SetPixel( d->dc, pix_x, pix_y, iter * ( 0xffffff / max_iter ) );
            else
                SetPixel( d->dc, pix_x, pix_y, 0 );
        }
    }

    QueryPerformanceCounter( reinterpret_cast< LARGE_INTEGER* >( &end ) );

    InvalidateRect( d->window, &d->rect, false );

    mpf_clear( g );
    mpf_clear( ix );
    mpf_clear( iy );
    mpf_clear( nix );
    mpf_clear( niy );
    mpf_clear( min_x );
    mpf_clear( min_y );
    mpf_clear( tmp_1 );
    mpf_clear( tmp_2 );
    mpf_clear( x );
    mpf_clear( y );

    mpf_clear( d->dx );
    mpf_clear( d->dy );
    mpf_clear( d->mid_x );
    mpf_clear( d->mid_y );

    delete d;

    return 0;
}

bei mir ewig ( >> 30 Sekunden ) braucht um so ein dämliches Apfelmännchen zu berechnen? Wie ihr seht, benutze ich die GNU MP Library ( welche von sich selbst behauptet, die schnellste bignum-Library zu sein ). Mache ich das ganze mit doubles, ist's für meinen geschmack auch langsam aber erträglich. Nunja, leider tut die Präzision von doubles nicht zum zoomen.

Hat jemand einen Vorschlag?

BTW: hat jemand einen Link zum Download der Version 4.2 von GNU MP (Compiliert als .lib für MSVC 2003 .net)?

Greetz, Swordfish

CodeFinder

N' Abend,

hmm hab mit der Lib noch nie gearbeitet... hasse mal n Down.-Link ? (also nen älteren)...hört sich interessant an

PS: Hast du schon Code Optimierungen im Compiler aktiviert ?

Swordfish

Hab's weil du es bist hochgeladen:
gmp.zip

CodeFinder schrieb:

PS: Hast du schon Code Optimierungen im Compiler aktiviert ?

[Moment bitte, mein Wienerisch auspacken muss] Jo nooo naaaa... [Wienerisch wieder einpack]

Greetz, Swordfish

Swordfish

Mit ist grad'

LINK schrieb:

: warning LNK4098: Standardbibliothek 'LIBC' steht in Konflikt mit anderen Bibliotheken; /NODEFAULT:Bibliothek verwenden

aufgefallen. Könnt's sein, daß gmp.lib gegen eine andere Version der libc gelinkt ist? Würde mein Programm (falls libc in gmp.lib eine andere version ist) sich denn dann überhaupt compilieren lassen?

Greetz, Swordfish

Ja das ist in der Tat schon mal EIN Problem. Ich würde die Bibliothek einmal neu kompilieren gegen die runtime library die du nutzt.

Swordfish

ich würd es liebend gerne tun, bring es jedoch nicht auf die Reihe, da dieses ding leider voll auf den gcc abziehlt.

So, any ideas?

Greetz, Swordfish

CodeFinder

Swordfish schrieb:

Hab's weil du es bist hochgeladen:

Dickes ThX !! M8 !!

aufgefallen. Könnt's sein, daß gmp.lib gegen eine andere Version der libc gelinkt ist? Würde mein Programm (falls libc in gmp.lib eine andere version ist) sich denn dann überhaupt compilieren lassen?

Davon würde ich mal ausgehen...und ja glaub das ist dann kompilierbar...NUR glaub da wird dich schnell das altbekannte undefinierte (Fehl-)Verhalten einholen ...würd sie mal neu kompilieren....hassu die gesamte Src ?

CodeFinder

Swordfish schrieb:

ich würd es liebend gerne tun, bring es jedoch nicht auf die Reihe, da dieses ding leider voll auf den gcc abziehlt.

So, any ideas?

Greetz, Swordfish

Hmm dann ladt dir doch gcc ...halt zwar auch nix davon...aber was sein muss ne^^

Was hat das eigentlich mit WinAPI zu tun?

Swordfish

Rolf Z. schrieb:

Ja das ist in der Tat schon mal EIN Problem. [...]

Gibt es denn MEHRERE Probleme?

@CodeFinder: Ja, schon, nur würd doch der auch wieder gegen seine eigene version von libc linken. Und ich glaub nicht, daß ich mit ihm die libc version von MSVS 2003 .net verwenden kann.

Greetz, Swordfish

CodeFinder

@CodeFinder: Ja, schon, nur würd doch der auch wieder gegen seine eigene version von libc linken. Und ich glaub nicht, daß ich mit ihm die libc version von MSVS 2003 .net verwenden kann.

Könnte n problem werden...aber ich würds probieren...anders wird das sonst nix...tja so sind nun mal 3rd Party libs

Dir bleibt wohl nur TryToError übrig... ...sry

Swordfish

Ich bin so dämlich! Hab' grad nachgeguckt, wasses mit dem Linkererror auf sich hat... Nix falsche Version der libc, sondern die gmp.lib ist halt nunmal nich für debug compiliert. Achja, CodeFinder, in dem zip gibt's zwar eine gmpdebug.lib der jedoch die Symbole fehlen.

So, bless God - no, not TGGC nor Linus Torvalds but God!!!

Hab' ne neue, compilierte Version gefunden, aber Ar***langsam isses immer noch. Also musses am algo liegen...

And again: Any Ideas?

Greetz, Swordfish

TGGC

Swordfish schrieb:

So, bless God - no, not TGGC nor Linus Torvalds but God!!!

Quatsch. Meine erste Antwort (hättest du in Grafikprogrammierung gefragt), wäre gewesen, das diese Software Implementierung nicht schneller als die Hardware (FPU) sein kann. Ausser mir hätte das keinen Gott gebraucht.

Übrigens finde ich die Sache mit den double sehr komisch. Die sollten völlig für solche Berechnungen aussreichen. Du kannst sowieso nie genau eine solche Reihe mit chaotischem Verhalten berechnen. Der kleineste Fehler führt nach wenigen Iterationen zu einem großem Fehler. Aber es lässt sich zeigen, das es zu jeder durch die Rechenfehler verfälschten Reihen eine korrekte Reihe geben muss, die dieser ähnelt (also er Unterschied zwischen beiden unter einer gewissen Grenze bleibt) und die nahe dem Startpunkt der verfälschten Reihe beginnt. f'`8k

Bye, TGGC (\-/ returns)

Swordfish

TGGC schrieb:

[...]Meine erste Antwort (hättest du in Grafikprogrammierung gefragt), wäre gewesen, das diese Software Implementierung nicht schneller als die Hardware (FPU) sein kann.

Klugscheißer!

TGGC schrieb:

[...]Übrigens finde ich die Sache mit den double sehr komisch.[...]

Naja, irgendwann läuft sie über...

Aber falls du Angegungen zur Optimierung des Algos hast...
Mir ist inzwischen die Idee gekommen, beim Ersten Durchlauf nur

xxxxxxxxxxxxxxxxxxxxxxxx
x x x x x x x x x x x xx
xx x x x x x x x x x x x
x x x x x x x x x x x xx
xx x x x x x x x x x x x 
x x x x x x x x x x x xx
xx x x x x x x x x x x x 
x x x x x x x x x x x xx
xx x x x x x x x x x x x 
xxxxxxxxxxxxxxxxxxxxxxxx

Pixel zu berechnen und für jedes x zu speichern, ob es Konvergiert oder nicht. Dann kann ich mir beim zweiten Durchlauf

x x x x x x x x x x x  
  x x x x x x x x x x x
 x x x x x x x x x x x  
  x x x x x x x x x x x
 x x x x x x x x x x x  
  x x x x x x x x x x x
 x x x x x x x x x x x  
  x x x x x x x x x x x

für jedes Pixel das von Pixeln umringt ist, die nicht konvergieren die berechnung sparen.

Greetz, Swordfish

TGGC

Swordfish schrieb:

Naja, irgendwann läuft sie über...

Ja irgendwann. Aber vorher hat man schon lang abgebrochen. Sobald die Zahl einmal einen Betrag > 2 hat divergiert sie sowieso.

Deine "Optimierung" ist übrigens ziemlich beknackt, hast du noch nie vom Schmetterling gehört? Eine Eigenschaft von Fraktalen ist, das eine leichte Änderung der Startwerte große Änderungen haben kann, daher kannst du nicht auf Nachbarpixel schliessen. f'`8k

Bye, TGGC (\-/ returns)

Das SetPixel ist doch voll lahm. Warum machste das Bild nicht im Speicher erstmal fertig?

Swordfish

TGGC schrieb:

Swordfish schrieb:

Naja, irgendwann läuft sie über...

Ja irgendwann. Aber vorher hat man schon lang abgebrochen. Sobald die Zahl einmal einen Betrag > 2 hat divergiert sie sowieso.

Ich beschreib' dir mal meine Vorgehensweise:

mid_x realer,
mid_y imaginärer Wert des Mittleren pixels meiner Bitmap

dx, dy offset / pixel

min_x berechnet aus mid_x, dx und SIZE_X
min_y analog ^

dann laufe ich durch die Bitmap:

double ix, iy = min_x;

for( int y = 0; y < SIZE_Y; ++y, iy += dy ) {

    iy = min_y;

    for( int x = 0; x < SIZE_X; ++x, ix += dx ) {

        ; // hier rechnen

    }    
}

Gut, klappt wuderbar, auch in erträglicher Geschwindigkeit. Nur wenn ich beginne zu zoomen ( dx /= 2; dy /=2 ) wird min_x bzw. min_y irgendwann so klein, daß es mit double nicht mehr darstellbar ist.

TGGC schrieb:

Deine "Optimierung" ist übrigens ziemlich beknackt, hast du noch nie vom Schmetterling gehört? Eine Eigenschaft von Fraktalen ist, das eine leichte Änderung der Startwerte große Änderungen haben kann, daher kannst du nicht auf Nachbarpixel schliessen. f'`8k

Schmetterling?

Greetz, Swordfish

TGGC

Swordfish schrieb:

Nur wenn ich beginne zu zoomen ( dx /= 2; dy /=2 ) wird min_x bzw. min_y irgendwann so klein

Sollte das beim reinzoomen nicht wachsen?

Bye, TGGC (\-/ returns)

Swordfish

@mods: Bitte schließt den Thread, ich muss mir über das Problem nochmal gründlicher den Kopf zerbrechen.