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





10 Answers

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

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

java c++ performance optimization branch-prediction

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

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

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

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

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



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

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

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 तेज है




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

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

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

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



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

लेकिन इस मामले में, हम जानते हैं कि मान सीमा [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];

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




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

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

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

आम तौर पर, आधुनिक प्रोसेसर में काफी लंबी पाइपलाइन होती है, लेकिन आसानी से चलिए इन 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 चक्रों में परिणाम।




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

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

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

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

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

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




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

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

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

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

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

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

1. स्टेटिक

2. गतिशील

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

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




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

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

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

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

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

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

दृश्य:

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

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

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



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

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

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

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

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

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

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

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

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

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

संदर्भ:




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

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

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



Related