Warum unsigned langsamer als signed?

*Cassiopeia*

Hallo,

folgendes konstruiertes Beispiel:

#include <iostream>
#include <ctime>
using namespace std;

int main()
{
    double time1,time2;
    int i,a,b,c;
    a=2;
    b=5;

    time1 = clock();
    for(i=1;i<90000000;++i)
        c=(a*i)/(b*i);
    time2 = clock();

    cout << c << ", " << ((double)(time2-time1)/CLOCKS_PER_SEC)*1000 << endl;
    return 0;
}

Die for-Schleife ist nur dazu da, um eine messbare Zeit zu bekommen.
Mit int (für i,a,b,c) erhalte ich 305 ms im Durschnitt, mit unsigned int 375 ms.

Warum gibt es hier Performance-Unterschiede? Ich dachte, dass nur der Wertebereich sich ändert.

volkard

Das messe ich auch.

Mit unsigned int:

.L2:
	movl	%ecx, %eax
	xorl	%edx, %edx
	addl	$2, %ecx
	divl	%ebx
	addl	$5, %ebx
	cmpl	$180000000, %ecx
	movl	%eax, %r12d
	jne	.L2

Mit signed int:

.L2:
	movl	%ecx, %edx
	movl	%ecx, %eax
	addl	$2, %ecx
	sarl	$31, %edx
	idivl	%ebx
	addl	$5, %ebx
	cmpl	$180000000, %ecx
	movl	%eax, %r12d
	jne	.L2

Komisch.

Übrigens, wenn die Schleife zehnmal so lang geht, habe ich 30ms zugunsten von unsigned int. 3230 zu 3200.

drakon

div und idiv müssen nicht gleich schnell sein. Kommt drauf an wie es implementiert ist.
Ist aber anscheinend nicht unüblich, dass sie unterschiedlich sind:
http://faydoc.tripod.com/cpu/idiv.htm
vs.
http://faydoc.tripod.com/cpu/div.htm

div (reg,32): 41 clocks
idiv (reg,32): 46 clocks

unsigned müsste also schneller sein als signed.
Könnte sein, dass die erste Messung doch zu viele Fehler hat. Ich würde das Ergebnis von volkard erwarten (die 10er Version).

SeppJ

Ich kann die Ergebnisse nicht nachvollziehen. Getestet auf i7, GCC 4.4, O3 Optimierung, testweise auch mal mit march="native" (hat sogar ein bisschen was gebracht). Bei gleicher Optimierung exakt die gleiche Zeit.

Intelcompiler 11 optimiert die Schleife gänzlich weg, Laufzeit 0. Habe aber gerade keine Lust, ihm das Optimieren künstlich zu erschweren, so dass er das nicht mehr macht.

edit: Ach ja, der Code des GCC unsigned:

.L4:
	movl	%ecx, %eax
	xorl	%edx, %edx
	addl	$2, %ecx
	divl	%ebx
	addl	$5, %ebx
	cmpl	$1800000000, %ecx
	movl	%eax, %r13d
	jne	.L4

Mit march=native (man beachte den kleinen aber feinen Unterschied:

.L4:
	movl	%ecx, %eax
	xorl	%edx, %edx
	addl	$2, %ecx
	divl	%ebx
	addl	$5, %ebx
	movl	%eax, %r13d
	cmpl	$1800000000, %ecx
	jne	.L4

Und mit int (hier nur die normale Version, die native Version könnt ihr euch denken):

.L4:
	movl	%ecx, %edx
	movl	%ecx, %eax
	addl	$2, %ecx
	sarl	$31, %edx
	idivl	%ebx
	addl	$5, %ebx
	cmpl	$1800000000, %ecx
	movl	%eax, %r13d
	jne	.L4

volkard

SeppJ schrieb:

Ich kann die Ergebnisse nicht nachvollziehen. Getestet auf i7, GCC 4.4, O3 Optimierung, testweise auch mal mit march="native" (hat sogar ein bisschen was gebracht). Überall exakt das gleiche.

Na, dann messe ich auch mal ausführlicher (i7, gcc4.5, -O3 -march=native):

g++ -O3 -march=native main.cpp && (for i in {1..100}; do time ./a.out ; done)2>&1 | grep real | sort | head

unsigned:

real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s
real	0m0.320s

signed:

real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s
real	0m0.293s

*Cassiopeia*

Ich hatte es im Ausgangspost ohne Optimierung getestet, aber habs jetzt nochmal mit -03 und -march=native gemacht (ebenfalls i7 und gcc 4.6.1). Ich komme auch auf die Zeiten von volkard (270 vs. 312 für signed). Auch wenn ich die Schleife länger laufen lasse, bleibt signed bei mir schneller (2920 vs. 3120)

Mit dem Assemblercode kenne ich mich leider nicht wirklich aus... ich hatte mich bei einem größeren Projekt nur gewundert, dass mein Code mit unsigned langsamer läuft und wollte das deswegen etwas genauer angucken mit dem kleinen Beispiel. Und zumindest auf meinem Rechner hat sich das ja bestätigt.

volkard

Leider kann man es nicht verallgemeinern. Bei mir ist meistens unsigned ein wenig schneller.

Vielleicht gibt es bei signed einen Schaltkreis mehr, der vorher einen Größenvergleich macht und als Nebenprodukt eine schnelle Nullnummer machen kann, falls der Zähler kleiner als der Nenner ist. Das habe ich mal weggemacht.

#include <iostream>
#include <ctime>
using namespace std;

int main()
{
    cout<<"test\n";
    double time1,time2;
    signed int i,a,b,c;
    c=0;
    a=2;
    b=5;

    time1 = clock();
    for(i=1;i<90000000;++i)
        c+=(b*i)/(a*i);//andersrum als vorher, und += gegen Wegoptimierung
    time2 = clock();

    cout << c << ", " << ((double)(time2-time1)/CLOCKS_PER_SEC)*1000 << endl;
    return 0;
}

unsigned: 373
signed: 373

SeppJ

@volkard: Das ist ja mal lustig:

signed:

real 0.339	user 0.340	sys 0.000	pcpu 100.22
real 0.339	user 0.340	sys 0.000	pcpu 100.27
real 0.339	user 0.340	sys 0.000	pcpu 100.28
real 0.339	user 0.340	sys 0.000	pcpu 100.29
real 0.339	user 0.340	sys 0.000	pcpu 100.29
real 0.339	user 0.340	sys 0.000	pcpu 100.30
real 0.339	user 0.340	sys 0.000	pcpu 100.31
real 0.339	user 0.340	sys 0.000	pcpu 100.31
real 0.339	user 0.340	sys 0.000	pcpu 100.31
real 0.339	user 0.340	sys 0.000	pcpu 100.32

unsigned:

real 0.339	user 0.320	sys 0.020	pcpu 100.29
real 0.339	user 0.330	sys 0.010	pcpu 100.28
real 0.339	user 0.330	sys 0.010	pcpu 100.33
real 0.339	user 0.340	sys 0.000	pcpu 100.15
real 0.339	user 0.340	sys 0.000	pcpu 100.16
real 0.339	user 0.340	sys 0.000	pcpu 100.17
real 0.339	user 0.340	sys 0.000	pcpu 100.17
real 0.339	user 0.340	sys 0.000	pcpu 100.20
real 0.339	user 0.340	sys 0.000	pcpu 100.21
real 0.339	user 0.340	sys 0.000	pcpu 100.22

Den Assembleroutput haben wir ja schon verlgichen, die Compilerversion kann's nicht sein. Das Programm ist gewiss auch nicht durch die externen Komponenten gebremst, das sollte reine CPU sein. Hat vielleicht Intel da ganz was grundlegendes an seiner Architektur geändert? Ich habe hier einen i7-920, also ein Nehalem. Da deiner ein bisschen schneller ist und ich weiß, dass du dir vor ein paar Monaten einen neuen Rechner gekauft hast, nehme ich mal an, du hast eine der neueren Mikroarchitekturen?

Glauben manche Leute eigentlich, dass ihr Code so perfekt ist, dass sie auf sowas achten müssen? Oder ist euch nur langweilig?

*Cassiopeia*

$geegt$ schrieb:

Glauben manche Leute eigentlich, dass ihr Code so perfekt ist, dass sie auf sowas achten müssen? Oder ist euch nur langweilig?

Interesse und auch Langeweile, ja ;)... natürlich sind das alles keine Größenordnungen, aber interessieren tuts mich schon.

volkard

SeppJ schrieb:

Ich habe hier einen i7-920, also ein Nehalem. Da deiner ein bisschen schneller ist und ich weiß, dass du dir vor ein paar Monaten einen neuen Rechner gekauft hast, nehme ich mal an, du hast eine der neueren Mikroarchitekturen?

Ja, "Sandy Bridge" hat mich erst überzeugt.
http://geizhals.at/deutschland/580311

*rant*

Ich habe aus Interesse den Code auch mal kompiliert mit (i<100000000) in einer Windows 7 VM und eine Feststellung gemacht. Das Resultat mit optimierten Solution Settings: Mit int 375, unsigned int 450!

Und dann habe ich folgendes gemacht: Visual C++ mit x64 Target und maximalen Optimierungen. Resultat: Beides 125. Kann es sein, dass der Compiler für x86 nicht mehr gut optimiert? Oder dass die neuen CPUs nicht mehr so toll mit den normalen ints umgehen?

CPU: Sandy Bridge i7 QM, 2.2 GHz.

volkard

/rant/ schrieb:

Oder dass die neuen CPUs nicht mehr so toll mit den normalen ints umgehen?

Nette Idee. Habe mit (un)signed long long gemessen.
unsigned long long: 0.750s
signed long long: 0.784s

Jetzt ist die Welt wieder in Ordnung. :xmas2: :xmas1:

camper

mit einem Atom N330 bekomme ich diese Wert (unter 64-bit-Gentoo):
unsigned: 3000 ms
signed: 3740 ms
unsigned long long: 7360 ms
signed long long: 8730 ms

Was zu dem gefunden:
http://stackoverflow.com/questions/410982/is-there-a-difference-in-term-of-performance-between-unsigned-int-and-int-on