Zeigerarithmetikproblem



  • Hallo liebe Community,

    ich habe gerade ein kleines Problem mit Zeigern und Pre/Postfixoperatoren beim Optimieren einer Funktion.

    Das ganze habe ich fürs Forum auf folgendes Minimalbeispiel reduziert:

    #include <iostream>
    using namespace std;
    int main()
    {
    	unsigned char a[4];
    	a[0] = 2;
    	a[1] = 4;
    	a[2] = 8;
    	a[3] = 16;
    
    	// V1
    	unsigned char* zeiger1 = &a[1];
    	unsigned char b1 = *(zeiger1++);
    	unsigned char b2 = *(zeiger1++);
    	int summe1 = b1 + b2;
    	cout << "V1: " << summe1 << endl; // Ausgabe: V1: 12 (G++: 12)
    
    	// V2
    	unsigned char* zeiger2 = &a[1];
    	int summe2 = *(zeiger2++) + *(zeiger2++);
    	cout << "V2: " << summe2 << endl; // Ausgabe: V1: 8 (G++: 8)
    
    	// V3
    	unsigned char* zeiger3 = &a[0];
    	int summe3 = *(++zeiger3) + *(++zeiger3);
    	cout << "V3: " << summe3 << endl; // Ausgabe: V1: 16 (G++: 12)
    
    	return 0;
    }
    

    Ich möchte bei allen drei Versionen 4+8=12 erhalten;
    Was aber tatsächlich ausgegeben wird, steht in den Kommentaren.
    Mein Compiler ist MS VC 2005 Express und das ganze passiert im Debug- sowie im Releasemodus gleichermaßen.
    In Klammern dahinter steht, was der GNU-Compiler hier macht

    Seit wann darf ein C/C++-Compiler alle Prefixoperatoren in einem arithmetischen Ausdruck vorher durchführen bzw. alle Postfixoperatoren erst ganz am Ende?
    Müsste er das nicht eigentlich da machen, wo es angebracht ist, nämlich beim Auswerten des entsprechenden Ausdrucks?
    Und gibt es eine Möglichkeit, ihn mit geschicktem Klammersetzen dazu zu bringen?
    Version 1 mit dem Zwischenspeichern ist (in einer Schleife in meiner eigentlichen Funktion) etwas langsamer, deshalb würde ich es gerne ohne hinbekommen. Es wird also offensichtlich nicht komplett wegoptimiert.

    Vielen Dank im Voraus,
    Dobias



  • Ok, anscheinend darf man das gar nicht machen, was ich da tue.

    There is a caveat. For each distinct variable, you cannot use more than one increment or decrement operator in the same statement.

    http://www.daniweb.com/forums/thread106633.html

    Schade. 😞



  • Dobias schrieb:

    int summe2 = *(zeiger2++) + *(zeiger2++);

    am besten den zeiger garnicht hochzählen, wenn du nicht musst. und wenn, dann hinterher:

    int summe2 = *zeiger2 + *(zeiger2+1);  // 
    zeiger += 2;  // <-- hier kannste gefahrlos weiterzählen
    

    🙂



  • Danke, aber dass es so geht, ist ja klar.
    Mir gehts hier jedoch darum, das letzte Stückchen Geschwindigkeit rauszupressen. 😉



  • Dobias schrieb:

    Mir gehts hier jedoch darum, das letzte Stückchen Geschwindigkeit rauszupressen.

    das geht mit umstellen irgendwelcher C-konstrukte 'auf verdacht' und kompakter schreibweise sowieso nicht. im gegenteil, je simpler der code ist, desto mehr hilfst du dem compiler, das beste daraus zu machen.
    🙂



  • Die gcc-Option -O3 hast du schon gefunden, oder?



  • @fricky: Mit Verdacht hatte das weniger zu tun, es ging mir einfach darum, die Zugriffe auf den Speicher (bzw. den CPU-Cache) zu reduzieren, indem ich den Kram nicht in Variablen zwischenspeicher, sondern das ganze direkt in den Registern bleiben kann.
    Variante 2 und 3 waren im Test auf meinem Rechner auch ca 20% schneller als Variante 1, was mir ja aber nix bringt, weil beide Fehlerhaft sind. 😉

    Hab jetzt was in der Art genommen:

    unsigned char* zeiger = &a[0];
    summe = *(++zeiger);
    summe += *(++zeiger);
    

    Durch setzen des Zeigers auf das Element vor dem jenigen, mit dem ich anfangen möchte, kann ich unten Prefixincrementoren (anstelle der postfixigen) benutzen, was auch wieder mindestens einen Takt sparen sollte, da das Ergebnis nicht zwichengespeichert werden muss.
    Klar optimiert ein guter Compiler (vorallem mit den richtigen Einstellungen) einiges weg, aber bei sowas kann man selbst meißtens noch was mehr rausholen, was hier ja auch geklappt hat. 🙂

    @nwp2: Ja. 😉



  • Mit Verdacht hatte das weniger zu tun, es ging mir einfach darum, die Zugriffe auf den Speicher (bzw. den CPU-Cache) zu reduzieren, indem ich den Kram nicht in Variablen zwischenspeicher, sondern das ganze direkt in den Registern bleiben kann.

    Nur ist eine Variable weder ein Register, noch ein Speicherbereich. 🙂

    Variante 2 und 3 waren im Test auf meinem Rechner auch ca 20% schneller als Variante 1, was mir ja aber nix bringt, weil beide Fehlerhaft sind.

    Wie hast du das gemessen?



  • Dobias schrieb:

    Durch setzen des Zeigers auf das Element vor dem jenigen, mit dem ich anfangen möchte, kann ich unten Prefixincrementoren (anstelle der postfixigen) benutzen, was auch wieder mindestens einen Takt sparen sollte, da das Ergebnis nicht zwichengespeichert werden muss.

    das wird zwar oft erzählt, aber ich hab's nie verstanden.

    // postinkrement:
    x = *p++;  // dereferenzieren, zuweisen, pointer hochzählen
    // entspricht:
    x = *p;
    p++;
    
    // preinkrement:
    x = *++p;  // pointer hochzählen, dereferenzieren, zuweisen
    // entspricht:
    p++;
    x = *p;
    

    ^^jeweils 3 operationen bzw. 6, wenn man das pointer hochzählen in read/+1/write aufdröselt. wieso sollte das eine oder andere schneller sein?
    🙂



  • µngbd schrieb:

    Nur ist eine Variable weder ein Register, noch ein Speicherbereich. 🙂

    Sondern?
    Klar, je nach Compileroptimierung befindet sie sich entweder im einen oder im anderen, aber ich glaub nicht, dass du das meintest, oder?

    µngbd schrieb:

    Nur ist eine Variable weder ein Register, noch ein Speicherbereich. 🙂

    Variante 2 und 3 waren im Test auf meinem Rechner auch ca 20% schneller als Variante 1, was mir ja aber nix bringt, weil beide Fehlerhaft sind.

    Wie hast du das gemessen?

    Riesenwhileschleife drumherum (so siehts im Endeffekt in meiner Anwendung auch aus) und dann vorher und nachher Zeiten ausgeben lassen.

    ;fricky schrieb:

    Dobias schrieb:

    Durch setzen des Zeigers auf das Element vor dem jenigen, mit dem ich anfangen möchte, kann ich unten Prefixincrementoren (anstelle der postfixigen) benutzen, was auch wieder mindestens einen Takt sparen sollte, da das Ergebnis nicht zwichengespeichert werden muss.

    das wird zwar oft erzählt, aber ich hab's nie verstanden.

    // postinkrement:
    x = *p++;  // dereferenzieren, zuweisen, pointer hochzählen
    // entspricht:
    x = *p;
    p++;
    
    // preinkrement:
    x = *++p;  // pointer hochzählen, dereferenzieren, zuweisen
    // entspricht:
    p++;
    x = *p;
    

    ^^jeweils 3 operationen bzw. 6, wenn man das pointer hochzählen in read/+1/write aufdröselt. wieso sollte das eine oder andere schneller sein?
    🙂

    Die Operatoren geben ja eine Referenz auf den Operanden zurück. Ich hatte es mal so gelernt, dass er beim Postfix eine Ladeoeratoin (schmeisse etwas in ein Register) mehr machen muss, weil er ja erst nach dem Dereferenzieren incrementiert. Hab mir aber nie die ASM-Ausgabe angeguckt, oder es getestet.
    Jetzt hab ichs aber grad mal mit g++ (mit und ohne O3) getestet und beide Varianten waren gleich schnell. Selbst bei sowas sollte man also nicht einfach religös "tugendhaft" Glauben ohne zu Hinterfragen. Wieder was gelernt. 👍 😉

    Edit: OK, jetzt wollt ichs dann doch genau wissen. 😉
    Hier meine beiden Testprogramme mit dazugehörigen ASM-Ausgaben von g++ mit "-S".

    // incrementASMtestPRE.cpp
    int main()
    {
    	unsigned char* zeiger1 = 0;
    	int summe1;
    
    	summe1 += *(++zeiger1);
    	return 0;
    }
    
    // incrementASMtestPOST.cpp
    int main()
    {
    	unsigned char* zeiger1 = 0;
    	int summe1;
    
    	summe1 += *(zeiger1++);
    	return 0;
    }
    

    Einmal ohne O3:

    .file	"incrementASMtestPOST.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	%esp, %ebp
    	subl	$24, %esp
    	andl	$-16, %esp
    	movl	$0, %eax
    	addl	$15, %eax
    	addl	$15, %eax
    	shrl	$4, %eax
    	sall	$4, %eax
    	movl	%eax, -12(%ebp)
    	movl	-12(%ebp), %eax
    	call	__alloca
    	call	___main
    	movl	$0, -4(%ebp)
    	movl	-4(%ebp), %eax
    	movzbl	(%eax), %edx
    	leal	-8(%ebp), %eax
    	addl	%edx, (%eax)
    	leal	-4(%ebp), %eax
    	incl	(%eax)
    	movl	$0, %eax
    	leave
    	ret
    
    .file	"incrementASMtestPRE.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	%esp, %ebp
    	subl	$24, %esp
    	andl	$-16, %esp
    	movl	$0, %eax
    	addl	$15, %eax
    	addl	$15, %eax
    	shrl	$4, %eax
    	sall	$4, %eax
    	movl	%eax, -12(%ebp)
    	movl	-12(%ebp), %eax
    	call	__alloca
    	call	___main
    	movl	$0, -4(%ebp)
    	leal	-4(%ebp), %eax
    	incl	(%eax)
    	movl	-4(%ebp), %eax
    	movzbl	(%eax), %edx
    	leal	-8(%ebp), %eax
    	addl	%edx, (%eax)
    	movl	$0, %eax
    	leave
    	ret
    

    Und hier mit O3:

    .file	"incrementASMtestPOST.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    	.p2align 4,,15
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	$16, %eax
    	movl	%esp, %ebp
    	subl	$8, %esp
    	andl	$-16, %esp
    	call	__alloca
    	call	___main
    	leave
    	xorl	%eax, %eax
    	ret
    
    .file	"incrementASMtestPRE.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    	.p2align 4,,15
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	$16, %eax
    	movl	%esp, %ebp
    	subl	$8, %esp
    	andl	$-16, %esp
    	call	__alloca
    	call	___main
    	leave
    	xorl	%eax, %eax
    	ret
    

    Mit 03 kommt haargenau das gleiche bei raus und ohne sieht es zwar etwas anders aus, aber die Gesamtbefehlszahl ist trotzdem gleich. 🙂



  • ^^hihi, beim 'O3' erkennt der compiler, dass das ergebnis garnicht benutzt wird und erzeugt deshalb auch keinen maschinencode dafür. mach doch mal aus dem 'return 0;' ein 'return summe1;' und compile es nochmal.
    🙂



  • Oh, da hast du natürlich recht. 😉

    So, habs mal mit

    return summe1;
    

    gemacht, und jetzt siehts mit O3 so aus

    .file	"incrementASMtestPOST.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    	.p2align 4,,15
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	$16, %eax
    	movl	%esp, %ebp
    	pushl	%ebx
    	subl	$4, %esp
    	andl	$-16, %esp
    	call	__alloca
    	call	___main
    	movzbl	0, %eax
    	leal	(%ebx,%eax), %eax
    	movl	-4(%ebp), %ebx
    	leave
    	ret
    
    .file	"incrementASMtestPRE.cpp"
    	.def	___main;	.scl	2;	.type	32;	.endef
    	.text
    	.align 2
    	.p2align 4,,15
    .globl _main
    	.def	_main;	.scl	2;	.type	32;	.endef
    _main:
    	pushl	%ebp
    	movl	$16, %eax
    	movl	%esp, %ebp
    	pushl	%ebx
    	subl	$4, %esp
    	andl	$-16, %esp
    	call	__alloca
    	call	___main
    	movzbl	1, %eax
    	leal	(%ebx,%eax), %eax
    	movl	-4(%ebp), %ebx
    	leave
    	ret
    

    Also auch kein Geschwindigkeitsunterschied.
    Im Netz findet man noch oft solche Hinweise:

    No they do not have the same performance:

    * Postincrement will create a copy then increment, then return the copy
    * Preincrement will increment then return the original

    So (unless you're handling simple things like ints) preincrement is faster.

    int preIncrement(int i)
    {
        i = i + 1;
        return i;
    }
    
    int postIncrement(int i)
    {
        int temp = i;
        i = i + 1;
        return temp;
    }
    

    Aber auch mit nem string::const_iterator konnte ich keine Lautzeitunterschiede messen.

    edit:
    iiik, in diesem Fall hier:

    #include <iostream>
    #include <string>
    #include <sys/time.h>
    
    using namespace std;
    int main()
    {
    	timeval start, end;
    	string b = "qwertzuiopasdfghjklyxcvbnm";
    	string bla = b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b+b;
    	string::iterator it;
    
    	gettimeofday(&start, 0);
    	for ( int i = 0; i < 1000000; i++ )
    	{
    		for ( it = bla.begin(); it != bla.end(); )
    		{
    			*it = *(it++);
    		}
    	}
    	gettimeofday(&end, 0);
    
    	cout << "time passed in ms: " << (end.tv_sec*1000 + end.tv_usec/1000) - (start.tv_sec*1000 + start.tv_usec/1000) << endl;
    
    	gettimeofday(&start, 0);
    	for ( int i = 0; i < 1000000; i++ )
    	{
    		for ( it = bla.begin(); it != bla.end(); )
    		{
    			*it = *(++it);
    		}
    	}
    	gettimeofday(&end, 0);
    
    	cout << "time passed in ms: " << (end.tv_sec*1000 + end.tv_usec/1000) - (start.tv_sec*1000 + start.tv_usec/1000) << endl;
    
    	return 0;
    }
    

    sieht meine Ausgabe sogar so aus:

    time passed in ms: 2703
    time passed in ms: 3141
    

    Also hier gewinnt das Postinkrement. 😮



  • Dobias schrieb:

    Im Netz findet man noch oft solche Hinweise:

    No they do not have the same performance:

    * Postincrement will create a copy then increment, then return the copy
    * Preincrement will increment then return the original

    So (unless you're handling simple things like ints) preincrement is faster.

    ^^ ja, von dem schmarrn findet man viel. mir ist echt nicht klar, warum post-increment sich so doof verhalten soll. zuerst zuweisen und danach hochzählen und schon braucht's keine kopie. und von wegen 'simple things like ints', mit floats oder pointern sollte es ebenso gut funktionieren.

    Dobias schrieb:

    Aber auch mit nem string::const_iterator konnte ich keine Lautzeitunterschiede messen.

    ist das was von C++? naja, irgendwelche unanschaulichen c++-tricks helfen wohl kaum weiter. dieser 'const_iterator' ist intern bestimmt auch nur ein einfacher pointer.
    🙂



  • ;fricky schrieb:

    ^^ ja, von dem schmarrn findet man viel. mir ist echt nicht klar, warum post-increment sich so doof verhalten soll. zuerst zuweisen und danach hochzählen und schon braucht's keine kopie. und von wegen 'simple things like ints', mit floats oder pointern sollte es ebenso gut funktionieren.

    Du kennste die Welt jenseits deines Tellerrandes nicht. Natürlich sind das C++-Aussagen und sind in diesem Forum nicht von Belang.



  • Ah ok, sorry. Jetzt weich ich natürlich von C ab.
    Könnte also sein, dass es bei C-Geschichten wirklich keinen Unterschied macht.
    In C++ returned der Postfix-Operator bei den meißten Klassen jedoch per Value und nicht per Referenz.

    class Number {
    public:
    Number& operator++ ();    // prefix ++
    Number  operator++ (int); // postfix ++
    };
    

    Hier würde es dann natürlich nen Unterschied (nämlich eine Kopie) machen.
    In meinem ursprünglichen Zeigerfall scheints allerdings tatsächlich egal zu sein. 👍



  • Dobias schrieb:

    In meinem ursprünglichen Zeigerfall scheints allerdings tatsächlich egal zu sein. 👍

    Jup, das hoffe ich.
    Ganz früher war dem Hörensagen nach Präinkrement auf Dummcompilern schneller. Dann war Postinkrement meistens schneller wegen irgendwas mit Pipelining. Heute weiß der optimierende Compiler sehr genau, wie man mit Pipelines spielt und er macht das Beste draus und Prä- oder Post- kümmert mich nicht.



  • volkard schrieb:

    Natürlich sind das C++-Aussagen und sind in diesem Forum nicht von Belang.

    das will ich doch wohl meinen. unter c++ könnt' ich mir gut vorstellen, dass überladene postinkrement-operatoren sich seltsam zickig verhalten. sowas gibts ja in C (zum glück) nicht.
    🙂


Log in to reply