Comment dérouler une courte boucle en C++

Question

Je me demande comment obtenir quelque chose comme ceci:

1. Ecrire

   copy(a, b, 2, 3) 
   

2. Et puis obtenir

   a[2] = b[2]; 
   a[3] = b[3]; 
   a[4] = b[4]; 
   

I sachez que C#defines ne peut pas être utilisé récursivement pour obtenir cet effet. Mais j'utilise C++, donc je suppose que la méta-programmation de template pourrait être appropriée.

Je sais qu'il existe une bibliothèque Boost pour cela, mais je ne veux que cette "simple" astuce, et Boost est trop "désordonné".

Answer 1

La solution la plus simple pour cela est d'écrire une boucle où les valeurs de début et de fin sont connus:

for(int i = 2; i <= 4; i++) { 
    a[i]=b[i]; 
} 

Je pense que cela vaut mieux que toute sorte de mélange appel d'exécution modèle /: La boucle telle qu'elle est écrite est complètement claire pour l'optimiseur des compilateurs, et il n'y a pas de niveaux d'appels de fonction à explorer juste pour voir ce qui se passe.

Answer 2

De http://www.sgi.com/tech/stl/Vector.html:

template <class InputIterator> 
vector(InputIterator, InputIterator) 

Creates a vector with a copy of a range. 

Answer 3

C++ méta-programmation est récursive.

Pensez à votre problème en termes de récursivité. Implémenter des cas terminaux et des cas non terminaux.

Votre boîtier de terminal peut être 0 ou un. Passez les limites en tant que paramètres de modèle. Utilisez une structure/classe car ils permettent une spécialisation partielle et d'autres choses intéressantes:

template<int from, int to> 
struct copy { 
    static void apply(source, destination) { 
     source[from] = destination[from]; 
     copy<from+1,to>:: apply(source, destination); 
    } 
}; 

// Terminal case 
template<int from> 
struct copy<from, from> { 
    static void apply(source, destination) { 
     source[from] = destination[from]; 
    } 
}; 

Answer 4

Vous pouvez probablement faire quelque chose comme ce qui suit. Selon votre compilateur et les paramètres d'optimisation que vous utilisez pouvez obtenir l'effet que vous recherchez. Sachez que pour les petits objets tels que char, il peut être plus lent qu'un std::copy ou un memcpy et que pour les objets plus gros, le coût d'une boucle risque d'être insignifiant par rapport aux copies en cours dans tous les cas.

#include <cstddef> 

template<std::size_t base, std::size_t count, class T, class U> 
struct copy_helper 
{ 
    static void copy(T dst, U src) 
    { 
     dst[base] = src[base]; 
     copy_helper<base + 1, count - 1, T, U>::copy(dst, src); 
    } 
}; 

template<std::size_t base, class T, class U> 
struct copy_helper<base, 0, T, U> 
{ 
    static void copy(T, U) 
    { 
    } 
}; 

template<std::size_t base, std::size_t count, class T, class U> 
void copy(T dst, U src) 
{ 
    copy_helper<base, count, T, U>::copy(dst, src); 
} 

template void copy<5, 9, char*, const char*>(char*, const char*); 

#include <iostream> 
#include <ostream> 

int main() 
{ 
    const char test2[] = "  , World\n"; 
    char test[14] = "Hello"; 

    copy<5, 9>(test, test2); 

    std::cout << test; 

    return 0; 
} 

Answer 5

Il est important de réaliser que le compilateur est très intelligent, et que le tromper pour dérouler les boucles en utilisant la métaprogrammation du template vous rappellera probablement qu'il vous fera avancer.

Pour tirer le meilleur parti de vos optimisations: gardez un œil sur le démontage. Cela vous apprendra peut-être plus que de lancer des modèles sur le problème. Notez, comme Johannes a dit: si le compilateur peut voir que vous exécutez une boucle pour un nombre fixe de fois (ou un multiple fixe de fois comme variable 4x), il peut créer un code très proche de l'optimal.

Answer 6

Il n'utilise pas de modèles et ce n'est pas un « complet » le déroulement, mais vous pouvez partiellement déroulez la boucle avec quelque chose comme ceci:

void copy (SomeType* a, SomeType* b, int start_index, int num_items) { 
    int i = start_index; 

    while (num_items > 4) { 
      a[i+0] = b[i+0]; 
      a[i+1] = b[i+1]; 
      a[i+2] = b[i+2]; 
      a[i+3] = b[i+3]; 
      i += 4; 
      num_items -= 4; 
    } 
    while (num_items > 0) { 
      a[i] = b[i]; 
      ++i; 
      --num_items; 
    } 
} 

maintenant dans cet exemple particulier, les calculs supplémentaires impliqués sera probablement l'emportent sur les avantages de ne dérouler que quatre éléments à la fois. Vous devriez tirer un avantage croissant d'un nombre croissant d'éléments dans la boucle supérieure (dans toute la fonction, remplacez 4 par de nombreux éléments que vous copiez dans chaque itération déroulée manuellement).

Answer 7

template <int begin, int end> struct copy_; 

template <int end> struct copy_<end, end> { 
    template <typename T> static void execute(T& a, T& b) 
    { 
    a[end] = b[end]; 
    } 
}; 

template <int begin, int end> struct copy_<begin, end> { 
    template <typename T> static void execute(T& a, T& b) 
    { 
    a[begin] = b[begin]; 
    copy_<begin+1, end>::execute(a, b); 
    } 
}; 

template <int begin, int how_many> struct copy { 
    template <typename T> static void execute(T& a, T& b) 
    { 
    copy_<begin, begin+how_many-1>::execute(a, b); 
    } 
}; 

copy<2, 3>::execute(a, b);

Answer 8

Le déroulement de la boucle en utilisant la méta-programmation peut être utilisé pour créer constexpr (je n'ai pas mesuré les temps). J'ai un exemple où il peut être utilisé pour faire la combinaison de la fonction (n, k) cosntexpr:

template <size_t N> struct iterate_forward { 
    template <class operation> static auto eval(const operation & op) 
    { 
     iterate_forward<N-1>::eval(op); 
     return op(N-1); 
    } 
}; 
template <> struct iterate_forward<1> 
{ 
    template <class operation> static auto eval(const operation & op) 
    { return op(0); } 
}; 
template <> struct iterate_forward<0> 
{ 
    template <class operation> static auto eval(const operation & op) {} 
}; 
template <size_t N, size_t K> constexpr size_t COMB() 
{ 
    struct ratio 
    { 
     size_t operator() (size_t i) const { return (res *= (N-i)/(i+1)); } 
     mutable size_t res = 1; 
    }; 
    return iterate_forward<K>::eval(ratio()); 
} 

Answer 9

#define tl template 
#define tn typename 
#define st struct 
#define cl class 
#define us using 


    template<tn A> st Typ { using type = A; }; 
    tl<tn T> using GetT = tn T::type; 
    tl<tn F, tn ...As> us apply = tn F::tl apply<As...>; 
    tl<tn, tn, tn ...> st LoopElements; 
    tl<tn, tn> st Loop; 
    tl<tn, tn, tn> st VLoop_i; 
    tl<tn Sq, tn MF> us VLoop = VLoop_i<GetT<Sq>, Sq, MF>; 

    // 
    // TY 
    // 
    template<tn T> struct Ty { 
     template<T ...> struct Pack : Typ<T> {}; 
     tl<tn ...> st Concat_i; tl<tn ...P> us Concat = GetT<Concat_i<P...>>; 
     tl<T, int64_t> st Seq_i; tl<T f, T t> us Seq = GetT<Seq_i<f, ((int64_t)(t - f))>>; tl<int64_t, tn> st add; 

     template<tl<T ...> tn C, T ...vs, tl<T ...> tn D, T ...ws, tn ...R> st Concat_i<C<vs...>, D<ws...>, R...> : Typ<Concat<C<vs..., ws...>, R...> >{}; 
     template<tl<T ...> tn C, T ...vs> st Concat_i<C<vs...>> : Typ<C<vs...> >{}; 

     template<int64_t x, T ...vs> struct add<x, Pack<vs...>> : Typ<Pack<((T)(vs + x))...>> {}; 
     template<T f, int64_t c> class Seq_i { 
      using A = tn Seq_i<f, c/2>::type; 
      using B = tn add<c/2, A>::type; 
      using C = tn Seq_i<f + c/2 * 2, c & 1>::type; 
     public: 
      using type = Concat<A, B, C>; 
     }; 
     tl<T f> st Seq_i<f, 0> : Typ<Pack<>> {};   
     tl<T f> st Seq_i<f, 1> : Typ<Pack<f>> {}; 
     tl<T f> st Seq_i<f, -1> : Typ<Pack<f>> {}; 
    }; 

    // 
    // LOOP 
    template<size_t i, tn F, tn T> struct LoopElement { LoopElement() { apply<F, T>(); }; }; 
    template<size_t ...is, tn F, tn ...P> struct LoopElements<Ty<size_t>::Pack<is...>, F, P...> : LoopElement<is, F, P>... {}; 
    template<tn F, tl<tn ...> cl C, tn ...P> struct Loop<F, C<P...>> : LoopElements<Ty<size_t>::Seq<0, sizeof...(P)>, F, P...> {}; 

    template<tn T, tl<T ...> cl ST, T ...vs, tn MF> struct VLoop_i<T, ST<vs...>, MF> : LoopElements<Ty<size_t>::Seq<0, sizeof...(vs)>, MF, Val<T, vs>...> {};