Geschwindigkeitsunterschied zwischen der Verwendung von int und unsigned int, wenn sie mit Doubles gemischt werden
Ich habe eine Anwendung, bei der ein Teil der inneren Schleife im Grunde war:
double sum = 0;
for (int i = 0; i != N; ++i, ++data, ++x) sum += *data * x;
Wenn x ein unsigned int ist, dann dauert der Code dreimal so lange wie mit int!
Dies war Teil einer größeren Codebasis, aber ich habe es auf das Wesentliche reduziert:
#include <iostream>
#include <cstdlib>
#include <vector>
#include <time.h>
typedef unsigned char uint8;
template<typename T>
double moments(const uint8* data, int N, T wrap) {
T pos = 0;
double sum = 0.;
for (int i = 0; i != N; ++i, ++data) {
sum += *data * pos;
++pos;
if (pos == wrap) pos = 0;
}
return sum;
}
template<typename T>
const char* name() { return "unknown"; }
template<>
const char* name<int>() { return "int"; }
template<>
const char* name<unsigned int>() { return "unsigned int"; }
const int Nr_Samples = 10 * 1000;
template<typename T>
void measure(const std::vector<uint8>& data) {
const uint8* dataptr = &data[0];
double moments_results[Nr_Samples];
time_t start, end;
time(&start);
for (int i = 0; i != Nr_Samples; ++i) {
moments_results[i] = moments<T>(dataptr, data.size(), 128);
}
time(&end);
double avg = 0.0;
for (int i = 0; i != Nr_Samples; ++i) avg += moments_results[i];
avg /= Nr_Samples;
std::cout << "With " << name<T>() << ": " << avg << " in " << (end - start) << "secs" << std::endl;
}
int main() {
std::vector<uint8> data(128*1024);
for (int i = 0; i != data.size(); ++i) data[i] = std::rand();
measure<int>(data);
measure<unsigned int>(data);
measure<int>(data);
return 0;
}
Kompilieren ohne Optimierung:
[email protected]:/home/luispedro/tmp/so §g++ test.cpp
[email protected]:/home/luispedro/tmp/so §./a.out
With int: 1.06353e+09 in 9secs
With unsigned int: 1.06353e+09 in 14secs
With int: 1.06353e+09 in 9secs
Mit Optimierung:
[email protected]:/home/luispedro/tmp/so §g++ -O3 test.cpp
[email protected]:/home/luispedro/tmp/so §./a.out
With int: 1.06353e+09 in 3secs
With unsigned int: 1.06353e+09 in 12secs
With int: 1.06353e+09 in 4secs
Ich verstehe nicht, warum so ein großer Unterschied in der Geschwindigkeit. Ich habe versucht, es aus der generierten Assembly herauszufinden, aber ich bin nirgendwo hingekommen. Hat jemand eine Idee?
Hat das etwas mit der Hardware zu tun oder ist es eine Einschränkung der Optimierungsmaschinerie von gcc? Ich wette auf das Zweite.
Mein Rechner ist ein Intel 32 Bit mit Ubuntu 9.10.
Bearbeiten :Da Stephen gefragt hat, hier ist die dekompilierte Quelle (aus einer -O3-Kompilation). Ich glaube, ich habe die Hauptschleifen:
int-Version:
40: 0f b6 14 0b movzbl (%ebx,%ecx,1),%edx
sum += *data * pos;
44: 0f b6 d2 movzbl %dl,%edx
47: 0f af d0 imul %eax,%edx
++pos;
4a: 83 c0 01 add $0x1,%eax
sum += *data * pos;
4d: 89 95 54 c7 fe ff mov %edx,-0x138ac(%ebp)
++pos;
if (pos == wrap) pos = 0;
53: 31 d2 xor %edx,%edx
55: 3d 80 00 00 00 cmp $0x80,%eax
5a: 0f 94 c2 sete %dl
T pos = 0;
double sum = 0.;
for (int i = 0; i != N; ++i, ++data) {
5d: 83 c1 01 add $0x1,%ecx
sum += *data * pos;
60: db 85 54 c7 fe ff fildl -0x138ac(%ebp)
++pos;
if (pos == wrap) pos = 0;
66: 83 ea 01 sub $0x1,%edx
69: 21 d0 and %edx,%eax
T pos = 0;
double sum = 0.;
for (int i = 0; i != N; ++i, ++data) {
6b: 39 f1 cmp %esi,%ecx
sum += *data * pos;
6d: de c1 faddp %st,%st(1)
T pos = 0;
double sum = 0.;
for (int i = 0; i != N; ++i, ++data) {
6f: 75 cf jne 40
unsignierte Version:
50: 0f b6 34 13 movzbl (%ebx,%edx,1),%esi
sum += *data * pos;
54: 81 e6 ff 00 00 00 and $0xff,%esi
5a: 31 ff xor %edi,%edi
5c: 0f af f0 imul %eax,%esi
++pos;
5f: 83 c0 01 add $0x1,%eax
if (pos == wrap) pos = 0;
62: 3d 80 00 00 00 cmp $0x80,%eax
67: 0f 94 c1 sete %cl
T pos = 0;
double sum = 0.;
for (int i = 0; i != N; ++i, ++data) {
6a: 83 c2 01 add $0x1,%edx
sum += *data * pos;
6d: 89 bd 54 c7 fe ff mov %edi,-0x138ac(%ebp)
73: 89 b5 50 c7 fe ff mov %esi,-0x138b0(%ebp)
++pos;
if (pos == wrap) pos = 0;
79: 89 ce mov %ecx,%esi
7b: 81 e6 ff 00 00 00 and $0xff,%esi
sum += *data * pos;
81: df ad 50 c7 fe ff fildll -0x138b0(%ebp)
++pos;
if (pos == wrap) pos = 0;
87: 83 ee 01 sub $0x1,%esi
8a: 21 f0 and %esi,%eax
for (int i = 0; i != N; ++i, ++data) {
8c: 3b 95 34 c7 fe ff cmp -0x138cc(%ebp),%edx
sum += *data * pos;
92: de c1 faddp %st,%st(1)
for (int i = 0; i != N; ++i, ++data) {
94: 75 ba jne 50
Dies ist die -O3-Version, weshalb die Quellzeilen auf und ab springen.
Danke.
Antworten:
Hier ist der Grund:Viele gängige Architekturen (einschließlich x86) haben eine Hardwareanweisung zum Konvertieren von signed int in Doubles, aber keine Hardwarekonvertierung von unsigned in double, sodass der Compiler die Konvertierung in Software synthetisieren muss. Darüber hinaus ist die einzige vorzeichenlose Multiplikation auf Intel eine Multiplikation in voller Breite, während vorzeichenbehaftete Multiplikationen die Anweisung "Signed Multiply Low" verwenden können.
Die Software-Konvertierung von GCC von unsigned int nach double ist möglicherweise suboptimal (was angesichts des Ausmaßes der von Ihnen beobachteten Verlangsamung mit ziemlicher Sicherheit der Fall ist), aber es wird erwartet, dass sich der Code schneller verhält, wenn signierte Ganzzahlen verwendet werden.
Unter der Annahme eines intelligenten Compilers sollte der Unterschied auf einem 64-Bit-System viel kleiner sein, da eine 64-Bit-Integer mit Vorzeichen -> Doppelkonvertierung verwendet werden kann, um eine 32-Bit-Konvertierung ohne Vorzeichen effizient durchzuführen.
Bearbeiten: Zur Veranschaulichung dies:
sum += *data * x;
wenn die Integer-Variablen signiert sind, sollte in etwas in dieser Richtung kompiliert werden:
mov (data), %eax
imul %ecx, %eax
cvtsi2sd %eax, %xmm1
addsd %xmm1, %xmm0
andererseits, wenn die Integer-Variablen unsigned sind, cvtsi2sd kann nicht für die Konvertierung verwendet werden, daher ist eine Softwareumgehung erforderlich. Ich würde so etwas erwarten:
mov (data), %eax
mul %ecx // might be slower than imul
cvtsi2sd %eax, %xmm1 // convert as though signed integer
test %eax, %eax // check if high bit was set
jge 1f // if it was, we need to adjust the converted
addsd (2^32), %xmm1 // value by adding 2^32
1: addsd %xmm1, %xmm0
Das wäre "akzeptables" Codegen für die unsignierte -> doppelte Konvertierung; es könnte leicht schlimmer sein.
All dies setzt die Generierung von Gleitkommacode für SSE voraus (ich glaube, dies ist die Standardeinstellung der Ubuntu-Tools, aber ich könnte mich irren).
Einige Code-Antworten
double sum = 0;
for (int i = 0;
i != N;
++i, ++data, ++x) sum += *data * x;
#include <iostream>
#include <cstdlib>
#include <vector>
#include <time.h>
typedef unsigned char uint8;
template<typename T>
double moments(const uint8* data, int N, T wrap) {
T pos = 0;
double sum = 0.;
for (int i = 0;
i != N;
++i, ++data) {
sum += *data * pos;
++pos;
if (pos == wrap) pos = 0;
}
return sum;
} template<typename T>
const char* name() { return "unknown";
} template<>
const char* name<int>() { return "int";
} template<>
const char* name<unsigned int>() { return "unsigned int";
} const int Nr_Samples = 10 * 1000;
template<typename T>
void measure(const std::vector<uint8>&
data) {
const uint8* dataptr = &data[0];
double moments_results[Nr_Samples];
time_t start, end;
time(&start);
for (int i = 0;
i != Nr_Samples;
++i) {
moments_results[i] = moments<T>(dataptr, data.size(), 128);
}
time(&end);
double avg = 0.0;
for (int i = 0;
i != Nr_Samples;
++i) avg += moments_results[i];
avg /= Nr_Samples;
std::cout <<
"With " <<
name<T>() <<
": " <<
avg <<
" in " <<
(end - start) <<
"secs" <<
std::endl;
} int main() {
std::vector<uint8>
data(128*1024);
for (int i = 0;
i != data.size();
++i) data[i] = std::rand();
measure<int>(data);
measure<unsigned int>(data);
measure<int>(data);
return 0;
} [email protected]:/home/luispedro/tmp/so §g++ test.cpp
[email protected]:/home/luispedro/tmp/so §./a.out With int: 1.06353e+09 in 9secs With unsigned int: 1.06353e+09 in 14secs With int: 1.06353e+09 in 9secs [email protected]:/home/luispedro/tmp/so §g++ -O3 test.cpp [email protected]:/home/luispedro/tmp/so §./a.out With int: 1.06353e+09 in 3secs With unsigned int: 1.06353e+09 in 12secs With int: 1.06353e+09 in 4secs 40: 0f b6 14 0b movzbl (%ebx,%ecx,1),%edx
sum += *data * pos;
44: 0f b6 d2 movzbl %dl,%edx 47: 0f af d0 imul %eax,%edx
++pos;
4a: 83 c0 01 add $0x1,%eax
sum += *data * pos;
4d: 89 95 54 c7 fe ff
mov %edx,-0x138ac(%ebp)
++pos;
if (pos == wrap) pos = 0;
53: 31 d2
xor %edx,%edx 55: 3d 80 00 00 00
cmp $0x80,%eax 5a: 0f 94 c2 sete %dl T pos = 0;
double sum = 0.;
for (int i = 0;
i != N;
++i, ++data) { 5d: 83 c1 01 add $0x1,%ecx
sum += *data * pos;
60: db 85 54 c7 fe ff
fildl -0x138ac(%ebp)
++pos;
if (pos == wrap) pos = 0;
66: 83 ea 01 sub $0x1,%edx 69: 21 d0
and %edx,%eax T pos = 0;
double sum = 0.;
for (int i = 0;
i != N;
++i, ++data) { 6b: 39 f1
cmp %esi,%ecx
sum += *data * pos;
6d: de c1
faddp %st,%st(1) T pos = 0;
double sum = 0.;
for (int i = 0;
i != N;
++i, ++data) { 6f: 75 cf
jne 40 50: 0f b6 34 13 movzbl (%ebx,%edx,1),%esi
sum += *data * pos;
54: 81 e6 ff 00 00 00
and $0xff,%esi 5a: 31 ff
xor %edi,%edi 5c: 0f af f0 imul %eax,%esi
++pos;
5f: 83 c0 01 add $0x1,%eax
if (pos == wrap) pos = 0;
62: 3d 80 00 00 00
cmp $0x80,%eax 67: 0f 94 c1 sete %cl T pos = 0;
double sum = 0.;
for (int i = 0;
i != N;
++i, ++data) { 6a: 83 c2 01 add $0x1,%edx
sum += *data * pos;
6d: 89 bd 54 c7 fe ff
mov %edi,-0x138ac(%ebp) 73: 89 b5 50 c7 fe ff
mov %esi,-0x138b0(%ebp)
++pos;
if (pos == wrap) pos = 0;
79: 89 ce
mov %ecx,%esi 7b: 81 e6 ff 00 00 00
and $0xff,%esi
sum += *data * pos;
81: df ad 50 c7 fe ff
fildll -0x138b0(%ebp)
++pos;
if (pos == wrap) pos = 0;
87: 83 ee 01 sub $0x1,%esi 8a: 21 f0
and %esi,%eax for (int i = 0;
i != N;
++i, ++data) { 8c: 3b 95 34 c7 fe ff
cmp -0x138cc(%ebp),%edx
sum += *data * pos;
92: de c1
faddp %st,%st(1) for (int i = 0;
i != N;
++i, ++data) { 94: 75 ba
jne 50 sum += *data * x;
mov
(data), %eax imul
%ecx,
%eax cvtsi2sd %eax,
%xmm1 addsd
%xmm1, %xmm0 mov
(data), %eax
mul
%ecx// might be slower than imul
cvtsi2sd %eax,
%xmm1 // convert as though signed integer
test
%eax,
%eax // check if high bit was set
jge
1f // if it was, we need to adjust the converted
addsd
(2^32), %xmm1 // value by adding 2^32 1: addsd
%xmm1, %xmm0 4:
int x = 12345;
0040E6D8 mov
dword ptr [ebp-4],3039h 5:
double d1 = x;
0040E6DF fild
dword ptr [ebp-4] 0040E6E2 fstp
qword ptr [ebp-0Ch] 6:
unsigned int y = 12345;
0040E6E5 mov
dword ptr [ebp-10h],3039h 7:
double d2 = y;
0040E6EC mov
eax,dword ptr [ebp-10h] 0040E6EF mov
dword ptr [ebp-20h],eax 0040E6F2 mov
dword ptr [ebp-1Ch],0 0040E6F9 fild
qword ptr [ebp-20h] 0040E6FC fstp
qword ptr [ebp-18h] With int: 4.23944e+009 in 9secs With unsigned int: 4.23944e+009 in 18secs With int: 4.23944e+009 in 9secs With int: 4.23944e+009 in 34secs With unsigned int: 4.23944e+009 in 58secs With int: 4.23944e+009 in 34secs for (int i = 0;
i != Nr_Samples;
++i) { 011714A1 fldz 011714A3 mov
edx,dword ptr [esi+4] 011714A6 add
esp,4 011714A9 xor
edi,edi 011714AB sub
edx,dword ptr [esi]
moments_results[i] = moments<T>(dataptr, data.size(), 128);
011714AD mov
ecx,dword ptr [ebp-1388Ch] 011714B3 fld
st(0) 011714B5 xor
eax,eax 011714B7 test
edx,edx 011714B9 je
measure<unsigned int>+79h (11714E9h) 011714BB mov
esi,edx 011714BD movzx
ebx,byte ptr [ecx] 011714C0 imul
ebx,eax 011714C3 mov
dword ptr [ebp-138A4h],ebx 011714C9 fild
dword ptr [ebp-138A4h] //only in unsigned 011714CF test
ebx,ebx //only in unsigned 011714D1 jns
measure<unsigned int>+69h (11714D9h) //only in unsigned 011714D3 fadd
qword ptr [[email protected] (11731C8h)] //only in unsigned 011714D9 inc
eax 011714DA faddp
st(1),st 011714DC cmp
eax,80h 011714E1 jne
measure<unsigned int>+75h (11714E5h) 011714E3 xor
eax,eax 011714E5 inc
ecx 011714E6 dec
esi 011714E7 jne
measure<unsigned int>+4Dh (11714BDh) 011714E9 fstp
qword ptr [ebp+edi*8-13888h] 011714F0 inc
edi 011714F1 cmp
edi,2710h 011714F7 jne
measure<unsigned int>+3Dh (11714ADh)
} for (int i = 0;
i != Nr_Samples;
++i) { 012A1351 fldz 012A1353 mov
edx,dword ptr [esi+4] 012A1356 add
esp,4 012A1359 xor
edi,edi 012A135B sub
edx,dword ptr [esi]
moments_results[i] = moments<T>(dataptr, data.size(), 128);
012A135D mov
ecx,dword ptr [ebp-13890h] 012A1363 fld
st(0) 012A1365 xor
eax,eax 012A1367 test
edx,edx 012A1369 je
measure<int>+6Fh (12A138Fh) 012A136B mov
esi,edx 012A136D movzx
ebx,byte ptr [ecx] 012A1370 imul
ebx,eax 012A1373 mov
dword ptr [ebp-1388Ch],ebx 012A1379 inc
eax 012A137A fild
dword ptr [ebp-1388Ch] //only in signed 012A1380 faddp
st(1),st 012A1382 cmp
eax,80h 012A1387 jne
measure<int>+6Bh (12A138Bh) 012A1389 xor
eax,eax 012A138B inc
ecx 012A138C dec
esi 012A138D jne
measure<int>+4Dh (12A136Dh) 012A138F fstp
qword ptr [ebp+edi*8-13888h] 012A1396 inc
edi 012A1397 cmp
edi,2710h 012A139D jne
measure<int>+3Dh (12A135Dh)
} With int: 4.23944e+009 in 8secs With unsigned int: 4.23944e+009 in 10secs With int: 4.23944e+009 in 8secs
for (int i = 0;
i != Nr_Samples;
++i) { 00F614C1 mov
edx,dword ptr [esi+4] 00F614C4 xorps
xmm0,xmm0 //added in sse version 00F614C7 add
esp,4 00F614CA xor
edi,edi 00F614CC sub
edx,dword ptr [esi]
moments_results[i] = moments<T>(dataptr, data.size(), 128);
00F614CE mov
ecx,dword ptr [ebp-13894h] 00F614D4 xor
eax,eax 00F614D6 movsd
mmword ptr [ebp-13890h],xmm0 //added in sse version 00F614DE test
edx,edx 00F614E0 je
measure<unsigned int>+8Ch (0F6151Ch) 00F614E2 fld
qword ptr [ebp-13890h] //added in sse version 00F614E8 mov
esi,edx 00F614EA movzx
ebx,byte ptr [ecx] 00F614ED imul
ebx,eax 00F614F0 mov
dword ptr [ebp-1388Ch],ebx 00F614F6 fild
dword ptr [ebp-1388Ch] 00F614FC test
ebx,ebx 00F614FE jns
measure<unsigned int>+76h (0F61506h) 00F61500 fadd
qword ptr [[email protected] (0F631C8h)] 00F61506 inc
eax 00F61507 faddp
st(1),st 00F61509 cmp
eax,80h 00F6150E jne
measure<unsigned int>+82h (0F61512h) 00F61510 xor
eax,eax 00F61512 inc
ecx 00F61513 dec
esi 00F61514 jne
measure<unsigned int>+5Ah (0F614EAh) 00F61516 fstp
qword ptr [ebp-13890h] 00F6151C movsd
xmm1,mmword ptr [ebp-13890h] //added in sse version 00F61524 movsd
mmword ptr [ebp+edi*8-13888h],xmm1 //added in sse version 00F6152D inc
edi 00F6152E cmp
edi,2710h 00F61534 jne
measure<unsigned int>+3Eh (0F614CEh)
} With int time per operation in ns: 11996, total time sec: 1.57237 Avg values: 1.06353e+09 With unsigned int time per operation in ns: 11539, total time sec: 1.5125 Avg values: 1.06353e+09 With int time per operation in ns: 11994, total time sec: 1.57217 Avg values: 1.06353e+09