इंटेल सी ++ कंपाइलर रिकर्सिव decltype रिटर्न संकलित करने के लिए बेहद धीमा है

Question

मैं char लेबलों की मनमानी संख्या द्वारा पैरामीट्रिज्ड अभिव्यक्तियों के लिए एक टेम्पलेट लिख रहा हूं।

एक तर्क सूची को देखते हुए, फैक्ट्री फ़ंक्शन अलग-अलग प्रकार की अभिव्यक्ति देता है कि इस प्रकार के दो तर्क हैं या वे अद्वितीय हैं या नहीं।

एक ठोस उदाहरण: मान लीजिए कि A?Expression<...> का उत्पादन करने के लिए अधिभारित "लेबल योग्य" ऑब्जेक्ट है। a, b, ... को लेबल LabelName<'a'>, LabelName<'b'>, ... के रूप में घोषित किया जाना चाहिए। फिर A(a,b,c,d)UniqueExpression<'a','b','c','d'> का उत्पादन करेगा, जबकि A(a,c,b,c) इसके बजाय RepeatedExpression<'a','c','b','c'> का उत्पादन करेगा।

इसे प्राप्त करने के लिए, मुझे ?Expression के फैक्टरी फ़ंक्शन को auto और decltype के साथ परिभाषित करना पड़ा। इसके अलावा, decltype को decltype तक कैस्केड करना है जब तक मेट्रोग्रामोग तर्कों के माध्यम से रिकर्सिंग समाप्त नहीं कर लेता है और अंततः वापसी का प्रकार तय किया जाता है। एक उदाहरण के रूप में, मैंने फैक्ट्री विधि के लिए काफी कम कोड अलग कर दिया है।

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

कारखाने कार्यक्रम में कहा जा सकता है ताकि तरह: (वास्तविक कार्यक्रम में वहाँ एक ओवरलोड operator() जो कारखाने कॉल के साथ एक और वर्ग है)

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

ऊपर कोड अपेक्षित तरीके से काम, और जीसीसी और इंटेल कंपाइलर दोनों द्वारा सही ढंग से संकलित किया गया है। अब, मैं समझता हूं कि संकलक को रिकर्सिव टेम्पलेट कटौती करने में अधिक समय लगेगा क्योंकि मैं उपयोग किए जाने वाले लेबलों की संख्या को क्रैंक करता हूं।

मेरे कंप्यूटर पर, यदि build_expression को एक तर्क के साथ बुलाया जाता है, तो औसत पर संकलित करने के लिए जीसीसी 4.7.1 लगभग 0.26 सेकेंड लेता है। संकलन समय पांच तर्कों के लिए लगभग 0.2 9 सेकेंड तक और दस तर्कों के लिए 0.62 सेकेंड तक स्केल करता है। यह सब बिल्कुल उचित है।

कहानी इंटेल कंपाइलर के साथ काफी अलग है। आईसीपीसी 13.0.1 0.35 सेकंड में एक-तर्क कोड संकलित करता है, और संकलन समय चार तर्कों के लिए काफी स्थिर रहता है। पांच तर्कों पर संकलन समय 12 सेकंड तक चला जाता है, और छह तर्कों पर यह 9600 सेकंड (यानी, 2 घंटे और 40 मिनट से अधिक) तक चलता है। कहने की जरूरत नहीं है, मैंने यह पता लगाने के लिए काफी देर तक इंतजार नहीं किया है कि सात-तर्क संस्करण को संकलित करने में कितना समय लगता है।

---

दो सवालों के तुरंत दिमाग में आते हैं:

• पुनरावर्ती decltype संकलित करने के लिए इंटेल संकलक विशेष रूप से धीमी गति से हो जाता है?

• क्या इस कोड को फिर से लिखने का कोई तरीका है जो एक ही प्रभाव को प्राप्त करने के लिए संभवतः संकलक के लिए मित्रवत है?

Answer 1

यहां पर एक स्टैब है। प्रत्येक तत्व की जोड़ी की तुलना करने के बजाय, मैं प्रकारों की सूची को क्रमबद्ध करता हूं, फिर किसी मस्तिष्क-मृत अद्वितीय एल्गोरिदम का उपयोग यह देखने के लिए करता हूं कि कोई डुप्लिकेट है या नहीं।

मैंने मर्ज प्रकार को प्रकारों पर लागू किया, क्योंकि यह मजेदार था। शायद एक बेवकूफ बबल प्रकार उचित तर्कों पर बेहतर काम करेगा।ध्यान दें कि थोड़ा सा काम हमें लंबी सूचियों पर एक विलय प्रकार करने की अनुमति देगा, और छोटी सूचियों पर बबल प्रकार (या यहां तक ​​कि सम्मिलन प्रकार) के लिए विशेषज्ञ होगा। मैं टेम्पलेट क्विकॉर्ट लिखने के लिए तैयार नहीं हूं।

यह मैं एक संकलन समय बूलियन का कहना है कि अगर वहाँ सूची में डुप्लिकेट हैं देता है। मैं फिर से चुनने के लिए enable_if का उपयोग कर सकता हूं कि मैं किस अधिभार का उपयोग करने जा रहा हूं।

ध्यान दें कि आपके समाधान में प्रत्येक चरण में टेम्पलेट रिकर्सन की एन^2 परतें शामिल हैं, जिनमें से वापसी के प्रकार को 1 चरण सरल वर्ग के प्रकार का मूल्यांकन करने की आवश्यकता होती है, और उसके बाद वापस लौटने की आवश्यकता भी होती है! यदि इंटेल कंपाइलर ज्ञापन विफल रहता है, तो आप काम की घातीय मात्रा में बात कर रहे हैं।

मैं कुछ सहायकों के साथ अपनी कक्षाओं के कुछ ही संवर्धित। मैंने LabelName के std::integral_constant से उत्तराधिकारी बनाया है, इसलिए मेरे पास उनके मूल्य पर आसान संकलन समय पहुंच है। यह सॉर्टिंग कोड को एक आसान बनाता है। मैं भी दोहराया और अद्वितीय वापसी मूल्यों से एक enum अवगत कराया तो मैं परिणाम पर सरल printf डिबगिंग कर सकते हैं।

इस काम के अधिकांश मर्ज तरह लिख रहा है - वहाँ एक मानक संकलन समय प्रकार प्रकार हम इस्तेमाल कर सकते हैं क्या है?

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

इसके अलावा मैं अपने कोड की आलोचना जोड़ना चाहते हैं: टेम्पलेट प्रोग्रामिंग प्रोग्रामिंग है - अपने typenames एक समारोह में पूर्णांक चर के लिए "i9" के माध्यम से "i1" का उपयोग करने के बराबर हैं। गैर-तुच्छ कुछ करने पर अपने टाइपनामों को सार्थक नाम दें।

यह कैसे इंटेल पर संकलित करता है?