लूप अनचाहे प्रभावी कब होता है?

Question

Loop unwinding प्रदर्शन को अनुकूलित करने के लिए कंपाइलर की सहायता करने का एक आम तरीका है। मैं सोच रहा था कि अगर और किस हद तक प्रदर्शन लाभ क्या पाश के शरीर में है से प्रभावित है:

1. बयानों की संख्या
2. समारोह की संख्या कॉल जटिल डेटा प्रकार, आभासी तरीकों में से
3. उपयोग , आदि
4. गतिशील (डी) स्मृति

क्या नियमों का (अंगूठे के?) आप चाहे या नहीं एक प्रदर्शन महत्वपूर्ण पाश तनाव कम करने का फैसला करने के लिए प्रयोग करते हैं आवंटन? इन मामलों में आप अन्य अनुकूलन पर क्या विचार करते हैं?

Answer 1

हाथ से सामान्य अनोलिंग लूप प्रयास में लायक नहीं है। कंपाइलर बेहतर जानता है कि लक्ष्य आर्किटेक्चर कैसे काम करता है और अगर यह फायदेमंद है तो लूप को अनलॉक कर देगा।

ऐसे कोड-पथ हैं जो पेंटियम-एम प्रकार के CPU के लिए अनियंत्रित होने पर लाभान्वित होते हैं लेकिन उदाहरण के लिए कोर 2 के लिए लाभ नहीं उठाते हैं। अगर मैं हाथ से अनलॉक करता हूं तो संकलक अब निर्णय नहीं ले सकता है और मैं इष्टतम कोड से कम अंत कर सकता हूं। जैसे बिल्कुल विपरीत मैं हासिल करने की कोशिश की।

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

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

Answer 2

यह एक अनुकूलन प्रश्न है, और इस तरह अंगूठे का केवल एक नियम है: प्रदर्शन का परीक्षण करें, और एक लूप को अवांछित ऑप्टिमाइज़ेशन केवल आज़माएं यदि आपका परीक्षण दर्शाता है कि आपको इसकी आवश्यकता है। पहले कम विघटनकारी अनुकूलन पर विचार करें।

Answer 3

मेरे अनुभव, पाश तनाव मुक्त होने के लिए, और काम लेता है में प्रभावी है जब:

• केवल पाश के भीतर कुछ बयान कर रहे हैं।
• बयान अलग वैरिएबल का केवल छोटी संख्या शामिल है और कोई समारोह
• आपका संचालन पहले से ही आबंटित स्मृति पर काम कहता है (उदाहरण के लिए एक में जगह छवि परिवर्तन)

आंशिक तनाव मुक्त होने के 80 के लिए अक्सर कम काम है लाभ का%। तो एम छवि (एन एम पुनरावृत्तियों) द्वारा एन के सभी पिक्सल पर लूप करने की बजाय जहां एन हमेशा आठ पिक्सेल के प्रत्येक ब्लॉक पर लूप (एन एम/8) द्वारा विभाजित होता है। यह विशेष रूप से कुशल है यदि आप कुछ ऑपरेशन परफॉर्म कर रहे हैं जो कुछ पड़ोसी पिक्सेल का उपयोग करता है।

मेरे पास एमएमएक्स या एसएसई निर्देशों (एक समय में 8 या 16 पिक्सेल) में हाथ-अनुकूलन पिक्सेल-वार ऑपरेशंस के बहुत अच्छे परिणाम हुए हैं, लेकिन मैंने कुछ हद तक अनुकूलित करने के लिए कुछ अनुकूलित किया है ताकि संस्करण अनुकूलित हो सके कंपाइलर द्वारा दस गुना तेज दौड़ गया।अपने कार्यस्थल पर अपने कोड के भविष्य पठनीयता दूर लाभ outweighs उत्पादन कोड में,: |

और वैसे, सबसे अधिक (सुंदर उल्लेखनीय) के लिए लूप तनाव का उदाहरण बाहर Duffs device

Answer 4

एक महत्वपूर्ण बात की जाँच पर विचार करने के लूप अनचाहे। हार्डवेयर सस्ता है, प्रोग्रामर समय नहीं है। मैं केवल लूप को अनचाहे करने की चिंता करता हूं अगर सिद्ध प्रदर्शन समस्या को हल करने का एकमात्र तरीका है (कम संचालित डिवाइस में कहें)।

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

Answer 5

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

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

चेतावनी का एक नोट हालांकि, एक लूप को अनलॉक करना अनुकूलित करते समय अंतिम उपाय होना चाहिए। यह आपके कोड को उस स्तर पर बदल देता है जो इसे अनजान बनाता है और इसे पढ़ने वाला कोई व्यक्ति आपको और आपके परिवार को बाद में स्नैप कर सकता है। यह जानकर, इसे लायक बनाएं :)

मैक्रोज़ का उपयोग कोड को और अधिक पठनीय बनाने में बहुत मदद कर सकता है और यह अनियंत्रित अनियंत्रित कर देगा।

उदाहरण: एक असंबंधित नोट पर

#define UNROLL (i) \ 
    a+=(ptr[i]) << 8; \ 
    a-=(ptr[i-k]) << 8; 


for(int i=0; i<32; i++) 
{ 
    UNROLL(i); 
    UNROLL(i+1); 
    UNROLL(i+2); 
    UNROLL(i+3); 
    UNROLL(i+4); 
    UNROLL(i+5); 
    UNROLL(i+6); 
    UNROLL(i+7); 
} 

लेकिन अभी भी कुछ हद तक संबंधित, यदि आप वास्तव में गिनती निर्देश तरफ जीतना चाहते हैं, सुनिश्चित करें कि सभी स्थिरांक प्राप्त करते हैं:

for(int i=0; i<256; i++) 
{ 
    a+=(ptr + i) << 8; 
    a-=(ptr + i - k) << 8; 
    // And possibly some more 
} 

को उतारना कर सकते हैं आपके कोड में जितना संभव हो उतना कम से कम एकीकृत करें ताकि आप निम्नलिखित असेंबली के साथ समाप्त न हों:

// Bad 
MOV r1, 4 
// ... 
ADD r2, r2, 1 
// ... 
ADD r2, r2, 4 

बजाय:

// Better 
ADD r2, r2, 8 

आमतौर पर, गंभीर compilers आप चीजों को इस तरह का के खिलाफ की रक्षा, लेकिन सभी इच्छा। उन '#define', 'enum' और 'static const' को आसान रखें, सभी कंपाइलर स्थानीय 'कॉन्स्ट' चर को अनुकूलित नहीं करेंगे।

Answer 6

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

बहुत अधिक चीज जो वास्तव में अनियंत्रण से लाभ प्राप्त कर सकती है वह कुछ है जैसे memcpy(), जहां लूप बॉडी सिर्फ बाइट को दूसरे स्थान से दूसरे स्थान पर ले जा रहा है --- यही कारण है कि कई सी & सी ++ कंपाइलर्स स्वचालित रूप से इनलाइनिंग कर रहे हैं और पिछले दशक के लिए memcpy अनलॉकिंग।

Answer 7

ये अनुकूलन सीपीयू पर अत्यधिक निर्भर हैं, कोड को निष्पादित किया गया है और संकलक द्वारा किया जाना चाहिए, लेकिन यदि आप ऐसे कंपाइलर लिख रहे हैं, तो आप इंटेल दस्तावेज़ Intel(R) 64 and IA-32 Architectures Optimization Reference Manual अनुभाग 3.4.1.7 पर एक नज़र डालना चाहेंगे :

• उतारना छोटे छोरों पाश के निष्पादन के समय के कम से कम 10% के लिए शाखा और प्रेरण चर खातों (आम तौर पर) के ऊपर जब तक।

• अनलॉकिंग लूप को अत्यधिक से बचें; यह ट्रेस कैश या निर्देश कैश फेंक सकता है।

• अनलॉक लूप जिन्हें अक्सर निष्पादित किया जाता है और 16 या उससे कम तक इंटरैक्शन की संख्या को कम करने के लिए अनुमानों की अनुमानित संख्या होती है। ऐसा तब तक करें जब तक कि यह कोड आकार बढ़ाता है ताकि कार्य सेट अब ट्रेस या निर्देश कैश में फिट न हो। यदि लूप बॉडी में एक से अधिक सशर्त शाखा होती है, तो अनलोल करें ताकि पुनरावृत्तियों की संख्या 16/(# कंडेंशनल शाखाएं) हो।

आप मुफ्त here के लिए हार्ड कॉपी भी ऑर्डर कर सकते हैं।

Answer 8

मैनुअल लूप अनचाहे केवल सबसे छोटी छोटी लूप के लिए उपयोगी है।

while(first != last && !(*first == val)) 
    ++first; 

मैंने देखा:

एक संदर्भ बिन्दु के रूप में, सी ++ ग्राम में मानक पुस्तकालय ++ पूरे स्रोत में ठीक दो छोरों, जिसके साथ और विधेय के बिना 'खोज' समारोह को लागू है, जो की तरह लग रहे unrolls इन पर, और अन्य, loops, और केवल loops के लिए फैसला किया यह छोटा यह करने लायक था।

बेशक, सबसे अच्छा जवाब केवल उन लूपों को अनलॉक करना है जहां आपका प्रोफाइलर दिखाता है कि ऐसा करने में उपयोगी है!

Answer 9

यदि आपने सबकुछ संभव किया है, और यह आपका शेष हॉटस्पॉट है, और लूप के अंदर लगभग कुछ भी नहीं है, तो अनलॉकिंग समझ में आता है। वे बहुत सारे "ifs" हैं। यह सत्यापित करने के लिए कि क्या यह आपका अंतिम विकल्प है, try this

Answer 10

मेरे अनुभव से लूप अनचाहे मेरे इंटेल i7 cpu पर SEE के उपयोग के बिना 20% से 50% प्रदर्शन ला सकता है।

एकल ऑपरेशन के साथ सरल पाश के लिए, एक सशर्त कूद और लूप में एक वृद्धि का ओवरहेड होता है। यह एक कूद और वृद्धि के लिए कई ऑपरेशन करने के लिए प्रभावशाली हो सकता है। प्रभावशाली पाश खोलने का उदाहरण कोड का पालन कर रहा है:

बिना किसी अवांछित के निम्नलिखित कोड में एक तुलना के ऊपरी हिस्से में + एक जुम्ब + एक वृद्धि प्रति एक ऑपरेशन है। इसके अलावा सभी ऑपरेशन को पिछले परिचालनों के परिणाम की प्रतीक्षा करनी है।

template<class TData,class TSum> 
inline TSum SumV(const TData* pVec, int nCount) 
{ 
    const TData* pEndOfVec = pVec + nCount; 
    TSum nAccum = 0; 

    while(pVec < pEndOfVec) 
    { 
     nAccum += (TSum)(*pVec++); 
    } 
    return nAccum; 
} 

और unwinded कोड में, एक की भूमि के ऊपर तुलना + एक jumb + एक प्रति चार योग आपरेशन वेतन वृद्धि है। फ़्यूथरमोर में बहुत सारे ऑपरेशन हैं जिन्हें पिछले ऑपरेशन के परिणाम की प्रतीक्षा करने की आवश्यकता नहीं है और संकलक द्वारा बेहतर अनुकूलित किया जा सकता है।

template<class TData,class TSum> 
inline TSum SumV(const TData* pVec, int nCount) 
{ 
    const TData* pEndOfVec = pVec + nCount; 
    TSum nAccum = 0; 

    int nCount4 = nCount - nCount % 4; 
    const TData* pEndOfVec4 = pVec + nCount4; 
    while (pVec < pEndOfVec4) 
    { 
     TSum val1 = (TSum)(pVec[0]); 
     TSum val2 = (TSum)(pVec[1]); 
     TSum val3 = (TSum)(pVec[2]); 
     TSum val4 = (TSum)(pVec[3]); 
     nAccum += val1 + val2 + val3 + val4; 
     pVec += 4; 
    }  

    while(pVec < pEndOfVec) 
    { 
     nAccum += (TSum)(*pVec++); 
    } 
    return nAccum; 
}