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




c++ performance (14)

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

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

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

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

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

इसमें कोई संदेह नहीं है कि हम में से कुछ को कोड की पहचान करने के तरीकों में दिलचस्पी होगी जो सीपीयू की शाखा-भविष्यवाणी के लिए समस्याग्रस्त है। 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)
...

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


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

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

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 की जांच कर सकते हैं।

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


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

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

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


आप शाखा भविष्यवाणी का शिकार हो गए हैं।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

तो ट्रेन को बैक अप लेने और दूसरी पथ पर जाने के समय की संख्या को कम करने के लिए आप रणनीतिक रूप से अनुमान लगाएंगे? आप पिछले इतिहास को देखते हैं! यदि ट्रेन 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[] सभी इनपुट मानों के लिए मान्य है 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

टिप्पणियों:

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

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

अद्यतन करें:

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

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

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

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

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


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

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

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

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

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

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

दृश्य:

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

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 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()झटका के रूप में बदल देगा ।

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


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

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. गतिशील

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

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


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

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

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

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

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

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

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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

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


एआरएम पर, कोई शाखा की आवश्यकता नहीं है, क्योंकि प्रत्येक निर्देश में 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

चूंकि सरणी को सॉर्ट करने पर 0 और 255 के बीच डेटा वितरित किया जाता है, पुनरावृत्तियों के पहले भाग के आसपास if-स्टेटमेंट में प्रवेश नहीं किया जाएगा ( ifकथन नीचे साझा किया गया है)।

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

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

आइए इसे बेहतर समझने के लिए कुछ बेंच मार्किंग करें

if-स्टेटमेंट का प्रदर्शन इस बात पर निर्भर करता है कि इसकी स्थिति में अनुमानित पैटर्न है या नहीं। यदि स्थिति हमेशा सत्य या हमेशा गलत होती है, प्रोसेसर में शाखा पूर्वानुमान तर्क पैटर्न को उठाएगा। दूसरी तरफ, यदि पैटर्न अप्रत्याशित है, तो if-स्टेटमेंट अधिक महंगा होगा।

आइए इस लूप के प्रदर्शन को विभिन्न स्थितियों के साथ मापें:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

विभिन्न सत्य-झूठे पैटर्न के साथ लूप के समय यहां दिए गए हैं:

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

एक " बुरा " सच्चा-झूठा पैटर्न ifएक " अच्छा " पैटर्न की तुलना में छह गुना धीमी गति से बना सकता है ! बेशक, कौन सा पैटर्न अच्छा है और जो बुरा है संकलक और विशिष्ट प्रोसेसर द्वारा उत्पन्न सटीक निर्देशों पर निर्भर करता है।

तो प्रदर्शन पर शाखा भविष्यवाणी के प्रभाव के बारे में कोई संदेह नहीं है!


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

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

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

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

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

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

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

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

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

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

संदर्भ:


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

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

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





branch-prediction