3. loop unrolling mit variadic Templates möglich?

loop unrolling mit variadic Templates möglich?

  • 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
  • C
    Mod

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

    0
Anmelden zum Antworten