java - কেন এটি একটি সাজানো অ্যারের চেয়ে একটি সাজানো অ্যারে প্রক্রিয়া দ্রুত?




c++ performance optimization branch-prediction (18)

এখানে সি ++ কোডের একটি অংশ যা খুব অস্বাভাবিক মনে হচ্ছে। কিছু অদ্ভুত কারণের জন্য, তথ্য ক্রমবর্ধমানভাবে কোডটিকে প্রায় ছয় গুণ দ্রুত করে তোলে।

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

একটি কিছুটা অনুরূপ কিন্তু কম চরম ফলাফল সঙ্গে।

আমার প্রথম চিন্তা ছিল যে সাজানোর তথ্যটি ক্যাশে নিয়ে আসে, কিন্তু তারপর আমি মনে করি কিভাবে অ্যারিটি কেবলমাত্র জেনারেট তৈরি করা হয়েছিল।

  • কি হচ্ছে?
  • কেন এটি একটি সাজানো অ্যারের চেয়ে একটি সাজানো অ্যারে প্রক্রিয়া দ্রুত?
  • কোড কিছু স্বাধীন পদ সংকলন করা হয়, এবং আদেশ ব্যাপার না হওয়া উচিত।

Answers

অ্যারের সাজানো হয় যখন তথ্য 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" ভাল " প্যাটার্নের তুলনায় ছয় গুণ ধীর গতির করতে পারে ! অবশ্যই, কোন প্যাটার্ন ভাল এবং যা খারাপ তা কম্পাইলার এবং নির্দিষ্ট প্রসেসর দ্বারা উত্পন্ন সঠিক নির্দেশাবলী উপর নির্ভর করে।

তাই কর্মক্ষমতা উপর শাখা পূর্বাভাস প্রভাব সম্পর্কে কোন সন্দেহ নেই!


আপনি শাখা পূর্বাভাস একটি শিকার ব্যর্থ হয়।

শাখা ভবিষ্যদ্বাণী কি?

একটি রেলপথ জংশন বিবেচনা করুন:

উইকিমিডিয়া কমন্সের মাধ্যমে, মেকানিজিমোর । CC-BY-SA 3.0 লাইসেন্সের অধীনে ব্যবহৃত।

এখন যুক্তি করার জন্য, ধরুন এটি 1800 এর দশকে - দীর্ঘ দূরত্ব বা রেডিও যোগাযোগের আগে।

আপনি একটি জংশন অপারেটর এবং আপনি একটি ট্রেন আসছে শুনতে। আপনি কোন উপায় এটি অনুমিত হয় অনুমিত আছে। আপনি ট্রেনটি থামাতে চান, ড্রাইভারকে জিজ্ঞাসা করুন যে তারা কোন দিকনির্দেশনা চায়। এবং তারপর আপনি সঠিকভাবে সুইচ সেট।

ট্রেন ভারী এবং জরায়ুর অনেক আছে। সুতরাং তারা শুরু এবং ধীর নিচে চিরতরে নিতে।

একটি ভাল উপায় আছে কি? আপনি কোন দিক ট্রেন যেতে হবে অনুমান!

  • যদি আপনি সঠিক অনুমান করেন, এটি চলতে থাকে।
  • যদি আপনি ভুল অনুমান করেন, তবে অধিনায়ক থামবেন, ব্যাক আপ করবেন এবং সুইচটি ফ্লিপ করার জন্য আপনাকে চিৎকার করবেন। তারপর এটি অন্য পাথ নিচে পুনরায় আরম্ভ করতে পারেন।

আপনি প্রতিবার সঠিক অনুমান করলে, ট্রেনটি কখনো থামতে হবে না।
আপনি যদি প্রায়শই ভুল অনুমান করেন তবে ট্রেনটি অনেকগুলি সময় বন্ধ, ব্যাক আপ এবং পুনরায় চালু করতে ব্যয় করবে।

একটি বিবৃতি বিবেচনা করুন: প্রসেসরের স্তরে, এটি একটি শাখা নির্দেশনা:

আপনি একটি প্রসেসর এবং আপনি একটি শাখা দেখতে। আপনি কোন উপায় এটি যেতে হবে কোন ধারণা আছে। আপনি কি করেন? আপনি মৃত্যুদন্ড বন্ধ করুন এবং পূর্ববর্তী নির্দেশাবলী সম্পূর্ণ না হওয়া পর্যন্ত অপেক্ষা করুন। তারপর আপনি সঠিক পথ অব্যাহত।

আধুনিক প্রসেসর জটিল এবং দীর্ঘ পাইপলাইন আছে। তাই তারা সর্বদা "উষ্ণ আপ" এবং "ধীরে ধীরে" নিতে।

একটি ভাল উপায় আছে কি? আপনি অনুমান করবেন যে শাখা কোন দিকে যাবে!

  • যদি আপনি সঠিক অনুমান করেন, আপনি নির্বাহ চালিয়ে যান।
  • আপনি ভুল অনুমান করা হলে, আপনি পাইপলাইন flush এবং শাখা ফিরে পাকানো প্রয়োজন। তারপর আপনি অন্য পাথটি পুনরায় আরম্ভ করতে পারেন।

আপনি সঠিকভাবে প্রতিটি সময় অনুমান , মৃত্যুদন্ড কার্যকর করা হবে না।
আপনি যদি প্রায়শই ভুল অনুমান করেন , তবে আপনি অনেক সময় স্থগিত করে, পিছনে ফিরে আসেন এবং পুনরায় শুরু করেন।

এই শাখা ভবিষ্যদ্বাণী। ট্রেনটি কেবল একটি পতাকা দিয়ে দিক নির্দেশ করতে পারে বলে আমি এটি যথোপযুক্ত সৃষ্টিকর্তা হিসাবে স্বীকার করি না। কিন্তু কম্পিউটারে, প্রসেসর জানেন না যে শেষ মুহুর্ত পর্যন্ত কোন শাখা যাবে।

তাহলে ট্রেনটি কীভাবে ব্যাক আপ করতে হবে এবং অন্য পথে যেতে হবে সেই সংখ্যাকে কমিয়ে আনতে আপনি কৌশলগতভাবে কীভাবে অনুমান করবেন? আপনি অতীত ইতিহাস তাকান! যদি ট্রেনের 99% সময় চলে যায়, তবে আপনি বাম অনুমান করুন। যদি এটি বিকল্প হয়, তাহলে আপনি আপনার অনুমান বিকল্প। যদি এটি প্রতি 3 বার এক উপায় যায়, আপনি একই অনুমান ...

অন্য কথায়, আপনি একটি প্যাটার্ন সনাক্ত এবং এটি অনুসরণ করার চেষ্টা করুন। এই শাখা predictors কাজ কিভাবে কম বা কম।

সর্বাধিক অ্যাপ্লিকেশন ভাল আচরণ শাখা আছে। সুতরাং আধুনিক শাখার ভবিষ্যদ্বাণী সাধারণত 90% হার হার অর্জন করবে। কিন্তু যখন কোন স্বীকৃত নকশার সাথে অনির্দেশ্য শাখার মুখোমুখি হন, তখন শাখা পূর্বাভাসকারী কার্যত নিরর্থক।

আরও পড়ুন: উইকিপিডিয়ার নিবন্ধ "শাখা পূর্বাভাস" ।

উপরে থেকে ইঙ্গিত করা হয়েছে, অপরাধী যদি এই বিবৃতি হয়:

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

লক্ষ্য করুন যে তথ্যটি 0 এবং ২55 এর মধ্যে সমানভাবে বিতরণ করা হয়েছে। যখন তথ্য সংশোধন করা হয়, তখন পুনরাবৃত্তির প্রথম অর্ধেক যদি-বিবৃতিটি প্রবেশ করবে না। তারপরে, তারা সব-যদি বিবৃতি লিখতে হবে।

শাখা পূর্বাভাসকারীর কাছে এটি খুবই বন্ধুত্বপূর্ণ কারণ শাখাটি ধারাবাহিকভাবে একই দিক থেকে অনেক বার চলে যায়। এমনকি একটি সহজ saturating পাল্টা সঠিকভাবে নির্দেশিকা সুইচ পরে কয়েক পুনরাবৃত্তি ছাড়া শাখা ভবিষ্যদ্বাণী করা হবে।

দ্রুত কল্পনা:

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

এটি শাখাটি নির্মূল করে এবং কিছু বিটwise ক্রিয়াকলাপের সাথে এটি প্রতিস্থাপন করে।

(মনে রাখবেন যে এই হ্যাক মূল যদি-স্টেটমেন্টের সমতুল্য নয় তবে এই ক্ষেত্রে, এটি সমস্ত ইনপুট মানগুলির জন্য বৈধ। 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 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

পর্যবেক্ষণ:

  • শাখা দিয়ে: সাজানো এবং অসংগঠিত তথ্য মধ্যে একটি বিশাল পার্থক্য আছে।
  • হ্যাক দিয়ে: সাজানো এবং অসংগঠিত তথ্য মধ্যে কোন পার্থক্য নেই।
  • C ++ ক্ষেত্রে, হ্যাক আসলে শংসাপত্রের সাথে শ্যাডোয়ের চেয়ে ধীর গতির।

চুম্বনের একটি সাধারণ নিয়ম সমালোচনামূলক loops মধ্যে তথ্য নির্ভর শাখা এড়াতে হয়। (যেমন এই উদাহরণে)

হালনাগাদ:

  • জি -O3 4.6.1 -O3 বা -ftree-vectorize x64 এ একটি শর্তাধীন পদক্ষেপ তৈরি করতে সক্ষম। সুতরাং সাজানো এবং অসংগঠিত তথ্য মধ্যে কোন পার্থক্য নেই - উভয় দ্রুত।

  • ভিসি ++ ২010 এই শাখাটির জন্যও /Ox অধীনে শর্তাধীন পদক্ষেপগুলি তৈরি করতে অক্ষম।

  • ইন্টেল কম্পাইলার 11 কিছু অলৌকিক কাজ করে। এটি দুটি লুপকে বিনিময় করে , যার ফলে বাইরের লুপে আনুমানিক শাখাটি উঠানো হয়। সুতরাং এটি শুধুমাত্র ভুল বানানগুলি অনাক্রম্য নয়, এটি VC ++ এবং GCC যা জেনারেট করতে পারে তার চেয়েও দ্বিগুণ দ্রুত! অন্য কথায়, আইসিসি টেস্ট-লুপের বেঞ্চমার্ক পরাজিত করার সুবিধা গ্রহণ করেছে ...

  • আপনি যদি ইন্টেল কম্পাইলারকে শাখাহীন কোডটি দেন তবে এটি ঠিক-ভেতরেই এটি ভেক্টরাইজ করে ... এবং শাখা (লুপ ইন্টারচেঞ্জ সহ) এর মতো দ্রুত।

এই এমনকি পরিপক্ক আধুনিক কম্পাইলার কোড optimize তাদের ক্ষমতা মধ্যে wildly পরিবর্তিত হতে পারে যে দেখায় যায় ...


শাখা ভবিষ্যদ্বাণী।

একটি সাজানো অ্যারের সাথে, শর্ত data[c] >= 128 মানগুলির একটি লাইনের জন্য প্রথম false , তারপর সমস্ত পরবর্তী মানগুলির জন্য true হয়ে যায়। এটা পূর্বাভাস করা সহজ। একটি unsorted অ্যারের সঙ্গে, আপনি শাখা খরচ জন্য অর্থ প্রদান।


শাখা ভবিষ্যদ্বাণী আপনাকে ধীর করে তুলতে পারে এমন ব্যতীত, একটি সাজানো অ্যারে আরেকটি সুবিধা রয়েছে:

মানটি চেক করার পরিবর্তে আপনি স্টপ অবস্থায় থাকতে পারেন, এইভাবে আপনি কেবল প্রাসঙ্গিক তথ্যটি লুপ করুন এবং বাকিগুলি উপেক্ষা করুন।
শাখা ভবিষ্যদ্বাণী শুধুমাত্র একবার মিস্ হবে।

 // 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. আপনি বেশ টাইট লুপে জিনিসগুলি চালাচ্ছেন এবং / অথবা প্রসেসর তথ্য লোড করতে পারবেন

পটভূমি এবং কেন

Pfew, তাই কি মানে জাহান্নাম মানে?

একটি প্রসেসর দৃষ্টিকোণ থেকে, আপনার মেমরি ধীর। গতিতে পার্থক্যের জন্য ক্ষতিপূরণ দেওয়ার জন্য, তারা আপনার প্রসেসরের (L1 / L2 ক্যাশে) কয়েকটি ক্যাশে তৈরি করে যা তার জন্য ক্ষতিপূরণ দেয়। তাই কল্পনা করুন যে আপনি আপনার চমৎকার গণনা করছেন এবং আপনি মেমরি একটি টুকরা প্রয়োজন যে চিন্তা। প্রসেসরটি 'লোড' অপারেশন পাবে এবং মেমরির টুকরো ক্যাশে লোড করবে - এবং তারপর বাকি গণনার জন্য ক্যাশ ব্যবহার করে। কারণ মেমরি অপেক্ষাকৃত ধীর, এই 'লোড' আপনার প্রোগ্রাম হ্রাস করা হবে।

শাখা পূর্বাভাসের মতো, এটি পেন্টিয়াম প্রসেসরগুলির মধ্যে অপ্টিমাইজ করা হয়েছিল: প্রসেসর ভবিষ্যদ্বাণী করে যে এটি ডেটা একটি টুকরো লোড করতে এবং অপারেশনের প্রকৃতপক্ষে ক্যাশে হিট করার আগে ক্যাশে লোড করার চেষ্টা করে। যেমনটি আমরা ইতিমধ্যে দেখেছি, শাখা ভবিষ্যদ্বাণী কখনও কখনও ভয়ানকভাবে ভুল হয়ে যায় - সবচেয়ে খারাপ ক্ষেত্রে দৃশ্যকল্পটি আপনাকে ফিরে যেতে হবে এবং প্রকৃতপক্ষে মেমরি লোডের জন্য অপেক্ষা করতে হবে যা চিরকালের জন্য নিতে হবে ( অন্য কথায়: ব্যর্থ শাখার ভবিষ্যদ্বাণী খারাপ, একটি মেমরি একটি শাখা ভবিষ্যদ্বাণী ব্যর্থ পরে লোড শুধু ভয়ঙ্কর! )।

সৌভাগ্যক্রমে আমাদের জন্য, যদি মেমরি অ্যাক্সেস প্যাটার্নটি প্রত্যাশিত হয়, প্রসেসর এটি দ্রুত ক্যাশে লোড করবে এবং সব ঠিক আছে।

প্রথম জিনিসটি কি আমাদের জানা দরকার তা ছোট ? যদিও সাধারণত ছোট ছোট হয়, থাম্বের নিয়মটি <= 4096 বাইট আকারের সন্ধানের টেবিলগুলিতে আটকাতে হয়। উপরের সীমা হিসাবে: আপনার সন্ধানের টেবিল 64K এর চেয়ে বড় হলে এটি সম্ভবত পুনর্বিবেচনার যোগ্য।

একটি টেবিল গঠন

সুতরাং আমরা figured করেছি যে আমরা একটি ছোট টেবিল তৈরি করতে পারেন। করতে পরবর্তী জিনিস জায়গায় একটি সন্ধান ফাংশন পেতে। লুপ ফাংশন সাধারণত ছোট ফাংশন যা কয়েকটি মৌলিক পূর্ণসংখ্যা ক্রিয়াকলাপ (এবং, বা, xor, shift, যোগ, অপসারণ এবং সম্ভবত গুণমান) ব্যবহার করে। আপনি সন্ধানের ফাংশন দ্বারা আপনার ইনপুটটি আপনার টেবিলের কোনও 'অনন্য কী' তে অনুবাদ করতে চান, যা কেবল তখনই আপনাকে যা করতে চান তার উত্তরটি দেয়।

এই ক্ষেত্রে:> = 128 মানে আমরা মান রাখতে পারি, <128 মানে আমরা এটি পরিত্রাণ পেতে পারি। এটি করার সবচেয়ে সহজ উপায় হল 'AND' ব্যবহার করে: যদি আমরা এটি রাখি, আমরা এবং এটি 7FFFFFFF সহ; যদি আমরা এটি পরিত্রাণ পেতে চাই, আমরা এবং এটি 0 দিয়ে। লক্ষ্য করুন যে 128 একটি পাওয়ার 2 - তাই আমরা এগিয়ে যেতে পারি এবং 32768/128 পূর্ণসংখ্যাগুলির একটি টেবিল তৈরি করতে পারি এবং এটি একটি শূন্য দিয়ে পূরণ করতে পারি এবং অনেকগুলি 7FFFFFFFF আছে।

পরিচালিত ভাষা

আপনি কেন পরিচালিত ভাষায় ভাল কাজ করে আশ্চর্য হতে পারে। সর্বোপরি, পরিচালিত ভাষাগুলি শাখাগুলির সাথে শৃঙ্খলের সীমানাগুলি পরীক্ষা করে দেখুন যাতে আপনি জগাখিচুড়ি না হন ...

আচ্ছা, ঠিক না ... :-)

পরিচালিত ভাষার জন্য এই শাখাটি নির্মূল করার বেশ কিছু কাজ হয়েছে। উদাহরণ স্বরূপ:

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

এই ক্ষেত্রে, এটি কম্পাইলারের কাছে স্পষ্ট যে সীমানা শর্ত কখনও আঘাত করা হবে না। কমপক্ষে মাইক্রোসফ্ট জিট কম্পাইলার (তবে আমি আশা করি জাভা একই জিনিসগুলি করবে) এটি লক্ষ্য করবে এবং চেকটি সম্পূর্ণভাবে মুছে ফেলবে। WOW - যে কোন শাখা মানে। একইভাবে, এটি অন্যান্য সুস্পষ্ট ক্ষেত্রে মোকাবেলা করবে।

পরিচালিত ভাষাগুলির সন্ধানে আপনি যদি সমস্যায় পড়েন তবে সীমানা পরীক্ষা & 0x[something]FFF আনতে আপনার কী কী & 0x[something]FFF ফাংশনটি একটি & 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();

অন্যদের দ্বারা ইতিমধ্যে উল্লেখ করা হয়েছে কি হিসাবে, রহস্য পিছনে শাখা predictor হয় কি ।

আমি কিছু যোগ করার চেষ্টা করছি না কিন্তু অন্য ভাবে ধারণা ব্যাখ্যা করছি। উইকি একটি সংক্ষিপ্ত পরিচিতি রয়েছে যা টেক্সট এবং ডায়াগ্রাম রয়েছে। আমি নীচের ব্যাখ্যাটি পছন্দ করি যা শাখা পূর্বাভাসদাতাকে intuitively সম্প্রসারিত করার জন্য একটি চিত্র ব্যবহার করে।

কম্পিউটার আর্কিটেকচারে, একটি শাখা পূর্বাভাসকারী একটি ডিজিটাল সার্কিট যা কোনও শাখা (যেমন- তারপর-যদি-অন্য কাঠামো) নিশ্চিত হওয়ার আগে এটি অনুমান করার চেষ্টা করে। শাখা পূর্বাভাস উদ্দেশ্য নির্দেশ পাইপলাইন প্রবাহ উন্নত করা হয়। শাখার ভবিষ্যদ্বাণীগুলি x86 হিসাবে অনেক আধুনিক পাইপলাইনযুক্ত মাইক্রোপ্রসেসার আর্কিটেকচারগুলিতে উচ্চ কার্যকরী কর্মক্ষমতা অর্জনে একটি গুরুত্বপূর্ণ ভূমিকা পালন করে।

দুই-উপায় শাখা সাধারণত একটি শর্তাধীন লাফ নির্দেশাবলী সঙ্গে প্রয়োগ করা হয়। শর্তসাপেক্ষ জাম্পটি "নেওয়া হয় না" এবং কোডের প্রথম শাখায় কার্যকর করা যেতে পারে যা শর্তাধীন ঝাঁপের পরে অবিলম্বে অনুসরণ করে বা এটি "নেওয়া" এবং প্রোগ্রাম মেমরির বিভিন্ন স্থানে যেতে পারে যেখানে কোডের দ্বিতীয় শাখা সংরক্ষণ করা হয়। এটি নির্দিষ্টভাবে জানানো হয় না যে কোনও শর্তাধীন লাফ নেওয়া হবে না বা শর্তটি গণনা না করা পর্যন্ত গৃহীত হবে না এবং শর্তাধীন ঝাঁপ নির্দেশ পাইপলাইনের নির্বাহ মঞ্চটি প্রেরণ করেছে (চিত্র দেখুন। 1)।

বর্ণিত দৃশ্যকল্পের উপর ভিত্তি করে, আমি বিভিন্ন পরিস্থিতিতে একটি পাইপলাইনে কিভাবে নির্দেশাবলী কার্যকর করা হয় তা দেখানোর জন্য একটি অ্যানিমেশন ডেমো লিখেছি।

  1. শাখা পূর্বাভাস ছাড়া।

শাখা পূর্বাভাস ছাড়াই, পরবর্তী নির্দেশটি পাইপলাইনে ভ্রূণ পর্যায়ে প্রবেশ করতে পারার আগে প্রসেসরটি কার্যকর সঞ্চালন পর্যায়টি পাস না হওয়া পর্যন্ত অপেক্ষা করতে হবে।

উদাহরণ তিন নির্দেশাবলী রয়েছে এবং প্রথম এক একটি শর্তাধীন লাফ নির্দেশনা রয়েছে। শর্তাধীন লাফ নির্দেশ কার্যকর না হওয়া পর্যন্ত পরবর্তী দুটি নির্দেশ পাইপলাইনে যেতে পারে।

3 নির্দেশাবলীর জন্য এটি 9 ঘড়ি চক্র গ্রহণ করবে।

  1. শাখা পূর্বাভাস ব্যবহার করুন এবং একটি শর্তাধীন লাফ না। চলুন অনুমান করা যে পূর্বাভাস শর্তাধীন লাফ গ্রহণ করা হয় না

3 নির্দেশাবলীর জন্য এটি 7 ঘড়ি চক্র গ্রহণ করবে।

  1. শাখা পূর্বাভাস ব্যবহার করুন এবং একটি শর্তাধীন লাফ নিন। চলুন অনুমান করা যে পূর্বাভাস শর্তাধীন লাফ গ্রহণ করা হয় না

3 নির্দেশাবলীর জন্য এটি 9 ঘড়ি চক্র গ্রহণ করবে।

একটি শাখা ভুল পূর্বাভাস ক্ষেত্রে নষ্ট হয় যে সময় পাইপলাইন পর্যায়ে পর্যাপ্ত পর্যায় থেকে সঞ্চালক পর্যায়ে সমান সংখ্যা। আধুনিক মাইক্রোপ্রসেসরগুলিতে দীর্ঘ লম্বা পাইপলাইন রয়েছে যাতে 10 এবং ২0 ঘড়ির চক্রের মধ্যে ভুল ভুলের বিলম্ব হয়। ফলস্বরূপ, পাইপলাইন তৈরি করা আরও একটি উন্নত শাখা ভবিষ্যদ্বাণী করার প্রয়োজন বাড়ায়।

আপনি দেখতে পারেন, মনে হচ্ছে আমাদের শাখা পূর্বাভাস ব্যবহার না করার কারণ নেই।

এটি একটি সাধারণ ডেমো যা শাখা পূর্বাভাসকের মূল অংশটিকে স্পষ্ট করে। যারা GIFs বিরক্তিকর, উত্তর থেকে তাদের অপসারণ করতে বিনা দ্বিধায় দয়া করে এবং দর্শক git থেকে ডেমো পেতে পারেনgit


শাখা ভবিষ্যদ্বাণী ত্রুটিগুলি এড়ানোর এক উপায় হল একটি সন্ধানের টেবিল তৈরি করা, এবং এটি ডেটা ব্যবহার করে সূচী। Stefan ডি Bruijn তার উত্তর যে আলোচনা।

কিন্তু এই ক্ষেত্রে, আমরা মানগুলি [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-বিট মানের জন্য আমরা কেবল উপরের অর্ধেক মান চাই, আমরা সম্ভাব্য 1২ বিট দ্বারা ডেটা স্থানান্তর করতে পারি এবং একটি টেবিলের সূচকের জন্য 1২-বিট মান সহ বাকি থাকতে পারি। একটি 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];

এখানে এই কোডটির একটি লিঙ্ক রয়েছে: লাল কালো গাছ , চিরতরে confuzzled


একই লাইনে (আমি মনে করি এটি কোনও উত্তর দ্বারা হাইলাইট করা হয়নি) এটি উল্লেখ করা ভাল যে কখনও কখনও (বিশেষত সফ্টওয়্যারগুলিতে যেখানে কার্যক্ষমতাগুলি-লিনাক্স কার্নেলের মতো) আপনি নীচের মত বিবৃতিগুলি খুঁজে পেতে পারেন:

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

বা অনুরূপভাবে:

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

উভয় likely()এবং unlikely()প্রকৃতপক্ষে ম্যাক্রোগুলি যা জি-সি-র মত কিছু ব্যবহার করে সংজ্ঞায়িত করা হয় __builtin_expect, কম্পাইলার সন্নিবেশ কোডটিকে ব্যবহারকারীর দ্বারা প্রদত্ত তথ্য বিবেচনা করে শর্তটি উপভোগ করতে সহায়তা করে। GCC অন্যান্য বিল্টিনগুলিকে সমর্থন করে যা চলমান প্রোগ্রামের আচরণ পরিবর্তন করতে পারে বা ক্যাশে সাফ করার মতো নিম্ন স্তরের নির্দেশনাগুলি নির্বাহ করে। উপলব্ধ GCC এর অন্তর্নির্মিতগুলিগুলির মাধ্যমে যা এই ডকুমেন্টেশনটি যায়।

সাধারণত এই ধরনের অপ্টিমাইজেশানগুলি প্রধানত হার্ড-রিয়েল টাইম অ্যাপ্লিকেশনগুলিতে বা এমবেডেড সিস্টেমে পাওয়া যায় যেখানে মৃত্যুদন্ড কার্যকর সময় এবং এটি সমালোচনামূলক। উদাহরণস্বরূপ, যদি আপনি কিছু ত্রুটি শর্ত পরীক্ষা করে থাকেন যা শুধুমাত্র 1/10000000 বার ঘটে তবে কেন কম্পাইলারকে এটি সম্পর্কে জানাবেন না? এই ভাবে, ডিফল্টরূপে, শাখা ভবিষ্যদ্বাণী অনুমান করবে যে শর্ত মিথ্যা।


ডেটা যখন সাজানো হয় তখন কর্মক্ষমতা উন্নতি করে যে কারণে শাখা পূর্বাভাসের শাস্তি সরানো হয়, যেমন উত্তর ব্যাখ্যা করা হয়েছে।

এখন, আমরা কোড তাকান

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

আমরা if... else... এই বিশেষটির অর্থ খুঁজে পেতে if... else... কোনও শর্ত সন্তুষ্ট হলে শাখাটি কিছু যোগ করতে হয়। এই ধরনের শাখা সহজেই একটি শর্তাধীন পদক্ষেপ বিবৃতিতে রূপান্তরিত করা যেতে পারে, যা একটি শর্তাধীন পদক্ষেপ নির্দেশনায় সংকলিত করা হবে: cmovl , একটি x86 সিস্টেমে। শাখা এবং এইভাবে সম্ভাব্য শাখা ভবিষ্যদ্বাণী জরিমানা মুছে ফেলা হয়।

C , এভাবে C++ , বিবৃতি, যা x86 এ শর্তাধীন পদক্ষেপ নির্দেশনায় সরাসরি (কোনও অপ্টিমাইজেশান ছাড়াই) কম্পাইল করবে, তা তিনটি অপারেটর ... ? ... : ... ... ? ... : ... তাই আমরা উপরের বিবৃতিটি সমতুল্য একটিতে পুনর্লিখন করি:

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

পাঠযোগ্যতা বজায় রাখার সময়, আমরা speedup ফ্যাক্টর চেক করতে পারেন।

একটি Intel Core i7-2600K @ 3.4 GHz এবং ভিজ্যুয়াল স্টুডিও 2010 রিলিজ মোডে, বেঞ্চমার্কটি (ফরম্যাট থেকে কপি করা ফর্ম্যাট):

এক্স 86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

ফলাফল একাধিক পরীক্ষায় শক্তসমর্থ। শাখা ফলাফল অনির্দেশ্য হয় যখন আমরা একটি দুর্দান্ত গতিপথ পেতে, কিন্তু এটা পূর্বাভাস যখন আমরা একটু সহ্য। প্রকৃতপক্ষে, একটি শর্তাধীন পদক্ষেপ ব্যবহার করার সময়, কর্মক্ষমতা তথ্য প্যাটার্ন নির্বিশেষে একই।

এখন তারা উৎপন্ন x86 সমাবেশ তদন্ত করে আরো ঘনিষ্ঠভাবে চেহারা যাক। সরলতার জন্য, আমরা দুটি ফাংশন max1 এবং max2 ব্যবহার 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 instruction cmovge ব্যবহারের কারণে অনেক কম কোড ব্যবহার করে। কিন্তু প্রকৃত লাভটি হল max2 শাখা জাম্প, max2 , যা ভবিষ্যদ্বাণী করা ফলাফল সঠিক না হলে উল্লেখযোগ্য পারফরম্যান্সের শাস্তি থাকবে না।

সুতরাং কেন একটি শর্তাধীন পদক্ষেপ ভাল সঞ্চালন না?

একটি সাধারণ x86 প্রসেসর ইন, একটি নির্দেশ কার্যকর করার বিভিন্ন পর্যায়ে বিভক্ত করা হয়। মোটামুটি, আমরা বিভিন্ন পর্যায়ে মোকাবেলা করার জন্য বিভিন্ন হার্ডওয়্যার আছে। সুতরাং একটি নতুন সূচনা শুরু করার জন্য আমাদের এক নির্দেশের জন্য অপেক্ষা করতে হবে না। এই pipelining বলা হয়।

একটি শাখা ক্ষেত্রে, নিম্নলিখিত নির্দেশ পূর্ববর্তী দ্বারা নির্ধারিত হয়, তাই আমরা পাইপলাইনিং করতে পারবেন না। আমরা অপেক্ষা বা পূর্বাভাস আছে।

একটি শর্তাধীন পদক্ষেপ ক্ষেত্রে, কার্যকর শর্তাধীন পদক্ষেপ নির্দেশনাটি বিভিন্ন পর্যায়ে বিভক্ত করা হয় তবে Fetch এবং Decode মতো পূর্ববর্তী ধাপ পূর্ববর্তী নির্দেশের ফলাফলের উপর নির্ভর করে না; শুধুমাত্র পরের পর্যায়ে ফলাফল প্রয়োজন। সুতরাং, আমরা একটি নির্দেশের নির্বাহ সময় একটি ভগ্নাংশ অপেক্ষা। ভবিষ্যদ্বাণী সহজ যখন শর্তাধীন পদক্ষেপ সংস্করণ শাখা তুলনায় ধীর হয়।

বই কম্পিউটার সিস্টেম: এ প্রোগ্রামার্স পার্সপেকটিভ বইটি দ্বিতীয় সংস্করণটি বিস্তারিতভাবে ব্যাখ্যা করে। শাখার ভবিষ্যদ্বাণী এবং মিসপ্রেডিকাল পেনাল্টিগুলির জন্য বিশেষ চিকিত্সার জন্য আপনি শর্তাধীন সরানো নির্দেশাবলীর জন্য বিভাগ 3.6.6, প্রসেসর আর্কিটেকচারের সমগ্র অধ্যায় 4 এবং বিভাগ 5.11.2 চেক করতে পারেন।

কখনও কখনও, কিছু আধুনিক কম্পাইলার ভাল কর্মক্ষমতা সহ সমাবেশে আমাদের কোডটি অপ্টিমাইজ করতে পারে, কখনও কখনও কিছু কম্পাইলার (প্রশ্ন কোডটি ভিজ্যুয়াল স্টুডিওর নেটিভ কম্পাইলার ব্যবহার করে) করতে পারে না। শাখা এবং শর্তাধীন পদক্ষেপের মধ্যে পারফরম্যান্সের পার্থক্যটি জানার সময় যখন অনুমানযোগ্য আমাদের উন্নত কর্মক্ষমতা সহ কোড লিখতে সহায়তা করতে পারে তখন দৃশ্যকল্পটি এত জটিল হয়ে যায় যে কম্পাইলার স্বয়ংক্রিয়ভাবে তাদের অপ্টিমাইজ করতে পারে না।


উপরের আচরণ শাখা পূর্বাভাসের কারণে ঘটছে।

শাখা ভবিষ্যদ্বাণী বুঝতে হলে প্রথমে নির্দেশনা পাইপলাইনটি বোঝা উচিত :

যেকোন নির্দেশনা ধাপে ক্রম অনুসারে বিভক্ত করা হয় যাতে বিভিন্ন পদক্ষেপগুলি সমান্তরালভাবে সমানভাবে কার্যকর করা যায়। এই কৌশল নির্দেশ পাইপলাইন হিসাবে পরিচিত এবং এই আধুনিক প্রসেসর মধ্যে থ্রুপুট বৃদ্ধি ব্যবহৃত হয়। এই ভাল বুঝতে দয়া করে উইকিপিডিয়ার এই উদাহরণটি দেখুন ।

সাধারণত, আধুনিক প্রসেসরগুলির বেশিরভাগ দীর্ঘ পাইপলাইন থাকে তবে সহজে এটির 4 টি ধাপ বিবেচনা করুন।

  1. যদি - মেমরি থেকে নির্দেশ আনতে
  2. আইডি - নির্দেশ ডিকোড
  3. EX - নির্দেশ কার্যকর করুন
  4. WB - সিপিইউ নিবন্ধন ফিরে লিখুন

2 নির্দেশাবলীর জন্য 4-পর্যায়ে পাইপলাইন।

উপরের প্রশ্নে ফিরে আসার নিম্নলিখিত নির্দেশাবলী বিবেচনা করা যাক:

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

শাখা পূর্বাভাস ছাড়া, নিম্নলিখিত ঘটবে:

নির্দেশনা বা নির্দেশনা সিটি চালানোর জন্য প্রসেসরকে নির্দেশ দিতে হবে যতক্ষণ না নির্দেশ A পাইপলাইনের পূর্ব পর্যায় পর্যন্ত পৌঁছাবে না, নির্দেশে যাওয়ার সিদ্ধান্ত B বা নির্দেশ C নির্দেশনার ফলাফলের উপর নির্ভর করে। সুতরাং পাইপলাইন এই মত চেহারা হবে।

যখন অবস্থা সত্য ফিরে আসে:

যখন অবস্থা মিথ্যা ফেরত দেয়:

নির্দেশের ফলাফলের জন্য অপেক্ষা করার ফলে, উপরের সিপিএস চক্রগুলি উপরের ক্ষেত্রে ব্যয় করা হয়েছে (শাখা পূর্বাভাস ছাড়া; সত্য এবং মিথ্যা উভয়ের জন্য) 7।

তাই শাখা ভবিষ্যদ্বাণী কি?

শাখা ভবিষ্যদ্বাণী নিশ্চিত করার জন্য কোন শাখা (কোন-যদি-অন্য-গঠন) আগে যেতে হবে তা অনুমান করার চেষ্টা করবে। পাইপলাইনের EX মঞ্চে পৌঁছানোর নির্দেশটি অপেক্ষা করবে না, তবে সিদ্ধান্তটি অনুমান করবে এবং সেই নির্দেশে যাবে (আমাদের উদাহরণের ক্ষেত্রে B বা C)।

সঠিক অনুমানের ক্ষেত্রে, পাইপলাইন এইরকম কিছু দেখায়:

যদি পরে এটি সনাক্ত করা হয় যে অনুমানটি ভুল ছিল তবে আংশিকভাবে কার্যকর নির্দেশাবলী বাতিল করা হবে এবং বিলম্বের কারণে, পাইপলাইনটি সঠিক শাখা দিয়ে শুরু হবে। একটি শাখা ভুল পূর্বাভাস ক্ষেত্রে নষ্ট হয় যে সময় পাইপলাইন পর্যায়ে পর্যাপ্ত পর্যায় থেকে সঞ্চালক পর্যায়ে সমান সংখ্যা। আধুনিক মাইক্রোপ্রসেসরগুলিতে দীর্ঘ লম্বা পাইপলাইন রয়েছে যাতে 10 এবং ২0 ঘড়ির চক্রের মধ্যে ভুল ভুলের বিলম্ব হয়। দীর্ঘ পাইপলাইন একটি ভাল শাখা predictor জন্য প্রয়োজন বৃহত্তর ।

অপারেটিং সিস্টেমের কোডে, শর্তাধীন প্রথমবারের মতো, শাখা পূর্বাভাসকারীর ভবিষ্যদ্বাণী ভিত্তিক কোন তথ্য নেই, তাই প্রথমবারের মতো এটি এলোমেলোভাবে পরবর্তী নির্দেশনাটি নির্বাচন করবে। পরে লুপের জন্য এটি ইতিহাসের পূর্বাভাসকে ভিত্তি করে তৈরি করতে পারে। আরোহী ক্রম অনুসারে সাজানো একটি অ্যারের জন্য, তিনটি সম্ভাবনার আছে:

  1. সব উপাদান 128 চেয়ে কম
  2. সমস্ত উপাদান 128 এর চেয়ে বেশি
  3. কিছু নতুন নতুন উপাদান 128 এর চেয়ে কম এবং পরে এটি 128 এর চেয়ে বেশি হয়ে ওঠে

আসুন আমরা অনুমান করি যে ভবিষ্যদ্বাণী সর্বদা প্রথম শাখায় প্রকৃত শাখাটি ধরবে।

সুতরাং প্রথম ক্ষেত্রে, ঐতিহাসিকভাবে তার সমস্ত ভবিষ্যদ্বাণী সঠিক হওয়ার পরে এটি সর্বদা সত্য শাখাটি নেবে। দ্বিতীয় ক্ষেত্রে, প্রাথমিকভাবে এটি ভুল ভবিষ্যদ্বাণী করা হবে, তবে কয়েক পুনরাবৃত্তি পরে, এটি সঠিকভাবে পূর্বাভাস দেবে। তৃতীয় ক্ষেত্রে, এটি 128 টিরও কম উপাদানগুলি পর্যন্ত সঠিকভাবে পূর্বাভাস দেবে। এর পরে এটি ইতিহাসে শাখা পূর্বাভাসের ব্যর্থতা দেখে কিছুটা সময় এবং সঠিক হবে।

এই সমস্ত ক্ষেত্রেই ব্যর্থতার সংখ্যা কম হবে এবং ফলস্বরূপ, মাত্র কয়েক বার এটি আংশিকভাবে কার্যকর নির্দেশগুলি বাতিল করতে হবে এবং সঠিক শাখা দিয়ে শুরু করবে, যার ফলে কম CPU চক্রগুলি হ্রাস পাবে।

কিন্তু একটি এলোমেলোভাবে বিন্যস্ত অ্যারের ক্ষেত্রে, ভবিষ্যদ্বাণীটি আংশিকভাবে চালিত নির্দেশগুলি বাতিল করতে হবে এবং সর্বাধিক সঠিক শাখা দিয়ে শুরু করতে হবে এবং ক্রম অনুসারে অ্যারের তুলনায় আরো CPU চক্রগুলির মধ্যে ফলাফল হবে।


সি ++ এ ব্যবহৃত প্রায়শই ব্যবহৃত বুলিয়ান ক্রিয়াকলাপগুলি সংকলিত প্রোগ্রামে অনেক শাখা তৈরি করে। এই শাখার ভিতরে loops হয় এবং ভবিষ্যদ্বাণী করা কঠিন তারা উল্লেখযোগ্যভাবে মৃত্যুদন্ড ধীর করতে পারেন। বুলিয়ান ভেরিয়েবল যেমন মান 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বিটwise অপারেটর ( &এবং |) ব্যবহার করা সম্ভব করার পরিবর্তে এটি ব্যবহার করা হয় । Bitwise অপারেটর একক ঘড়ি চক্র যে একক নির্দেশাবলী। বা অপারেটর ( ) কাজ করে এমনকি যদি এবং ছাড়া অন্য মান বা । এবং অপারেটর ( ) এবং একচেটিয়া বা অপারেটর ( যদি operands ছাড়া অন্য মান) অসঙ্গত ফলাফল দিতে পারে এবং ।&&|||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;

বেশিরভাগ ক্ষেত্রে সর্বোত্তম (যদি না আপনি &&এক্সপ্রেশনটি অনেক শাখা ভুল বানান তৈরি করার আশা করেন )।


কোন সন্দেহ নেই যে আমাদের মধ্যে কয়েকটি সিপিইউ শাখা-পূর্বাভাসের জন্য সমস্যাযুক্ত কোড সনাক্ত করার উপায়গুলিতে আগ্রহী হবে। Valgrind টুল 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 দ্বারা উত্পাদিত লাইন-বাই-লাইন আউটপুট মধ্যে নিচে তুরপুন আমরা প্রশ্ন লুপ জন্য দেখুন:

সাজানো:

          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) বর্ননাহীন সংস্করণে if (data[c] >= 128) লাইনটি ক্যাশগ্রিডের শাখা-পূর্বনির্ধারক মডেলের অধীনে 164,050,007 Bcm শর্তাধীন শাখা ( Bcm ) সৃষ্টি করে, তবে এটি সাজানো সংস্করণে শুধুমাত্র 10,006 ।

অন্যথায়, লিনাক্সে আপনি একই কাজটি সম্পাদন করতে পারফরমেন্স কাউন্টার সাব-সিস্টেম ব্যবহার করতে পারেন, তবে CPU কাউন্টার ব্যবহার করে স্থানীয় কর্মক্ষমতা সহ।

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)
...

আরো বিস্তারিত জানার জন্য কর্মক্ষমতা টিউটোরিয়াল দেখুন।


যদি আপনি এই কোডটিতে আরও বেশি অপটিমাইজেশান সম্পর্কে আগ্রহী হন, তবে এটি বিবেচনা করুন:

মূল লুপ দিয়ে শুরু হচ্ছে:

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 শর্তসাপেক্ষ হয় if আপনি if আউট হয়ে উঠতে 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. ইন্টেল - Mispredicts প্রতিরোধ করার জন্য শাখা এবং লুপ পুনর্গঠন
  3. বৈজ্ঞানিক কাগজপত্র - শাখা পূর্বাভাস কম্পিউটার স্থাপত্য
  4. বই: জেএল হেনেসি, ডিএ প্যাটারসন: কম্পিউটার আর্কিটেকচার: একটি পরিমাণগত পদ্ধতি
  5. বৈজ্ঞানিক প্রকাশনা প্রবন্ধসমূহ: হ্যাঁ Yeh, YN প্যাটার্ন শাখা পূর্বাভাস উপর এই অনেক তৈরি।

কেন আপনি শাখা পূর্বাভাস বিভ্রান্ত পায় কেন এই সুদৃশ্য diagram থেকে দেখতে পারেন ।

মূল কোড প্রতিটি উপাদান একটি র্যান্ডম মান

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

তাই ভবিষ্যদ্বাণী std::rand()আঘাত হিসাবে পক্ষের পরিবর্তন হবে ।

অন্যদিকে, এটি সাজানোর পরে, ভবিষ্যদ্বাণী প্রথমে দৃঢ়ভাবে গ্রহণ না করা অবস্থায় স্থানান্তরিত হবে এবং যখন মানগুলি উচ্চ মানের দিকে পরিবর্তিত হবে তখন ভবিষ্যদ্বাণী দৃঢ়ভাবে দৃঢ়ভাবে গ্রহণ না করেই তিনটি চালের মধ্যে পরিবর্তিত হবে।


এআরএমে, কোন শাখা প্রয়োজন নেই, কারণ প্রতিটি নির্দেশের একটি 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

সাজানো ক্ষেত্রে, আপনি সফল শাখা ভবিষ্যদ্বাণী বা কোন শাখাহীন তুলনা কৌশল উপর নির্ভর করার চেয়ে ভাল করতে পারেন: সম্পূর্ণভাবে শাখা অপসারণ।

প্রকৃতপক্ষে, অ্যারের সাথে একটি সংলগ্ন জোন data < 128এবং অন্য সঙ্গে বিভাজিত হয় data >= 128। সুতরাং আপনি পার্টিশন বিন্দুটি ডাইকোটোমিক অনুসন্ধানের সাথে Lg(arraySize) = 15তুলনা করুন ( তুলনা করে), তারপর সেই বিন্দু থেকে সরাসরি সংশ্লেষ করুন।

কিছু পছন্দ (অনির্ধারিত)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

অথবা, সামান্য আরো obfuscated

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

একটি দ্রুততর পদ্ধতির পদ্ধতি, যা সাজানো বা সাজানো উভয়ের জন্য আনুমানিক সমাধান দেয় : sum= 3137536;(সত্যিকারের ইউনিফর্ম বিতরণ, প্রত্যাশিত মান 191.5 সহ নমুনাগুলি অনুমান করা হচ্ছে 191.5) :-)


এটা সত্যি!...

শাখার ভবিষ্যদ্বাণী আপনার ধাপে যা ঘটছে তা স্যুইচিংয়ের কারণে লজিক চালনাকে ধীর করে তোলে! মনে হচ্ছে আপনি সোজা স্ট্রিট বা রাস্তায় যাচ্ছেন অনেক রাস্তা দিয়ে যাচ্ছেন, নিশ্চিতভাবেই সোজা হয়ে যাবেন দ্রুত!

অ্যারে সাজানো হয়, আপনার অবস্থা প্রথম ধাপে মিথ্যা: data[c] >= 128তারপর, রাস্তার শেষে সম্পূর্ণ ভাবে সত্যিকারের মান হয়ে যায়। এভাবেই আপনি যুক্তিটির শেষে দ্রুত পৌঁছাবেন। অন্যদিকে, একটি অসংগঠিত অ্যারে ব্যবহার করে, আপনাকে অনেক বাঁক এবং প্রক্রিয়াকরণ দরকার যা আপনার কোডটিকে নিশ্চিত করার জন্য ধীর গতির করে তোলে ...

নিচে আপনার জন্য তৈরি ইমেজ তাকান। কোন রাস্তা দ্রুত শেষ করা যাচ্ছে?

সুতরাং প্রোগ্রাম্যাটিক্যালি, শাখা ভবিষ্যদ্বাণী প্রক্রিয়া হ্রাস হতে কারণ ...

শেষ পর্যন্ত, এটি জানা ভাল যে আমাদের কাছে দুটি ধরণের শাখা পূর্বাভাস রয়েছে যা প্রত্যেকে আপনার কোডটিকে আলাদাভাবে প্রভাবিত করবে:

1. স্ট্যাটিক

2. গতিশীল

স্ট্যাটিক শাখা পূর্বাভাস মাইক্রোপ্রসেসর দ্বারা প্রথমবার একটি শর্তাধীন শাখা সম্মুখীন হয়, এবং নিয়মিত শাখা কোডের ফাঁসির জন্য ডাইনামিক শাখা ভবিষ্যদ্বাণী ব্যবহার করা হয়।

এই নিয়মগুলির সুবিধা নেওয়ার জন্য আপনার কোডটি কার্যকরভাবে লেখার জন্য, যদি অন্য-কিছু বা সুইচ স্টেটমেন্ট লেখার সময় প্রথমে সর্বাধিক সাধারণ ক্ষেত্রে পরীক্ষা করুন এবং কমপক্ষে কমপক্ষে সাধারণভাবে কাজ করুন। লুপগুলি স্ট্যাটিক শাখা পূর্বাভাসের জন্য কোডের কোনও বিশেষ ক্রম প্রয়োজন হয় না, কেবলমাত্র লুপ থেরাপির শর্তটি সাধারণত ব্যবহৃত হয়।


মেমরি ব্যবহার তার প্রিমিয়াম এ যেখানে এলাকায়, পয়েন্টার সহজে আসে। উদাহরণস্বরূপ, একটি মিনিম্যাক্স অ্যালগরিদম বিবেচনা করুন, যেখানে পুনরাবৃত্তিমূলক রুটিন ব্যবহার করে হাজার হাজার নোড তৈরি করা হবে এবং পরবর্তীতে গেমটিতে পরবর্তী সেরা পদক্ষেপের মূল্যায়ন করার জন্য, স্মার্টফোনের বিযুক্তকরণ বা পুনরায় সেট করার ক্ষমতা উল্লেখযোগ্যভাবে মেমরি খরচ হ্রাস করে। অ-পয়েন্টার ভেরিয়েবল যতক্ষণ না পুনরাবৃত্তি কল একটি মান ফেরত না হওয়া পর্যন্ত স্থান দখল করে চলতে থাকে।





java c++ performance optimization branch-prediction