Kompilator Intel C++ bardzo wolno kompiluje rekursywne zwracanie deklaracji.

Question

Piszę szablon dla wyrażeń sparametryzowanych przez dowolną liczbę etykiet char.

Przy danej liście argumentów funkcja fabryczna zwraca wyrażenia różnych typów w zależności od tego, czy istnieją dwa argumenty tego samego typu, czy też są unikatowe.

Konkretny przykład: załóżmy, że A jest obiektem "etykietowanym" z przeciążonym operator() w celu utworzenia ?Expression<...>. Niech a, b, ... zostanie zadeklarowane jako etykiety LabelName<'a'>, LabelName<'b'>, .... Następnie A(a,b,c,d) wytworzyłby UniqueExpression<'a','b','c','d'>, podczas gdy A(a,c,b,c) wygenerowałby zamiast tego RepeatedExpression<'a','c','b','c'>.

Aby to osiągnąć, musiałem zdefiniować funkcję fabryczną ?Expression z auto i decltype. Co więcej, decltype musi się kaskadować do kolejnego decltype, aż metaprogram zakończy rekursję przez argumenty i ostatecznie zdecyduje się na typ powrotu. Jako ilustrację, wyizolowałem dość minimalny kod dla metody fabrycznej.

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<>()); 
    } 
}; 

Fabryka można nazwać w programie tak: (w rzeczywistym programie istnieje inna klasa z przeciążonej operator() który wzywa fabrykę)

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; 
} 

Powyższy kod działa zgodnie z przeznaczeniem, i jest poprawnie skompilowany zarówno przez GCC, jak i kompilator Intel. Rozumiem, że kompilacja zajęłaby więcej czasu, aby wykonać rekurencyjne odliczanie szablonów, ponieważ zwiększam liczbę etykiet, których używam.

Na moim komputerze, jeśli build_expression jest wywoływany z jednym argumentem, wówczas GCC 4.7.1 zajmuje średnio 0,26 sekundy. Czas kompilacji skaluje się do około 0,29 sekundy dla pięciu argumentów i do 0,62 sekundy dla dziesięciu argumentów. Wszystko to jest całkowicie uzasadnione.

Historia jest zupełnie inna w przypadku kompilatora Intel. ICPC 13.0.1 kompiluje kod jednokrotny w 0.35 sekundy, a czas kompilacji pozostaje prawie stały dla maksymalnie czterech argumentów. Przy pięciu argumentach czas kompilacji wzrasta do 12 sekund, a przy sześciu argumentach strzela ponad 9600 sekund (czyli ponad 2 godziny i 40 minut). Nie trzeba dodawać, że nie czekałem wystarczająco długo, aby dowiedzieć się, ile czasu zajmuje kompilacja wersji siedmiokonwersalnej.

---

dwa pytania od razu przychodzą na myśl:

• Czy kompilator Intel szczególnie znane jako powolne kompilacji rekurencyjnej decltype?

• Czy istnieje sposób na przepisanie tego kodu w celu osiągnięcia tego samego efektu w sposób, który jest być może bardziej przyjazny kompilatorowi?

Answer 1

Oto strzał w to. Zamiast porównywania poszczególnych elementów z każdego z nich, sortuję listę typów, a następnie wykorzystuję unikalny algorytm, aby sprawdzić, czy są jakieś duplikaty.

Zaimplementowałem scalanie sortowania na typy, ponieważ było fajnie. Prawdopodobnie naiwny rodzaj bąbelków działałby lepiej na uzasadnionej liczbie argumentów.Zauważ, że odrobina pracy pozwoliłaby nam na sortowanie korespondencji na długich listach i specjalizację dla sortowania bąbelkowego (a nawet sortowania wstawek) na krótkich listach. Nie mam zamiaru pisać szablonu quicksort.

To daje mi wartość logiczną czasu kompilacji, która mówi, czy są duplikaty na liście. Mogę następnie użyć enable_if, aby wybrać, które przeciążenie będę używać.

Zauważ, że twoje rozwiązanie dotyczyło n^2 warstw rekursji szablonu, na każdym etapie których typ zwracany wymaga oceny typu klasy 1-krokowej prostszej, a następnie zwracany typ również wymaga tego samego! Jeśli proces zapamiętywania kompilatora Intel nie powiedzie się, mówisz o wykładniczej ilości pracy.

Wzmocniłem kilka twoich zajęć z pomocą niektórych pomocników. Zrobiłem twoje LabelName s odziedziczone po std::integral_constant, więc mam łatwy czas kompilacji dostępu do ich wartości. Dzięki temu kod sortowania jest odrobinę łatwiejszy. Wyeksponowałem również enum z powtarzających się i unikatowych wartości zwracanych, dzięki czemu mogę przeprowadzić proste debugowanie na printf wyniku.

Większość tej pracy polega na pisaniu sortowania scalonego - czy istnieje standardowy sortowany typ kompilacji, który możemy wykorzystać?

#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"; 
} 

Ponadto chciałbym dodać krytykę kodzie: Szablon jest programowanie programowanie - Twoje typenames są odpowiednikiem użyciu „I1” do „i9” dla zmiennych całkowitych w funkcji. Nadaj swoim nazwom wymowne imiona, gdy robisz coś niebanalnego.

Jak to się kompiluje na Intel?