4. SOLVED - Arbeiten mit Sprungadressen

SOLVED - Arbeiten mit Sprungadressen

  • C

    Hallo.

    Mein Code läuft soweit, ist aber ziemlich langsam. Jetzt bin ich a.d. Optimierung. Sehr häufig habe ich Fälle wie diese:

    int Berechne(double* Stack, int nStack, int Type){
    int i=0;

    for(i=0;i<nStack;i++){
        switch(Type){
            case 0: /*Berechnungsmethode 0*/
                Function_0(&Stack[i]);
                break;
            case 1: /*Berechnungsmethode 1*/
                Function_1(&Stack[i]);
                break;
            default: /*Berechnungsmethode 2*/
                Function_2(&Stack[i]);
                break;
        }
    }
}

/*Die Argumente sind immer gleich*/
void Function_0(double* x){/*Code*/}
void Function_1(double* x){/*Code*/}
void Function_2(double* x){/*Code*/}

    Der Code ist natürlich viel komplizierter.

    nStack liegt typischerweise bei 100 000 000 oder größer und
    die Berechnung muss jede Iteration neu ausgeführt werden - also
    typischerweise 300 mal. Die Größe "Type" kann bei jedem Aufruf der
    Function "Berechne" anders sein, aber innerhalb dieser Function ändert er sich nicht. Das heißt, dass die switch-case Abfrage 100 000 000 mal durchgeführt wird. Natürlich kann ich die Schleife jetzt in die switch-case Klammer
    ziehen, aber dann habe ich jede Menge Code. Und solche Fälle habe ich leider sehr oft.

    Ist es möglich, dass ich die Sprungadresse der Funktionen Function_0, Function_1 und Function_2 abfrage, die switch-case Anweisung vor der Schleife ausführe und dann nurnoch zu der jeweiligen Funktion springe, ohne eine Abfrage zu stellen? Ich würde mir somit die switch-case Anweisung sparen.

    In Pseudocode meine ich in etwa so etwas:

    int Berechne(double* Stack, int nStack, int Type){
    int i=0;
    void* Function = NULL;

    switch(Type){
        case 0: /*Berechnungsmethode 0*/
            Function = &Function_0;
            break;
       case 1: /*Berechnungsmethode 1*/
           Function = &Function_1;
           break;
        default: /*Berechnungsmethode 2*/
            Function = &Function_2;
            break;
    }

    for(i=0;i<nStack;i++){
        Function(Stack[i]);
    }
}

void Function_0(double* x){/*Code*/}
void Function_1(double* x){/*Code*/}
void Function_2(double* x){/*Code*/}

    Bin für jeden Tipp dies bezüglich dankbar. Vllt. auch ein kleines Beispiel oder einfach ein paar Schlagworte, denn ich kann dazu mit "Sprungadresse C Function" nicht wirklich etwas brauchbares finden. Vielleicht gibt es für so etwas ja einen festen Begriff

    0
  • Mod

    Machste aus dem void* einen Funktionszeiger:

    void (*Function)(double);

    Fertig.

    Wobei ich mir nicht sicher bin, ob der Typ stimmt, weil der Typ der Funktion in deinem Code inkonsistent ist.

    Höchstwahrscheinlich noch viel besser wäre eine Überarbeitung der Funktionen selber, so dass man diese nicht 300x einzeln auf allen Elementes des Array aufrufen muss, sondern einmal auf dem ganzen Array.

    0

  • CJens schrieb:

    "Sprungadresse C Function" nicht wirklich etwas brauchbares finden.

    Das ist plausibel, da es diesen Begriff auch nicht gibt.
    Die Adresse einer definierten Funktion ist ebenso wie die einer Variablen immer fest, da gibt es nichts umzurechnen oder zu optimieren.
    Optimieren kannst du, indem du die Anzahl der Funktionsaufrufe reduzierst, indem du also wie SeppJ schon sagte, nicht immer nur ein Element zur Berechnung übergibst sondern einen Block von Elementen. Eine solche fachliche Optimierung schlägt immer eine technische.
    Das switch/case kannst du optimieren, es wird dir aber nichts nützen, da die Auflösung der konstanten "Sprungadresse" der Funktionen vom Compiler sowieso gemacht werden muss, ob nun mit oder ohne switch.

    Hier mal eine optisch optimierte Variante, obwohl ich nicht glaube, dass ein Compiler hier großartig anderen Code erzeugen würde:

    int Berechne(double* Stack, int nStack, int Type){
    int i=0;

    for(i=0;i<nStack;i++)
        (Type==0?Function_0:(Type==1?Function_1:Function_2))(Stack+i);
}
    0
  • C

    Also, ich sehe da kein Optimierungspotential, denn die Funktion wird in einer äußeren Iteration, die von 0 bis 300 zählt aufgerufen. Dabei müssen aber die Werte der vorherigen Iteration bekannt sein. Ich kann also schlecht einen ganzen Block übergeben. Es handelt sich um ein Zeitschrittverfahren und da muss ich den Zeitstrahl einhalten.

    Kann man denn dann mehrfach auf die Funktion springen? Denn ich möchte die Schleife dann irgendwann gerne noch mit OpenMP parallelisieren. Das heißt, wenn Type bei einem Aufruf konstant bleibt, werden alle Threads dann auf die Funktion springen.

    Ansonsten werde ich das mal versuchen und schauen, obs nen signifikanten Speedup gibt.

    0
  • Mod

    CJens schrieb:

    Also, ich sehe da kein Optimierungspotential, denn die Funktion wird in einer äußeren Iteration, die von 0 bis 300 zählt aufgerufen. Dabei müssen aber die Werte der vorherigen Iteration bekannt sein. Ich kann also schlecht einen ganzen Block übergeben.

    Diese Beschreibung passt nicht zu deiner vorherigen Beschreibung.

    Aus deiner vorherigen Beschreibung:

    for(i=0;i<nStack;i++){
        Function(Stack[i]);
    }

    Wenn dieses for in der Funktion selbst stecken würde, dann wären nStack-1 unnötige Funktionsaufrufe gespart.

    0
  • S

    Ich sehe auch kein richtiges Optimierungspotential in Berechne , ich denke nicht, dass die switch Anweisungen so viel kosten, dass die Vermeidung davon etwas bringen würde. Wenn du aber auf die switch Anweisungen verzichten willst, dann könntest du sowas machen

    int Berechne(double* Stack, int nStack, void (*func)(double*) ){
    int i=0;

    for(i=0;i<nStack;i++)
        func(Stack + i);
}

    Und die User von Berechne müssen dann anstatt Type zu übergeben, die Berechnungsfunktion übergeben

    void Function_0(double* x);
void Function_1(double* x);
void Function_2(double* x);

void foo()
{
  double *stack1, *stack2;
  size_t len1, len2;

  ....

  Berechne(stack1, len1, Function_2);
  Berechne(stack2, len2, Function_0);
}

    // edit:
    SeppJ's Kommentar macht Sinn, wieso ist die for-Schleife außerhalb von Function_* und nicht innerhalb der Funktionen selbst?

    0
  • ?

    Bei Performanceproblemen sollte man nicht denken, sondern messen, was genau am langsamsten ist.

    Na klar sollte man nicht unnötig Dinge ineffizient programmieren. Und: Schaffen Compiler es zum Beispiel, das switch automatisch aus der Schleife zu ziehen? Vermutlich nicht im allgemeinen Fall, aber vielleicht bei genügend einfachen Berechne-Funktionen? Naja, jedenfalls allgemein: immer messen!

    0
  • C

    Ich habe mal ein Beispiel vorbereitet und gemessen:

    #include <stdio.h>
#include <time.h>
//#define JUMP
//#define MEASURE

double Function_1(double x);
double Function_2(double x);
double Function_3(double x);

int main() {
	int Type = 0, i = 0, nStack = 100000000;
	void (*f)(double) = NULL;

#ifdef MEASURE
	clock_t prgstart, prgende; 
	prgstart = clock();
#endif

	do{
		printf("Please select function:");
		scanf("%i", &Type);
	}while (Type > 2 || Type < 0);

	switch (Type) {
		case 0:
			f = Function_1;
			break;
		case 1:
			f = Function_2;
			break;
		default:
			f = Function_3;
			break;
	}
#ifdef JUMP
	for (i = 0; i < nStack; i++) { f((double)i); }
#else
	for (i = 0; i < nStack; i++) {
		switch (Type) {
		case 0:
			Function_1((double)i);
			break;
		case 1:
			Function_2((double)i);
			break;
		default:
			Function_3((double)i);
			break;
		}
}
#endif

#ifdef MEASURE
	prgende = clock();
	printf("Laufzeit %.2f Sekunden\n", (float)(prgende - prgstart) / CLOCKS_PER_SEC);
#endif
	getchar();

	return 0;
}

double Function_1(double x) {return (x * x) / 1.0;}

double Function_2(double x) {return (x * x) / 2.0;}

double Function_3(double x) {return (x * x) / 3.0;}

    Und was soll ich sagen: Mit der switch-case-Anweisung in der Schleife ist der Code ungefähr um Faktor 5 schneller 😮 Verstehen kann ich das nicht, aber ist zumindest mal eine Erkenntnis und ich kann die Idee getrost ad acta legen. Wäre aber interessant, wenn jemand eine Idee hat, wie das sein kann.

    0
  • C

    Wenn man es wie folgt macht, ist der Unterschied nicht so groß:

    #include <stdio.h>
#include <time.h>
//#define JUMP
//#define MEASURE

void Function_1(double x);
void Function_2(double x);
void Function_3(double x);
static void(*f)(double) = NULL;

int main() {
	int Type = 0, i = 0, nStack = 100000000;

#ifdef MEASURE
	clock_t prgstart, prgende; 
	prgstart = clock();
#endif

	do{
		printf("Please select function:");
		scanf("%i", &Type);
	}while (Type > 2 || Type < 0);

	switch (Type) {
		case 0:
			f = Function_1;
			break;
		case 1:
			f = Function_2;
			break;
		default:
			f = Function_3;
			break;
	}
#ifdef JUMP
	for (i = 0; i < nStack; i++) { f((double)i); }
#else
	for (i = 0; i < nStack; i++) {
		switch (Type) {
		case 0:
			Function_1((double)i);
			break;
		case 1:
			Function_2((double)i);
			break;
		default:
			Function_3((double)i);
			break;
		}
}
#endif

#ifdef MEASURE
	prgende = clock();
	printf("Laufzeit %.2f Sekunden\n", (float)(prgende - prgstart) / CLOCKS_PER_SEC);
#endif
	getchar();

	return 0;
}

void Function_1(double x) {double fc = (x * x) / 1.0;}

void Function_2(double x) {double fc = (x * x) / 2.0;}

void Function_3(double x) {double fc = (x * x) / 3.0;}

    Also, void statt double für die Funktionen hat eine sehr große Auswirkung auf die Geschwindigkeit.

    0
  • Mod

    Hast du etwa unoptimierte Programme verglichen? Da dein Programm überhaupt nichts tut, sollte eigentlich so gut wie alles wegoptimiert werden. Das ist jedenfalls was bei mir passiert, nachdem ich die zahlreichen Warnungen entferne. Was passiert, wenn ich das undefinierte Verhalten im Programm belasse, habe ich nicht geprüft, da uninteressant.

    Übersetzte main (GCC 5.3.1, O3) mit JUMP eingeschaltet:

    main:
.LFB23:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movq    %fs:40, %rax
        movq    %rax, 8(%rsp)
        xorl    %eax, %eax
        movl    $0, 4(%rsp)
        .p2align 4,,10
        .p2align 3
.L2:
        movl    $.LC0, %esi
        movl    $1, %edi
        xorl    %eax, %eax
        call    __printf_chk
        leaq    4(%rsp), %rsi
        xorl    %eax, %eax
        movl    $.LC1, %edi
        call    __isoc99_scanf
        cmpl    $2, 4(%rsp)
        ja      .L2
        movq    stdin(%rip), %rdi
        call    _IO_getc
        xorl    %eax, %eax
        movq    8(%rsp), %rdx
        xorq    %fs:40, %rdx
        jne     .L7
        addq    $24, %rsp
        .cfi_remember_state
        .cfi_def_cfa_offset 8
        ret
.L7:
        .cfi_restore_state
        call    __stack_chk_fail
        .cfi_endproc

    Die andere Variante:

    main:
.LFB23:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movq    %fs:40, %rax
        movq    %rax, 8(%rsp)
        xorl    %eax, %eax
        movl    $0, 4(%rsp)
        .p2align 4,,10
        .p2align 3
.L2:
        movl    $.LC0, %esi
        movl    $1, %edi
        xorl    %eax, %eax
        call    __printf_chk
        leaq    4(%rsp), %rsi
        xorl    %eax, %eax
        movl    $.LC1, %edi
        call    __isoc99_scanf
        cmpl    $2, 4(%rsp)
        ja      .L2
        movq    stdin(%rip), %rdi
        call    _IO_getc
        xorl    %eax, %eax
        movq    8(%rsp), %rdx
        xorq    %fs:40, %rdx
        jne     .L7
        addq    $24, %rsp
        .cfi_remember_state
        .cfi_def_cfa_offset 8
        ret
.L7:
        .cfi_restore_state
        call    __stack_chk_fail
        .cfi_endproc

    Man sieht: Komplett identisch. Zudem wurde alles zwischen Zeile 23 und dem return (zurecht) wegoptimiert. Laufzeit des Programms ist entsprechend ca. 0.

    Wenn du also irgendwelche Geschwindigkeitsunterschiede gemessen haben möchtest, dann muss entweder deine Messmethode Schrott sein oder du hast keine aggressiven Optimierungen aktiviert. In beiden Fällen sind die Ergebnisse vollkommen wertlos. Wenn du beim echten Problem genauso nachlässig vorgegangen bist, kann man vergessen, dir hier sinnvoll helfen zu können.

    edit: Label L7 hinzu gefügt, damit man sieht, dass da auch nichts passiert. Wenn man den Stackprotector ganz abschaltet und das unsinnige getchar rauswirft, kommt man zu:

    main:
.LFB23:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movl    $0, 12(%rsp)
        .p2align 4,,10
        .p2align 3
.L2:
        movl    $.LC0, %esi
        movl    $1, %edi
        xorl    %eax, %eax
        call    __printf_chk
        leaq    12(%rsp), %rsi
        xorl    %eax, %eax
        movl    $.LC1, %edi
        call    __isoc99_scanf
        cmpl    $2, 12(%rsp)
        ja      .L2
        xorl    %eax, %eax
        addq    $24, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

    Also ein Programm, dass 100% äquivalent ist zu

    #include <stdio.h>

int main() {
  int i;

  do{
    printf("Please select function:");
    scanf("%i", &i);
  }while (i > 2 || i < 0);

  return 0;
}
    0
  • C

    Hallo.

    Nein, ich nutze od, also keine Optimierung. Habe den Code leicht abgeändert:

    #include <stdio.h>
#include <time.h>
//#define JUMP
//#define MEASURE

void Function_1(double x, double* y);
void Function_2(double x, double* y);
void Function_3(double x, double* y);
static void(*f)(double) = NULL;

int main() {
	int Type = 0, i = 0, nStack = 100000000;
	double Sum = .0;

#ifdef MEASURE
	clock_t prgstart, prgende; 
	prgstart = clock();
#endif

	do{
		printf("Please select function:");
		scanf("%i", &Type);
	}while (Type > 2 || Type < 0);

	switch (Type) {
		case 0:
			f = Function_1;
			break;
		case 1:
			f = Function_2;
			break;
		default:
			f = Function_3;
			break;
	}
#ifdef JUMP
	for (i = 0; i < nStack; i++) { f((double)i, &Sum); }
#else
	for (i = 0; i < nStack; i++) {
		switch (Type) {
		case 0:
			Function_1((double)i, &Sum);
			break;
		case 1:
			Function_2((double)i, &Sum);
			break;
		default:
			Function_3((double)i, &Sum);
			break;
		}
}
#endif

#ifdef MEASURE
	prgende = clock();
	printf("Laufzeit %.2f Sekunden\n", (float)(prgende - prgstart) / CLOCKS_PER_SEC);
#endif

	printf("Summe: %2.4e\n", Sum);

	getchar();

	return 0;
}

void Function_1(double x, double* y) { double fc = (x * x) / 1.0; *y += fc; }

void Function_2(double x, double* y) { double fc = (x * x) / 2.0; *y += fc; }

void Function_3(double x, double* y) { double fc = (x * x) / 3.0; *y += fc; }

    Jetzt tut das Programm auch etwas. Außerdem - wie kann er die switch-case Anweisung wegoptimieren, wenn der Wert von Type erst zur Laufzeit festgelegt wird? Das hatte ich ja extra deshalb so gemacht.

    0
  • Mod

    Niemanden interessiert, wie schnell unoptimierter Code läuft.

    0
Anmelden zum Antworten