Warum wird der Code nicht optimiert?
-
Opti schrieb:
CodeA braucht 11540ms.
CodeB braucht 7090ms.Mit -O3 bekomme ich ein ähnliches Ergebnis (CodeA ein ganz klein wenig langsamer bis gleich schnell).
Mit -O2 bekomme ich dasselbe.
Mit -O1 bekomme ich raus, dass CodeA schneller ist.Müsste CodeB nicht langsamer sein, wegen den vielen length() Aufrufen?
Nö, wird eh geinlined. Hängt aber auch von der Implementierung ab -
std::stringkönnte auch zwei Zeiger speichern...
-
Zwei Zeiger auf was?
-
Auf Stringanfang und -ende.
-
Ok danke,
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht,
was soll das bringen, bzw. warum sollte das schneller als eine Addition mit __int64 sein?
-
Also das ist mal der Assembler den mir GCC 4.9 generiert.
.file "TEMP2.cxx" .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "Hello World!" .LC1: .string "sum: " .text .globl _Z3foov .type _Z3foov, @function _Z3foov: .LFB1219: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 .cfi_lsda 0x3,.LLSDA1219 pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 subq $32, %rsp .cfi_def_cfa_offset 48 leaq 29(%rsp), %rdx movl $.LC0, %esi leaq 16(%rsp), %rdi .LEHB0: call _ZNSsC1EPKcRKSaIcE .LEHE0: movq 16(%rsp), %rax movl -24(%rax), %edx movl $1000000000, %esi movl $0, %ebx movslq %edx, %rcx jmp .L2 .L6: addq %rcx, %rbx addl $1, %eax cmpl %eax, %edx jg .L6 .L5: subl $1, %esi je .L4 .L2: testl %edx, %edx jle .L5 movl $0, %eax jmp .L6 .L4: movl $5, %edx movl $.LC1, %esi movl $_ZSt4cout, %edi .LEHB1: call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l movq %rbx, %rsi movl $_ZSt4cout, %edi call _ZNSo9_M_insertImEERSoT_ movb $10, 15(%rsp) movl $1, %edx leaq 15(%rsp), %rsi movq %rax, %rdi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l .LEHE1: movq 16(%rsp), %rax leaq -24(%rax), %rdi cmpq $_ZNSs4_Rep20_S_empty_rep_storageE, %rdi je .L1 leaq -8(%rax), %rdx movl $_ZL28__gthrw___pthread_key_createPjPFvPvE, %ecx testq %rcx, %rcx je .L8 movl $-1, %eax lock xaddl %eax, (%rdx) jmp .L9 .L8: movl -8(%rax), %edx leal -1(%rdx), %ecx movl %ecx, -8(%rax) movl %edx, %eax .L9: testl %eax, %eax jg .L1 leaq 30(%rsp), %rsi call _ZNSs4_Rep10_M_destroyERKSaIcE jmp .L1 .L11: movq %rax, %rbx movq 16(%rsp), %rax leaq -24(%rax), %rdi leaq 31(%rsp), %rsi call _ZNSs4_Rep10_M_disposeERKSaIcE movq %rbx, %rdi .LEHB2: call _Unwind_Resume .LEHE2: .L1: addq $32, %rsp .cfi_def_cfa_offset 16 popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1219: .globl __gxx_personality_v0 .section .gcc_except_table,"a",@progbits .LLSDA1219: .byte 0xff .byte 0xff .byte 0x1 .uleb128 .LLSDACSE1219-.LLSDACSB1219 .LLSDACSB1219: .uleb128 .LEHB0-.LFB1219 .uleb128 .LEHE0-.LEHB0 .uleb128 0 .uleb128 0 .uleb128 .LEHB1-.LFB1219 .uleb128 .LEHE1-.LEHB1 .uleb128 .L11-.LFB1219 .uleb128 0 .uleb128 .LEHB2-.LFB1219 .uleb128 .LEHE2-.LEHB2 .uleb128 0 .uleb128 0 .LLSDACSE1219: .text .size _Z3foov, .-_Z3foov .globl _Z4foo2v .type _Z4foo2v, @function _Z4foo2v: .LFB1220: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 .cfi_lsda 0x3,.LLSDA1220 pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 subq $32, %rsp .cfi_def_cfa_offset 48 leaq 29(%rsp), %rdx movl $.LC0, %esi leaq 16(%rsp), %rdi .LEHB3: call _ZNSsC1EPKcRKSaIcE .LEHE3: movq 16(%rsp), %rax movq -24(%rax), %rdx movl $1000000000, %esi movl $0, %ebx jmp .L14 .L18: addq %rdx, %rbx addl $1, %eax movslq %eax, %rcx cmpq %rdx, %rcx jb .L18 .L17: subl $1, %esi je .L16 .L14: testq %rdx, %rdx je .L17 movl $0, %eax jmp .L18 .L16: movl $5, %edx movl $.LC1, %esi movl $_ZSt4cout, %edi .LEHB4: call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l movq %rbx, %rsi movl $_ZSt4cout, %edi call _ZNSo9_M_insertImEERSoT_ movb $10, 15(%rsp) movl $1, %edx leaq 15(%rsp), %rsi movq %rax, %rdi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l .LEHE4: movq 16(%rsp), %rax leaq -24(%rax), %rdi cmpq $_ZNSs4_Rep20_S_empty_rep_storageE, %rdi je .L13 leaq -8(%rax), %rdx movl $_ZL28__gthrw___pthread_key_createPjPFvPvE, %ecx testq %rcx, %rcx je .L20 movl $-1, %eax lock xaddl %eax, (%rdx) jmp .L21 .L20: movl -8(%rax), %edx leal -1(%rdx), %ecx movl %ecx, -8(%rax) movl %edx, %eax .L21: testl %eax, %eax jg .L13 leaq 30(%rsp), %rsi call _ZNSs4_Rep10_M_destroyERKSaIcE jmp .L13 .L23: movq %rax, %rbx movq 16(%rsp), %rax leaq -24(%rax), %rdi leaq 31(%rsp), %rsi call _ZNSs4_Rep10_M_disposeERKSaIcE movq %rbx, %rdi .LEHB5: call _Unwind_Resume .LEHE5: .L13: addq $32, %rsp .cfi_def_cfa_offset 16 popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1220: .section .gcc_except_table .LLSDA1220: .byte 0xff .byte 0xff .byte 0x1 .uleb128 .LLSDACSE1220-.LLSDACSB1220 .LLSDACSB1220: .uleb128 .LEHB3-.LFB1220 .uleb128 .LEHE3-.LEHB3 .uleb128 0 .uleb128 0 .uleb128 .LEHB4-.LFB1220 .uleb128 .LEHE4-.LEHB4 .uleb128 .L23-.LFB1220 .uleb128 0 .uleb128 .LEHB5-.LFB1220 .uleb128 .LEHE5-.LEHB5 .uleb128 0 .uleb128 0 .LLSDACSE1220: .text .size _Z4foo2v, .-_Z4foo2v .globl main .type main, @function main: .LFB1223: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 subq $16, %rsp .cfi_def_cfa_offset 32 call clock movq %rax, %rbx call _Z3foov call clock subq %rbx, %rax movq %rax, %rsi movl $_ZSt4cout, %edi call _ZNSo9_M_insertIlEERSoT_ movb $10, 14(%rsp) movl $1, %edx leaq 14(%rsp), %rsi movq %rax, %rdi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l call clock movq %rax, %rbx call _Z4foo2v call clock subq %rbx, %rax movq %rax, %rsi movl $_ZSt4cout, %edi call _ZNSo9_M_insertIlEERSoT_ movb $10, 15(%rsp) movl $1, %edx leaq 15(%rsp), %rsi movq %rax, %rdi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l movl $0, %eax addq $16, %rsp .cfi_def_cfa_offset 16 popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1223: .size main, .-main .type _GLOBAL__sub_I__Z3foov, @function _GLOBAL__sub_I__Z3foov: .LFB1377: .cfi_startproc subq $8, %rsp .cfi_def_cfa_offset 16 movl $_ZStL8__ioinit, %edi call _ZNSt8ios_base4InitC1Ev movl $__dso_handle, %edx movl $_ZStL8__ioinit, %esi movl $_ZNSt8ios_base4InitD1Ev, %edi call __cxa_atexit addq $8, %rsp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1377: .size _GLOBAL__sub_I__Z3foov, .-_GLOBAL__sub_I__Z3foov .section .init_array,"aw" .align 8 .quad _GLOBAL__sub_I__Z3foov .local _ZStL8__ioinit .comm _ZStL8__ioinit,1,1 .weakref _ZL28__gthrw___pthread_key_createPjPFvPvE,__pthread_key_create .hidden __dso_handle .ident "GCC: (GNU) 4.9.0 20130414 (experimental)" .section .note.GNU-stack,"",@progbits
-
CodeA oder CodeB?
-
Opti schrieb:
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht
Da hat dich Sone auch verarscht. Es sind in Wirklichkeit 3 Zeiger (Start, Stringende, Memoryblockende).
Warum 3 Zeiger und nicht 2+Länge? Ja weil der übliche Weg einen String durchzuiterieren Iteratoren sind
for(string::iterator it=s.begin(), end=send(); it!=end; ++it)
-
scherzkeks schrieb:
Opti schrieb:
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht
Da hat dich Sone auch verarscht. Es sind in Wirklichkeit 3 Zeiger (Start, Stringende, Memoryblockende).
Der dritte spielt hier keine Rolle.
-
Opti schrieb:
CodeA oder CodeB?
Ich hab mal ganz direkt den hier genommen, obwohl ich natürlich einen hundert mal einfacheren nehmen sollte:
#include <iostream> #include <ctime> void foo() { std::string s = "Hello World!"; int length = s.length(); uint64_t sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < length; ++j) { sum += length; } } std::cout << "sum: " << sum << '\n'; /// Die Ausgaben sind da, damit sum nicht wegoptimiert wird (volatile funktioniert nicht - as-if) } void foo2() { std::string s = "Hello World!"; uint64_t sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < s.length(); ++j) { sum += s.length(); } } std::cout << "sum: " << sum << '\n'; } class stop_watch { clock_t first; public: void start() { first = clock(); } clock_t elapsed() const { return clock() - first; } }; int main() { stop_watch sw; sw.start(); foo(); std::cout << sw.elapsed() << '\n'; sw.start(); foo2(); std::cout << sw.elapsed() << '\n'; }
-
Opti schrieb:
Ok danke,
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht,
was soll das bringen, bzw. warum sollte das schneller als eine Addition mit __int64 sein?Schneller nicht. Aber es muss dann im jeden Schritt, um die Länge zu bestimmen, eine Subtraktion durchgeführt werden - durchaus kritisch.
-
Sone schrieb:
Opti schrieb:
Ok danke,
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht,
was soll das bringen, bzw. warum sollte das schneller als eine Addition mit __int64 sein?Schneller nicht. Aber es muss dann im jeden Schritt, um die Länge zu bestimmen, eine Subtraktion durchgeführt werden - durchaus kritisch.
Wobei das Ergebnis immer gleich bleibt und der Optimierer die Subtraktion aus der Schleife herausziehen könnte.
-
http://gcc.godbolt.org/
Lass ich mal hier.#include <string> using namespace std; void foo() { string s = "Hello World!"; int length = s.length(); unsigned long long sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < length; ++j) { sum += length; } } }.LC0: .string "Hello World!" foo(): subq $40, %rsp movl $.LC0, %esi leaq 16(%rsp), %rdi leaq 15(%rsp), %rdx call std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) movq 16(%rsp), %rax leaq -24(%rax), %rdi cmpq std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_S_empty_rep_storage, %rdi jne .L9 .L1: addq $40, %rsp ret .L9: leaq 16(%rdi), %rcx movl __gthrw_pthread_cancel(unsigned long), %edx testq %rdx, %rdx je .L4 orl $-1, %edx lock xaddl %edx, (%rcx) .L5: testl %edx, %edx jg .L1 leaq 15(%rsp), %rsi call std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_M_destroy(std::allocator<char> const&) jmp .L1 .L4: movl -8(%rax), %edx leal -1(%rdx), %ecx movl %ecx, -8(%rax) jmp .L5#include <string> using namespace std; void foo() { string s = "Hello World!"; int length = s.length(); unsigned long long sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < s.length(); ++j) { sum += s.length(); } } }.LC0: .string "Hello World!" foo(): subq $40, %rsp movl $.LC0, %esi leaq 15(%rsp), %rdx leaq 16(%rsp), %rdi call std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) movq 16(%rsp), %rdx leaq -24(%rdx), %rdi cmpq std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_S_empty_rep_storage, %rdi jne .L9 .L1: addq $40, %rsp ret .L9: leaq 16(%rdi), %rcx movl __gthrw_pthread_cancel(unsigned long), %eax testq %rax, %rax je .L4 movl $-1, %eax lock xaddl %eax, (%rcx) .L5: testl %eax, %eax jg .L1 leaq 15(%rsp), %rsi call std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_M_destroy(std::allocator<char> const&) addq $40, %rsp ret .L4: movl -8(%rdx), %eax leal -1(%rax), %ecx movl %ecx, -8(%rdx) jmp .L5
-
von mir noch der Hinweis: std::string ist von Compiler zu Compiler sehr unterschiedlich implementiert, demzufolge wird auch CodeA und CodeB unterschiedlich optimiert
der GCC std::string enthält nur einen Pointer, alle anderen Daten sind in dem Speicherbereich, auf den der Pointer vereist. der MSVC std::string enthält einen 16 Byte Buffer für kleine Strings
-
Aber wie kann es sein, dass string::length() schneller ist als eine einfache Addition?
-
Opti schrieb:
Aber wie kann es sein, dass string::length() schneller ist als eine einfache Addition?
-O3 nennt man auch den Götterhammer.
Der macht alles, was Du trivialerweise auch per Hand könntest. Und noch viele Tricks, die Du noch gar nicht kennst.
-
Opti schrieb:
Wieso ist CodeA langsamer als CodeB?
CodeA:
string s = "Hello World!"; int length = s.length(); unsigned __int64 sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < length; ++j) { sum += length; } }CodeB:
string s = "Hello World!"; unsigned __int64 sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < s.length(); ++j) { sum += s.length(); } }CodeA braucht 11540ms.
CodeB braucht 7090ms.Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.
-
also schrieb:
Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.
Meinst du, der Compiler erkennt, dass sum = s.length()^2 * 10^9 ist und die Schleifen weg lässt?
-
also schrieb:
Opti schrieb:
Wieso ist CodeA langsamer als CodeB?
CodeA:
string s = "Hello World!"; int length = s.length(); unsigned __int64 sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < length; ++j) { sum += length; } }CodeB:
string s = "Hello World!"; unsigned __int64 sum = 0; for(int i = 0; i < 1000000000; ++i) { for(int j = 0; j < s.length(); ++j) { sum += s.length(); } }CodeA braucht 11540ms.
CodeB braucht 7090ms.Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.
Genau. Habe den Code gerade nicht probiert. Aber habe die GCC mit -O3 schon oft erlebt, wie sie verschachtelte Summierschleifen erkannt hat und zu einer simplen Multiplikation aufgelöst hat. Einfach frech. Superfrech.
Kommt wohl auch ein wenig daher, daß jeder Hans und Kunz dran rumpopeln darf (uns soll!). Wenn ein H&K am eigenen Code sieht, daß da eine Optimierung vom Compiler übernommen werden könnte, fummelt er sie halt rein.
Derzeit macht GCC schnelleren Code als MS. So viele Ideen kann man nicht einkaufen.Aber MSVC6.1 war härter drauf. Ein Messprogramm, das mit new[] Speicher besorgt hat und nur den Speicher in komplextester Weise beschrieben, gelesen, verrechnet hat, und danach ihn mit delete[] sauber gelöscht hat, aber keine Ausgabe hatte, wurde zu 0ms optimiert. Soweit ich mich erinnere, sind aktuelle Compiler nicht mehr so frech.
-
Aber ein guter Compiler kann das:
// Ursprungscode (platzsparend formatiert) string s = "Hello World!"; unsigned __int64 sum = 0; for(int i = 0; i < 1000000000; ++i) for(int j = 0; j < s.length(); ++j) sum += s.length(); // loop interchange for(int j = 0; j < s.length(); ++j) for(int i = 0; i < 1000000000; ++i) sum += s.length(); // Die 1000000000 Additionen in eine Multiplikation for(int j = 0; j < s.length(); ++j) sum += s.length()*1000000000; // Die s.length() Additionen in eine Multiplikation unsigned __int64 sum = 0; sum += s.length()*s.length()*1000000000; // =0 ist unnötig string s = "Hello World!"; unsigned __int64 sum = s.length()*s.length()*1000000000;
-
Letzter Schritt:
// unsigned __int64 sum wird nicht gebraucht; einfach weglassen string s = "Hello World!";