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


9 Answers

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

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

Question

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

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

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

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

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



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

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

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

সাধারণত, আধুনিক প্রসেসরগুলির বেশিরভাগ দীর্ঘ পাইপলাইন থাকে তবে সহজে এটির 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 চক্রগুলির মধ্যে ফলাফল হবে।




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

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

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

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

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

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




আমি শুধু এই প্রশ্নের এবং তার উত্তর উপর পড়তে, এবং আমি একটি উত্তর অনুপস্থিত মনে হয়।

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

এই পদ্ধতির সাধারণ কাজ করে যদি:

  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- সীমানাটি পূর্বাভাসযোগ্য করে তুলতে আপনার সন্ধানের ফাংশনে একটি যোগ করা কী - এবং এটি আরও দ্রুত চলছে।

এই ক্ষেত্রে ফলাফল

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



শাখা ভবিষ্যদ্বাণী ত্রুটিগুলি এড়ানোর এক উপায় হল একটি সন্ধানের টেবিল তৈরি করা, এবং এটি ডেটা ব্যবহার করে সূচী। 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




এটা শাখা ভবিষ্যদ্বাণী সম্পর্কে। এটা কি?

  • একটি শাখা ভবিষ্যদ্বাণী প্রাচীন কর্মক্ষমতা উন্নত কৌশল যা এখনও আধুনিক স্থাপত্য মধ্যে প্রাসঙ্গিকতা খুঁজে। সাধারণ ভবিষ্যদ্বাণী কৌশলগুলি যখন দ্রুত ভুল সন্ধান এবং শক্তি দক্ষতা প্রদান করে তখন এটি একটি উচ্চ ভুলের হার থেকে ভুগছে।

  • অন্যদিকে, জটিল শাখার ভবিষ্যদ্বাণী - উভয় স্তরের শাখা পূর্বাভাসের স্নায়বিক ভিত্তিক বা বৈকল্পিক-ভাল ভবিষ্যদ্বাণী নির্ভুলতা প্রবর্তন করে, তবে তারা আরও শক্তি এবং জটিলতাকে দ্রুত বর্ধনশীল করে।

  • এর পাশাপাশি, জটিল ভবিষ্যদ্বাণী কৌশলগুলিতে শাখাগুলি পূর্বাভাস দেওয়ার জন্য সময় নেওয়া খুব বেশি-থেকে 2 থেকে 5 চক্রের মধ্যে-যা প্রকৃত শাখার নির্বাহের সময় সমান।

  • শাখা ভবিষ্যদ্বাণীটি মূলত একটি অপ্টিমাইজেশান (ক্ষুদ্রীকরণ) সমস্যা যেখানে সর্বনিম্ন সম্ভাব্য মিস রেট, কম শক্তি খরচ এবং সর্বনিম্ন সংস্থার কম জটিলতা অর্জনের উপর জোর দেওয়া হয়।

শাখা তিনটি ভিন্ন ধরনের আছে:

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

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

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

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

তথ্যসূত্র:




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

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

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

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

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

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

1. স্ট্যাটিক

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 শর্তসাপেক্ষ হয় 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 দ্রুত




শাখা-ভবিষ্যদ্বাণী লাভ!

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

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

যখনই একটি আছে if-else\ switchবিবৃতি প্রকাশের নির্ধারণ করতে যা ব্লক চালানো উচিত মূল্যায়ন করতে হবে। কম্পাইলার দ্বারা উত্পন্ন সমাবেশ কোড, শর্তাধীন branch নির্দেশাবলী সন্নিবেশ করা হয়।

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

যে বলা হচ্ছে, কম্পাইলার প্রকৃতপক্ষে মূল্যায়নের পূর্বে ফলাফল পূর্বাভাস করার চেষ্টা করে। এটা ifব্লক থেকে নির্দেশাবলী আনতে হবে , এবং যদি অভিব্যক্তি সত্য হতে সক্রিয়, তারপর বিস্ময়কর! আমরা এটি মূল্যায়ন এবং কোড উন্নতি অগ্রগতি সময় গ্রহণ; যদি না হয় তবে আমরা ভুল কোডটি চালাচ্ছি, পাইপলাইনে ফ্লাশ করা হয়েছে এবং সঠিক ব্লকটি চালানো হচ্ছে।

ভিজুয়ালাইজেশান:

ধরুন আপনার রুট 1 বা রুট 2 নিতে হবে। আপনার অংশীদারের জন্য মানচিত্রটি পরীক্ষা করার জন্য অপেক্ষা করছেন, আপনি ## এ থামুন এবং অপেক্ষা করেছেন, অথবা আপনি রুট 1 বেছে নিতে পারেন এবং যদি আপনি ভাগ্যবান হন (রুট 1 সঠিক রুট), তারপরে আপনাকে আপনার অংশীদারকে মানচিত্রটি পরীক্ষা করার জন্য অপেক্ষা করতে হবে না (আপনি মানচিত্রটি পরীক্ষা করতে সময় নিয়ে যাবেন সে সময়টি সংরক্ষণ করেছিলেন), অন্যথায় আপনি ফিরে আসবেন।

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

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



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

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

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



Related