Optimierungen von for-Schleifen
-
Hi,
ich schaue mir gerade ein Video an, wo behauptet wird, dass numbers.end() bei jeder Iteration aufgerufen wird. Das Komische ist: numbers ist ein konstanter Vector. Aus welchem Grund sollte der Compiler das Ergebnis von numbers.end() nicht als Kontante optimieren können, wenn die Größe von numbers konstant bleibt?https://www.youtube.com/watch?v=JSjoCisIHcM#t=2524
L. G.,
IBV
-
Das hat mit dem const nichts zu tun, aber prinzipiell sollte ein Compiler das schon optimieren können. Das ist schließlich alles extrem simpler Template-Code, wird geinlinet etc.
-
Ich habe mal den Test gemacht:
#include <iostream> #include <vector> using namespace std; int main(int argc, char **argv) { const vector<int> numbers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) { cout << *it << " "; } return 0; }
#include <iostream> #include <vector> using namespace std; int main(int argc, char **argv) { const vector<int> numbers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for (const auto number : numbers) { cout << number << " "; } return 0; }
g++ -S -std=c++11 -O3 main.cpp -o for_test.asm g++ -S -std=c++11 -O3 main.cpp -o for_test_2.asm diff -w for_test.asm for_test_2.asm
Es gab tatsächlich keinen Unterschied! Da hat der Google-Mitarbeiter (der übrigens zugibt, von Templates nichts zu verstehen), Mist erzählt!
L. G.,
IBV
-
Es gibt aber durchaus einen Unterschied zu folgendem Code, den ich allerdings nicht zu interpretieren vermag. :p
#include <iostream> #include <vector> using namespace std; int main(int argc, char **argv) { vector<int> numbers; numbers.push_back(1); numbers.push_back(2); numbers.push_back(3); numbers.push_back(4); numbers.push_back(5); numbers.push_back(6); numbers.push_back(7); numbers.push_back(8); numbers.push_back(9); numbers.push_back(10); for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) { cout << *it << " "; } return 0; }
-
No comments?
-
Du findest es ja selbst nicht interessant genug, sonst würdest du den Unterschied ja mal nennen.
-
Die Unterschiede sind wirklich gravierend.
C++ 11 Code:.file "main.cpp" .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string " " .section .text.startup,"ax",@progbits .p2align 4,,15 .globl main .type main, @function main: .LFB1578: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 .cfi_lsda 0x3,.LLSDA1578 pushq %r12 .cfi_def_cfa_offset 16 .cfi_offset 12, -16 movl $40, %edi pushq %rbp .cfi_def_cfa_offset 24 .cfi_offset 6, -24 pushq %rbx .cfi_def_cfa_offset 32 .cfi_offset 3, -32 .LEHB0: call _Znwm .LEHE0: movq %rax, %r12 movq ._84(%rip), %rax leaq 40(%r12), %rbp movq %r12, %rbx movq %rax, (%r12) movq ._84+8(%rip), %rax movq %rax, 8(%r12) movq ._84+16(%rip), %rax movq %rax, 16(%r12) movq ._84+24(%rip), %rax movq %rax, 24(%r12) movq ._84+32(%rip), %rax movq %rax, 32(%r12) .p2align 4,,10 .p2align 3 .L2: movl (%rbx), %esi movl $_ZSt4cout, %edi .LEHB1: call _ZNSolsEi movq %rax, %rdi movl $1, %edx movl $.LC0, %esi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l .LEHE1: addq $4, %rbx cmpq %rbp, %rbx jne .L2 testq %r12, %r12 je .L12 movq %r12, %rdi call _ZdlPv .L12: popq %rbx .cfi_remember_state .cfi_def_cfa_offset 24 popq %rbp .cfi_def_cfa_offset 16 xorl %eax, %eax popq %r12 .cfi_def_cfa_offset 8 ret .L8: .cfi_restore_state testq %r12, %r12 movq %rax, %rbx je .L7 movq %r12, %rdi call _ZdlPv .L7: movq %rbx, %rdi .LEHB2: call _Unwind_Resume .LEHE2: .cfi_endproc .LFE1578: .globl __gxx_personality_v0 .section .gcc_except_table,"a",@progbits .LLSDA1578: .byte 0xff .byte 0xff .byte 0x1 .uleb128 .LLSDACSE1578-.LLSDACSB1578 .LLSDACSB1578: .uleb128 .LEHB0-.LFB1578 .uleb128 .LEHE0-.LEHB0 .uleb128 0 .uleb128 0 .uleb128 .LEHB1-.LFB1578 .uleb128 .LEHE1-.LEHB1 .uleb128 .L8-.LFB1578 .uleb128 0 .uleb128 .LEHB2-.LFB1578 .uleb128 .LEHE2-.LEHB2 .uleb128 0 .uleb128 0 .LLSDACSE1578: .section .text.startup .size main, .-main .p2align 4,,15 .type _GLOBAL__sub_I_main, @function _GLOBAL__sub_I_main: .LFB1807: .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 addq $8, %rsp .cfi_def_cfa_offset 8 jmp __cxa_atexit .cfi_endproc .LFE1807: .size _GLOBAL__sub_I_main, .-_GLOBAL__sub_I_main .section .init_array,"aw" .align 8 .quad _GLOBAL__sub_I_main .section .rodata .align 32 .type ._84, @object .size ._84, 40 ._84: .long 1 .long 2 .long 3 .long 4 .long 5 .long 6 .long 7 .long 8 .long 9 .long 10 .local _ZStL8__ioinit .comm _ZStL8__ioinit,1,1 .hidden __dso_handle .ident "GCC: (SUSE Linux) 4.8.3 20140627 [gcc-4_8-branch revision 212064]" .section .note.GNU-stack,"",@progbits
C++ 98 Code:
EDIT: Der Code wurde ohne "-std=c++11" kompiliert!.file "main.cpp" .section .text._ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi,"axG",@progbits,_ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi,comdat .align 2 .p2align 4,,15 .weak _ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi .type _ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi, @function _ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi: .LFB1268: .cfi_startproc pushq %r14 .cfi_def_cfa_offset 16 .cfi_offset 14, -16 pushq %r13 .cfi_def_cfa_offset 24 .cfi_offset 13, -24 pushq %r12 .cfi_def_cfa_offset 32 .cfi_offset 12, -32 pushq %rbp .cfi_def_cfa_offset 40 .cfi_offset 6, -40 movq %rsi, %rbp pushq %rbx .cfi_def_cfa_offset 48 .cfi_offset 3, -48 movq %rdi, %rbx subq $16, %rsp .cfi_def_cfa_offset 64 movq 8(%rdi), %rax cmpq 16(%rdi), %rax je .L2 testq %rax, %rax je .L3 movl -4(%rax), %ecx movl %ecx, (%rax) .L3: leaq 4(%rax), %rcx movq %rcx, 8(%rbx) movl (%rdx), %ebx leaq -4(%rax), %rdx subq %rbp, %rdx sarq $2, %rdx testq %rdx, %rdx je .L4 salq $2, %rdx movq %rbp, %rsi subq %rdx, %rax movq %rax, %rdi call memmove .L4: movl %ebx, 0(%rbp) .L1: addq $16, %rsp .cfi_remember_state .cfi_def_cfa_offset 48 popq %rbx .cfi_def_cfa_offset 40 popq %rbp .cfi_def_cfa_offset 32 popq %r12 .cfi_def_cfa_offset 24 popq %r13 .cfi_def_cfa_offset 16 popq %r14 .cfi_def_cfa_offset 8 ret .p2align 4,,10 .p2align 3 .L2: .cfi_restore_state movq (%rdi), %rcx subq %rcx, %rax sarq $2, %rax testq %rax, %rax je .L6 leaq (%rax,%rax), %rsi cmpq %rsi, %rax jbe .L32 .L7: movq %rbp, %r12 movq $-4, %r13 subq %rcx, %r12 sarq $2, %r12 .L14: movq %r13, %rdi movq %rdx, 8(%rsp) call _Znwm movq (%rbx), %rsi movq %rbp, %rdi movq 8(%rsp), %rdx movq %rax, %r14 subq %rsi, %rdi sarq $2, %rdi movq %rdi, %r8 .L8: leaq (%r14,%r12,4), %rax testq %rax, %rax je .L9 movl (%rdx), %edx movl %edx, (%rax) .L9: testq %rdi, %rdi leaq 0(,%r8,4), %r12 je .L11 movq %r12, %rdx movq %r14, %rdi call memmove .L11: movq 8(%rbx), %rcx leaq 4(%r14,%r12), %r8 xorl %r12d, %r12d subq %rbp, %rcx sarq $2, %rcx testq %rcx, %rcx je .L12 leaq 0(,%rcx,4), %r12 movq %r8, %rdi movq %rbp, %rsi movq %r12, %rdx call memmove movq %rax, %r8 .L12: movq (%rbx), %rdi addq %r8, %r12 testq %rdi, %rdi je .L13 call _ZdlPv .L13: addq %r14, %r13 movq %r14, (%rbx) movq %r12, 8(%rbx) movq %r13, 16(%rbx) jmp .L1 .p2align 4,,10 .p2align 3 .L6: movq %rsi, %r12 movl $4, %r13d subq %rcx, %r12 sarq $2, %r12 jmp .L14 .L32: movabsq $4611686018427387903, %rdi cmpq %rdi, %rsi ja .L7 movq %rbp, %r12 leaq 0(,%rax,8), %r13 subq %rcx, %r12 sarq $2, %r12 testq %rsi, %rsi jne .L14 movq %r12, %r8 movq %r12, %rdi movq %rcx, %rsi xorl %r14d, %r14d jmp .L8 .cfi_endproc .LFE1268: .size _ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi, .-_ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi .section .text._ZNSt6vectorIiSaIiEE9push_backERKi,"axG",@progbits,_ZNSt6vectorIiSaIiEE9push_backERKi,comdat .align 2 .p2align 4,,15 .weak _ZNSt6vectorIiSaIiEE9push_backERKi .type _ZNSt6vectorIiSaIiEE9push_backERKi, @function _ZNSt6vectorIiSaIiEE9push_backERKi: .LFB1244: .cfi_startproc movq 8(%rdi), %rax cmpq 16(%rdi), %rax je .L34 testq %rax, %rax je .L35 movl (%rsi), %edx movl %edx, (%rax) .L35: addq $4, %rax movq %rax, 8(%rdi) ret .p2align 4,,10 .p2align 3 .L34: subq $8, %rsp .cfi_def_cfa_offset 16 movq %rsi, %rdx movq %rax, %rsi call _ZNSt6vectorIiSaIiEE13_M_insert_auxEN9__gnu_cxx17__normal_iteratorIPiS1_EERKi addq $8, %rsp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1244: .size _ZNSt6vectorIiSaIiEE9push_backERKi, .-_ZNSt6vectorIiSaIiEE9push_backERKi .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string " " .section .text.startup,"ax",@progbits .p2align 4,,15 .globl main .type main, @function main: .LFB1236: .cfi_startproc .cfi_personality 0x3,__gxx_personality_v0 .cfi_lsda 0x3,.LLSDA1236 pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 subq $48, %rsp .cfi_def_cfa_offset 64 leaq 16(%rsp), %rdi movq %rsp, %rsi movq $0, 16(%rsp) movq $0, 24(%rsp) movq $0, 32(%rsp) movl $1, (%rsp) .LEHB0: call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $2, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $3, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $4, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $5, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $6, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $7, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $8, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $9, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi leaq 16(%rsp), %rdi movq %rsp, %rsi movl $10, (%rsp) call _ZNSt6vectorIiSaIiEE9push_backERKi movq 16(%rsp), %rbx cmpq 24(%rsp), %rbx je .L45 .p2align 4,,10 .p2align 3 .L52: movl (%rbx), %esi movl $_ZSt4cout, %edi call _ZNSolsEi movl $1, %edx movl $.LC0, %esi movq %rax, %rdi call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l .LEHE0: addq $4, %rbx cmpq 24(%rsp), %rbx jne .L52 .L45: movq 16(%rsp), %rdi testq %rdi, %rdi je .L54 call _ZdlPv .L54: addq $48, %rsp .cfi_remember_state .cfi_def_cfa_offset 16 xorl %eax, %eax popq %rbx .cfi_def_cfa_offset 8 ret .L49: .cfi_restore_state movq 16(%rsp), %rdi movq %rax, %rbx testq %rdi, %rdi je .L48 call _ZdlPv .L48: movq %rbx, %rdi .LEHB1: call _Unwind_Resume .LEHE1: .cfi_endproc .LFE1236: .globl __gxx_personality_v0 .section .gcc_except_table,"a",@progbits .LLSDA1236: .byte 0xff .byte 0xff .byte 0x1 .uleb128 .LLSDACSE1236-.LLSDACSB1236 .LLSDACSB1236: .uleb128 .LEHB0-.LFB1236 .uleb128 .LEHE0-.LEHB0 .uleb128 .L49-.LFB1236 .uleb128 0 .uleb128 .LEHB1-.LFB1236 .uleb128 .LEHE1-.LEHB1 .uleb128 0 .uleb128 0 .LLSDACSE1236: .section .text.startup .size main, .-main .p2align 4,,15 .type _GLOBAL__sub_I_main, @function _GLOBAL__sub_I_main: .LFB1326: .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 addq $8, %rsp .cfi_def_cfa_offset 8 jmp __cxa_atexit .cfi_endproc .LFE1326: .size _GLOBAL__sub_I_main, .-_GLOBAL__sub_I_main .section .init_array,"aw" .align 8 .quad _GLOBAL__sub_I_main .local _ZStL8__ioinit .comm _ZStL8__ioinit,1,1 .hidden __dso_handle .ident "GCC: (SUSE Linux) 4.8.3 20140627 [gcc-4_8-branch revision 212064]" .section .note.GNU-stack,"",@progbits
L. G.,
IBV
-
IBV schrieb:
Es gab tatsächlich keinen Unterschied! Da hat der Google-Mitarbeiter (der übrigens zugibt, von Templates nichts zu verstehen), Mist erzählt!
Nein, der Google-Mitarbeiter hat keinen Mist erzählt. Nur du hast Mist gemessen.
Der Aufruf von
vector::end
kann nicht grundsätzlich wegoptimiert werden. D.h. es gibt viele Fälle wo der Optimizer es nicht aus der Schleife rausziehen kann.
Das heisst aber nicht dass es nicht in bestimmten Fällen trotzdem geht.Grund:
const
heisst in C++ nicht dass sich keine Membervariablen ändern dürfen. In C++ 03 heisst const genaugenommen überhaupt nicht viel, und in C++ 11 nur dass alle Änderungen die in einem const Objekt bzw. über eine const Referenz erfolgen intern synchronisiert sein müssen (also Thread-safe). Lies einfach mal nach was das Keywordmutable
bedeutet/bewirkt.Beispiel:
int main() { const Foo foo; SomeFunction(foo); for (size_t i = 0; i < foo.GetSomething(); i++) std::cout << foo.GetSomeOtherThing() << ComputeSomeValue(foo); }
Damit der Optimizer den Aufruf von
foo.GetSomething()
aus der Schleife rausziehen kann, müsste er sehen können, dass hier bestimmte Dinge nicht passieren.Und bestimmte Dinge beinhaltet (unter anderem):
-
SomeFunction
könnte die Adresse vonfoo
irgendwo ablegen (z.B. globale Variable), und der (evtl. vom Programm überschriebene)operator new
könnte dann auffoo
zugreifen, und Foo-Funktionen aufrufen diemutable
Variablen vonfoo
verändern. Was wiederrum das Ergebnis vonGetSomething()
verändern könnte. Wobeioperator new
jetzt nur ein Beispiel ist von Funktionen die vonstd::cout <<
irgendwo indirekt aufgerufen werden könnten. -
foo.GetSomeOtherThing()
könnte mutable Member vonfoo
verändern, oder wiederrum die Adresse vonfoo
irgendwo ablegen. -
ComputeSomeValue(foo)
könnte mutable Member vonfoo
verändern oder die Adresse vonfoo
irgendwo ablegen. -
foo.GetSomething()
könnte beobachtbare Nebeneffekte haben.
uswusf.
Heisst: damit der Optimizer überhaupt eine Chance hat das rauszuziehen muss er zumindest die Definition von sämtlchenen Funktionen einsehen können die die Adresse von
foo
übergeben bekommen.
Das ist oft nicht der Fall, und daher kann der Compiler es oft nicht optimieren.
Und da man sich - wenn es wirklich auf Performance ankommt - normalerweise nicht darauf verlassen will dass er es in diesem speziellen Fall doch schafft, macht man es (EDIT: dort, wo es wirklich auf Performance ankommt) am besten selbst.
-
-
IBV, was soll das denn jetzt? Welche Programme genau hast du verglichen. Dass ein list-initializer möglicherweise anderen Code liefert als eine Reihe von push_back ist doch irgendwie klar, oder nicht? Und warum mit unterschiedlichen Compileroptionen? Und was hat das mit Optimierungen zu tun? Bevor ich jetzt anfange herumzuraten und die geposteten Codes zu diffen, mach erstmal deine Hausaufgaben.
-
10 einzelne Funktionsaufrufe sind eben nicht zu einem großen optimierbar. push_back ist letztendlich nicht trivial. Der Compiler kann ja beispielsweise nicht wissen, ob eines der push_backs nicht zur Laufzeit mit einer Exception aussteigen würde. Welches genau, könnte das Programmverhalten ändern. Angenommen der Rechner hätte genau 11*sizeof(int) Byte auf dem Heap am Stück frei. Der C++11-Konstruktor würde da genau 10 Plätze belegen und das Programm liefe durch. Ein push_back mit einer typischen Strategie, immer um einen gewissen Faktor den reservierten Bereich zu vergrößern, könnte da in Schwierigkeiten kommen und das Programm mit einer Exception abbrechen.
-
Meine Fragen wurde soweit beantwortet, danke!
L. G.,
IBV