Steigert das Ersetzen von "if"´s durch logische Konstrukte die Performance?
-
Hallo
Am besten erkläre ich es an einem Beispiel, das zählt, wie oft ein Wert in einem Array vorkommt (mein performancekritisches Problem ist analog dazu)
int func1(int* array, int number, int value){ int number_of_value = 0; for(int i=0; i<number; i++){ if(array[i] == value) number_of_value++; } return number_of_value; } int func2(int* array, int number, int value){ int number_of_value = 0; for(int i = number-1; i >= 0; i--){ //i >= 0 sollte schneller als i<number sein number_of_value += (array[i] == value); //Vermeidung des bedingten Sprunges } return number_of_value; }Es ist Code für einen normalen PC, also nicht embedded oder so.
Ist func2 nennenswert schneller als func1? Kann allgemein gesagt werden, dass das Vermeiden von if´s schnelleren Code bringt? Welche anderen Optimierungsmaßnahmen gibt es sonst noch für dieses Beispiel?
Würd mich freuen, wenn mir wer helfen könnte, meine Performancekenntnisse aufzubessern
-
Nein, sollte so wie ich das sehe, keinen Boost geben (nicht keinen nennenswerten, sondern keinen). Denn nun muss der Bool'sche Wert ja in einen Integer umgewandelt werden.
Zumal moderne Rechner solche Schleifen schon ziemlich flott können.
Bist du mal mit einem Profiler an deinen Code gegangen und der hat dir gesagt, dass dort der Performanceflaschenhals liegt?
-
ok, danke.
Mein Hintergedanke war, dass sich bedingte Sprünge und Pipelining nicht mögenDann ist die Variante mit dem if besser, weil das sieht nicht so kryptisch aus
-
Ich sag mal ganz pauschal: Dein Compiler ist klug genug, so was zu erkennen und zu optimieren. (Wenn du nicht irgendwas ganz komisches benutzt.) Wenn du die Optimierung ausschaltest, kann es vielleicht einen Unterschied machen, aber wen interessiert das?
Die Argumentation mit der Umwandlung des boolschen Wertes in einen Integer kann ich aber nicht nachvollziehen. Der ist doch schon einer.
-
Der Code der da erzeugt wird ist durchaus unterschiedlich, ich habe mal folgende Funktionen zum Vergleichen genommen:
std::uint64_t /*__declspec(noinline) */ count1(const std::int32_t* numbers, std::size_t size, std::int32_t number_to_count) { std::uint64_t counter = 0; for (std::size_t i = 0; i != size; ++i) { if (numbers[i] == number_to_count) ++counter; } return counter; }std::uint64_t /* __declspec(noinline) */ count2(const std::int32_t* numbers, std::size_t size, std::int32_t number_to_count) { std::uint64_t counter = 0; for (std::size_t i = 0; i != size; ++i) { counter += numbers[i] == number_to_count; } return counter; }GCC 4.9 -O3 -std=c++11 für count1:
count1(int const*, unsigned long, int): test rsi, rsi je .L4 lea rsi, [rdi+rsi*4] xor eax, eax .L3: cmp DWORD PTR [rdi], edx lea rcx, [rax+1] cmove rax, rcx add rdi, 4 cmp rdi, rsi jne .L3 rep ret .L4: xor eax, eax retGCC 4.9 -O3 -std=c++11 für count2:
count2(int const*, unsigned long, int): test rsi, rsi push rbx je .L13 mov rcx, rdi and ecx, 15 shr rcx, 2 neg rcx and ecx, 3 cmp rcx, rsi cmova rcx, rsi cmp rsi, 5 ja .L25 mov rcx, rsi .L3: xor eax, eax cmp DWORD PTR [rdi], edx sete al cmp rcx, 1 je .L16 xor r8d, r8d cmp DWORD PTR [rdi+4], edx sete r8b add rax, r8 cmp rcx, 2 je .L17 xor r8d, r8d cmp DWORD PTR [rdi+8], edx sete r8b add rax, r8 cmp rcx, 3 je .L18 xor r8d, r8d cmp DWORD PTR [rdi+12], edx sete r8b add rax, r8 cmp rcx, 5 jne .L19 xor r8d, r8d cmp DWORD PTR [rdi+16], edx sete r8b add rax, r8 mov r8d, 5 .L5: cmp rsi, rcx je .L2 .L4: mov r11, rsi lea r10, [rsi-1] sub r11, rcx lea r9, [r11-4] sub r10, rcx shr r9, 2 add r9, 1 cmp r10, 2 lea rbx, [0+r9*4] jbe .L7 mov DWORD PTR [rsp-4], edx pxor xmm2, xmm2 movd xmm6, DWORD PTR [rsp-4] pxor xmm3, xmm3 movdqa xmm4, XMMWORD PTR .LC0[rip] lea r10, [rdi+rcx*4] pshufd xmm5, xmm6, 0 xor ecx, ecx .L8: movdqa xmm1, XMMWORD PTR [r10] add rcx, 1 add r10, 16 cmp r9, rcx pcmpeqd xmm1, xmm5 pand xmm1, xmm4 movdqa xmm0, xmm1 punpckldq xmm1, xmm3 punpckhdq xmm0, xmm3 paddq xmm2, xmm1 paddq xmm2, xmm0 ja .L8 movdqa xmm0, xmm2 add r8, rbx psrldq xmm0, 8 paddq xmm0, xmm2 movq rcx, xmm0 add rax, rcx cmp r11, rbx je .L2 .L7: xor ecx, ecx cmp DWORD PTR [rdi+r8*4], edx sete cl add rax, rcx lea rcx, [r8+1] cmp rsi, rcx je .L2 cmp DWORD PTR [rdi+rcx*4], edx sete cl add r8, 2 movzx ecx, cl add rax, rcx cmp rsi, r8 je .L2 cmp DWORD PTR [rdi+r8*4], edx sete dl movzx edx, dl add rax, rdx .L2: pop rbx ret .L25: test rcx, rcx jne .L3 xor r8d, r8d xor eax, eax jmp .L4 .L19: mov r8d, 4 jmp .L5 .L16: mov r8d, 1 jmp .L5 .L17: mov r8d, 2 jmp .L5 .L18: mov r8d, 3 jmp .L5 .L13: xor eax, eax pop rbx ret .LC0: .long 1 .long 1 .long 1 .long 1Also was der GCC sich dabei denkt muss mir auch mal jemand erklären.
Bei VS gibt's auch Unterschiede:std::uint64_t __declspec(noinline) count1(const std::int32_t* numbers, std::size_t size, std::int32_t number_to_count) { 002312A0 push ebp 002312A1 mov ebp,esp 002312A3 sub esp,0Ch 002312A6 push esi 002312A7 push edi 002312A8 mov edi,edx 002312AA xorps xmm0,xmm0 std::uint64_t counter = 0; 002312AD movlpd qword ptr [counter],xmm0 for (std::size_t i = 0; i != size; ++i) 002312B2 xor esi,esi 002312B4 mov edx,dword ptr [ebp-8] 002312B7 mov eax,dword ptr [counter] 002312BA test edi,edi 002312BC je count1+31h (02312D1h) 002312BE mov edi,edi { if (numbers[i] == number_to_count) 002312C0 cmp dword ptr [ecx+esi*4],2Ah { if (numbers[i] == number_to_count) 002312C4 jne count1+2Ch (02312CCh) ++counter; 002312C6 add eax,1 002312C9 adc edx,0 for (std::size_t i = 0; i != size; ++i) 002312CC inc esi 002312CD cmp esi,edi 002312CF jne count1+20h (02312C0h) } return counter; } 002312D1 pop edi 002312D2 pop esi 002312D3 mov esp,ebp 002312D5 pop ebp 002312D6 retstd::uint64_t __declspec(noinline) count2(const std::int32_t* numbers, std::size_t size, std::int32_t number_to_count) { 002312E0 push ebp 002312E1 mov ebp,esp 002312E3 sub esp,18h 002312E6 push ebx 002312E7 push esi 002312E8 xorps xmm0,xmm0 002312EB mov dword ptr [ebp-8],edx std::uint64_t counter = 0; for (std::size_t i = 0; i != size; ++i) 002312EE xor eax,eax 002312F0 movlpd qword ptr [counter],xmm0 002312F5 mov ebx,ecx 002312F7 push edi 002312F8 test edx,edx 002312FA je count2+54h (0231334h) 002312FC mov esi,dword ptr [ebp-10h] std::uint64_t counter = 0; for (std::size_t i = 0; i != size; ++i) 002312FF mov edi,dword ptr [counter] { counter += numbers[i] == number_to_count; 00231302 cmp dword ptr [ebx+eax*4],2Ah 00231306 jne count2+31h (0231311h) 00231308 mov ecx,1 0023130D xor edx,edx 0023130F jmp count2+3Fh (023131Fh) 00231311 xorps xmm0,xmm0 00231314 movlpd qword ptr [counter],xmm0 00231319 mov edx,dword ptr [ebp-10h] 0023131C mov ecx,dword ptr [counter] 0023131F add edi,ecx 00231321 adc esi,edx 00231323 inc eax 00231324 cmp eax,dword ptr [ebp-8] 00231327 jne count2+22h (0231302h) } return counter; 00231329 mov eax,edi 0023132B mov edx,esi } 0023132D pop edi 0023132E pop esi 0023132F pop ebx 00231330 mov esp,ebp 00231332 pop ebp 00231333 ret } return counter; 00231334 mov eax,dword ptr [counter] 00231337 mov edx,dword ptr [ebp-10h] } 0023133A pop edi 0023133B pop esi 0023133C pop ebx 0023133D mov esp,ebp 0023133F pop ebp 00231340 retclang 3.3 dagegen generiert bei beiden Funktionen exakt das gleiche: (sorry clang mag keine Intel-Syntax)
.LCPI0_0: .quad 4294967295 # 0xffffffff .quad 4294967295 # 0xffffffff .LCPI0_1: .quad 1 # 0x1 .quad 1 # 0x1 count2(int const*, unsigned long, int): # @count2(int const*, unsigned long, int) xorl %eax, %eax testq %rsi, %rsi je .LBB0_8 movq %rsi, %rcx andq $-4, %rcx je .LBB0_2 movd %edx, %xmm2 movlhps %xmm2, %xmm2 # xmm2 = xmm2[0,0] pxor %xmm0, %xmm0 xorl %eax, %eax movaps .LCPI0_0(%rip), %xmm3 andps %xmm3, %xmm2 movdqa .LCPI0_1(%rip), %xmm4 pxor %xmm1, %xmm1 .LBB0_4: # %vector.body movq 8(%rdi,%rax,4), %xmm5 pshufd $16, %xmm5, %xmm6 # xmm6 = xmm5[0,0,1,0] pand %xmm3, %xmm6 pcmpeqd %xmm2, %xmm6 pshufd $-79, %xmm6, %xmm5 # xmm5 = xmm6[1,0,3,2] movq (%rdi,%rax,4), %xmm7 pand %xmm6, %xmm5 pshufd $16, %xmm7, %xmm6 # xmm6 = xmm7[0,0,1,0] pand %xmm3, %xmm6 pcmpeqd %xmm2, %xmm6 addq $4, %rax pand %xmm4, %xmm5 paddq %xmm5, %xmm1 pshufd $-79, %xmm6, %xmm5 # xmm5 = xmm6[1,0,3,2] pand %xmm6, %xmm5 pand %xmm4, %xmm5 paddq %xmm5, %xmm0 cmpq %rax, %rcx jne .LBB0_4 jmp .LBB0_5 .LBB0_2: xorl %ecx, %ecx pxor %xmm0, %xmm0 pxor %xmm1, %xmm1 .LBB0_5: # %middle.block paddq %xmm0, %xmm1 movdqa %xmm1, %xmm0 punpckhqdq %xmm0, %xmm0 # xmm0 = xmm0[1,1] paddq %xmm1, %xmm0 movd %xmm0, %rax cmpq %rsi, %rcx je .LBB0_8 subq %rcx, %rsi leaq (%rdi,%rcx,4), %r8 .LBB0_7: # %scalar.ph cmpl %edx, (%r8) sete %cl movzbl %cl, %edi addq %rdi, %rax addq $4, %r8 decq %rsi jne .LBB0_7 .LBB0_8: # %._crit_edge ret
-
cooky451 schrieb:
Also was der GCC sich dabei denkt muss mir auch mal jemand erklären.
Er vektorisiert und betrachtet 4 Zahlen gleichzeitig.
-
Oh. Ich muss alles zurücknehmen und bin ziemlich überrascht, dass das dabei herauskommt. Auch deshalb, weil gcc 4.8 mit -O2 noch exakt den gleichen Code für beide Varianten erzeugt (mit -O3 dann auch nicht mehr).
Das ist schon seltsam, dass er für die erste Variante nicht mehr die selbe Struktur erkennt. Scheinbar läuft er irgendwo vorher in einen anderen Optimierungspfad -- ersetzt die Verzweigung durch den lea/cmove-Trick -- und findet von da aus die Vektorisierung nicht mehr. Spannend.
-
Ja, Vektorisierung ist ab -O3 standardmäßig aktiviert.
