java एक अनुक्रमित सरणी की तुलना में एक क्रमबद्ध सरणी को संसाधित करना क्यों तेज़ है?




c++ performance (17)

जैसा कि दूसरों द्वारा पहले से ही उल्लेख किया गया है, रहस्य के पीछे क्या शाखा भविष्यवाणी है ।

मैं किसी अन्य तरीके से अवधारणा को समझाते हुए कुछ जोड़ने की कोशिश नहीं कर रहा हूं। विकी पर एक संक्षिप्त परिचय है जिसमें टेक्स्ट और आरेख शामिल है। मैं नीचे स्पष्टीकरण की तरह करता हूं जो शाखा पूर्वानुमानकर्ता को सहजता से विस्तारित करने के लिए आरेख का उपयोग करता है।

कंप्यूटर आर्किटेक्चर में, एक शाखा भविष्यवाणी एक डिजिटल सर्किट है जो अनुमान लगाने की कोशिश करता है कि किस तरह से शाखा (उदाहरण के लिए एक if-then-else संरचना) निश्चित रूप से जानी जाती है। शाखा भविष्यवाणी का उद्देश्य निर्देश पाइपलाइन में प्रवाह में सुधार करना है। शाखा अनुमानक कई आधुनिक पाइपलाइन माइक्रोप्रोसेसर आर्किटेक्चर जैसे x86 में उच्च प्रभावी प्रदर्शन प्राप्त करने में महत्वपूर्ण भूमिका निभाते हैं।

दो-तरफा शाखाओं को आमतौर पर एक सशर्त कूद निर्देश के साथ लागू किया जाता है। एक सशर्त कूद या तो "नहीं लिया जा सकता" और कोड की पहली शाखा के साथ निष्पादन जारी रखता है जो सशर्त कूद के तुरंत बाद आता है, या इसे "लिया" जा सकता है और प्रोग्राम मेमोरी में एक अलग जगह पर जा सकता है जहां कोड की दूसरी शाखा है संग्रहीत। यह निश्चित रूप से ज्ञात नहीं है कि क्या सशर्त कूद लिया जाएगा या नहीं लिया जाएगा जब तक कि स्थिति की गणना नहीं की जाती है और सशर्त कूद ने निर्देश पाइपलाइन में निष्पादन चरण पारित किया है (अंजीर देखें 1)।

वर्णित परिदृश्य के आधार पर, मैंने यह दिखाने के लिए एक एनीमेशन डेमो लिखा है कि विभिन्न स्थितियों में पाइपलाइन में निर्देश कैसे निष्पादित किए जाते हैं।

  1. शाखा भविष्यवाणी के बिना।

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

उदाहरण में तीन निर्देश हैं और पहला एक सशर्त कूद निर्देश है। सशर्त कूद निर्देश निष्पादित होने तक बाद के दो निर्देश पाइपलाइन में जा सकते हैं।

3 निर्देशों को पूरा करने में 9 घड़ी चक्र लगेगा।

  1. शाखा भविष्यवाणी का प्रयोग करें और एक सशर्त कूद मत लें। आइए मान लें कि भविष्यवाणी सशर्त कूद नहीं ले रही है।

3 निर्देशों को पूरा करने में 7 घड़ी चक्र लगेगा।

  1. शाखा भविष्यवाणी का प्रयोग करें और एक सशर्त कूद लें। आइए मान लें कि भविष्यवाणी सशर्त कूद नहीं ले रही है।

3 निर्देशों को पूरा करने में 9 घड़ी चक्र लगेगा।

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

जैसा कि आप देख सकते हैं, ऐसा लगता है कि हमारे पास शाखा पूर्वानुमानकर्ता का उपयोग न करने का कोई कारण नहीं है।

यह एक साधारण डेमो है जो शाखा भविष्यवाणी के बहुत ही बुनियादी भाग को स्पष्ट करता है। यदि उन gifs परेशान हैं, तो कृपया उन्हें जवाब से हटाने के लिए स्वतंत्र महसूस करें और आगंतुक भी git से डेमो प्राप्त कर सकते हैंgit

यहां सी ++ कोड का एक टुकड़ा है जो बहुत ही असाधारण लगता है। कुछ अजीब कारणों से, डेटा को चमत्कारी रूप से क्रमबद्ध करने से कोड लगभग छः गुना तेज हो जाता है।

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • std::sort(data, data + arraySize); बिना std::sort(data, data + arraySize); , कोड 11.54 सेकंड में चलता है।
  • सॉर्ट किए गए डेटा के साथ, कोड 1.93 सेकंड में चलता है।

प्रारंभ में, मैंने सोचा कि यह सिर्फ एक भाषा या कंपाइलर विसंगति हो सकती है। तो मैंने जावा में कोशिश की।

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

कुछ हद तक समान लेकिन कम चरम परिणाम के साथ।

मेरा पहला विचार था कि सॉर्टिंग डेटा को कैश में लाती है, लेकिन फिर मैंने सोचा कि यह कितना मूर्खतापूर्ण है क्योंकि सरणी अभी उत्पन्न हुई थी।

  • क्या हो रहा है?
  • एक अनुक्रमित सरणी की तुलना में एक क्रमबद्ध सरणी को संसाधित करना क्यों तेज़ है?
  • कोड कुछ स्वतंत्र शर्तों को जोड़ रहा है, और आदेश कोई फर्क नहीं पड़ता।

शाखा-पूर्वानुमान लाभ!

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

if (expression)
{
    // Run 1
} else {
    // Run 2
}

जब भी कोई if-else\ switchकथन होता है, तो यह निर्धारित करने के लिए अभिव्यक्ति का मूल्यांकन किया जाना चाहिए कि कौन सा ब्लॉक निष्पादित किया जाना चाहिए। कंपाइलर द्वारा उत्पन्न असेंबली कोड में, सशर्त branch निर्देश डाले जाते हैं।

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

ऐसा कहा जा रहा है कि संकलक वास्तव में मूल्यांकन किए जाने से पहले परिणाम की भविष्यवाणी करने की कोशिश करता है। यह ifब्लॉक से निर्देश लाएगा , और अगर अभिव्यक्ति सच साबित हो जाती है, तो अद्भुत! हमने इसका मूल्यांकन करने के लिए समय निकाला और कोड में प्रगति की; यदि नहीं तो हम गलत कोड चला रहे हैं, पाइपलाइन फ्लश हो गई है, और सही ब्लॉक चलाया गया है।

दृश्य:

आइए मान लें कि आपको मार्ग 1 या मार्ग 2 चुनना होगा। मानचित्र को चेक करने के लिए अपने साथी की प्रतीक्षा कर रहे हैं, आपने ## पर रोक दिया है और इंतजार किया है, या आप केवल रूट 1 चुन सकते हैं और यदि आप भाग्यशाली थे (मार्ग 1 सही मार्ग है) तो बढ़िया आपको अपने साथी के लिए मानचित्र की जांच करने की प्रतीक्षा नहीं करनी पड़ी (आपने उस समय को बचाया जब वह उसे मानचित्र की जांच करने के लिए ले जाता), अन्यथा आप वापस आ जाएंगे।

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

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

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

शाखा भविष्यवाणी नामक घटना के कारण सॉर्ट किए गए सरणी को एक अनुरक्षित सरणी से तेज़ी से संसाधित किया जाता है।

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

गलत भविष्यवाणी करना पिछले चरण में वापस जाने और दूसरी भविष्यवाणी के साथ निष्पादित करने की ओर जाता है। भविष्यवाणी मानना ​​सही है, कोड अगले चरण तक जारी रहेगा। सही भविष्यवाणी होने तक गलत भविष्यवाणी एक ही चरण को दोहराने में परिणाम देती है।

आपके प्रश्न का उत्तर बहुत आसान है।

एक अनुरक्षित सरणी में, कंप्यूटर कई भविष्यवाणियां करता है, जिससे त्रुटियों में वृद्धि हुई है। जबकि, सॉर्ट किए गए में, कंप्यूटर कम भविष्यवाणियों को त्रुटियों के मौके को कम करता है। अधिक भविष्यवाणी करने के लिए अधिक समय की आवश्यकता है।

क्रमबद्ध ऐरे: सीधे सड़क

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

अनारक्षित ऐरे: घुमावदार सड़क

______   ________
|     |__|

शाखा भविष्यवाणी: अनुमान लगाया / भविष्यवाणी करना कि कौन सी सड़क सीधे है और जांच के बिना इसका पालन करती है

___________________________________________ Straight road
 |_________________________________________|Longer road

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

अपडेट करें: @Simon_Weaver ने जो कहा, उसके बाद मैं एक और तथ्य जोड़ना चाहता हूं कि ... "इससे कम भविष्यवाणियां नहीं होतीं - इससे कम गलत भविष्यवाणियां होती हैं। इसे अभी भी लूप के माध्यम से हर बार पूर्वानुमान करना पड़ता है।"


सी ++ में अक्सर उपयोग किए जाने वाले बूलियन ऑपरेशंस संकलित प्रोग्राम में कई शाखाएं उत्पन्न करते हैं। यदि ये शाखाएं लूप के अंदर हैं और भविष्यवाणी करना मुश्किल है कि वे निष्पादन को धीमा कर सकते हैं। बूलियन चर के रूप में मूल्य के साथ 8 बिट पूर्णांकों जमा हो जाती है 0के लिए falseऔर 1के लिए true

बूलियन चर अर्थ में overdetermined कर रहे हैं कि सभी ऑपरेटरों इनपुट चेक के रूप में बूलियन चर है कि अगर आदानों के अलावा कोई अन्य मान होना 0या 1, लेकिन ऑपरेटरों आउटपुट के रूप में है कि Booleans के अलावा कोई अन्य मूल्य का उत्पादन कर सकते 0या 1। यह बूलियन वैरिएबल के साथ संचालन को आवश्यकतानुसार इनपुट कम कुशल बनाता है। उदाहरण पर विचार करें:

bool a, b, c, d;
c = a && b;
d = a || b;

यह आम तौर पर निम्नलिखित तरीके से संकलक द्वारा कार्यान्वित किया जाता है:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

यह कोड इष्टतम से बहुत दूर है। गलतफहमी के मामले में शाखाओं में काफी समय लग सकता है। बूलियन ऑपरेशंस को और अधिक कुशल बनाया जा सकता है यदि यह निश्चित रूप से ज्ञात है कि ऑपरेटरों के पास कोई अन्य मूल्य नहीं है 0और 1। संकलक इस तरह की धारणा नहीं बनाते हैं कि वेरिएबल्स में अन्य मान हो सकते हैं यदि वे अनियमित हैं या अज्ञात स्रोतों से आते हैं। उपरोक्त कोड यदि अनुकूलित किया जा सकता है aऔर bमान्य मान के लिए शुरू कर दिया है या कि बूलियन उत्पादन का उत्पादन करता है, तो वे ऑपरेटरों से आते हैं। अनुकूलित कोड इस तरह दिखता है:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charबूलियन ऑपरेटर ( और ) के बजाय boolबिटवाई ऑपरेटरों ( &और |) का उपयोग करना संभव बनाने के बजाय इसका उपयोग किया जाता है । Bitwise ऑपरेटर एकल निर्देश हैं जो केवल एक घड़ी चक्र लेते हैं। OR ऑपरेटर ( ) काम करता है, भले ही और के अलावा अन्य मान हो या । एंड ऑपरेटर ( ) और विशिष्ट या ऑपरेटर ( ) असंगत परिणाम दे सकते हैं यदि ऑपरेटरों के पास अन्य मान हैं और ।&&|||ab01&^01

~नहीं के लिए इस्तेमाल नहीं किया जा सकता है। इसके बजाए, आप एक वेरिएबल पर एक बूलियन नहीं बना सकते हैं जिसे इसके साथ 0या 1XOR'ing द्वारा जाना जाता है 1:

bool a, b;
b = !a;

अनुकूलित किया जा सकता है:

char a = 0, b;
b = a ^ 1;

a && bसाथ बदला नहीं जा सकता a & bहै, तो bएक अभिव्यक्ति है, तो मूल्यांकन नहीं किया जाना चाहिए कि है aहै false( &&का मूल्यांकन नहीं होगा b, &होगा)। इसी तरह, a || bके साथ बदला नहीं जा सकता a | bहै, तो bएक अभिव्यक्ति है कि मूल्यांकन नहीं किया जाना चाहिए aहै true

ऑपरेटिंग तुलना की तुलना में ऑपरेंड वैरिएबल हैं यदि बिटवे ऑपरेटरों का उपयोग करना अधिक फायदेमंद है:

bool a; double x, y, z;
a = x > y && z < 5.0;

ज्यादातर मामलों में इष्टतम है (जब तक आप &&अभिव्यक्ति की अपेक्षा नहीं करते कि कई शाखा गलतफहमी उत्पन्न हो)।


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

if (likely( everything_is_ok ))
{
    /* Do something */
}

या इसी प्रकार:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

दोनों likely()और unlikely()तथ्य यह है कि मैक्रो जीसीसी के तरह कुछ का उपयोग करके परिभाषित कर रहे हैं में हैं __builtin_expectहालत को ध्यान में उपयोगकर्ता द्वारा उपलब्ध कराई गई जानकारी लेने के पक्ष में संकलक डालने भविष्यवाणी कोड में मदद करेगा। जीसीसी अन्य अंतर्निहितों का समर्थन करता है जो चल रहे कार्यक्रम के व्यवहार को बदल सकते हैं या कैश को साफ़ करने जैसे निम्न स्तर के निर्देशों को उत्सर्जित कर सकते हैं । उपलब्ध दस्तावेज जो उपलब्ध जीसीसी के बिल्टिन के माध्यम से जाते हैं।

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


यदि आप इस कोड के लिए और भी अनुकूलन के बारे में उत्सुक हैं, तो इस पर विचार करें:

मूल पाश से शुरू करना:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

लूप इंटरचेंज के साथ, हम इस लूप को सुरक्षित रूप से बदल सकते हैं:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

फिर, आप देख सकते हैं कि if लैंडअप के निष्पादन के दौरान सशर्त स्थिर है, तो आप बाहर निकल सकते हैं:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

फिर, आप देखते हैं कि आंतरिक लूप को एक एकल अभिव्यक्ति में ध्वस्त किया जा सकता है, यह मानते हुए कि फ़्लोटिंग पॉइंट मॉडल इसे अनुमति देता है (/ fp: फास्ट फेंक दिया गया है, उदाहरण के लिए)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

वह पहले से 100,000x तेज है


इसमें कोई संदेह नहीं है कि हम में से कुछ को कोड की पहचान करने के तरीकों में दिलचस्पी होगी जो सीपीयू की शाखा-भविष्यवाणी के लिए समस्याग्रस्त है। cachegrind टूल cachegrind में शाखा-भविष्यवाणी सिम्युलेटर है, जो --branch-sim=yes flag का उपयोग करके सक्षम है। इस प्रश्न में उदाहरणों पर इसे चलाते हुए, बाहरी लूपों की संख्या 10000 तक कम हो गई और g++ साथ संकलित, इन परिणामों को देता है:

छाँटे गए:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

अवर्गीकृत:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

cg_annotate द्वारा उत्पादित लाइन-बाय-लाइन आउटपुट में cg_annotate हम प्रश्न में लूप के लिए देखते हैं:

छाँटे गए:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

अवर्गीकृत:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

यह आपको समस्याग्रस्त रेखा को आसानी से पहचानने देता है - अनसुलझा संस्करण में if (data[c] >= 128) लाइन 164,050,007 दुर्घटनाग्रस्त सशर्त शाखाओं (बीसीएम) को कैश्रिंड के शाखा-भविष्यवाणी मॉडल के तहत उत्पन्न कर रही है, जबकि यह क्रमबद्ध संस्करण में केवल 10,006 है ।

वैकल्पिक रूप से, लिनक्स पर आप एक ही कार्य को पूरा करने के लिए प्रदर्शन काउंटर उपप्रणाली का उपयोग कर सकते हैं, लेकिन सीपीयू काउंटर का उपयोग करके देशी प्रदर्शन के साथ।

perf stat ./sumtest_sorted

छाँटे गए:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

अवर्गीकृत:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

यह dissassembly के साथ स्रोत कोड एनोटेशन भी कर सकते हैं।

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

अधिक जानकारी के लिए प्रदर्शन ट्यूटोरियल देखें।


उपरोक्त व्यवहार शाखा भविष्यवाणी के कारण हो रहा है।

शाखा भविष्यवाणी को समझने के लिए सबसे पहले निर्देश पाइपलाइन को समझना चाहिए :

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

आम तौर पर, आधुनिक प्रोसेसर में काफी लंबी पाइपलाइन होती है, लेकिन आसानी से चलिए इन 4 चरणों को केवल मानते हैं।

  1. अगर - स्मृति से निर्देश प्राप्त करें
  2. आईडी - निर्देश डीकोड करें
  3. पूर्व - निर्देश निष्पादित करें
  4. डब्ल्यूबी - सीपीयू रजिस्टर पर वापस लिखें

2 निर्देशों के लिए सामान्य रूप से 4-चरण पाइपलाइन।

उपरोक्त प्रश्न पर वापस जाने के लिए निम्नलिखित निर्देशों पर विचार करें:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

शाखा भविष्यवाणी के बिना, निम्नलिखित होगा:

निर्देश बी या निर्देश सी निष्पादित करने के लिए प्रोसेसर को तब तक इंतजार करना होगा जब तक कि निर्देश ए बी पाइपलाइन में EX चरण तक नहीं पहुंचता है, क्योंकि निर्देश बी या निर्देश सी पर जाने का निर्णय निर्देश ए के परिणाम पर निर्भर करता है। इसलिए पाइपलाइन इस तरह दिखेगा।

जब स्थिति सही हो जाती है:

जब स्थिति झूठी वापसी करती है:

निर्देश ए के परिणाम की प्रतीक्षा के परिणामस्वरूप, उपर्युक्त मामले में खर्च किए गए कुल CPU चक्र (शाखा भविष्यवाणी के बिना; सत्य और गलत दोनों के लिए) 7 है।

तो शाखा भविष्यवाणी क्या है?

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

सही अनुमान के मामले में, पाइपलाइन इस तरह कुछ दिखती है:

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

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

  1. सभी तत्व 128 से कम हैं
  2. सभी तत्व 128 से अधिक हैं
  3. कुछ शुरुआती नए तत्व 128 से कम हैं और बाद में यह 128 से अधिक हो जाते हैं

आइए मान लें कि भविष्यवाणियों को हमेशा पहले भाग पर सच्ची शाखा माननी होगी।

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

इन सभी मामलों में विफलता संख्या में बहुत कम होगी और नतीजतन, केवल कुछ ही बार आंशिक रूप से निष्पादित निर्देशों को त्यागने और सही शाखा के साथ शुरू करने की आवश्यकता होगी, जिसके परिणामस्वरूप कम CPU चक्र होंगे।

लेकिन एक यादृच्छिक unsorted सरणी के मामले में, भविष्यवाणी आंशिक रूप से निष्पादित निर्देशों को त्यागने और सही समय के साथ सही शाखा के साथ शुरू करने की आवश्यकता होगी और परिणामस्वरूप क्रमबद्ध सरणी की तुलना में अधिक CPU चक्रों में परिणाम।


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

लेकिन इस मामले में, हम जानते हैं कि मान सीमा [0, 255] में हैं और हम केवल मूल्यों की देखभाल करते हैं> = 128. इसका मतलब है कि हम आसानी से एक बिट निकाल सकते हैं जो हमें बताएगा कि हम एक मूल्य चाहते हैं या नहीं: स्थानांतरित करके सही 7 बिट्स के डेटा, हमें 0 बिट या 1 बिट के साथ छोड़ दिया गया है, और हम केवल 1 बिट होने पर मान जोड़ना चाहते हैं। आइए इसे "निर्णय थोड़ा" कहते हैं।

किसी सरणी में इंडेक्स के रूप में निर्णय बिट के 0/1 मान का उपयोग करके, हम कोड बना सकते हैं जो समान रूप से तेज़ होगा कि डेटा सॉर्ट किया गया है या सॉर्ट नहीं किया गया है। हमारा कोड हमेशा एक मूल्य जोड़ता है, लेकिन जब निर्णय बिट 0 होता है, तो हम उस मूल्य को जोड़ देंगे जहां हमें परवाह नहीं है। यहां कोड है:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

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

लेकिन मेरे परीक्षण में, एक स्पष्ट लुकअप टेबल इससे थोड़ा तेज था, संभवतः क्योंकि लुकअप टेबल में अनुक्रमण करना बिट स्थानांतरण से थोड़ा तेज था। यह दिखाता है कि मेरा कोड कैसे सेट अप करता है और लुकअप टेबल का उपयोग करता है (अकल्पनीय रूप lutसे कोड में " लुकअप टेबल " के लिए बुलाया जाता है )। यहां सी ++ कोड है:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

इस मामले में, लुकअप टेबल केवल 256 बाइट था, इसलिए यह एक कैश में अच्छी तरह फिट बैठता है और सब तेज़ थे। यदि डेटा 24-बिट मान था तो यह तकनीक अच्छी तरह से काम नहीं करेगी और हम केवल उनमें से आधा चाहते थे ... लुकअप टेबल व्यावहारिक होने के लिए बहुत बड़ी होगी। दूसरी तरफ, हम ऊपर दिखाए गए दो तकनीकों को जोड़ सकते हैं: पहले बिट्स को ऊपर ले जाएं, फिर एक लुकअप टेबल इंडेक्स करें। 24-बिट मान के लिए कि हम केवल शीर्ष आधा मान चाहते हैं, हम संभावित रूप से 12 बिट्स द्वारा डेटा को स्थानांतरित कर सकते हैं, और तालिका सूचकांक के लिए 12-बिट मान के साथ छोड़े जा सकते हैं। एक 12-बिट टेबल इंडेक्स 4096 मानों की एक तालिका का तात्पर्य है, जो व्यावहारिक हो सकता है।

संपादित करें: एक चीज जिसे मैं अंदर रखना भूल गया था।

एक ifकथन का उपयोग करने के बजाय, सरणी में अनुक्रमणित करने की तकनीक का उपयोग करने के लिए किस पॉइंटर का उपयोग करने के लिए किया जा सकता है। मैंने एक पुस्तकालय देखा जिसने बाइनरी पेड़ों को लागू किया, और दो नामित पॉइंटर्स ( pLeftऔर pRightया जो कुछ भी) के बजाय पॉइंटर्स की लम्बाई 2 सरणी थी और निर्णय लेने के लिए "निर्णय बिट" तकनीक का उपयोग किया गया था कि कौन सा अनुसरण करना है। उदाहरण के लिए, इसके बजाए:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

यह पुस्तकालय कुछ ऐसा करेगा:

i = (x < node->value);
node = node->link[i];

यहां इस कोड का एक लिंक दिया गया है: लाल ब्लैक पेड़ , कभी-कभी उलझन में


यह शाखा भविष्यवाणी के बारे में है। यह क्या है?

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

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

  • इसके अलावा, जटिल भविष्यवाणी तकनीकों में शाखाओं की भविष्यवाणी करने के लिए समय निकाला जाता है, यह 2 से 5 चक्रों से बहुत अधिक होता है - जो वास्तविक शाखाओं के निष्पादन समय के बराबर है।

  • शाखा भविष्यवाणी अनिवार्य रूप से एक अनुकूलन (न्यूनीकरण) समस्या है जहां कम से कम संभव मिस दर, कम बिजली की खपत, और न्यूनतम संसाधनों के साथ कम जटिलता प्राप्त करने के लिए जोर दिया जाता है।

वास्तव में तीन अलग-अलग शाखाएं हैं:

फॉरवर्ड सशर्त शाखाएं - रन-टाइम स्थिति के आधार पर, पीसी (प्रोग्राम काउंटर) को निर्देश स्ट्रीम में आगे एक पते पर इंगित करने के लिए बदला जाता है।

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

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

स्टेटिक / गतिशील शाखा भविष्यवाणी : स्थिर शाखा भविष्यवाणी माइक्रोप्रोसेसर द्वारा पहली बार एक सशर्त शाखा का सामना करना पड़ता है, और सशर्त शाखा कोड के कार्यान्वयन के लिए गतिशील शाखा भविष्यवाणी का उपयोग किया जाता है।

संदर्भ:


जब डेटा सॉर्ट किया जाता है तो प्रदर्शन में भारी सुधार होता है, यह कारण है कि शाखा भविष्यवाणी दंड हटा दिया गया है, जैसा कि के जवाब में खूबसूरती से समझाया गया है।

अब, अगर हम कोड देखते हैं

if (data[c] >= 128)
    sum += data[c];

हम पाते हैं कि इस विशेष का अर्थ if... else... शाखा किसी शर्त को संतुष्ट होने पर कुछ जोड़ना है। इस प्रकार की शाखा को आसानी से एक सशर्त चाल कथन में परिवर्तित किया जा सकता है, जिसे एक सशर्त चाल निर्देश में संकलित किया जाएगा: cmovl , x86 सिस्टम में। शाखा और इस प्रकार संभावित शाखा पूर्वानुमान दंड हटा दिया गया है।

C , इस प्रकार C++ , कथन, जो x86 में सशर्त चाल निर्देश में सीधे (बिना किसी अनुकूलन के) संकलित करेगा, टर्नरी ऑपरेटर है ... ? ... : ... ... ? ... : ... इसलिए हम उपरोक्त कथन को समकक्ष में फिर से लिखते हैं:

sum += data[c] >=128 ? data[c] : 0;

पठनीयता को बनाए रखने के दौरान, हम स्पीडअप कारक की जांच कर सकते हैं।

इंटेल कोर i7 -2600K @ 3.4 गीगाहर्ट्ज और विजुअल स्टूडियो 2010 रिलीज मोड पर, बेंचमार्क है (मिस्टिकियल से प्रारूपित प्रारूप):

86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

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

अब वे जेनरेट की गई x86 असेंबली की जांच करके अधिक बारीकी से देखें। सादगी के लिए, हम दो कार्य max1 और max1 2 का उपयोग करते हैं।

max1 सशर्त शाखा का उपयोग करता है if... else ... :

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 टर्नरी ऑपरेटर का उपयोग करता है ... ? ... : ... ... ? ... : ... :

int max2(int a, int b) {
    return a > b ? a : b;
}

X86-64 मशीन पर, GCC -S नीचे असेंबली उत्पन्न करता है।

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 निर्देश cmovge के उपयोग के कारण बहुत कम कोड का उपयोग करता है। लेकिन वास्तविक लाभ यह है कि jmp में शाखा कूदता, jmp शामिल नहीं है, यदि भविष्यवाणी का परिणाम सही नहीं है तो इसका महत्वपूर्ण प्रदर्शन दंड होगा।

तो एक सशर्त कदम बेहतर प्रदर्शन क्यों करता है?

एक विशिष्ट x86 प्रोसेसर में, निर्देश का निष्पादन कई चरणों में बांटा गया है। असल में, अलग-अलग चरणों से निपटने के लिए हमारे पास अलग-अलग हार्डवेयर हैं। तो हमें एक नया शुरू करने के लिए एक निर्देश के लिए इंतजार करने की प्रतीक्षा नहीं करनी है। इसे pipelining कहा जाता है।

एक शाखा मामले में, निम्नलिखित निर्देश पिछले एक द्वारा निर्धारित किया जाता है, इसलिए हम पाइपलाइनिंग नहीं कर सकते हैं। हमें या तो इंतजार करना या भविष्यवाणी करना है।

एक सशर्त चाल मामले में, निष्पादन सशर्त चाल निर्देश कई चरणों में बांटा गया है, लेकिन पिछले चरण जैसे Fetch और Decode पिछले निर्देश के परिणाम पर निर्भर नहीं है; केवल बाद के चरणों के परिणाम की आवश्यकता है। इस प्रकार, हम एक निर्देश के निष्पादन समय के एक अंश का इंतजार करते हैं। यही कारण है कि जब भविष्यवाणी आसान है तो सशर्त चाल संस्करण शाखा की तुलना में धीमी है।

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

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


इस तथ्य के अलावा कि शाखा भविष्यवाणी आपको धीमा कर सकती है, एक क्रमबद्ध सरणी का एक और फायदा है:

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

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

एक आधिकारिक जवाब से होगा

  1. इंटेल - शाखा गलतफहमी की लागत से बचें
  2. इंटेल - ब्रश और लूप पुनर्गठन Mispredicts को रोकने के लिए
  3. वैज्ञानिक पत्र - शाखा भविष्यवाणी कंप्यूटर वास्तुकला
  4. किताबें: जेएल हेनेसी, डीए पैटरसन: कंप्यूटर आर्किटेक्चर: एक मात्रात्मक दृष्टिकोण
  5. वैज्ञानिक प्रकाशनों में लेख: टीवाई ये, वाईएन पैट ने शाखा भविष्यवाणियों पर इनमें से बहुत कुछ बनाया है।

आप इस सुंदर diagram से भी देख सकते हैं कि क्यों शाखा भविष्यवाणी भ्रमित हो जाती है।

मूल कोड में प्रत्येक तत्व एक यादृच्छिक मान है

data[c] = std::rand() % 256;

तो भविष्यवाणी पक्षियों को std::rand()झटका के रूप में बदल देगा ।

दूसरी तरफ, इसे हल करने के बाद, भविष्यवाणियों को पहले दृढ़ता से लेने की स्थिति में स्थानांतरित नहीं किया जाएगा और जब मूल्य उच्च मूल्य में बदल जाएंगे तो भविष्यवाणियों को दृढ़ता से उठाए जाने के लिए दृढ़ता से नहीं लिया जाता है।


शाखा भविष्यवाणी

एक क्रमबद्ध सरणी के साथ, स्थिति data[c] >= 128 मूल्यों की एक लकीर के लिए पहली false , फिर सभी बाद के मूल्यों के लिए true हो जाता true । भविष्यवाणी करना आसान है। एक अनुरक्षित सरणी के साथ, आप शाखा लागत के लिए भुगतान करते हैं।


वह पक्का है!...

शाखा की भविष्यवाणी आपके कोड में होने वाली स्विचिंग की वजह से तर्क को धीमा कर देती है! ऐसा लगता है कि आप सीधी सड़क या सड़क पर कई मोड़ों के साथ जा रहे हैं, निश्चित रूप से सीधे एक जल्दी किया जा रहा है! ...

यदि सरणी को सॉर्ट किया गया है, तो आपकी स्थिति पहले चरण में गलत है: data[c] >= 128फिर सड़क के अंत तक पूरी तरह से एक वास्तविक मूल्य बन जाती है। इस तरह आप तर्क के अंत तक तेजी से पहुंच जाते हैं। दूसरी तरफ, एक अनुरक्षित सरणी का उपयोग करके, आपको बहुत सारे मोड़ और प्रसंस्करण की आवश्यकता होती है जो आपके कोड को धीमा करने के लिए धीमा कर देता है ...

मैंने आपके लिए बनाई गई छवि को देखें। कौन सी सड़क तेजी से खत्म होने जा रही है?

तो प्रोग्रामेटिक रूप से, शाखा भविष्यवाणी प्रक्रिया धीमी होने का कारण बनती है ...

अंत में, यह जानना अच्छा होता है कि हमारे पास दो प्रकार की शाखा भविष्यवाणियां हैं जो प्रत्येक आपके कोड को अलग-अलग प्रभावित करने जा रही हैं:

1. स्टेटिक

2. गतिशील

स्टेटिक शाखा भविष्यवाणी माइक्रोप्रोसेसर द्वारा पहली बार एक सशर्त शाखा का सामना किया जाता है, और सशर्त शाखा कोड के निष्पादन के लिए गतिशील शाखा भविष्यवाणी का उपयोग किया जाता है।

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


मैं बस इस सवाल और उसके उत्तरों पर पढ़ता हूं, और मुझे लगता है कि एक जवाब गुम है।

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

यह दृष्टिकोण सामान्य रूप से काम करता है अगर:

  1. यह एक छोटी सी मेज है और प्रोसेसर में कैश होने की संभावना है
  2. आप चीजों को काफी तंग लूप में चला रहे हैं और / या प्रोसेसर डेटा को प्री-लोड कर सकता है

पृष्ठभूमि और क्यों

Pfew, तो क्या मतलब है कि मतलब है?

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

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

सौभाग्य से हमारे लिए, अगर मेमोरी एक्सेस पैटर्न अनुमानित है, प्रोसेसर इसे अपने तेज कैश में लोड करेगा और सब ठीक है।

सबसे पहले हमें जानने की जरूरत है कि क्या छोटा है ? जबकि छोटे आम ​​तौर पर बेहतर होता है, अंगूठे का नियम आकार में <= 4096 बाइट्स वाले लुकअप टेबल पर चिपकना होता है। ऊपरी सीमा के रूप में: यदि आपकी लुकअप तालिका 64K से बड़ी है तो यह शायद पुनर्विचार के लायक है।

एक टेबल का निर्माण

तो हमने पाया है कि हम एक छोटी सी टेबल बना सकते हैं। करने के लिए अगली चीज़ जगह पर एक लुकअप समारोह मिलता है। लुकअप फ़ंक्शंस आमतौर पर छोटे फ़ंक्शन होते हैं जो कुछ मूल पूर्णांक संचालन (और, या, xor, shift, add, remove और शायद गुणा करते हैं) का उपयोग करते हैं। आप लुकअप फ़ंक्शन द्वारा अपनी तालिका में किसी प्रकार की 'अनूठी कुंजी' में अपना इनपुट अनुवाद करना चाहते हैं, जो तब आपको केवल उस काम का उत्तर देता है जिसे आप करना चाहते थे।

इस मामले में:> = 128 का मतलब है कि हम मान रख सकते हैं, <128 का मतलब है कि हम इससे छुटकारा पा सकते हैं। ऐसा करने का सबसे आसान तरीका 'AND' का उपयोग करना है: यदि हम इसे रखते हैं, तो हम और 7FFFFFFF के साथ; अगर हम इससे छुटकारा पाना चाहते हैं, तो हम और 0 के साथ यह ध्यान दें कि 128 128 की शक्ति है - इसलिए हम आगे बढ़ सकते हैं और 32768/128 पूर्णांक की एक तालिका बना सकते हैं और इसे एक शून्य से भर सकते हैं और बहुत सारे 7FFFFFFFF की।

प्रबंधित भाषाएं

आपको आश्चर्य हो सकता है कि यह प्रबंधित भाषाओं में क्यों अच्छा काम करता है। आखिरकार, प्रबंधित भाषाएं शाखाओं के साथ सरणी की सीमाओं की जांच करती हैं ताकि आप यह सुनिश्चित कर सकें कि आप गड़बड़ नहीं करते हैं ...

खैर, बिल्कुल नहीं ... :-)

प्रबंधित भाषाओं के लिए इस शाखा को खत्म करने पर काफी कुछ काम किया गया है। उदाहरण के लिए:

for (int i=0; i<array.Length; ++i)
   // Use array[i]

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

यदि आप प्रबंधित भाषाओं पर लुकअप के साथ परेशानी में भाग लेते हैं - कुंजी सीमा जांचने के लिए अपने लुकअप फ़ंक्शन में एक & 0x[something]FFF जोड़ना है - और इसे तेज़ी से चलना देखें।

इस मामले का नतीजा

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();




branch-prediction