शाखा भविष्यवाणी और शाखा लक्ष्य भविष्यवाणी अनुकूलन

Question

मेरा कोड एकाधिक (अप्रत्याशित) शाखाओं के साथ एक फ़ंक्शन पर लगातार कॉल करता है। जब मैंने प्रोफाइल किया, मैंने पाया कि यह एक मामूली बाधा है, जिसमें अधिकांश CPU समय सशर्त जेएमपी पर उपयोग किया जाता है।

निम्नलिखित दो कार्यों पर विचार करें, जहां मूल में कई स्पष्ट शाखाएं हैं।

void branch_example_original(void* mem, size_t s) 
{ 
    if(!(s & 7)) { 
     /* logic in _process_mem_64 inlined */ 
    } 
    else if(!(s & 3)) { 
     /* logic in _process_mem_32 inlined */ 
    } 
    else if(!(s & 1)) { 
     /* logic in _process_mem_16 inlined */ 
    } 
    else { 
     /* logic in _process_mem_8 inlined */ 
    } 
} 

यहां नया कार्य है, जहां मैंने बाधा उत्पन्न करने वाली शाखाओं को हटाने का प्रयास किया।

void branch_example_new(void* mem, size_t s) 
{ 
    const fprocess_mem mem_funcs[] = {_process_mem_8, _process_mem_16, _process_mem_32, _process_mem_64}; 
    const uint32_t magic = 3 - !!(s & 7) - !!(s & 3) - !!(s & 1); 
    mem_funcs[magic](mem, size >> magic); 
} 

हालांकि, जब मैं नए कोड, प्रदर्शन केवल ~ 20% की वृद्धि हुई है, और कॉल खुद (mem_funcs सरणी में एक समारोह के लिए) प्रोफाइल एक बहुत लंबे समय ले लिया।

क्या दूसरा बदलाव बस एक अधिक अंतर्निहित सशर्त है, क्योंकि सीपीयू अभी भी उस फ़ंक्शन की भविष्यवाणी नहीं कर सकता है जिसे कॉल किया जाएगा? क्या मैं यह मानने में सही हूं कि इसे शाखा लक्ष्य भविष्यवाणी के साथ करना है?

ऐसा क्यों होता है, और इसके अन्य समाधान भी हैं?

संपादित करें:

विचारों के लिए धन्यवाद, लेकिन मैं क्यों इस रूप में अच्छी तरह से होता है की एक विवरण चाहते हैं।

Answer 1

क्या दूसरा बदलाव बस एक अधिक अंतर्निहित सशर्त है, क्योंकि CPU अभी भी उस फ़ंक्शन की भविष्यवाणी नहीं कर सकता है जिसे कॉल किया जाएगा? क्या मैं में सही मान रहा हूं कि इसे शाखा लक्ष्य पूर्वानुमान के साथ करना है?

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

जैसा कि मैंने एक टिप्पणी में सुझाव दिया है, यदि आप एक वेक्टरकृत लूप के चारों ओर एक स्केलर परिचय और सफाई करने के लिए अपने कोड को पुन: स्थापित करना चाहिए। जब तक आप एक गठबंधन तत्व तक नहीं पहुंच जाते तब तक परिचय तत्वों को संभालता है। क्लीनअप लूप उन मामलों को संभालता है जहां अंतिम पूर्ण वेक्टर के बाद प्रक्रिया करने के लिए छोड़े गए तत्वों की गैर-शून्य मात्रा होती है। फिर आप स्केलर लूप को फंस नहीं रहे हैं क्योंकि पहले तत्व का आकार या संरेखण आदर्श नहीं था।

---

आप क्या प्रोसेस कर रहे हैं पर निर्भर करता है, अगर यह काम करते हैं और ओवरलैप को दोहराने के लिए ठीक है, तो आप एक शाखा स्टार्टअप है कि एक असंरेखित हिस्सा है, तो बाकी गठबंधन करता है बना सकते हैं।,

// not shown: check that count >= 16 
endp = dest + count; 
unaligned_store_16B(dest); // e.g. x86 movdqu 
dest+=16; 
dest &= ~0xf; // align by 16, first aligned write overlaps by up to 15B 
for (; dest < endp-15 ; dest+=16) { 
    aligned_store_16B(dest); // e.g. x86 movdqa 
} 
// handle the last up-to-15 bytes from dest to endp similarly. 

इस पाश शाखा की असंरेखित शुरू से निपटने में आता है क्योंकि आप परवाह नहीं है कि कितना असंरेखित शुरू ओवरलैप: कुछ पुस्तकालयों शायद memset कुछ इस तरह impement।

ध्यान दें कि अधिकांश वन-बफर फ़ंक्शन दोहराने योग्य नहीं हैं, हालांकि। जैसे इन-जगह a[i] *= 2, या sum+=a[i] को दो बार एक ही इनपुट को प्रोसेस करने से बचने की आवश्यकता है। आम तौर पर स्केलर लूप के साथ जब तक आप एक गठबंधन पते तक नहीं पहुंच जाते। a[i] &= 0x7f, या maxval = max(a[i], maxval) हालांकि अपवाद हैं। दो स्वतंत्र संकेत दिए गए कि विभिन्न मात्रा द्वारा गलत संरेखित हो सकता है के साथ

---

कार्य जटिल काम कर रहे हैं। आपको सावधान रहना होगा कि मास्किंग के साथ अपने रिश्तेदार ऑफसेट को न बदलें। memcpy एक फ़ंक्शन का सबसे सरल उदाहरण है जो एक स्रोत से डेटा को एक dest buffer में संसाधित करता है। memcpy को (src+3) %16 == 0 और (dest+7) %16 ==0 पर काम करना है। जब तक आप कॉलर्स पर बाधा डाल नहीं सकते, तब तक आप सामान्य रूप से सबसे अच्छा कर सकते हैं या तो प्रत्येक लोड या प्रत्येक लूप मुख्य लूप में गठबंधन किया जाता है।

86 पर, असंरेखित कदम निर्देश (movdqu और दोस्तों) संरेखण आवश्यक संस्करण जब पता गठबंधन है के रूप में बस के रूप में तेजी से कर रहे हैं। तो आपको विशेष मामले के लिए लूप के एक अलग संस्करण की आवश्यकता नहीं है जब src और dest के समान (गलत) संरेखण होता है, और लोड और स्टोर दोनों को गठबंधन किया जा सकता है। आईआईआरसी, यह इंटेल नेहलेम और नए सीपीयू, और हाल ही में एएमडी के लिए सच है।

// check count >= 16 
endp = dest + count; 
unaligned_copy_16B(dest, src); // load with movdqu, store with movdqu 
// src+=16; dest+=16; // combine this with aligning dest, below 

dest_misalign = dest & 0xf; // number of bytes the first aligned iteration will overlap 
src += 16 - dest_misalign; // src potentially still misaligned 
dest += 16 - dest_misalign; // dest aligned 

for (; dest <= endp-16 ; src+=16, dest+=16) { 
    tmpvec = unaligned_load_16B(src); // x86 movdqu is fast if src is aligned 
    aligned_store_16B(dest, tmpvec); // x86 movdqa 
} 
// handle the last dest to endp bytes. 

---

एक गठबंधन गंतव्य शायद एक गठबंधन स्रोत की तुलना में अधिक होने की संभावना है। कोई ओवरलैपिंग बार-बार काम नहीं होता है जब हम जिस सूचक को संरेखित करते हैं वह पहले से ही गठबंधन होता है।

यदि आप memcpy नहीं कर रहे हैं, तो यह एक लाभ हो सकता है कि स्रोत गठबंधन हो ताकि लोड मेमोरी ऑपरेंड के रूप में किसी अन्य निर्देश में गुना हो। यह एक निर्देश बचाता है, और कई मामलों में आंतरिक रूप से इंटेल यूओपी भी बचाता है।

ऐसे मामले के लिए जहां src और dest के पास अलग-अलग संरेखण हैं, मैंने परीक्षण नहीं किया है कि यह गठबंधन भार और असाइन किए गए स्टोर, या अन्य तरीकों से तेज़ है या नहीं। मैंने संभावित स्टोर की वजह से गठबंधन स्टोर उठाए-> छोटे बफर के लिए लोड अग्रेषण लाभ। यदि dest बफर गठबंधन किया गया है, और केवल कुछ वैक्टर लंबे समय तक पढ़े जाएंगे, और तुरंत फिर से पढ़े जाएंगे, तो भाग से 10 गठबंधन (इंटेल एसएनबी) के लिए गठबंधन भार बंद हो जाएगा यदि लोड दो पूर्ववर्ती स्टोरों के बीच सीमा पार करता है जो ' इसे अभी तक एल 1 कैश में नहीं बनाया गया है। (यानी स्टोर अग्रेषण विफल रहता है)। इस तरह के निम्न-स्तर के विवरणों पर जानकारी के लिए http://agner.org/optimize/ देखें (esp। Microarch guide।)

अगले लूप में memcpy से लोड करने के लिए स्टोर अग्रेषण केवल तभी होता है जब बफर छोटे होते हैं (शायद 64 बी तक?) , या यदि आपका अगला लूप बफर के अंत से पढ़ना शुरू कर देता है (जो अभी भी कैश में होगा, भले ही शुरुआत पहले से ही बेदखल हो गई हो)। अन्यथा, बफर की शुरुआत में स्टोरों ने इसे स्टोर बफर से एल 1 तक बना दिया होगा, इसलिए स्टोर अग्रेषण खेल में नहीं आएगा।

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

Answer 2

आप कुछ इस तरह की कोशिश कर सकते:

switch(s & 7) { 
case 0: 
    /* _process_mem_64 */ 
    break; 
case 1: 
case 3: 
case 5: 
case 7: 
    /* _process_mem_8 */ 
    break; 
case 2: 
case 6: 
    /* _process_mem_16 */ 
    break; 
case 4: 
    /* _process_mem_32 */ 
    break; 
} 

यह एक कूद तालिका में केवल एक ही कूद शामिल है, और एक फोन अनुदेश आवश्यकता नहीं है।

Answer 3

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

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