loop unrolling mit variadic Templates möglich?
-
das Template mit der Index Liste finde ich interessant,
werde aber einige Zeit brauchen um das zu verstehen.
Danke!Boost.PP ist boost Preprocessor?
bezügleich das der Compiler loops selst aufrollt und optimiert
Bsp: data und data1 ist ein array und sagen wir size = 4
for (int i=0; i<data.size(); i++)
{
sum += data[i] + data1[i];
}der Compiler macht automatisch so oder so ähnlich/besser?
int sum1 = data[0] + data1[0];
int sum2 = data[1] + data1[1];
int sum3 = data[2] + data1[2];
int sum4 = data[3] + data1[3];
int sum = sum1 + sum2 + sum3 + sum4;kann man sich darauf verlassen?
-
kann man sich darauf verlassen?
Nein.
-
knivil schrieb:
kann man sich darauf verlassen?
Nein.
dachte ich mir,
desswegen dachte ich mir das mir vielleicht ein Template helfen könnte.
aber oben wurde geschrieben das es nicht besser sondern eher vielleicht schlechter wird.
dh ich werde wohl, das array Bsp hernehmend, jede Array grösse extra implementieren müssen oder mit einer loop leben müssen die u.U. nicht optimal implementiert ist.
-
kurze_frage schrieb:
der Compiler macht automatisch so oder so ähnlich/besser?
int sum1 = data[0] + data1[0];
int sum2 = data[1] + data1[1];
int sum3 = data[2] + data1[2];
int sum4 = data[3] + data1[3];
int sum = sum1 + sum2 + sum3 + sum4;Wenn man ihm die entsprechenden Optimierungsoptionen mitgibt.
Beispiel
constexpr int size = 1000; int data[size]; int data1[size]; int foo() { int sum = 0; for (int i=0; i<size; i++) { sum += data[i] + data1[i]; } return sum; } #include <iostream> #include <ctime> int main() { std::srand(std::time(0)); for (int i=0; i<size; i++) { data[i] = rand(); data1[i] = rand(); } std::cout << foo() << '\n'; }gcc-4.8.1 mit -O2 (nur der interessante Teil der Schleife)
.L3: addl (%rsi,%rdx), %eax addl (%rcx,%rdx), %eax addq $4, %rdx cmpq $4000, %rdx jne .L3kein Unrolling, keine Vektorisierung
zusätzlich -ftree-vectorize (durch -O3 impliziert).L3: paddd (%rcx,%rax), %xmm0 paddd (%rdx,%rax), %xmm0 addq $16, %rax cmpq $4000, %rax jne .L3zusätzlich -funroll-loops
.L3: paddd (%rcx,%rax), %xmm0 paddd (%rdx,%rax), %xmm0 paddd 16(%rcx,%rax), %xmm0 paddd 16(%rdx,%rax), %xmm0 paddd 32(%rcx,%rax), %xmm0 paddd 32(%rdx,%rax), %xmm0 paddd 48(%rcx,%rax), %xmm0 paddd 48(%rdx,%rax), %xmm0 paddd 64(%rcx,%rax), %xmm0 paddd 64(%rdx,%rax), %xmm0 paddd 80(%rcx,%rax), %xmm0 paddd 80(%rdx,%rax), %xmm0 paddd 96(%rcx,%rax), %xmm0 paddd 96(%rdx,%rax), %xmm0 paddd 112(%rcx,%rax), %xmm0 paddd 112(%rdx,%rax), %xmm0 paddd 128(%rcx,%rax), %xmm0 paddd 128(%rdx,%rax), %xmm0 paddd 144(%rcx,%rax), %xmm0 paddd 144(%rdx,%rax), %xmm0 addq $160, %rax cmpq $4000, %rax jne .L3zusätzlich -march=corei7-avx
.L3: vpaddd (%rcx,%rax), %xmm3, %xmm0 vpaddd (%rdx,%rax), %xmm0, %xmm1 vpaddd 16(%rcx,%rax), %xmm1, %xmm2 vpaddd 16(%rdx,%rax), %xmm2, %xmm3 vpaddd 32(%rcx,%rax), %xmm3, %xmm4 vpaddd 32(%rdx,%rax), %xmm4, %xmm5 vpaddd 48(%rcx,%rax), %xmm5, %xmm6 vpaddd 48(%rdx,%rax), %xmm6, %xmm7 vpaddd 64(%rcx,%rax), %xmm7, %xmm8 vpaddd 64(%rdx,%rax), %xmm8, %xmm9 vpaddd 80(%rcx,%rax), %xmm9, %xmm10 vpaddd 80(%rdx,%rax), %xmm10, %xmm11 vpaddd 96(%rcx,%rax), %xmm11, %xmm12 vpaddd 96(%rdx,%rax), %xmm12, %xmm13 vpaddd 112(%rcx,%rax), %xmm13, %xmm14 vpaddd 112(%rdx,%rax), %xmm14, %xmm15 vpaddd 128(%rcx,%rax), %xmm15, %xmm0 vpaddd 128(%rdx,%rax), %xmm0, %xmm1 vpaddd 144(%rcx,%rax), %xmm1, %xmm2 vpaddd 144(%rdx,%rax), %xmm2, %xmm3 addq $160, %rax cmpq $4000, %rax jne .L3Dieses einfache Beispiel ist für den Compiler kein Problem.
-
Wobei ich jetzt mal die Geschwindigkeit des funroll-loops mit dem O3 vergleichen würde. Es ist nämlich nicht immer die beste Idee, alle Schleifen abzurollen.
-
Mit
#include <cstddef> // C++14 (N3658) //////////////// template<class T, T... I> struct integer_sequence { using value_type = T; static constexpr size_t size() noexcept { return sizeof...(I); } }; template<size_t... I> using index_sequence = integer_sequence<size_t, I...>; template <typename T, std::size_t N, typename = integer_sequence<T>> struct make_integer_sequence_; template <typename T, std::size_t N, T... I> struct make_integer_sequence_<T, N, integer_sequence<T, I...>> { using type = typename make_integer_sequence_<T, N-1, integer_sequence<T, 0, 1+I...>>::type; }; template <typename T, T... I> struct make_integer_sequence_<T, 0, integer_sequence<T, I...>> { using type = integer_sequence<T, I...>; }; template<class T, T N> using make_integer_sequence = typename make_integer_sequence_<T, N>::type; template<size_t N> using make_index_sequence = make_integer_sequence<size_t, N>; template<class... T> using index_sequence_for = make_index_sequence<sizeof...(T)>; ///////////////////////// constexpr int size = 1000; int data[size]; int data1[size]; template <int... i> int foo_N(integer_sequence<int, i...>) { int sum = 0; bool dummy[] = { ((sum+=data[i]+data1[i]),false)... }; return sum; } int foo() { return foo_N(make_integer_sequence<int,size>{}); } #include <iostream> #include <ctime> int main() { std::srand(std::time(0)); for (int i=0; i<size; i++) { data[i] = rand(); data1[i] = rand(); } std::cout << foo() << '\n'; }-O2 -ftemplate-depth=2000
movl data(%rip), %eax addl data1(%rip), %eax addl 4+data(%rip), %eax addl 4+data1(%rip), %eax addl 8+data(%rip), %eax addl 8+data1(%rip), %eax addl 12+data(%rip), %eax addl 12+data1(%rip), %eax ... usw. addl 3996+data(%rip), %eax addl 3996+data1(%rip), %eax movq -8(%rbp), %rdx xorq %fs:40, %rdx jne .L5Ich bin nicht ganz sicher, wie viel Speicher eine einzelne add-Instruktion hier braucht (5 oder 6 schätze ich mal), auf jedenfall ist das eine Menge Code, der ggf. nicht mehr in den L1-Cache passt.
zusätzlich -ftree-vectorize
movl data(%rip), %eax addl data1(%rip), %eax addl 4+data(%rip), %eax addl 4+data1(%rip), %eax addl 8+data(%rip), %eax addl 8+data1(%rip), %eax addl 12+data(%rip), %eax addl 12+data1(%rip), %eax ... usw.Schlecht! Keine Vectorisierung.
-
wow, super interessante Information, vielen Dank!
-
constexpr int size = 1000;Hmm, und jetzt, wenn die Feldgroesse keine fixe Groesse ist. Aber sicherlich ist das Beispiel viel zu einfach.
paddd (%rcx,%rax), %xmm0Hmm, noch nie gesehen.
Sehr interessante Syntax, 2 64 Bitregister zusammenzufassen und mit einem XMM-Register zu verheiraten. Wo kann ich mehr darueber nachlesen? Gibt es dafuer Intrinsics? Geht das auch andersherum?
-
-ftemplate-depth=2000
Wozu? Braucht es tatsächlich 2000 rekursive Instantiierungen? (Oder gibst du das standardmäßig an?)
Dieses einfache Beispiel ist für den Compiler kein Problem.
Und was geschieht, wenn du -Os mitgibst?
Boost.PP ist boost Preprocessor?
Richtig. Wenn die Anzahl Schleifendurchläufe ein Literal ist, dann geht es damit. (Damit wird aber der Code möglicherweise recht lang)
-
Hmm, und jetzt, wenn die Feldgroesse keine fixe Groesse ist.
Keine fixe Größe? Reden wir jetzt von VLAs?
-
Nein, std::vector<int> tuts auch. Glaube Intel versucht SSE bei valarray ... zumindestens habe ich mal was gelesen ... lange her.
-
knivil schrieb:
paddd (%rcx,%rax), %xmm0Hmm, noch nie gesehen.
Sehr interessante Syntax, 2 64 Bitregister zusammenzufassen und mit einem XMM-Register zu verheiraten. Wo kann ich mehr darueber nachlesen? Gibt es dafuer Intrinsics? Geht das auch andersherum?das ist AT&T-Syntax für Speicheroperanden. Bei intel sieht das so aus
paddd xmm0, [rcx+rax]allgemein
disp(base_reg,index_reg,scale) entspricht [base_reg+index_reg*scale+disp]
-
Ach verdammt ...
-
1. Code mit -Os ergibt
.L3: leaq data(%rip), %rcx addl (%rcx,%rdx), %eax leaq data1(%rip), %rcx addl (%rcx,%rdx), %eax addq $4, %rdx cmpq $4000, %rdx jne .L3-ftree-vectorize und -funroll-loops führen zu keiner Änderung (ausser vertauschter Reihenfolge der 2. und 3. Instruktion mit -funroll-loops)
-
- schrieb:
-ftemplate-depth=2000
Wozu? Braucht es tatsächlich 2000 rekursive Instantiierungen? (Oder gibst du das standardmäßig an?)
Habe 2000 angegeben, es mehr als 1000 sein müssen bei dieser primitiven Art der Generierung von make_integer_sequence.
