c++ - सरल, आभासी, पर्यवेक्षक-प्रकार का सबसे तेज क्रियान्वयन, सी++ में पैटर्न?




enums virtual-functions (2)

अगर आपको वास्तव में आभासी प्रेषण की आवश्यकता होती है , तो अलग-अलग व्युत्पन्न प्रकारों के ऑब्जेक्ट की सूची पर एक ही आभासी विधि के लिए प्रेषण को गति देने के लिए एक विधि का उपयोग करना है जिसे मैं टाइप-अनस्विचिंग कहूँगा

कुछ हिस्सों को समान रूप से लूप से हटाना , यह एक एकल लूप को रूपांतरित करता है, ताकि हर वस्तु पर एन ऑब्ज़ (एन समर्थित प्रकारों के लिए) में विधि बुलाया जा सके, जो प्रत्येक विशिष्ट प्रकार के सभी ऑब्जेक्ट्स पर विधि कॉल करते हैं। यह अप्रत्याशित आभासी प्रेषण की प्राथमिक लागत से बचा जाता है: शाखा गलत-पूर्वानुमान जो कि वीटेल में एक अज्ञात, अप्रत्याशित कार्य के अप्रत्यक्ष कॉल द्वारा निहित है।

इस तकनीक के सामान्य कार्यान्वयन में वस्तुओं के प्रकार को विभाजित करने के लिए पहला पास शामिल है: इस विभाजन के बारे में जानकारी दूसरे पास के द्वारा उपयोग की जाती है जिसमें प्रत्येक प्रकार 1 के लिए अलग-अलग लूप हैं, विधि बुलाते हैं। यह आम तौर पर किसी भी अप्रत्याशित शाखाओं को शामिल नहीं करता है, अगर सावधानीपूर्वक लागू किया जाता है

B और C के दो व्युत्पन्न वर्गों के मामले में आप टाइप की जानकारी को स्टोर करने के लिए बस एक बिटमैप का उपयोग कर सकते हैं। प्रश्न में दिए गए कोड से प्रकार A , B , C का उपयोग करते हुए यहां एक उदाहरण कार्यान्वयन है:

void virtual_call_unswitch(std::vector<A*>& vec) {

    // first create a bitmap which specifies whether each element is B or C type
    std::vector<uint64_t> bitmap(vec.size() / 64);

    for (size_t block = 0; block < bitmap.size(); block++) {
        uint64_t blockmap = 0;
        for (size_t idx = block * 64; idx < block * 64 + 64; idx++) {
            blockmap >>= 1;    
            blockmap |= (uint64_t)vec[idx + 0]->typecode_ << 63;
        }
        bitmap[block] = blockmap;
    }

    // now loop over the bitmap handling all the B elements, and then again for all the C elements

    size_t blockidx;
    // B loop
    blockidx = 0;
    for (uint64_t block : bitmap) {
        block = ~block;
        while (block) {
            size_t idx = blockidx + __builtin_ctzl(block);
            B* obj = static_cast<B*>(vec[idx]);
            obj->Update();
            block &= (block - 1);
        }
        blockidx += 64;
    }

    // C loop
    blockidx = 0;
    for (uint64_t block : bitmap) {
        while (block) {
            size_t idx = blockidx + __builtin_ctzl(block);
            C* obj = static_cast<C*>(vec[idx]);
            obj->Update();
            block &= (block - 1);
        }
        blockidx += 64;
    }
}

यहां, typecode में एक आम फ़ील्ड है जो ऑब्जेक्ट प्रकार, B लिए 0 और C लिए 1 को पहचानता C । प्रकार के अनुसार वर्गीकरण को संभव बनाने के लिए कुछ समान होना आवश्यक है (यह एक आभासी कॉल नहीं हो सकता, क्योंकि एक अप्रत्याशित कॉल करने से हम पहली जगह से बचने का प्रयास कर रहे हैं)।

उपरोक्त शो का एक थोड़ा अनुकूलित संस्करण, सादे लगभग प्रेषित पाश के बिना अनिर्धारित संस्करण के लिए 3.5% की गति के बारे में, आभासी संस्करण प्रति प्रेषण के लगभग 19 चक्रों में और लगभग 5.5 के आस-पास संस्करण में घड़ी के साथ। पूर्ण परिणाम:

-----------------------------------------------------------------------------
Benchmark                                      Time           CPU Iterations
-----------------------------------------------------------------------------
BenchWithFixture/VirtualDispatchTrue       30392 ns      30364 ns      23033   128.646M items/s
BenchWithFixture/VirtualDispatchFakeB       3564 ns       3560 ns     196712   1097.34M items/s
BenchWithFixture/StaticBPtr                 3496 ns       3495 ns     200506    1117.6M items/s
BenchWithFixture/UnswitchTypes              8573 ns       8571 ns      80437   455.744M items/s
BenchWithFixture/StaticB                    1981 ns       1981 ns     352397    1.9259G items/s

VirtualDispatchTrue एक प्रकार की एक सूचक पर सरल लूप कॉलिंग Update() :

for (A *a : vecA) {
    a->Update();
}

VirtualDispatchFakeB सूचक को कॉल करने से पहले B* (चाहे अंतर्निहित प्रकार क्या है) को सूचक देता है Update() चूंकि B::Update() अंतिम है, कंपाइलर पूरी तरह डी-वर्चुअलाइज करना और कॉल को इनलाइन कर सकता है। बेशक, यह बिल्कुल सही काम नहीं कर रहा है: यह किसी C ऑब्जेक्ट्स को B रूप में इलाज कर रहा है और इसलिए गलत पद्धति (और पूरी तरह से यूबी) को बुला रहा है - लेकिन यह अनुमान लगाने के लिए है कि आप कितनी तेजी से पॉइंटर्स के वेक्टर पर तरीकों को कॉल कर सकते हैं अगर हर ऑब्जेक्ट एक ही स्थिर रूप से ज्ञात प्रकार था

for (A *a : vecA) {
    ((B *)a)->Update();
}

StaticBPtr एक std::vector<B*> से std::vector<A*> StaticBPtr iterates। जैसा कि अपेक्षित प्रदर्शन ऊपर "नकली बी" कोड के समान है, चूंकि Update() लिए लक्ष्य स्थिर रूप से ज्ञात है और पूरी तरह से लचीलापन है। यह एक विवेक जांच के रूप में यहां है

UnswitchTypes प्रकार ऊपर वर्णित चाल से हटाना चाल है।

StaticB एक std::vector<B> पर पुनरावृत्त करता है यह है कि, B ऑब्जेक्ट्स को पॉइंटर्स के सदिश की बजाय B ऑब्जेक्ट की गई वस्तुओं को आवंटित किया जाता है। यह एक स्तर के अविश्वास को दूर करता है और इस ऑब्जेक्ट लेआउट 2 के लिए सर्वोत्तम केस जैसा कुछ दिखाता है।

पूर्ण स्रोत उपलब्ध है

सीमाएं

साइड इफेक्ट्स और ऑर्डर

इस तकनीक के साथ मुख्य सीमा यह है कि Update() कॉल के क्रम में कोई फर्क नहीं होना चाहिए। जबकि Update() अभी भी प्रत्येक ऑब्जेक्ट पर एक बार कहा जाता है, ऑर्डर में स्पष्ट रूप से बदल दिया गया है। जब तक ऑब्जेक्ट किसी भी अस्थिर वैश्विक या साझा स्थिति को अद्यतन नहीं करता है, तब तक यह संतुष्ट करना आसान होना चाहिए।

दो प्रकार के लिए समर्थन करता है

उपरोक्त कोड केवल दो प्रकार का समर्थन करता है, बिटमैप के उपयोग के आधार पर रिकॉर्ड प्रकार की जानकारी दर्ज करता है।

इस प्रतिबंध को हटाने में काफी आसान है सबसे पहले, बिटमैप दृष्टिकोण को बढ़ाया जा सकता है। उदाहरण के लिए, 4 प्रकारों का समर्थन करने के लिए, दो समान बिटमैप बनाए जा सकते हैं, जिसके लिए प्रत्येक बिटमैप के संबंधित बिट्स को 2-बिट फ़ील्ड प्रकार के एन्कोडिंग के लिए आवश्यक है। लूप समान होते हैं, सिवाय इसके कि बाहरी लूप में वे & और बिटमैप उन सभी तरीकों से जो सभी 4 प्रकारों से अधिक है। उदाहरण के लिए:

// type 1 (code 11)
for (size_t i = 0; i < bitmap1.size(); i++) {
        block = bitmap1[i] & bitmap2[i];
        ...
}


// type 2 (code 01)
for (size_t i = 0; i < bitmap1.size(); i++) {
        block = ~bitmap1[i] & bitmap2[i];
        ...
}

...

एक अन्य दृष्टिकोण बिटमैप का बिल्कुल उपयोग नहीं करना है, बल्कि केवल प्रति प्रकार के अनुक्रमित सरणी को संग्रहित करना है। सरणी में प्रत्येक इंडेक्स मास्टर ऑरेंज में उस प्रकार के ऑब्जेक्ट को इंगित करता है। मूलतः यह टाइप-कोड पर 1-पास के रेडिक्स सॉर्ट है। यह संभवतः टाइप सॉर्टिंग पार्ट को थोड़ी धीमी बना देता है, लेकिन संभवतः लूप ctz लॉजिक ( x & (x - 1) और ctz सामान गायब हो जाता है, जो कि एक और ctz की लागत पर x & (x - 1) ctz

समर्थित प्रकार की निश्चित संख्या

उपरोक्त कोड एक निश्चित संख्या के संकलन समय ज्ञात प्रकारों (अर्थात्, B और C ) का समर्थन करता है। यदि एक नया प्रकार पेश किया जाता है, तो उपरोक्त कोड या तो तोड़ देगा और निश्चित रूप से इन नए प्रकारों पर Update() को कॉल करने में विफल होगा।

हालांकि, यह अज्ञात प्रकारों के लिए समर्थन जोड़ने के लिए सरल है। बस सभी अज्ञात प्रकार के समूह, और फिर उन प्रकारों के लिए केवल, पाश के भीतर एक पूर्ण आभासी प्रेषण करें (यानी, Update() A* ) सीधे A* )। आप पूरी कीमत का भुगतान करेंगे, लेकिन केवल उन प्रकारों के लिए जिन्हें आपने स्पष्ट रूप से समर्थन नहीं किया था! इस तरह से, तकनीक आभासी प्रेषण तंत्र की व्यापकता को पुनर्प्राप्त करती है।

1 दरअसल, आपको केवल एक ही प्रकार की एक पाश की आवश्यकता होती है, जो सभी आभासी पद्धतियों के समान कार्यान्वयन साझा करते हैं , हालांकि यह सामान्य तरीके से लागू करना मुश्किल हो सकता है क्योंकि यह जानकारी आसानी से उपलब्ध नहीं है। उदाहरण के लिए अगर कक्षाएं Y और Z दोनों X से प्राप्त होती हैं, लेकिन X से कुछ आभासी पद्धति के क्रियान्वयन को न तो ओवरराइड करते हैं, तो सभी X , Y और Z को उसी लूप द्वारा नियंत्रित किया जा सकता है।

2 "ऑब्जेक्ट लेआउट" के द्वारा मेरा मतलब है कि B ऑब्जेक्ट्स अभी भी आभासी तरीके हैं और इसलिए एक vtable है। यदि आप सभी आभासी विधियों को निकालते हैं और vtable से छुटकारा पाने के लिए, चीजें बहुत तेजी से बढ़ती हैं, क्योंकि कंपाइलर फिर कॉम्पैक्ट रूप से व्यवस्थित क्षेत्रों के अतिरिक्त वेक्टर बनाते हैं। वोटेबल अप खराब करता है

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

निम्न कोड का पैटर्न कम से कम रीडायरेक्शन / ऑपरेशन के साथ कैसे लागू किया जा सकता है?

यह मानक C ++ में किया जाना चाहिए, 17 तक।

class A{
    virtual void Update() = 0; // A is so pure *¬*
};

class B: public A
{
    override void Update() final
    {
        // DO B STUFF
    }
}

class C: public A
{
    override void Update() final
    {
        // DO C STUFF
    }
}

// class...

int main()
{
    std::vector<A*> vecA{};

    // Insert instances of B, C, ..., into vecA

    for(auto a: vecA) // This for will be inside a main loop
        a->Update(); // Ridiculous amount of calls per unit of time

    // Free memory
}

पीएस: अगर एन्यूम, स्विच और मैक्रोज़ वास्तव में सबसे अच्छा विकल्प है, तो मुझे लगता है कि मैं बस मेरी कैश को ताज़ा करने की कोशिश करूँगा और बेहतर डिज़ाइन के साथ आना चाहूंगा।

पीएसएस: मुझे पता है कि यह माइक्रो-ऑप्टिमाइज़ेशन है ... अरे, मुझे नैनो की ज़रूरत है या पिको भी इसका अनुकूलन करने की ज़रूरत है, इसलिए मैं बस किसी भी उपयोगितावादी प्रतिक्रिया को नजरअंदाज कर दूँगा जो शायद ऊपर आ सकें।


पहली टिप्पणी के रूप में, आपके पास एक XY समस्या है छंटाई / क्रमिकरण ठीक है, और आपके पास कई ऑब्जेक्ट हैं, बहुत भिन्न कक्षाएं नहीं हैं, और उन प्रकारों को समर्थन देने की कोई ज़रूरत नहीं है, जो आपके कोड को समय संकलित करने के बारे में नहीं जानते हैं। बहुरूपता + आभासी विरासत गलत विकल्प है

इसके बजाय, एन अलग-अलग कंटेनर का उपयोग करें, प्रत्येक प्रकार के ऑब्जेक्ट के लिए, बिना किसी आक्षेप के। कंपाइलर इनलाइन B::Update() को सभी B ऑब्जेक्ट्स पर लूप में दे देना बेहतर है । (एक सदस्य int बढ़ाने के नीचे के तुच्छ उदाहरण के लिए, एएसएम को देखने से मेरा स्थिर प्रदर्शन विश्लेषण स्काईलेक पर 24 घंटे के तेजी से एल 1 डी कैश में गर्म डेटा के साथ रखता है। एवीएक्स 2 ऑटो-वेक्टर बनाम बनाम call लूप में वास्तव में है विशाल।)

अगर वस्तुओं के बीच कुछ आवश्यक ऑर्डर होती हैं, जिसमें विभिन्न प्रकार के ऑब्जेक्ट्स शामिल होते हैं, तो किसी प्रकार के बहुरूपता या मैनुअल डिस्पैचिंग उचित होगा। (उदाहरण के लिए यदि यह तय किया गया कि आपने किस ऑर्डर को vecA में संसाधित किया है, तो सभी C ऑब्जेक्ट्स से अलग सभी B ऑब्जेक्ट्स को अलग रखना ठीक नहीं होगा।)

यदि आप प्रदर्शन के बारे में ध्यान रखते हैं, तो आपको यह समझना होगा कि स्रोत को बड़ा बनाने से एम्पल आउटपुट में कंपाइलर के लिए चीजें सरल हो सकती है। आंतरिक लूप के अंदर प्रत्येक ऑब्जेक्ट के प्रकार के आधार पर जांच / प्रेषण महंगा है। किसी ऑब्जेक्ट के ऑब्जेक्ट पर डिस्पैच करने के लिए फ़ंक्शन पॉइंटर या एउमंड के किसी भी प्रकार का उपयोग आसानी से शाखा की गलतफहमी से पीड़ित हो सकता है जब आपके पास विभिन्न ऑब्जेक्ट्स का मिश्रण होता है।

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

एक अलग प्रकार के प्रत्येक कंटेनर के लिए एक अलग लूप को लिखना एक प्रकार का लूप है जिसमें आंतरिक लूप के प्रकार को प्रेषित करने के बाद विभिन्न प्रकारों पर पूरी तरह से लूप को अनारोल्ड किया जाता है। संकलक को कॉल करने के लिए यह आवश्यक है, जो आप चाहते हैं यदि प्रत्येक प्रकार के बहुत सारे ऑब्जेक्ट हैं। इनलाइनिंग, ऑब्जेक्ट्स के रजिस्टरों में स्थिरांक रखने देती है, कई ऑब्जेक्ट में सिम ऑटो-वेक्टरिंग को सक्षम करती है, और केवल वास्तविक फ़ंक्शन कॉल के ओवरहेड से बचा जाता है। (रजिस्टरों के फोन और फैल / पुनः लोड दोनों ही कॉल करें।)

आप सही थे कि अगर आपको प्रति-ऑब्जेक्ट प्रेषण की ज़रूरत होती है , तो C ++ आभासी फ़ंक्शन यह प्राप्त करने का एक शानदार तरीका है जब आप final ओवरराइड का उपयोग कर रहे हैं आप एक ही क्रम लागत का भुगतान कर रहे हैं जो कि आपके कोड को मनमाना आकार के नए व्युत्पन्न वर्गों का समर्थन करने देगा, जो उसे समय के संकलन के बारे में नहीं पता था, लेकिन उस से कोई लाभ प्राप्त नहीं कर रहा था

वर्चुअल डिस्पैच केवल आपरेशन के स्तर के साथ काम करता है (जैसे आपके द्वारा उपयोग किए जाने वाले पॉइंटर्स का वेक्टर), जिसका मतलब है कि आपको किसी तरह ऑब्जेक्ट टू ऑब्जेक्ट्स को प्रबंधित करने की आवश्यकता है, जैसे वे vector<B> poolB और vector<C> poolC से आवंटित करके। vector<C> poolC हालांकि मुझे यकीन नहीं है कि vector<> अधिकांश कार्यान्वयन vector<> realloc() उपयोग करें जब उन्हें बढ़ने की आवश्यकता होती है; new/delete एपीआई में एक realloc नहीं है, इसलिए vector वास्तव में मौजूदा आवंटन को बढ़ाने के बजाय हर समय इसकी प्रतिलिपि बना सकता है। जांचें कि आपका सी ++ कार्यान्वयन क्या करता है, चूंकि यह मॉलोक / रीअलॉक के साथ आप क्या कर सकते हैं इसके मुकाबले चूसना चाहिए।

और बीटीडब्लू, आवंटन / डीओलोकेशन के लिए अतिरिक्त ओवरहेड के साथ आरएआई के साथ new / delete जाने के लिए संभव होना चाहिए, जब तक कि आपकी सभी कक्षाएं क्षुधा से विनाशकारी नहीं होनी चाहिए। (लेकिन ध्यान रखें कि unique_ptr पॉइंटर्स के वेक्टर के उपयोग के लिए अन्य ऑप्टिमाइजेशन को पराजित कर सकता है )। std::unique_ptr चेतावनी देता है कि यह यूबी को आधार वर्ग में एक संकेतक के माध्यम से नष्ट करने के लिए है, इसलिए आपको अपना स्वयं रोल करना पड़ सकता है फिर भी, जीसीसी पर x86-64, sizeof(unique_ptr<class C>) केवल 8 है, इसलिए इसमें केवल एक पॉइंटर सदस्य है। लेकिन जो कुछ भी, छोटे वस्तुओं के अलग-अलग zillions आवंटित करते हैं तो ऐसा पहली जगह में ऐसा नहीं करते

यदि आपको शीर्षक की तरह किसी तरह की प्रेषण की आवश्यकता होती है तो पूछता है

यदि ऑब्जेक्ट सभी समान आकार हैं, तो आप वास्तव में ऑब्जेक्ट्स पर लूप चाहते हैं, पॉइंटर्स-टू ऑब्जेक्ट नहीं । यह संकेतक के एक सदिश के अतिरिक्त कैश पदचिह्न से बचना होगा, और यह निष्पादन इकाइयों को व्यस्त रखने के लिए आउट-ऑफ-ऑर्डर निष्पादन को छिपाने के लिए अतिरिक्त सूचक-पीछा विलंबता से बचा जाता है। लेकिन सी ++ वर्चुअल union upoly { B b; C c; } poly_array[1024]; लिए बहुरूपता पाने के लिए कोई मानक-अनुपालन तरीका प्रदान नहीं करता है union upoly { B b; C c; } poly_array[1024]; union upoly { B b; C c; } poly_array[1024]; आप इसे अपने आप को reinterpret_cast<> साथ एक तरह से हैक कर सकते हैं जो संभवत: x86-64 जीसीसी पर काम करता है, लेकिन आपको संभवतः नहीं करना चाहिए। @ बीऑनरोप का अनुसरण करें देखें: बहुउपयोगी प्रकारों के लगातार भंडारण । (एक पुरानी क्यू एंड ए: सी ++ सरणी में वस्तु का बहुरूपता )

यदि आपको इसकी ज़रूरत है, तो फ़ंक्शन पॉइंटर्स की तालिका को सूचकांक (या एक switch() उपयोग करें, यदि आपके फ़ंक्शंस इनलाइन कर सकते हैं) के लिए सबसे अधिक प्रदर्शन का तरीका संभवतः स्वयं को बनाना होगा। यदि आपके फ़ंक्शंस इनलाइन नहीं हैं, फ़ंक्शन-कॉल case एक गुच्छा पर switch() , आमतौर पर फ़ंक्शन पॉइंटर्स की मेज पर ऑप्टिमाइज़ नहीं करता है भले ही उनके पास एक ही तर्क (या कोई आर्ग्स) न हो। आपको आम तौर पर एक अप्रत्यक्ष call करने की बजाए कॉल निर्देशों के ब्लॉक पर एक छलांग टेबल मिलता है। तो हर प्रेषण में एक अतिरिक्त छलांग है।

सी ++ 17 std::visit std::variant<B, C> (बी और सी के लिए गैर-आभासी विरासत का उपयोग करके) आपको एक आंतरिक enum आधार पर प्रेषण करना लगता है। std::visit , दोनों को इनलाइन करने और सशर्त शाखा का उपयोग करने के बजाय केवल 2 संभावित प्रकारों के साथ प्रेषण करने के लिए अपनी कूद तालिका का उपयोग करता है। उसे "अपरिभाषित" स्थिति के लिए हर समय जांचना पड़ता है। यदि आप मैन्युअल रूप से B *tmp = std::get_if<B>(&my_variant) , और एक __builtin_unreachable() जीसीसी को बताते हैं कि nullptr संभावना नहीं है, तो आप अच्छे कोड प्राप्त कर सकते हैं। लेकिन उस बिंदु पर आप अपने खुद के struct polymorph { enum type; union { B b; C c; }; }; रोल कर सकते हैं struct polymorph { enum type; union { B b; C c; }; }; struct polymorph { enum type; union { B b; C c; }; }; (गैर-वर्चुअल फ़ंक्शंस के साथ) यदि आपको "अपरिचालित" स्थिति की आवश्यकता नहीं है संबंधित: एक सरणी में वस्तु का सी ++ बहुरूपता

इस मामले में आपके पास केवल एक फ़ंक्शन है, ताकि आप सदस्य के रूप में प्रत्येक ऑब्जेक्ट के अंदर फ़ंक्शन पॉइंटर डाल सकते हैंvoid (*m_update)(A* this_object) तरह void (*m_update)(A* this_object) । कॉलर में ऑब्जेक्ट को ऑब्जेक्ट को void* या A* , क्योंकि यह एक गैर सदस्यीय फ़ंक्शन है। फ़ंक्शन के कार्यान्वयन को reinterpret_cast<C*>(this_object) ( dynamic_cast नहीं: हम सी ++ के उपयोग नहीं कर रहे हैं, हमारे अपने प्रेषण कर रहे हैं)

यदि आप अन्य संदर्भों में बी और सी का उपयोग करना चाहते हैं, जहां फ़ंक्शन-पॉइंटर सदस्य कोई लाभ के लिए स्थान नहीं लेगा, तो आप फ़ंक्शन पॉइंटर्स को बेस क्लास के बजाए एक अलग कंटेनर में रख सकते हैं । तो यह for(i=0..n) funcptrs[i]( &objects[i] ); । जब तक आपका कंटेनर सिंक से बाहर नहीं निकलते, आप हमेशा एक फ़ंक्शन के लिए एक पॉइंटर गुजरते हैं जो जानता है कि इसके साथ क्या करना है। उस union {B b; C c} objects[] साथ प्रयोग करें union {B b; C c} objects[] union {B b; C c} objects[] (या एक vector<union> )

यदि आप चाहें तो void* उपयोग कर सकते हैं, खासकर यदि आप फ़ंक्शन पॉइंटर्स की एक अलग सरणी बनाते हैं फिर संघ के सदस्यों को एक आम आधार से वारिस करने की आवश्यकता नहीं है।

आप std::function<> का उपयोग करने के लिए पॉइंटर्स को सदस्य कार्यों को आवंटित कर सकते हैं, लेकिन std::function<> 86-64 जीसीसी पर जो कि 32-बाइट ऑब्जेक्ट है। यह आपके कैश पदचिह्न के लिए केवल 8-बाइट नियमित फ़ंक्शन पॉइंटर्स का उपयोग करने के लिए बेहतर है और यह कोड लिखता है जो this पॉइंटर के बराबर एक स्पष्ट पॉइंटर को पास करने के लिए जानता है।

प्रत्येक ऑब्जेक्ट में फंक्शन पॉइंटर को लगाते हुए मौजूदा आकार / संरेखण के आधार पर, एक enum या uint8_t से अधिक स्थान ले सकते हैं। फ़ंक्शन पॉइंटर्स की एक तालिका में एक छोटा पूर्णांक अनुक्रमणिका आपके ऑब्जेक्ट्स के प्रत्येक उदाहरण के आकार को कम कर सकता है, एक पॉइंटर सदस्य, विशेषकर 64-बिट लक्ष्य के लिए। छोटे ऑब्जेक्ट आसानी से कार्य पॉइंटर्स की एक सरणी सूचकांक के लिए अतिरिक्त अतिरिक्त निर्देशों के लायक हो सकते हैं, और अतिरिक्त पॉइंटर डीरेफरेंस से संभावित रूप से अधिक गलत अनुमान लगाया जा सकता है। मेमोरी / कैश की यादें अक्सर एक बाधा होती हैं

मैं मान रहा हूँ कि आपके पास प्रत्येक प्रति-उदाहरण राज्य है, भले ही आप कोई भी नहीं दिखाते हैं यदि नहीं, तो गैर-सदस्यीय कार्यों के लिए सामान्य फ़ंक्शन पॉइंटर्स की एक सदिश काफी सस्ता होगी!

उपरि तुलना:

मुझे ऐसा करने के कुछ तरीकों के लिए कंपाइलर-जेनरेट किए गए asm (जीसीसी और वर्णक लक्ष्यीकरण x86-64) पर एक नज़र आया।

Godbolt कंपाइलर एक्सप्लोरर पर x86-64 क्लैंग 5.0 से यह + asm करने के कई तरीके के लिए स्रोत । आप इसे जीसीसी, या गैर- x86 आर्किटेक्चर पर फ्लिप कर सकते हैं।

class A{
    public:
    virtual void Update() = 0; // A is so pure *¬*
};

struct C : public A {
    int m_c = 0;
    public:
    void Update() override final
    {  m_c++;  }
};
int SC = sizeof(C);  // 16 bytes because of the vtable pointer

C global_c;  // to instantiate a definition for C::Update();

// not inheriting at all gives equivalent asm to making Update non-virtual
struct nonvirt_B //: public A
{
    int m_b = 0;
    void Update() //override final
    {  m_b++;  }
};
int SB = sizeof(nonvirt_B);  // only 4 bytes per object with no vtable pointer

void separate_containers(std::vector<nonvirt_B> &vecB, std::vector<C> &vecC)
{
    for(auto &b: vecB)        b.Update();
    for(auto &c: vecC)        c.Update();   
}

क्लैंक और जीसीसी ऑटो- vecB को vecB पर लूप को समानांतर में 8 vecB तत्वों पर प्रोसेस करने के लिए, इसलिए यदि आप मेमोरी बैंडविड्थ (यानी एल 1 डी कैश में गर्म) पर बाधा उत्पन्न नहीं करते हैं, तो यह लूप प्रति घड़ी चक्र 8 तत्वों को बढ़ा सकता है। यह लूप एक vector<int> पर एक लूप के रूप में तेजी से चलता है; सब कुछ सुराग और अनुकूलित करता है और यह सिर्फ एक सूचक वृद्धि है

vecC पर लूप केवल प्रति घड़ी 1 चक्र कर सकता है , क्योंकि प्रत्येक ऑब्जेक्ट 16 बाइट्स (8 बाइट int m_c पॉइंटर, 4 बाइट int m_c , अगली संरेखण सीमा में पैडिंग के 4 बाइट्स क्योंकि सूचक की एक 8 बी संरेखण आवश्यकता है।) बिना final , कंपाइलर यह भी देखने के लिए vtable सूचक को जांचता है कि क्या यह वास्तव में एक C का उपयोग करने से पहले C::Update() , अन्यथा यह प्रेषण ऐसा लगता है कि आप struct { int a,b,c,d; } vecC[SIZE]; पर एक पाश के लिए क्या चाहते हैं struct { int a,b,c,d; } vecC[SIZE]; struct { int a,b,c,d; } vecC[SIZE]; vecC[i].c++; कर रहा है vecC[i].c++;

आखिरकार पूर्ण स्वनिर्धारितकरण की अनुमति दी गई, लेकिन हमारे डेटा को वीटेल पॉइंटर्स के साथ मिश्रित किया गया है, इसलिए कंपाइलर केवल स्केलर add [mem], 1 जो केवल 1 प्रति घड़ी पर चला सकते हैं (1 प्रति घड़ी की दुकान थ्रूपूट पर बाधा, भले ही स्टोर के आकार की परवाह किए बिना यह एल 1 डी कैश में गर्म है)। यह ज्यादातर इस उदाहरण के लिए सिम को पराजित करता है। (साथ -march=skylake-avx512 , जीसीसी और -march=skylake-avx512 कुछ हास्यास्पद फेरबदल करते हैं या इकट्ठा करते हैं / स्कैटर इकट्ठा करते हैं जो स्केलर की तुलना में भी धीमी है, पूरी ऑब्जेक्ट को लोड करने / बहाल करने और एक सदिश के साथ जोड़ने से, जो केवल int सदस्य को बदलता है। इसमें कोई अस्थिर या परमाणु सदस्य नहीं होते हैं, और AVX2 के साथ 2 प्रति घड़ी, या 4 AVX512 के साथ प्रति घड़ी में चलेंगे।) अपनी वस्तुओं को 12 बाइट्स तक बढ़ाना एक बड़ा नकारात्मक पक्ष है, यदि वे छोटे हैं और आपके पास उनमें से बहुत से

प्रति ऑब्जेक्ट एकाधिक सदस्यों के साथ, यह जरूरी नहीं कि SIMD को हराने के लिए, लेकिन यह अभी भी प्रत्येक ऑब्जेक्ट में अंतरिक्ष खर्च करता है, बस एक एन्यूम या फंक्शन पॉइंटर की तरह होता है

चूंकि आपने अलग धुरी प्रमेय का उल्लेख किया है , मुझे आशा है कि आप प्रत्येक ऑब्जेक्ट में float x,y जोड़े को संग्रहीत करने की योजना नहीं बना रहे हैं। एआरआर-ऑफ-स्ट्रैक्ट्स मूल रूप से सिम के लिए बेकार हैं, क्योंकि उसी ऑब्जेक्ट के लिए y साथ x का उपयोग करने के लिए बहुत से फेरबदल की आवश्यकता होती है । आप क्या चाहते हैं std::vector<float> x, y या समान, तो आपका सीपीयू एक रजिस्टर में 4 x मानों को लोड कर सकता है और दूसरे रजिस्टरों में 4 y मान कर सकता है। (या 8 एक बार में AVX के साथ)

स्लाइड देखें : SIMD के लिए अपने डेटा की संरचना कैसे करें, और कुछ और उन्नत सामग्री के परिचय के लिए Insomniac Games (GDC 2015) पर SIMD अधिक गाइडों के लिए एसएस टैग विकी भी देखें। इसके अलावा, x86 टैग विकी में बहुत कम स्तर की x86 अनुकूलन सामग्री है। यहां तक ​​कि अगर आप मैन्युअल रूप से कुछ भी विक्षेपित नहीं करते हैं, तो x और y लिए अलग-अलग एरे के साथ, एक अच्छा मौका है कि कंपाइलर आपके लिए स्वत: वेक्टर कर सकते हैं। (एएसएम आउटपुट, या बेंचमार्क gcc -O3 -march=native बनाम gcc -O3 -march=native -fno-tree-vectorize )। आपको कुछ प्रकार के एफपी -ffast-math लिए -ffast-math की आवश्यकता हो सकती है।

C ++ आभासी प्रेषण:

प्रश्न के रूप में जिस तरह से आप करते हैं, वस्तुतः आभासी विरासत के साथ और

std::vector<A*> vecA{};

void vec_virtual_pointers() {
    for(auto a: vecA)
        a->Update();
}

हमें इस पाश को clang5.0 -O3 -march=skylake

   # rbx = &vecA[0]
.LBB2_1:                         # do{
    mov     rdi, qword ptr [rbx]   # load a pointer from the vector (will be the this pointer for Update())
    mov     rax, qword ptr [rdi]   # load the vtable pointer
    call    qword ptr [rax]        # memory-indirect call using the first entry in the vtable
    add     rbx, 8                 # pointers are 8 bytes
    cmp     r14, rbx
    jne     .LBB2_1              # }while(p != vecA.end())

तो अंतिम फ़ंक्शन सूचक तीन आश्रित भारों की श्रृंखला के अंत में है। आउट-ऑफ-ऑर्डर एक्जीक्यूशन इस पुनरावृत्तियों के बीच ओवरलैप करने की सुविधा देता है (यदि शाखा सही तरीके से भविष्यवाणी करती है), लेकिन यह केवल ओवर-एंड के लिए कुल निर्देशों में, साथ ही साथ गलत परिपेक्षिक दंड के लिए बहुत अधिक ओवरहेड है। ( call [m] 3 यूओप्स है, इसलिए केवल लूप ही 8 यूप्स है, और स्काईलाक पर केवल 2 रुपये प्रति एक चक्र जारी कर सकता है। कॉल / रिटर्न ओवरहेड भी है। अगर कैली पूरी तरह से तुच्छ नहीं है, तो हम शायद बाधा नहीं रिटर्न पते को धक्का देने / रिक्त करने के लिए स्टोर-फॉरवर्डिंग पर, फ़ॉप कॉल के साथ लूप को रिक्त लूप से तेज़ी से कॉल करता है । (मुझे पता है कि उसी पते पर स्वतंत्र स्टोर / पुनः लोड ऑपरेशन के थ्रूपुट के बारे में कोई जानकारी नहीं है। स्काईलेक ऐसा नहीं करता है, इस पर बाधा उत्पन्न नहीं करने के लिए कि अगर बछड़ा यहाँ बहुत छोटा है।)

सी :: अद्यतन के लिए रबड़ की परिभाषा () है

C::Update():                         # @C::Update()
    inc     dword ptr [rdi + 8]
    ret

यदि कुछ को गणना करने से पहले इसे किसी भी स्थैतिक सेट करने की आवश्यकता होती है, तो यह अधिक खर्चीला नहीं होता है कि इसे इनलाइन न किया जाए। इसलिए, वर्चुअल डिस्पैच के साथ, यह संभवतः स्काईलेक पर लगभग प्रति 1 सदस्य प्रति घड़ी की बजाय 3 से 5 घड़ियों के बारे में एक पर चलता है। (या गैर-वर्चुअल class B लिए AVX2 के साथ प्रति 8 सदस्यों को जो अंतरिक्ष को बर्बाद नहीं करता है, और स्वत: वेक्टराइजेशन काम को अच्छी तरह बना देता है।) Http://agner.org/optimize/ स्काइलेक में एक 3 घड़ी call थ्रूपुट प्रति है, तो एलएडीडी कैश में डेटा गर्म है, तो 24x प्रदर्शन हानि कहने दें। बिल्कुल अलग माइक्रोआर्किटेक्चर अलग होंगे, बिल्कुल। अधिक x86 perf जानकारी के लिए x86 टैग विकी देखें।

संघ हैक:

शायद आप इसे कभी भी उपयोग नहीं करना चाहिए, लेकिन आप asm से देख सकते हैं कि यह x86-64 पर रिंगों और जीसीसी के साथ काम करेगा। मैंने यूनियनों की एक सरणी बनाई है, और इसे खत्म कर दिया है:

union upoly {
    upoly() {}   // needs an explicit constructor for compilers not to choke
     B b;
     C c;
} poly_array[1024];

void union_polymorph() {
    upoly *p = &poly_array[0];
    upoly *endp = &poly_array[1024];
    for ( ; p != endp ; p++) {
        A *base = reinterpret_cast<A*>(p);
        base->Update();           // virtual dispatch
    }
}

एबी और सी के सभी शुरू में अपने vtable है, इसलिए मुझे लगता है कि यह आम तौर पर काम करेंगे हम asm कि मूल रूप से एक ही है, कम से कम एक संकेतक के पीछा के साथ। (मैं सदिश के बजाय एक स्थैतिक सरणी का इस्तेमाल करता था, क्योंकि मैं चीजों को सरल और सी-जैसा बना रहा था, जबकि बाहर निकालने के लिए क्या करना था।

    lea     rdi, [rbx + poly_array]       ; this pointer
    mov     rax, qword ptr [rbx + poly_array]   ; load it too, first "member" is the vtable pointer
    call    qword ptr [rax]
    add     rbx, 16                       ; stride is 16 bytes per object
    cmp     rbx, 16384                    ; 16 * 1024
    jne     .LBB4_1

यह बेहतर है, और कम स्मृति को छूता है, लेकिन ओवरहेड के लिए यह थोड़ा बेहतर है।

#include <functional> से std::function

यह किसी भी तरह का कोलाज बात रख सकता है लेकिन वोलेबल डिस्पैच की तुलना में इससे भी अधिक ऊंचा है, क्योंकि इसे किसी त्रुटि-अगर-प्रयोग की स्थिति में होने की अनुमति है। इसलिए आंतरिक पाश को उस के लिए हर उदाहरण की जांच करना है, और यदि यह है तो फँस गया है। इसके अलावा, sizeof(std::function<void()>); 32 बाइट्स (x86-64 सिस्टम वी एबीआई पर) है

#include <functional>
// pretty crappy: checks for being possibly unset to see if it should throw().
std::vector<std::function<void()>> vecF{};
void vec_functional() {
    for(auto f: vecF)     f();
}

                                # do {
.LBB6_2:                                # =>This Inner Loop Header: Depth=1
    mov     qword ptr [rsp + 16], 0       # store a 0 to a local on the stack?
    mov     rax, qword ptr [rbx + 16]
    test    rax, rax
    je      .LBB6_5           # throw on pointer==0  (nullptr)
    mov     edx, 2            # third arg:  2
    mov     rdi, r14          # first arg: pointer to local stack memory (r14 = rsp outside the loop)
    mov     rsi, rbx          # second arg: point to current object in the vector
    call    rax               # otherwise call into it with 2 args
    mov     rax, qword ptr [rbx + 24]    # another pointer from the std::function<>
    mov     qword ptr [rsp + 24], rax    # store it to a local
    mov     rcx, qword ptr [rbx + 16]    # load the first pointer again
    mov     qword ptr [rsp + 16], rcx
    test    rcx, rcx
    je      .LBB6_5           # check the first pointer for null again (and throw if null)
    mov     rdi, r14
    call    rax               # call through the 2nd pointer
    mov     rax, qword ptr [rsp + 16]
    test    rax, rax
    je      .LBB6_12          # optionally skip a final call
    mov     edx, 3
    mov     rdi, r14
    mov     rsi, r14
    call    rax
.LBB6_12:                               #   in Loop: Header=BB6_2 Depth=1
    add     rbx, 32
    cmp     r15, rbx
    jne     .LBB6_2

.LBB6_13:                       # return
    add     rsp, 32
    pop     rbx
    pop     r14
    pop     r15
    ret

.LBB6_5:
    call    std::__throw_bad_function_call()
    jmp     .LBB6_16
    mov     rdi, rax
    call    __clang_call_terminate

इसलिए तीन call निर्देश तक होते हैं, जब तक कि सूचक nullptr न हो। यह आभासी प्रेषण से कहीं ज्यादा खराब दिखता है

यह डिफ़ॉल्ट- libstdc++ बजाय -stdlib=libc++ साथ थोड़ी अलग दिखता है ( https://libcxx.llvm.org/ )। लेकिन अभी भी तीन call निर्देश इनर लूप में हैं, जिसमें उन्हें छोड़ने या थ्रो करने की शर्त है।

जब तक कि कोड-जीन विभिन्न प्रकार के function<T> लिए बहुत अलग है, यदि आप अधिक कुशल विकल्प लिख सकते हैं, तो शायद यह संकेतकों के सदस्य कार्यों को देखने के लिए भी उपयुक्त नहीं है।







micro-optimization