loop unrolling mit variadic Templates möglich?

kurze_frage

Hallo,

wenn ich etwas wiederholen möchte und zur compile zeit weiss wie oft,

kann ich statt einer
for (int i = 0; i < wieoft ++ i) machwas(i)
loop
variadic templates benutzen um das auf zu rollen?
sodas es sowas wie
machwas(0)
machwas(1)
machwas(2)
...
wird und der optimizer gegebenenfalls berechungen besser simd optimieren kann

theoretisch muss das ja möglich sein, nur wie geht das?
brauch ich dafür variadic Templates oder bin ich damit am falschen Weg?

knivil

wird und der optimizer gegebenenfalls berechungen besser simd optimieren kann

Kommt drauf an, eher nicht.

nur wie geht das

Indem du Iteration durch Rekursion ersetzt.

brauch ich dafür variadic Templates oder bin ich damit am falschen Weg

Du brauchst keine Templates mit variable Argumenten.

camper

kurze_frage schrieb:

theoretisch muss das ja möglich sein, nur wie geht das?

Sicher, allerdings ist es höchstwahrscheinlich kontraproduktiv, d.h. je nach Komplexität ist der erzeugte Code eher geanuso schnell oder langsamer als eine einfache Schleife, deren Optimierung dem Compiler überlassen wurde.

Ein Aufrollen per variadic Template ist nat. möglich.
Erst einmal benötigen wir dafür eine entsprechende Argumentliste, müssen das Ganze also über einen Funktionsaufruf deligieren. Zum Beispiel so:

// C++14 (N3658)
////////////////
template<class T, T...> 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<>>
struct make_index_sequence_;
template <typename T, std::size_t N, T... I>
struct make_index_sequence_<T, N, integer_sequence<T, I...>>
{
    using type = typename make_index_sequence_<T, N-1, integer_sequence<T, 0, 1+I...>>::type;
};
template <typename T, T... I>
struct make_index_sequence_<T, 0, integer_sequence<T, I...>>
{
    using type = integer_sequence<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)>;
/////////////////////////
void machwas(int);
void foo()
{
    constexpr auto wieoft = ...
    for (int i = 0; i < wieoft ++ i)
        machwas(i);
}
// wird zu
template <typename Fun, int... i>
void machwas_N(Fun f, integer_sequence<int, i...>)
{
    bool dummy[] = { f(i)... }; // Ausführungsreihenfolge garantiert
}
void foo()
{
    constexpr auto wieoft = ...
    machwas_N(machwas, make_integer_sequence<int, wieoft>{});
}

Ich bezweifle aber, das so eine Transformation einer Vektorisierung durch den Compiler zuträglich ist.

Columbo

Wenn die Schleife eine feste Durchlaufzahl hat, dann lohnt sich das nicht - loop unrolling sollte der Compiler doch selbst hinbekommen. Machen die auch.

Übrigens würde man hier vielleicht zu Boost.PP greifen... variadic templates tun es aber auch:

template< void(*)(index_type),
          size_type len,
          typename = eval<make_index_list<len>>> struct repeat;

template< void(*ptr)(index_type), size_type len,
          index_type... indices >
struct repeat<ptr, len, index_list<indices...>>
{
	static void run()
	{
		bool _[]{ (ptr(indices), false)... };
	}
};

void foo(index_type i)
{
	std::cout << i << ',';
}

int main()
{
	repeat<foo, 7>::run();
}

Ausgabe sollte sein:
0,1,2,3,4,5,6
Man kann die Warnung auch entfernen, in dem man eine temporäre initializer_list erzeugt.

War jetzt aber nur zum Spaß.

Edit: camper! Verdammt, ich bin zu spät

camper

schrieb:

Edit: camper! Verdammt, ich bin zu spät

Dafür hat sich bei mir ein offensichtlicher Fehler eingeschlichen.

Columbo

https://ideone.com/jxX6pW

Dafür hat sich bei mir ein offensichtlicher Fehler eingeschlichen.

Ja, das Array hat falsche initializer.

Man sollte meines noch ändern zu

template< size_type len, 
          typename = eval<make_index_list<len>>> struct repeat;

template< size_type len, index_type... indices >
struct repeat<len, index_list<indices...>> // Edit: template-id korrigiert
{
    template< typename Fun >
    static void run(Fun f)
    {
        bool _[]{ (f(indices), false)... };
    }
};

Columbo

Edit: Hat sich erledigt.

kurze_frage

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?

knivil

kann man sich darauf verlassen?

Nein.

kurze_frage

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.

camper

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     .L3

kein 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     .L3

zusä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     .L3

zusä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     .L3

Dieses einfache Beispiel ist für den Compiler kein Problem.

SeppJ

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.

camper

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     .L5

Ich 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.

kurze_frage

wow, super interessante Information, vielen Dank!

knivil

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), %xmm0

Hmm, 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?

Columbo

-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)

Columbo

Hmm, und jetzt, wenn die Feldgroesse keine fixe Groesse ist.

Keine fixe Größe? Reden wir jetzt von VLAs?

knivil

Nein, std::vector<int> tuts auch. Glaube Intel versucht SSE bei valarray ... zumindestens habe ich mal was gelesen ... lange her.

camper

knivil schrieb:

paddd   (%rcx,%rax), %xmm0
Hmm, 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]

knivil

Ach verdammt ...