Il compilatore Intel C++ è estremamente lento per la compilazione dei rendimenti decltype ricorsivi

Question

Sto scrivendo un modello per espressioni parametrizzate da un numero arbitrario di etichette char.

Dato un elenco di argomenti, una funzione factory restituisce un'espressione di tipi diversi a seconda che esistano due argomenti dello stesso tipo o se siano univoci.

Un esempio concreto: supponiamo che A sia un oggetto "etichettabile" con il suo operator() sovraccarico per produrre un ?Expression<...>. Lascia che sia a, b, ... dichiarato come etichette LabelName<'a'>, LabelName<'b'>, .... Quindi A(a,b,c,d) produrrebbe uno UniqueExpression<'a','b','c','d'>, mentre invece A(a,c,b,c) produrrebbe uno RepeatedExpression<'a','c','b','c'>.

Per raggiungere questo obiettivo, ho dovuto definire la funzione di fabbrica ?Expression con auto e decltype. Inoltre, lo decltype deve sovrapporsi a un altro decltype fino a quando il metaprogramma termina ricorrendo agli argomenti e il tipo restituito viene infine deciso. A titolo illustrativo, ho isolato un codice abbastanza minimale per il metodo factory.

template <typename... T> struct TypeList { }; 
template <char C> struct LabelName { }; 

template <typename... T> class UniqueExpression 
{ 
    // Contains implementation details in actual code 
}; 

template <typename... T> class RepeatedExpression 
{ 
    // Contains implementation details in actual code 
}; 

class ExpressionFactory { 
private: 
    template <char _C, typename... T, typename... _T> 
    static UniqueExpression<T...> 
    _do_build(TypeList<T...>, 
       TypeList<LabelName<_C>>, 
       TypeList<>, 
       TypeList<_T...>) 
    { 
     return UniqueExpression<T...>(); 
    } 

    template <char _C, typename... T, typename... _T1, typename... _T2, typename... _T3> 
    static RepeatedExpression<T...> 
    _do_build(TypeList<T...>, 
       TypeList<LabelName<_C>, _T1...>, 
       TypeList<LabelName<_C>, _T2...>, 
       TypeList<_T3...>) 

    { 
     return RepeatedExpression<T...>(); 
    } 

    template <char _C1, char _C2, typename... T, typename... _T1, typename... _T2, typename... _T3> 
    static auto 
    _do_build(TypeList<T...>, 
       TypeList<LabelName<_C1>, _T1...>, 
       TypeList<LabelName<_C2>, _T2...>, 
       TypeList<_T3...>) 
    -> decltype(_do_build(TypeList<T...>(), 
          TypeList<LabelName<_C1>, _T1...>(), 
          TypeList<_T2...>(), 
          TypeList<_T3..., LabelName<_C2>>())) 
    { 
     return _do_build(TypeList<T...>(), 
         TypeList<LabelName<_C1>, _T1...>(), 
         TypeList<_T2...>(), 
         TypeList<_T3..., LabelName<_C2>>()); 
    } 

    template <char _C1, char _C2, typename... T, typename... _T1, typename... _T2> 
    static auto 
    _do_build(TypeList<T...>, 
       TypeList<LabelName<_C1>, LabelName<_C2>, _T1...>, 
       TypeList<>, 
       TypeList<LabelName<_C2>, _T2...>) 
    -> decltype(_do_build(TypeList<T...>(), 
          TypeList<LabelName<_C2>, _T1...>(), 
          TypeList<_T2...>(), 
          TypeList<>())) 
    { 
     return _do_build(TypeList<T...>(), 
         TypeList<LabelName<_C2>, _T1...>(), 
         TypeList<_T2...>(), 
         TypeList<>()); 
    } 

public: 
    template <char C, typename... T> 
    static auto 
    build_expression(LabelName<C>, T...) 
    -> decltype(_do_build(TypeList<LabelName<C>, T...>(), 
          TypeList<LabelName<C>, T...>(), 
          TypeList<T...>(), 
          TypeList<>())) 
    { 
     return _do_build(TypeList<LabelName<C>, T...>(), 
         TypeList<LabelName<C>, T...>(), 
         TypeList<T...>(), 
         TypeList<>()); 
    } 
}; 

La fabbrica potrebbe essere chiamato nel programma in questo modo: (nel programma vero e proprio c'è un'altra classe con un sovraccarico operator() che chiama la fabbrica)

int main() 
{ 
    LabelName<'a'> a; 
    LabelName<'b'> b; 
    ... 
    LabelName<'j'> j; 

    auto expr = ExpressionFactory::build_expression(a,b,c,d,e,f,g,h,i,j); 

    // Perhaps do some cool stuff with expr 

    return 0; 
} 

Il codice precedente funziona come previsto, ed è compilato correttamente sia da GCC che dal compilatore Intel. Ora, capisco che il compilatore impiegherebbe più tempo per eseguire la deduzione dei template ricorsivi mentre aumento il numero di etichette che uso.

Sul mio computer, se build_expression viene chiamato con un argomento, GCC 4.7.1 richiede circa 0,26 secondi per la compilazione in media. Il tempo di compilazione è scalabile fino a circa 0,29 secondi per cinque argomenti e a 0,62 secondi per dieci argomenti. Questo è tutto perfettamente ragionevole.

La storia è abbastanza diversa con il compilatore Intel. ICPC 13.0.1 compila il codice a un argomento in 0,35 secondi e il tempo di compilazione rimane praticamente costante per un massimo di quattro argomenti. A cinque argomenti il ​​tempo di compilazione sale a 12 secondi, e in sei argomenti spara sopra 9600 secondi (cioè oltre 2 ore e 40 minuti). Inutile dire che non ho aspettato abbastanza per scoprire quanto tempo ci vuole per compilare la versione a sette argomenti.

---

Due domande vengono subito in mente:

• è il compilatore Intel particolarmente conosciuto per essere lento per compilare ricorsiva decltype?

• C'è un modo per riscrivere questo codice per ottenere lo stesso effetto in un modo forse più amichevole con il compilatore?

Answer 1

Ecco una pugnalata. Invece di fare confronti a coppie di ciascuno degli elementi, ordino l'elenco dei tipi, quindi uso un algoritmo unico cerebralmente morto per vedere se ci sono duplicati.

Ho implementato un tipo di merge sui tipi, perché era divertente. Probabilmente una sorta di bolla ingenua funzionerebbe meglio su un numero ragionevole di argomenti.Si noti che un po 'di lavoro ci consentirebbe di fare un ordinamento di fusione in liste lunghe e specializzarsi per tipi di bolle (o anche tipi di inserimento) su liste brevi. Non sono pronto per scrivere un modello di quicksort.

Questo mi dà un tempo di compilazione booleano che dice se ci sono duplicati nella lista. Posso quindi utilizzare enable_if per selezionare il sovraccarico che userò.

Si noti che la propria soluzione implicava n^2 livelli di ricorsione modello, in ogni fase in cui il tipo restituito richiede la valutazione del tipo di una classe più semplice di 1 passo e quindi il tipo restituito richiede anche lo stesso! Se la memoizzazione del compilatore Intel fallisce, si parla di quantità di lavoro esponenziali.

Ho aumentato alcune delle tue lezioni con alcuni aiutanti. Ho ereditato il tuo LabelName da std::integral_constant, quindi ho un accesso facile al tempo di compilazione al loro valore. Questo rende il codice di ordinamento un po 'più semplice. Ho anche esposto uno enum dai valori di ritorno ripetuti e univoci in modo da poter eseguire il debug semplice su printf sul risultato.

La maggior parte di questo lavoro sta scrivendo l'ordinamento di unione: esiste un ordinamento di tipo di compilazione standard che è possibile utilizzare?

#include <type_traits> 
#include <iostream> 

template <typename... T> struct TypeList { }; 

// NOTE THIS CHANGE: 
template <char C> struct LabelName:std::integral_constant<char, C> {}; 

template <typename... T> class UniqueExpression 
{ 
    // Contains implementation details in actual code 
public: 
    enum { is_unique = true }; 
}; 

template <typename... T> class RepeatedExpression 
{ 
    // Contains implementation details in actual code 
public: 
    enum { is_unique = false }; 
}; 

// A compile time merge sort for types 
// Split takes a TypeList<>, and sticks the even 
// index types into Left and odd into Right 
template<typename T> 
struct Split; 
template<> 
struct Split<TypeList<>> 
{ 
    typedef TypeList<> Left; 
    typedef TypeList<> Right; 
}; 
template<typename T> 
struct Split<TypeList<T>> 
{ 
    typedef TypeList<T> Left; 
    typedef TypeList<> Right; 
}; 

// Prepends First into the TypeList List. 
template<typename First, typename List> 
struct Prepend; 
template<typename First, typename... ListContents> 
struct Prepend<First,TypeList<ListContents...>> 
{ 
    typedef TypeList<First, ListContents...> type; 
}; 

template<typename First, typename Second, typename... Tail> 
struct Split<TypeList<First, Second, Tail...>> 
{ 
    typedef typename Prepend< First, typename Split<TypeList<Tail...>>::Left>::type Left; 
    typedef typename Prepend< Second, typename Split<TypeList<Tail...>>::Right>::type Right; 
}; 

// Merges the sorted TypeList<>s Left and Right to the end of TypeList<> MergeList 
template< typename Left, typename Right, typename MergedList=TypeList<> > 
struct Merge; 
template<typename MergedList> 
struct Merge< TypeList<>, TypeList<>, MergedList > 
{ 
    typedef MergedList type; 
}; 
template<typename L1, typename... Left, typename... Merged> 
struct Merge< TypeList<L1, Left...>, TypeList<>, TypeList<Merged... >> 
{ 
    typedef TypeList<Merged..., L1, Left...> type; 
}; 
template<typename R1, typename... Right, typename... Merged> 
struct Merge< TypeList<>, TypeList<R1, Right...>, TypeList<Merged...> > 
{ 
    typedef TypeList<Merged..., R1, Right...> type; 
}; 
template<typename L1, typename... Left, typename R1, typename... Right, typename... Merged> 
struct Merge< TypeList<L1, Left...>, TypeList<R1, Right...>, TypeList<Merged...>> 
{ 
    template<bool LeftIsSmaller, typename LeftList, typename RightList, typename MergedList> 
    struct MergeHelper; 

    template<typename FirstLeft, typename... LeftTail, typename FirstRight, typename... RightTail, typename... MergedElements> 
    struct MergeHelper< true, TypeList<FirstLeft, LeftTail...>, TypeList<FirstRight, RightTail...>, TypeList<MergedElements...> > 
    { 
    typedef typename Merge< TypeList<LeftTail...>, TypeList< FirstRight, RightTail... >, TypeList< MergedElements..., FirstLeft > >::type type; 
    }; 
    template<typename FirstLeft, typename... LeftTail, typename FirstRight, typename... RightTail, typename... MergedElements> 
    struct MergeHelper< false, TypeList<FirstLeft, LeftTail...>, TypeList<FirstRight, RightTail...>, TypeList<MergedElements...> > 
    { 
    typedef typename Merge< TypeList<FirstLeft, LeftTail...>, TypeList<RightTail... >, TypeList< MergedElements..., FirstRight > >::type type; 
    }; 

    typedef typename MergeHelper< (L1::value < R1::value), TypeList<L1, Left...>, TypeList<R1, Right...>, TypeList<Merged...> >::type type; 
}; 

// Takes a TypeList<T...> and sorts it via a merge sort: 
template<typename List> 
struct MergeSort; 
template<> 
struct MergeSort<TypeList<>> 
{ 
    typedef TypeList<> type; 
}; 
template<typename T> 
struct MergeSort<TypeList<T>> 
{ 
    typedef TypeList<T> type; 
}; 
template<typename First, typename Second, typename... T> 
struct MergeSort<TypeList<First, Second, T...>> 
{ 
    typedef Split<TypeList<First, Second, T...>> InitialSplit; 
    typedef typename MergeSort< typename InitialSplit::Left >::type Left; 
    typedef typename MergeSort< typename InitialSplit::Right >::type Right; 
    typedef typename Merge< Left, Right >::type type; 
}; 

// Sorts a TypeList<T..>: 
template<typename List> 
struct Sort: MergeSort<List> {}; 

// Checks sorted TypeList<T...> SortedList for adjacent duplicate types 
// return value is in value 
template<typename SortedList> 
struct Unique; 

template<> struct Unique< TypeList<> >:std::true_type {}; 
template<typename T> struct Unique< TypeList<T> >:std::true_type {}; 

template<typename First, typename Second, typename... Tail> 
struct Unique< TypeList< First, Second, Tail... > > 
{ 
    enum 
    { 
    value = (!std::is_same<First, Second>::value) && 
     Unique< TypeList<Second, Tail...> >::value 
    }; 
}; 

// value is true iff there is a repeated type in Types... 
template<typename... Types> 
struct RepeatedType 
{ 
    typedef TypeList<Types...> MyListOfTypes; 

    typedef typename Sort<MyListOfTypes>::type MyListOfTypesSorted; 
    enum 
    { 
    value = !Unique<MyListOfTypesSorted>::value 
    }; 
}; 

// A struct that creates an rvalue trivial constructed type 
// of any type requested. 
struct ProduceRequestedType 
{ 
    template<typename Result> 
    operator Result() { return Result(); }; 
}; 

struct ExpressionFactory { 
    template<typename... T> 
    typename std::enable_if< 
    !RepeatedType<T...>::value, 
    UniqueExpression<T...> 
    >::type 
    build_expression(T...) const 
    { 
    return ProduceRequestedType(); 
    }; 
    template<typename... T> 
    typename std::enable_if< 
    RepeatedType<T...>::value, 
    RepeatedExpression<T...> 
    >::type 
    build_expression(T...) const 
    { 
    return ProduceRequestedType(); 
    }; 
}; 

// Simple testing code for above: 
int main() 
{ 
    auto foo1 = ExpressionFactory().build_expression(LabelName<'a'>(), LabelName<'b'>(), LabelName<'a'>()); 
    typedef decltype(foo1) foo1Type; 
    if (foo1Type::is_unique) 
    std::cout << "foo1 is unique\n"; 
    else 
    std::cout << "foo1 is repeated\n"; 

    auto foo2 = ExpressionFactory().build_expression(LabelName<'q'>(), LabelName<'a'>(), LabelName<'b'>(), LabelName<'d'>(), LabelName<'t'>(), LabelName<'z'>()); 
    typedef decltype(foo2) foo2Type; 
    if (foo2Type::is_unique) 
    std::cout << "foo2 is unique\n"; 
    else 
    std::cout << "foo2 is repeated\n"; 
} 

Inoltre mi piacerebbe aggiungere una critica del codice: la programmazione del modello è la programmazione - i vostri dei tipi sono l'equivalente di utilizzare "i1" attraverso "I9" per variabili intere in una funzione. Dai ai tuoi nomi di battesimo nomi significativi quando fai qualcosa di non banale.

Come si compila su Intel?