3. loop unrolling mit variadic Templates möglich?

loop unrolling mit variadic Templates möglich?

  • K

    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?

    0
  • K

    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.

    0
  • C
    Mod

    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.

    0
  • Mod

    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 😡

    0
  • C
    Mod

    • schrieb:

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

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

    0
  • Mod

    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)... };
    }
};
    0
  • Mod

    Edit: Hat sich erledigt.

    0
  • K

    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?

    0
  • K

    kann man sich darauf verlassen?

    Nein.

    0
  • K

    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.

    0
  • C
    Mod

    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.

    0
  • Mod

    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.

    0
  • C
    Mod

    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.

    0
  • K

    wow, super interessante Information, vielen Dank!

    0
  • K
     

    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?

    0
  • Mod

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

    0
  • Mod

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

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

    0
  • K

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

    0
  • C
    Mod

    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]

    0
  • K

    Ach verdammt ...

    0
  • C
    Mod

    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)

    0
Anmelden zum Antworten