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


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

#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);, कोड 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);
    }
}

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


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

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

21674
2018-06-27 13:51


मूल


सिर्फ रिकार्ड के लिए। विंडोज / वीएस2017 / i7-6700K 4GHz पर दो संस्करणों के बीच कोई अंतर नहीं है। यह दोनों मामलों के लिए 0.6s लेता है। यदि बाहरी लूप में पुनरावृत्तियों की संख्या 10 गुना बढ़ जाती है तो दोनों मामलों में निष्पादन समय 10 गुना बढ़कर 6 हो जाता है। - mp31415
@ user194715: कोई भी कंपाइलर जो इसका उपयोग करता है cmovया अन्य शाखा रहित कार्यान्वयन (जैसे ऑटो-वेक्टरेशन के साथ pcmpgtd) प्रदर्शन होगा जो किसी भी CPU पर डेटा निर्भर नहीं है। लेकिन अगर यह ब्रांची है, तो यह किसी भी सीपीयू पर आउट-ऑफ-ऑर्डर सट्टा निष्पादन के साथ क्रमबद्ध होगा। (यहां तक ​​कि उच्च-प्रदर्शन इन-ऑर्डर सीपीयू शाखाओं की भविष्यवाणी का उपयोग शाखाओं पर लाने / डीकोड बुलबुले से बचने के लिए करते हैं; मिस पेनल्टी छोटी है)। - Peter Cordes
Woops ... पुन: मंदी और स्पेक्ट्रर - KyleMit
@ केलीमिट के पास दोनों के साथ कुछ करने के लिए है? मैंने दोनों पर ज्यादा पढ़ा नहीं है - mohitmun
@ मोहितमुन, उन दोनों सुरक्षा त्रुटियों के रूप में वर्गीकृत भेद्यता की एक विस्तृत श्रेणी में फिट "शाखा लक्ष्य इंजेक्शन" हमलों - KyleMit


जवाब:


आप का शिकार हो शाखा भविष्यवाणी असफल।


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

रेलवे जंक्शन पर विचार करें:

Licensed Image छवि विकिमीडिया कॉमन्स के माध्यम से, मेकनसिमो द्वारा। के तहत प्रयुक्त सीसी-बाय-एसए 3.0 लाइसेंस।

अब तर्क के लिए, मान लीजिए कि यह 1800 के दशक में है - लंबी दूरी या रेडियो संचार से पहले।

आप एक जंक्शन के ऑपरेटर हैं और आप एक ट्रेन आते हैं। आपको पता नहीं है कि इसे किस तरह से जाना है। आप ट्रेन को ड्राइवर से पूछने के लिए रोकते हैं कि वे कौन सी दिशा चाहते हैं। और फिर आप स्विच को उचित रूप से सेट करते हैं।

गाड़ियों भारी हैं और बहुत जड़ता है। तो वे हमेशा शुरू करने और धीमा करने के लिए हमेशा लेते हैं।

क्या कोई बेहतर तरीका है? आप अनुमान लगाते हैं कि ट्रेन किस दिशा में जाएगी!

  • यदि आपने सही अनुमान लगाया है, तो यह जारी है।
  • यदि आपने गलत अनुमान लगाया है, तो कप्तान स्विच को फ्लिप करने के लिए आपको रोक देगा, बैक अप करेगा और चिल्लाएगा। फिर यह दूसरे पथ को पुनरारंभ कर सकता है।

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


एक कथन पर विचार करें: प्रोसेसर स्तर पर, यह एक शाखा निर्देश है:

image2

आप एक प्रोसेसर हैं और आप एक शाखा देखते हैं। आपको पता नहीं है कि यह किस तरह से जाएगा। आप क्या करते हैं? आपने निष्पादन रोक दिया है और पिछले निर्देशों को पूरा होने तक प्रतीक्षा करें। फिर आप सही पथ को जारी रखते हैं।

आधुनिक प्रोसेसर जटिल हैं और लंबी पाइपलाइन हैं। तो वे हमेशा के लिए "गर्म" और "धीमा" करने के लिए लेते हैं।

क्या कोई बेहतर तरीका है? आप अनुमान लगाते हैं कि शाखा किस दिशा में जाएगी!

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

यदि आप हर बार सही अनुमान लगाते हैं, निष्पादन को कभी नहीं रोकना होगा।
यदि आप अक्सर गलत लगता है, आप बहुत समय बिताते हैं, वापस रोलिंग करते हैं, और पुनरारंभ करते हैं।


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

तो ट्रेन को बैक अप लेने और दूसरी पथ पर जाने के समय की संख्या को कम करने के लिए आप रणनीतिक रूप से अनुमान लगाएंगे? आप पिछले इतिहास को देखते हैं! यदि ट्रेन 99% बार छोड़ जाती है, तो आप बाएं अनुमान लगाते हैं। यदि यह वैकल्पिक होता है, तो आप अपने अनुमानों को वैकल्पिक करते हैं। यदि यह हर 3 बार एक तरफ जाता है, तो आप वही अनुमान लगाते हैं ...

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

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

आगे की पढाई: विकिपीडिया पर "शाखा भविष्यवाणी" लेख


ऊपर से संकेत के रूप में, अपराधी यह है अगर कथन:

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

ध्यान दें कि डेटा को समान रूप से 0 और 255 के बीच वितरित किया जाता है। जब डेटा सॉर्ट किया जाता है, तो लगभग पुनरावृत्तियों के पहले भाग में if-statement दर्ज नहीं किया जाएगा। उसके बाद, वे सभी if-statement दर्ज करेंगे।

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

त्वरित दृश्यता:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

हालांकि, जब डेटा पूरी तरह यादृच्छिक होता है, तो शाखा पूर्वानुमानकर्ता बेकार हो जाता है क्योंकि यह यादृच्छिक डेटा की भविष्यवाणी नहीं कर सकता है। इस प्रकार शायद लगभग 50% गलत भविष्यवाणी होगी। (यादृच्छिक अनुमान से बेहतर नहीं)

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

तो क्या कर सकते हैं?

यदि संकलक शाखा को एक सशर्त चाल में अनुकूलित करने में सक्षम नहीं है, तो आप कुछ हैक्स को आजमा सकते हैं यदि आप प्रदर्शन के लिए पठनीयता को त्यागने के इच्छुक हैं।

बदलने के:

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

साथ में:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

यह शाखा को हटा देता है और इसे थोड़ा सा संचालन के साथ बदल देता है।

(ध्यान दें कि यह हैक मूल if-statement के बराबर नहीं है। लेकिन इस मामले में, यह सभी इनपुट मानों के लिए मान्य है data[]।)

बेंचमार्क: कोर i7 920 @ 3.5 गीगाहर्ट्ज

सी ++ - विजुअल स्टूडियो 2010 - x64 रिलीज

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

जावा - नेटबीन्स 7.1.1 जेडीके 7 - एक्स 64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

टिप्पणियों:

  • शाखा के साथ: क्रमबद्ध और छोड़े गए डेटा के बीच एक बड़ा अंतर है।
  • हैक के साथ: क्रमबद्ध और छोड़े गए डेटा के बीच कोई अंतर नहीं है।
  • सी ++ मामले में, हैक वास्तव में शाखा के मुकाबले एक टैड धीमी है जब डेटा सॉर्ट किया जाता है।

अंगूठे का एक सामान्य नियम महत्वपूर्ण लूप में डेटा-निर्भर शाखाओं से बचने के लिए है। (जैसे कि इस उदाहरण में)


अद्यतन करें:

  • जीसीसी 4.6.1 के साथ -O3 या -ftree-vectorize x64 पर एक सशर्त चाल उत्पन्न करने में सक्षम है। तो क्रमबद्ध और छोड़े गए डेटा के बीच कोई अंतर नहीं है - दोनों तेज़ हैं।

  • वीसी ++ 2010 इस शाखा के लिए भी सशर्त चाल उत्पन्न करने में असमर्थ है /Ox

  • इंटेल कंपाइलर 11 कुछ चमत्कारी करता है। यह दो loops interchanges, जिससे बाहरी लूप को अप्रत्याशित शाखा उछालती है। इसलिए न केवल यह गलत भविष्यवाणियों को प्रतिरक्षा करता है, यह भी दो गुना तेज है जितना वीसी ++ और जीसीसी उत्पन्न कर सकता है! दूसरे शब्दों में, आईसीसी ने बेंचमार्क को हराने के लिए टेस्ट-लूप का लाभ उठाया ...

  • यदि आप इंटेल कंपाइलर को शाखा रहित कोड देते हैं, तो यह सिर्फ सही-सही वेक्टरेट करता है ... और शाखा के साथ जितना तेज़ है (लूप इंटरचेंज के साथ)।

यह दिखाता है कि परिपक्व आधुनिक कंपाइलर कोड को अनुकूलित करने की उनकी क्षमता में जंगली रूप से भिन्न हो सकते हैं ...


28593
2018-06-27 13:56



@Mysticial स्थानांतरण हैक से बचने के लिए आप कुछ लिख सकते हैं int t=-((data[c]>=128)) मुखौटा उत्पन्न करने के लिए। यह भी तेज होना चाहिए। यह जानना दिलचस्प होगा कि संकलक एक सशर्त चाल डालने के लिए पर्याप्त चालाक है या नहीं। - Mackie Messer
@phonetagger इस अनुवर्ती प्रश्न पर एक नज़र डालें: stackoverflow.com/questions/11276291/... इंटेल कंपाइलर पूरी तरह से बाहरी पाश से छुटकारा पाने के करीब आया था। - Mysticial
@ नोवेलोक्रेट केवल इसका आधा सही है। शून्य होने पर साइन-बिट में 1 को स्थानांतरित करना वास्तव में यूबी है। ऐसा इसलिए है क्योंकि यह पूर्णांक ओवरफ़्लो पर हस्ताक्षर है। लेकिन साइन-बिट में से 1 को स्थानांतरित करना आईबी है। नकारात्मक हस्ताक्षरित पूर्णांक को सही स्थानांतरित करना आईबी है। आप तर्क में जा सकते हैं कि सी / सी ++ की आवश्यकता नहीं है कि शीर्ष बिट संकेत संकेतक हो। लेकिन कार्यान्वयन विवरण आईबी हैं। - Mysticial
@ मिस्टिकियल लिंक के लिए बहुत बहुत धन्यवाद। यह आशाजनक लग रहा है। हालांकि मैं जाऊंगा। एक आखिरी अनुरोध क्षमा करें, लेकिन कृपया ध्यान न दें, क्या आप मुझे बता सकते हैं कि आप यह कैसे कर सकते हैं int t = (data[c] - 128) >> 31; sum += ~t & data[c]; उपरोक्त मूल स्थिति को प्रतिस्थापित करने के लिए? - Unheilig
मेरे में व्याकरण चाहता है कि मुझे यह सोचना चाहिए कि "इसे पढ़ना चाहिए" ... शाखा भविष्यवाणी का शिकार विफल हो गयाure"बस के बजाय" ... शाखा भविष्यवाणी का शिकार विफल। " - jdero


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

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


3640
2018-06-27 13:54



क्या शाखा भविष्यवाणी अलग-अलग पैटर्न के साथ क्रमबद्ध सरणी बनाम सरणी पर बेहतर काम करती है? उदाहरण के लिए, सरणी के लिए -> {10, 5, 20, 10, 40, 20, ...} पैटर्न से सरणी में अगला तत्व 80 है। क्या इस तरह की सरणी शाखा भविष्यवाणी द्वारा बढ़ाई जाएगी यदि पैटर्न का पालन किया जाता है तो अगला तत्व 80 है? या यह आमतौर पर केवल क्रमबद्ध सरणी के साथ मदद करता है? - Adam Freeman
तो मूल रूप से मैं जो कुछ भी पारंपरिक रूप से बड़े-ओ के बारे में सीखा वह खिड़की से बाहर है? एक शाखा लागत से एक छंटनी लागत लगाना बेहतर है? - Agrim Pathak
@AgrimPathak यह निर्भर करता है। बहुत अधिक इनपुट के लिए, उच्च जटिलता वाले एल्गोरिदम कम जटिलता वाले एल्गोरिदम से तेज़ होते हैं जब स्थिरता उच्च जटिलता वाले एल्गोरिदम के लिए छोटी होती है। जहां ब्रेक-इवेंट पॉइंट भविष्यवाणी करना मुश्किल हो सकता है। इसके अलावा, इसकी तुलना करें, इलाका महत्वपूर्ण है। बिग-ओ महत्वपूर्ण है, लेकिन यह प्रदर्शन के लिए एकमात्र मानदंड नहीं है। - Daniel Fischer
शाखा भविष्यवाणी कब होती है? भाषा कब जानती है कि सरणी सॉर्ट की जाती है? मैं सरणी की स्थिति के बारे में सोच रहा हूं जो दिखता है: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? यह अस्पष्ट 3 रनिंग समय बढ़ेगा? क्या यह अनसुलझा सरणी के रूप में होगा? - Filip Bartuzi
@ फिलिप बार्टुज़ी शाखा भविष्यवाणी भाषा स्तर से नीचे प्रोसेसर में होती है (लेकिन भाषा संकलक को बताने के तरीकों की पेशकश कर सकती है, इसलिए संकलक उस कोड को उपयुक्त बना सकता है)। आपके उदाहरण में, आउट ऑफ़ ऑर्डर 3 शाखा-गलतफहमी का कारण बन जाएगा (उचित परिस्थितियों के लिए, जहां 3 1000 से अलग परिणाम देता है), और इस प्रकार उस सरणी को संसाधित करने से संभवतः दो दर्जन या सौ नैनोसेकंड अधिक समय लगेगा क्रमबद्ध सरणी, शायद ही कभी ध्यान देने योग्य होगा। मुझे कितना समय लगता है कि मैं गलत भविष्यवाणियों की उच्च दर है, प्रति 1000 एक गलतफहमी ज्यादा नहीं है। - Daniel Fischer


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

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

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 तथा max2

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। लेकिन असली लाभ यह है कि max2 शाखा कूदता नहीं है, jmp, यदि भविष्यवाणी परिणाम सही नहीं है, तो एक महत्वपूर्ण प्रदर्शन दंड होगा।

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

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

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

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

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

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


2961
2018-06-28 02:14



जब तक आप अपनी जीसीसी कमांड लाइनों में नहीं जोड़ते हैं, तब तक कोई डिफ़ॉल्ट अनुकूलन स्तर नहीं होता है। (और आप मेरे से सबसे खराब अंग्रेजी नहीं हो सकता है;) - Yann Droneaud
मुझे विश्वास करना मुश्किल लगता है कि संकलक टर्नरी-ऑपरेटर को समकक्ष अगर-कथन के मुकाबले बेहतर कर सकता है। आपने दिखाया है कि जीसीसी एक सशर्त चाल पर टर्नरी-ऑपरेटर को अनुकूलित करता है; आप नहीं है दिखाया गया है कि यह if-statement के लिए बिल्कुल वही काम नहीं करता है। वास्तव में, उपरोक्त रहस्यवादी के अनुसार, जीसीसी कर देता है एक सशर्त चाल पर if-statement को अनुकूलित करें, जो यह उत्तर पूरी तरह से गलत बना देगा। - BlueRaja - Danny Pflughoeft
@WiSaGaN कोड कुछ भी प्रदर्शित नहीं करता है, क्योंकि कोड के आपके दो टुकड़े एक ही मशीन कोड में संकलित होते हैं। यह गंभीर रूप से महत्वपूर्ण है कि लोगों को यह विचार नहीं मिलता है कि किसी भी तरह आपके उदाहरण में यदि कथन आपके उदाहरण में तेज़ से अलग है। यह सच है कि आप अपने पिछले अनुच्छेद में समानता के स्वामी हैं, लेकिन यह इस तथ्य को मिटा नहीं देता है कि शेष उदाहरण हानिकारक है। - Justin L.
@WiSaGaN यदि आप भ्रामक को हटाने के लिए अपना उत्तर संशोधित करते हैं तो मेरा डाउनवोट निश्चित रूप से एक अपवर्तित हो जाएगा -O0 उदाहरण और अंतर दिखाने के लिए अनुकूलित अपने दो टेस्टकेस पर एएसएम। - Justin L.
@UpAndAdam परीक्षण के पल में, वीएस -2010 उच्च शाखा अनुकूलन स्तर निर्दिष्ट करते समय भी मूल शाखा को एक सशर्त चाल में अनुकूलित नहीं कर सकता है, जबकि जीसीसी कर सकते हैं। - WiSaGaN


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

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

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 सशर्त निरंतर पूरे निष्पादन में है i लूप, तो आप उछाल सकते हैं 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 तेज है


2026
2017-07-03 02:25



यदि आप धोखा देना चाहते हैं, तो आप लूप के बाहर गुणा भी ले सकते हैं और लूप के बाद * * 100000 कर सकते हैं। - Jyaif
@ माइकल - मेरा मानना ​​है कि यह उदाहरण वास्तव में एक उदाहरण है पाश-invariant hoisting (एलआईएच) अनुकूलन, और नहीं लूप स्वैप। इस मामले में, संपूर्ण आंतरिक पाश बाहरी लूप से स्वतंत्र होता है और इसलिए बाहरी पाश से बाहर निकाल दिया जा सकता है, जिसके परिणामस्वरूप परिणाम केवल एक योग से गुणा हो जाता है i एक इकाई = 1e5 का। यह अंतिम परिणाम में कोई फर्क नहीं पड़ता है, लेकिन मैं सिर्फ रिकॉर्ड सेट करना चाहता था क्योंकि यह एक ऐसा लगातार पृष्ठ है। - Yair Altman
हालांकि लूप स्वैपिंग की सरल भावना में नहीं, आंतरिक if इस बिंदु पर परिवर्तित किया जा सकता है: sum += (data[j] >= 128) ? data[j] * 100000 : 0; जो संकलक को कम करने में सक्षम हो सकता है cmovge या उसके बराबर। - Alex North-Keys
बाहरी लूप आंतरिक लूप द्वारा लिया गया समय बड़ा करने के लिए पर्याप्त है। तो आप लूप स्वैप क्यों करेंगे। अंत में, उस लूप को वैसे भी हटा दिया जाएगा। - saurabheights
@ सोराबाइट्स: गलत सवाल: संकलक क्यों लूप स्वैप नहीं करेगा। माइक्रोबेंचमार्क मुश्किल है;) - Matthieu M.


इसमें कोई संदेह नहीं है कि हम में से कुछ को कोड की पहचान करने के तरीकों में दिलचस्पी होगी जो सीपीयू की शाखा-भविष्यवाणी के लिए समस्याग्रस्त है। वालग्रिंड उपकरण cachegrind एक शाखा-भविष्यवाणी सिम्युलेटर है, जिसका उपयोग करके सक्षम है --branch-sim=yes झंडा। इस प्रश्न में उदाहरणों पर इसे चलाते हुए, बाहरी लूपों की संख्या 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 हम सवाल में लूप के लिए देखते हैं:

छाँटे गए:

          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 गलत अनुमानित सशर्त शाखाएं पैदा कर रही है (Bcm) कैशग्रींड के शाखा-भविष्यवाणी मॉडल के तहत, जबकि यह क्रमबद्ध संस्करण में केवल 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)
...

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


1690
2017-10-12 05:53



यह डरावना सूची में, डरावना है, जोड़ को मारने का 50% मौका होना चाहिए। किसी भी तरह शाखा भविष्यवाणी में केवल 25% मिस दर है, यह 50% से अधिक छूट कैसे कर सकती है? - TallBrianL
@ tall.b.lo: 25% सभी शाखाओं में से हैं - वहां हैं दो लूप में शाखाएं, एक के लिए data[c] >= 128 (जैसा कि आप सुझाव देते हैं 50% छूट दर है) और लूप की स्थिति के लिए एक c < arraySize जिसमें ~ 0% मिस दर है। - caf


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

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

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

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

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

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

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

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

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

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

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

तो हमने पाया है कि हम एक छोटी सी टेबल बना सकते हैं। करने के लिए अगली चीज़ जगह पर एक लुकअप समारोह मिलता है। लुकअप फ़ंक्शंस आमतौर पर छोटे फ़ंक्शन होते है