java لماذا هو أسرع لمعالجة صف مصنفة من صفيف لم يتم فرزها؟




c++ performance (17)

السبب في تحسن الأداء بشكل كبير عندما يتم فرز البيانات هو أن يتم إزالة عقوبة التنبؤ فرع ، كما هو موضح بشكل جميل في الجواب .

الآن ، إذا نظرنا إلى الشفرة

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

يمكننا أن نجد أن معنى هذا الفرع المعنون if... else... هو إضافة شيء ما عند استيفاء الشرط. يمكن تحويل هذا النوع من الفروع بسهولة إلى بيان تحرك شرطي ، والذي سيتم تجميعه في تعليمات نقل مشروطة: cmovl ، في نظام x86 . يتم إزالة الفرع وبالتالي عقوبة المحتملة فرع التنبؤ.

في C ، وبالتالي C++ ، البيان ، الذي سيترجم مباشرة (بدون أي تحسين) إلى تعليمات النقل المشروطة في x86 ، هو المشغل الثلاثي ... ? ... : ... ... ? ... : ... لذا ، نعيد كتابة العبارة أعلاه إلى بيان مماثل:

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

مع الحفاظ على سهولة القراءة ، يمكننا التحقق من عامل السرعة.

في وضع Intel Core i7 -2600K @ 3.4 غيغاهرتز و Visual Studio الإصدار 2010 ، يكون المعيار (تم نسخ التنسيق من Mysticial):

إلى x86

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

يستخدم max1 الفرع الشرطي if... else ... :

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

يستخدم max2 المشغل الثلاثي ... ? ... : ... ... ? ... : ... :

int max2(int a, int b) {
    return a > b ? a : b;
}

على جهاز x86-64 ، تقوم GCC -S بإنشاء التجميع أدناه.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

يستخدم max2 رمز أقل بكثير بسبب استخدام cmovge التعليمات. لكن الكسب الحقيقي هو أن max2 لا يتضمن قفزات فرعية ، jmp ، والتي سيكون لها جزاء أداء كبير إذا كانت النتيجة المتوقعة غير صحيحة.

فلماذا تؤدي الحركة الشرطية بشكل أفضل؟

في معالج x86 نموذجي ، ينقسم تنفيذ التعليمات إلى عدة مراحل. تقريبا ، لدينا أجهزة مختلفة للتعامل مع المراحل المختلفة. لذلك ليس علينا الانتظار حتى تنتهي إحدى التعلميات لبدء واحدة جديدة. وهذا ما يسمى pipelining .

في حالة الفرع ، يتم تحديد التعليمات التالية بواسطة الحالة السابقة ، لذلك لا يمكننا تنفيذ خط الأنابيب. علينا إما الانتظار أو التنبؤ.

في حالة نقل الشرطية ، يتم تقسيم تعليمات النقل الشرطي للتنفيذ إلى عدة مراحل ، ولكن لا تعتمد المراحل السابقة مثل Fetch و Decode على نتيجة التعليمة السابقة ؛ المراحل الأخيرة فقط تحتاج إلى النتيجة. وبالتالي ، فإننا ننتظر جزءًا من وقت تنفيذ التعليمة الواحدة. هذا هو السبب في أن إصدار النقل الشرطي أبطأ من الفرع عندما يكون التوقع سهلاً.

كتاب أنظمة الكمبيوتر: منظور المبرمج ، الطبعة الثانية تشرح ذلك بالتفصيل. يمكنك التحقق من القسم 3.6.6 من تعليمات النقل الشرطي ، الفصل 4 بأكمله في معمارية المعالج ، والقسم 5.11.2 من أجل معالجة خاصة لعقوبات التنبؤ بالعواقب والمخاطر .

في بعض الأحيان ، يمكن لبعض compilers الحديثة تحسين التعليمات البرمجية الخاصة بنا إلى التجميع مع أداء أفضل ، أحياناً بعض compilers لا يمكن (التعليمات البرمجية في السؤال يستخدم برنامج التحويل البرمجي الأصلي Visual Studio). يمكن أن يساعدنا معرفة فرق الأداء بين الفرع والحركة المشروطة عندما لا يمكن التنبؤ بها في كتابة التعليمات البرمجية بأداء أفضل عندما يصبح السيناريو معقدًا لدرجة لا يستطيع المترجم من خلالها تحسينها تلقائيًا.

هنا هو قطعة من رمز C ++ التي تبدو غريبة جدا. لسبب غريب ، يؤدي ترتيب البيانات إلى جعل الشفرة أسرع بمعدل ست مرات.

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

مع نتيجة مشابهة إلى حد ما ولكن أقل تطرفا.

كان أول ما فكرت به هو أن الفرز يجلب البيانات إلى ذاكرة التخزين المؤقت ، ولكن بعد ذلك فكرت كم هو سخيف لأن المصفوفة تم إنشاؤها للتو.

  • ما الذي يجري؟
  • لماذا هو أسرع لمعالجة صف مصنفة من صفيف لم يتم فرزها؟
  • تلخص الشفرة بعض المصطلحات المستقلة ، ويجب ألا يهم الأمر.

الجواب الرسمي سيكون من

  1. انتل - تجنب كلفة سوء الفهم
  2. إنتل - فرع وإعادة تنظيم حلقة لمنع سوء التوقيعات
  3. أوراق علمية - هندسة معمارية تتنبأ بفرع
  4. كتب: JL هينيسي ، DA باترسون: هندسة الكمبيوتر: نهج كمي
  5. مقالات في المنشورات العلمية: TY Yeh ، YN Patt قدمت الكثير من هذه التنبؤات الفرعية.

يمكنك أيضًا أن ترى من هذا diagram الجميل سبب اختلاط فرع التنبؤ.

كل عنصر في الكود الأصلي هو قيمة عشوائية

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

لذلك فإن المتنبئ سيغير الجانبين std::rand()كضربة.

من ناحية أخرى ، بمجرد أن يتم فرزها ، سينتقل المتنبئ أولاً إلى حالة لا يتم أخذها بقوة وعندما تتغير القيم إلى القيمة المرتفعة التي سيعمل بها المتنبئ في ثلاث خطوات من خلال التغيير على طول الطريق من عدم أخذها بقوة إلى قوة.


إذا كنت تشعر بالفضول بشأن المزيد من التحسينات التي يمكن القيام بها لهذا الرمز ، ففكر في هذا:

بدءا من الحلقة الأصلية:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

من خلال تبادل الحلقات ، يمكننا تغيير هذه الحلقة بأمان:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

ثم ، يمكنك أن ترى أن الشرطية if ثابتة طوال تنفيذ حلقة i ، حتى يمكنك رفع if الخروج:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

ثم ، سترى أنه يمكن طي الحلقة الداخلية في تعبير واحد ، على افتراض أن نموذج النقطة العائمة يسمح بذلك (/ fp: يتم طرح سريع ، على سبيل المثال)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

هذا واحد هو 100000x أسرع من ذي قبل


نظرًا لتوزيع البيانات بين 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الاستنتاج أبطأ بستة أضعاف من النمط " الجيد "! بطبيعة الحال ، ما هو النمط الجيد والسيئ يعتمد على التعليمات الدقيقة التي يولدها المترجم وعلى المعالج الخاص.

لذلك ليس هناك شك حول تأثير التنبؤ فرع على الأداء!


لقد قرأت للتو عن هذا السؤال وأجوبته ، وأشعر أن هناك إجابة مفقودة.

من الطرق الشائعة للتخلص من التنبؤ الفرعى الذي وجدته جيدًا في اللغات المدارة هو البحث عن جدول بدلاً من استخدام فرع (على الرغم من أنني لم أختبره في هذه الحالة).

يعمل هذا النهج بشكل عام إذا:

  1. إنها طاولة صغيرة ومن المحتمل تخزينها مؤقتًا في المعالج
  2. أنت تقوم بتشغيل الأشياء في حلقة ضيقة جدًا و / أو يمكن للمعالج تحميل البيانات مسبقًا

الخلفية ولماذا

ما هذا الجحيم الذي من المفترض أن يعني؟

من منظور المعالج ، تكون الذاكرة بطيئة. للتعويض عن الاختلاف في السرعة ، فإنها تقوم ببناء مخابئ في المعالج (L1 / L2 cache) لتعويض ذلك. لذا تخيل أنك تقوم بحساباتك الحسنة وتكتشف أنك بحاجة إلى جزء من الذاكرة. سيحصل المعالج على عملية "التحميل" ويحمّل قطعة الذاكرة في ذاكرة التخزين المؤقت - ثم يستخدم ذاكرة التخزين المؤقت لإجراء بقية العمليات الحسابية. نظرًا لأن الذاكرة بطيئة نسبيًا ، سيؤدي هذا "التحميل" إلى إبطاء البرنامج.

مثل التنبؤ بالفرع ، تم تحسين ذلك في معالجات Pentium: يتوقع المعالج أنه يحتاج إلى تحميل جزء من البيانات ويحاول تحميله في ذاكرة التخزين المؤقت قبل أن تضرب العملية فعليًا ذاكرة التخزين المؤقت. كما رأينا سابقاً ، فإن التنبؤ بالفروع يذهب أحياناً بشكل خاطئ - في أسوأ الحالات ، تحتاج إلى العودة والانتظار فعليًا لحمل ذاكرة ، والذي سيستغرق إلى الأبد ( وبعبارة أخرى: فشل التنبؤ بالفرع هو سيئ ، ذاكرة تحميل بعد فشل فرع التنبؤ هو مجرد الرهيبة! ).

لحسن الحظ بالنسبة لنا ، إذا كان نمط الوصول إلى الذاكرة قابلاً للتنبؤ ، فسيقوم المعالج بتحميله في ذاكرة التخزين المؤقت السريعة وكل شيء على ما يرام.

أول شيء نحتاج إلى معرفته هو ما هو صغير ؟ بينما يكون الأصغر بشكل عام أفضل ، فإن القاعدة الأساسية هي الالتصاق بجداول البحث التي تبلغ <= 4096 بايت في الحجم. كحد أعلى: إذا كان جدول البحث أكبر من 64 كيلو بايت ، فربما يستحق الأمر إعادة النظر.

بناء طاولة

لذلك اكتشفنا أنه يمكننا إنشاء طاولة صغيرة. والشيء التالي الذي يجب عمله هو الحصول على وظيفة البحث في مكانها. دالات البحث عادة ما تكون وظائف صغيرة تستخدم زوجين من العمليات الأساسية الأساسية (و ، أو ، xor ، shift ، add ، remove و might multiply). إذا كنت تريد أن تتم ترجمة إدخالك من خلال وظيفة البحث إلى نوع من "المفتاح الفريد" في الجدول الخاص بك ، فهذا يعني ببساطة أنه يوفر لك الإجابة عن كل الأعمال التي تريد أن تقوم بها.

في هذه الحالة:> = 128 يعني أنه يمكننا الاحتفاظ بالقيمة ، يعني <128> أننا نتخلص منها. أسهل طريقة للقيام بذلك هي استخدام "AND": إذا احتفظنا بها ، فإننا نحن و 7 CFFFFFF ؛ إذا أردنا التخلص منه ، ونحن مع 0. لاحظ أيضا أن 128 هي قوة 2 - حتى نتمكن من المضي قدما وجعل جدول من 32768/128 الأعداد الصحيحة وملئه مع صفر واحد والكثير من و7FFFFFFFF.

اللغات المدارة

قد تتساءل لماذا يعمل هذا بشكل جيد في اللغات المدارة. بعد كل شيء ، تحقق اللغات المدارة من حدود المصفوفات مع فرع لضمان عدم العبث ...

حسنا ، ليس بالضبط ... :-)

كان هناك بعض العمل على القضاء على هذا الفرع للغات المدارة. فمثلا:

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

في هذه الحالة ، من الواضح أن المحول البرمجي لن يتم ضرب شرط الحدود. على الأقل مترجم Microsoft JIT (ولكن أتوقع Java يفعل أشياء مشابهة) سوف تلاحظ هذا وإزالة الاختيار تماما. نجاح باهر - وهذا يعني عدم وجود فرع. وبالمثل ، فإنه سيتناول الحالات الواضحة الأخرى.

إذا واجهت مشكلة مع عمليات البحث في اللغات التي تتم إدارتها - فالمفتاح هو إضافة علامة & 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();

عمليات Boolean المستخدمة بشكل متكرر في C ++ إنتاج العديد من الفروع في برنامج مترجمة. إذا كانت هذه الفروع داخل حلقات ومن الصعب التنبؤ بأنها يمكن أن تبطئ التنفيذ بشكل كبير. يتم تخزين متغيرات منطقية أنها أعداد صحيحة 8 بت مع القيمة 0ل falseو 1ل true.

يتم تحديد المتغيرات البولية أكثر من المعنى بمعنى أن جميع المشغلين الذين لديهم متغيرات منطقية كمدخل يتحققون من أن المدخلات لها أي قيمة أخرى من 0أو 1، لكن المشغلين الذين لديهم Booleans كمخرج لا يمكن أن ينتجوا أي قيمة أخرى من 0أو 1. هذا يجعل العمليات مع المتغيرات Boolean كمدخل أقل كفاءة من اللازم. النظر في المثال:

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أجل تمكين استخدام عوامل تشغيل البت ( &و |) بدلاً من عوامل التشغيل المنطقية ( &&و ||). عوامل تشغيل البت هي تعليمات فردية تأخذ دورة ساعة واحدة فقط. المشغل OR ( |) يعمل حتى لو aو bلها قيمة أخرى من 0أو 1. عامل التشغيل AND ( &) و EXCLUSIVE OR operator ( ^) قد يعطي نتائج غير متناسقة إذا كانت المعاملات تحتوي على قيم أخرى من 0و 1.

~لا يمكن استخدامها ل NOT. بدلاً من ذلك ، يمكنك جعل Boolean NOT على متغير معروف أنه 0أو 1بواسطة XOR'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;

هو الأمثل في معظم الحالات (إلا إذا كنت تتوقع &&أن ينتج عن هذا التعبير العديد من سوء تفسير الفروع).


أنت ضحية لتوقع فرع الفشل.

ما هو التنبؤ فرع؟

النظر في مفترق السكك الحديدية:

عن طريق Mecanismo ، عبر ويكيميديا ​​كومنز. تُستخدم تحت رخصة CC-By-SA 3.0 .

الآن من أجل الجدل ، افترض أن هذا يعود في 1800s - قبل الاتصال البعيدة أو الراديو.

أنت المشغل للتقاطع وتسمع قطار قادم. ليس لديك فكرة عن الطريقة التي من المفترض أن تذهب. توقف القطار عن سؤال السائق عن الاتجاه الذي يريده. ثم قمت بتعيين التبديل بشكل مناسب.

القطارات ثقيلة ولديها الكثير من القصور الذاتي. لذلك يأخذون إلى الأبد لبدء وإبطاء.

هل هناك طريقة أفضل؟ أنت تخمن أي اتجاه سيذهب القطار!

  • إذا كنت خمنت الحق ، فإنه يستمر.
  • إذا كنت قد خمنت خطأ ، سيتوقف القبطان عن العمل ، وينسخه احتياطياً ، ويصيح في وجهك لقلب المفتاح. ثم يمكن إعادة تشغيل المسار الآخر.

إذا كنت على حق في كل مرة ، لن يتوقف القطار أبدًا.
إذا كنت تخمن الخطأ في كثير من الأحيان ، سينفق القطار الكثير من الوقت في التوقف والنسخ الاحتياطي وإعادة التشغيل.

خذ بعين الاعتبار if-statement: على مستوى المعالج ، هو تعليمة فرع:

أنت معالج وترى فرع. ليس لديك أي فكرة عن الطريقة التي ستذهب بها. ماذا تفعل؟ يمكنك إيقاف التنفيذ والانتظار حتى تكتمل الإرشادات السابقة. ثم تستمر في المسار الصحيح.

المعالجات الحديثة معقدة ولها خطوط أنابيب طويلة. لذلك يأخذون إلى الأبد "الاحماء" و "تبطئ".

هل هناك طريقة أفضل؟ يمكنك تخمين الاتجاه الذي سوف يذهب الفرع!

  • إذا خمنت حقًا ، فأنت تستمر في التنفيذ.
  • إذا كنت خمنت خطأ ، تحتاج إلى مسح خط الأنابيب وتراجع إلى الفرع. ثم يمكنك إعادة تشغيل المسار الآخر.

إذا كنت تخمين الحق في كل مرة ، لن يتوقف التنفيذ أبدا.
إذا كنت تخمين الخطأ في كثير من الأحيان ، فإنك تقضي الكثير من الوقت في التوقف ، والتراجع ، وإعادة التشغيل.

هذا هو التنبؤ فرع. أعترف أنه ليس أفضل تشبيه لأن القطار كان يمكن أن يشير فقط إلى الاتجاه بعلم. ولكن في أجهزة الكمبيوتر ، لا يعرف المعالج أي اتجاه سيذهب إليه الفرع حتى آخر لحظة.

إذاً ، كيف ستخمن استراتيجياً لتقليل عدد المرات التي يجب أن يقوم فيها القطار بالنسخ الاحتياطي والهبوط في المسار الآخر؟ أنت تنظر إلى التاريخ الماضي! إذا غادر القطار 99٪ من الوقت ، فحينئذٍ يمكنك تخمين اليسار. إذا بدل ذلك ، فإنك بديل التخمينات الخاصة بك. إذا ذهبت بطريقة واحدة كل 3 مرات ، فأنت تخمن نفس الشيء ...

بمعنى آخر ، تحاول تحديد نمط ومتابعته. هذا هو أكثر أو أقل كيف تعمل فروع التنبؤ.

معظم التطبيقات لديها فروع حسنة التصرف. لذلك ، عادةً ما تحقق تنبؤات الفروع الحديثة أكثر من 90٪ من معدلات النجاح. ولكن عند مواجهة فروع لا يمكن التنبؤ بها دون وجود أنماط يمكن التعرف عليها ، تنبئ الفروع غير مجدية.

مزيد من القراءة: مقال "فرع متنبئ" على ويكيبيديا .

كما ألمح من فوق ، فإن الجاني هو هذا if-statement:

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

لاحظ أن البيانات موزعة بالتساوي بين 0 و 255. عندما يتم فرز البيانات ، لن يدخل النصف الأول من التكرارات في if-statement. بعد ذلك ، سيدخلون جميعًا في بيان if.

هذا هو ودية للغاية لمتنبئ الفرع حيث يذهب الفرع بشكل متتابع في نفس الاتجاه عدة مرات. حتى العداد المشبع البسيط سوف يتنبأ بشكل صحيح بالفرع باستثناء التكرارات القليلة بعد أن يغير اتجاهه.

التصور السريع:

T = branch taken
N = branch not taken

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

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

ومع ذلك ، عندما تكون البيانات عشوائية تمامًا ، يتم عرض متنبئ الفرع عديم الفائدة لأنه لا يمكنه التنبؤ بالبيانات العشوائية. وبالتالي سيكون هناك على الأرجح حوالي 50 ٪ من سوء التقدير. (لا يوجد أفضل من التخمين العشوائي)

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

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

إذن ما الذي يمكن عمله؟

إذا كان المحول البرمجي غير قادر على تحسين الفرع في خطوة مشروطة ، فيمكنك تجربة بعض الاختراقات إذا كنت على استعداد للتضحية بالقابلية للأداء.

يحل محل:

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

مع:

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

هذا يحل الفرع ويستبدلها ببعض عمليات البت.

(لاحظ أن هذا الاختراق لا يماثل تمامًا العبارة الأصلية if-statement. ولكن في هذه الحالة ، يكون صالحًا لكل قيم إدخال data[] .)

المقاييس: كور i7 920 @ 3.5 غيغاهرتز

C ++ - Visual Studio 2010 - الإصدار x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

الملاحظات:

  • مع الفرع: هناك فرق كبير بين البيانات المفروزة وغير المفروزة.
  • مع هاك: لا يوجد فرق بين البيانات المفروزة وغير المفروزة.
  • في حالة C ++ ، يكون الاختراق أبطأ أبطأ من الفرع عندما يتم فرز البيانات.

والقاعدة العامة هي تجنب المتفرعة المعتمدة على البيانات في الحلقات الحرجة. (على سبيل المثال في هذا المثال)

تحديث:

  • GCC 4.6.1 مع -O3 أو -ftree-vectorize على x64 قادر على توليد حركة شرطية. لذلك لا يوجد فرق بين البيانات المفروزة والمفرطة - كلاهما سريعان.

  • VC ++ 2010 غير قادر على إنشاء حركات شرطية لهذا الفرع حتى تحت /Ox .

  • إنتل مترجم 11 يفعل شيئا معجزة. وهي تتبادل الحلقتين ، وبالتالي رفع فرع لا يمكن التنبؤ بها إلى الحلقة الخارجية. لذلك فهي ليست فقط محصنة لسوء التوقعات ، بل هي أيضا أسرع مرتين من أي VC ++ و GCC يمكن أن تولد! وبعبارة أخرى ، استفادت المحكمة الجنائية الدولية من حلقة الاختبار لإلحاق الهزيمة بالمعايير ...

  • إذا أعطيت Intel Compiler الشفرة الخالية من الشفرة ، فسيتم توجيهها إلى اليمين فقط ... وهي بنفس سرعة الفرع (مع تبادل الحلقات).

هذا يدل على أنه حتى المترجمين الحديثين الناضجين يمكن أن يختلفان بشدة في قدرتهما على تحسين الكود ...


كسب التنبؤ الفروع!

من المهم أن نفهم أن سوء فهم الفرع لا يبطئ البرامج. إن تكلفة التنبؤ الفائت هي كما لو أن التوقع الفرعي لم يكن موجودًا وانتظرت تقييم التعبير لتحديد الكود المطلوب تشغيله (مزيد من الشرح في الفقرة التالية).

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

عندما يكون هناك عبارة if-else\ switchstatement ، يجب تقييم التعبير لتحديد الكتلة المطلوب تنفيذها. في رمز التجميع الذي تم إنشاؤه بواسطة المحول البرمجي ، يتم إدراج تعليمات branch الشرطي .

يمكن أن يتسبب تعليمة الفروع في أن يبدأ الكمبيوتر في تنفيذ تسلسل تعليمي مختلف ، ومن ثم ينحرف عن سلوكه الافتراضي لتنفيذ التعليمات بالترتيب (أي إذا كان التعبير خاطئًا ، يتخطى البرنامج شفرة ifالكتلة) بناءً على بعض الشروط ، تقييم التعبير في حالتنا.

ومع ذلك ، يحاول المترجم التنبؤ بالنتيجة قبل تقييمها فعليًا. وسوف تجلب التعليمات من ifالكتلة ، وإذا تبين أن التعبير صحيح ، ثم رائع! لقد حصلنا على الوقت الذي استغرقته لتقييمه وإحراز تقدم في الشفرة ؛ إذا لم يكن الأمر كذلك فإننا ندير الكود الخاطئ ، يتم مسح خط الأنابيب ، ويتم تشغيل الكتلة الصحيحة.

التصور:

لنفترض أنك بحاجة إلى اختيار الطريق 1 أو الطريق 2. في انتظار التحقق من الشريك للخريطة ، توقفت عند ## وانتظرت ، أو يمكنك فقط اختيار الطريق 1 وإذا كنت محظوظًا (الطريق 1 هو المسار الصحيح) ، عندئذٍ لم تكن مضطرًا إلى الانتظار حتى يتحقق شريكك من الخريطة (التي قمت بحفظ الوقت الذي كان سيأخذها إليه للتحقق من الخريطة) ، وإلا فإنك ستعود إلى الخلف.

في حين أن خطوط الأنابيب تتدفق بسرعة فائقة ، فإن أخذ هذه المقامرة في الوقت الحاضر يستحق ذلك. إن التنبؤ بالبيانات المصنفة أو البيانات التي تتغير ببطء يكون دائمًا أسهل وأفضل من التنبؤ بالتغييرات السريعة.

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

في الحالة التي تم فرزها ، يمكنك أن تفعل أفضل من الاعتماد على توقع فرع ناجح أو أي خدعة مقارنة دون فرع: إزالة الفرع بالكامل.

في الواقع ، يتم تقسيم المصفوفة في منطقة مجاورة مع 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];

أو ، أكثر قليلا غامضة

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;(على افتراض توزيع موحد حقا ، 16384 عينات مع القيمة المتوقعة 191.5) :-)


انها عن التنبؤ فرع. ما هذا؟

  • يعتبر متنبئ الفرع أحد تقنيات تحسين الأداء القديمة التي لا تزال تجد أهمية في معماريات حديثة. في حين أن تقنيات التنبؤ البسيطة توفر بحثًا سريعًا وكفاءة في استهلاك الطاقة ، فإنها تعاني من نسبة عالية من الخطأ في التنبؤ.

  • من ناحية أخرى ، فإن التنبؤات المعقدة للفرع ، سواء كانت قائمة على أساس جيني أو متغيرات من التنبؤ ذي الفروع على مستويين ، توفر دقة أفضل للتنبؤ ، ولكنها تستهلك المزيد من القوة والتعقيد وتزداد أضعافا مضاعفة.

  • بالإضافة إلى ذلك ، في تقنيات التنبؤ المعقدة ، فإن الوقت المستغرق للتنبؤ بالفروع يكون في حد ذاته مرتفعًا جدًا من 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];

هذا التعليمة البرمجية تهدر نصف عدد المرات ، ولكن لا يوجد به أي فشل في التنبؤ بالفرع. انها أسرع بشكل كبير على البيانات العشوائية من الإصدار مع بيان if الفعلي.

ولكن في الاختبار الخاص بي ، كان جدول البحث السريع أسرع قليلاً من هذا ، ربما بسبب الفهرسة في جدول البحث كان أسرع قليلاً من نقل بت. يوضح هذا كيفية إعداد التعليمة البرمجية الخاصة بي واستخدامها في جدول البحث (يسمى بشكل غير lutمتوقع "LookUp Table" في التعليمات البرمجية). إليك رمز C ++:

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

إليك رابط لهذا الرمز: Red Black Trees ، Confluzzled عبر الزمن


إلى جانب حقيقة أن توقع الفرع قد يبطئك ، فإن مصفوفة الفرز لها ميزة أخرى:

يمكن أن يكون لديك شرط إيقاف بدلاً من مجرد التحقق من القيمة ، وبهذه الطريقة تقوم فقط بحل البيانات ذات الصلة ، وتجاهل الباقي.
سوف تفوت التنبؤ فرع مرة واحدة فقط.

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

لا شك في أن البعض منا سيهتم بطرق تحديد الكودات التي تثير المشاكل بالنسبة لمؤشر فرع وحدة المعالجة المركزية. الأداة craggrind أداة cachegrind لديها محاكي التنبؤ فرع ، مكنت باستخدام --branch-sim=yes العلم. تشغيله على الأمثلة في هذا السؤال ، مع عدد من الحلقات الخارجية خفضت إلى 10000 وتجميعها مع g++ ، يعطي هذه النتائج:

مرتبة:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

لم يتم فرزها:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

الحفر لأسفل في إخراج سطر سطر بواسطة cg_annotate نرى للحلقة في السؤال:

مرتبة:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

لم يتم فرزها:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

يتيح لك ذلك تحديد الخط الإشكالي بسهولة - في النسخة التي لم يتم فرزها ، if (data[c] >= 128) يسبب 164،050،007 فرعيًا شرطيًا خاطئًا ( Bcm ) تحت نموذج متنبئ فرع cachegrind ، بينما يتسبب فقط في حدوث 10،006 في النسخة التي تم فرزها .

بدلاً من ذلك ، في Linux يمكنك استخدام النظام الفرعي عدادات الأداء لإنجاز نفس المهمة ، ولكن مع الأداء الأصلي باستخدام عدادات 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

ويمكنه أيضًا عمل التعليقات التوضيحية للكود المصدري مع التفكيك.

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

انظر البرنامج التعليمي للأداء لمزيد من التفاصيل.


بالتأكيد!...

يجعل توقع الفرع المنطقي أبطأ ، بسبب التبديل الذي يحدث في التعليمات البرمجية الخاصة بك! انها مثل كنت تسير في الشارع المستقيم أو الشارع مع الكثير من الخراطة ، وبالتأكيد سوف يتم القيام به بشكل مستقيم! ...

إذا تم فرز المصفوفة ، تكون حالتك خاطئة في الخطوة الأولى: data[c] >= 128، ثم تصبح قيمة حقيقية للطريق كله إلى نهاية الشارع. هكذا تصل إلى نهاية المنطق بشكل أسرع. من ناحية أخرى ، باستخدام مصفوفة لم يتم فرزها ، تحتاج إلى الكثير من الدوران والمعالجة مما يجعل تشغيل الكود أبطأ بالتأكيد ...

انظر إلى الصورة التي أنشأتها لك أدناه. أي شارع سينتهي بشكل أسرع؟

لذلك برمجيا ، يسبب التنبؤ الفرعى أن تكون العملية أبطأ ...

أيضًا في النهاية ، من الجيد أن نعرف أن لدينا نوعين من تنبؤات الفروع التي سيؤثر كل منها على شفرتك بشكل مختلف:

1. ثابت

2. ديناميكية

يتم استخدام التنبؤ الفرعى الثابت من قبل المعالجات الدقيقة في المرة الأولى التي يتم فيها مواجهة فرع الشرطية ، ويتم استخدام التنبؤ الديناميكي للفرع من أجل التنفيذ الناجح لرمز الفرع الشرطي.

من أجل كتابة التعليمات البرمجية الخاصة بك بشكل فعال للاستفادة من هذه القواعد ، عند كتابة if-else أو عبارات التبديل ، قم بفحص الحالات الأكثر شيوعًا أولاً ثم قم بالعمل تدريجيا إلى الأقل شيوعًا. لا تتطلب الحلقات بالضرورة أي طلب خاص من التعليمات البرمجية للتنبؤ الفرعى الثابت ، حيث يتم استخدام حالة تكرار الحلقة فقط عادة.


تتم معالجة المصفوفات التي تم فرزها بشكل أسرع من المصفوفة التي لم يتم فرزها ، نظرًا للظواهر التي تسمى التنبؤ الفرعى.

متنبئ الفرع هو عبارة عن دائرة رقمية (في هندسة الكمبيوتر) تحاول التنبؤ بالطريقة التي سيذهب بها الفرع ، مما يحسن التدفق في خط أنابيب التعليمات. تتنبأ الدارة / الكمبيوتر بالخطوة التالية وتنفذها.

يؤدي التنبؤ الخاطئ إلى الرجوع إلى الخطوة السابقة وتنفيذها بتنبؤ آخر. إذا افترضنا أن التوقع صحيح ، فستستمر الشفرة في الخطوة التالية. يؤدي التوقع الخاطئ إلى تكرار نفس الخطوة ، إلى أن يحدث التوقع الصحيح.

الإجابة على سؤالك بسيطة للغاية.

في مجموعة غير مجزأة ، يقوم الكمبيوتر بإجراء تنبؤات متعددة ، مما يؤدي إلى زيادة احتمال حدوث أخطاء. في حين أن الكمبيوتر ، مصنّفًا ، يجعل تنبؤات أقل يقلل من فرص الأخطاء. يتطلب عمل المزيد من التنبؤ المزيد من الوقت.

الترتيب مصفوفة: مستقيم الطريق

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

مصفوفة غير محددة: طريق منحني

______   ________
|     |__|

توقع الفرع: التخمين / التنبؤ بأي طريق مستقيم ومتابعته دون فحص

___________________________________________ Straight road
 |_________________________________________|Longer road

على الرغم من أن كلا الطريقين يصلان إلى نفس الوجهة ، فإن الطريق المستقيم أقصر ، والآخر أطول. إذا اخترت الآخر عن طريق الخطأ ، فلن يكون هناك عودة إلى الوراء ، وبالتالي سوف تضيع بعض الوقت الإضافي إذا اخترت الطريق الأطول. هذا مشابه لما يحدث على الكمبيوتر ، وآمل أن يساعدك هذا على فهم أفضل.

تحديث: بعد ما قالهSimon_Weaver ، أريد إضافة حقيقة أخرى مفادها ... "إنها لا تقدم تنبؤات أقل - إنها تقدم عددًا أقل من التنبؤات غير الصحيحة. ولا يزال عليها أن تتنبأ بكل مرة من خلال الحلقة".


كما سبق ذكره من قبل الآخرين ، ما وراء الغموض هو Predictor .

أنا لا أحاول أن أضيف شيئًا لكن أشرح المفهوم بطريقة أخرى. هناك مقدمة موجزة عن الويكي تحتوي على نص ورسم بياني. أنا أحب التفسير أدناه الذي يستخدم رسم تخطيطي لتوضيح Prideictor الفرع بشكل حدسي.

في هندسة الكمبيوتر ، يكون متنبئ الفرع عبارة عن دائرة رقمية تحاول تخمين الطريقة التي سيذهب بها الفرع (مثل بنية if-then-else) قبل أن يكون هذا معروفًا على وجه اليقين. الغرض من متنبئ الفرع هو تحسين التدفق في خط أنابيب التعليمات. يلعب متنبئو الفرع دورًا حاسمًا في تحقيق أداء فائق الفعالية في العديد من معماريات المعالجات الدقيقة الحديثة مثل x86.

عادةً ما يتم تنفيذ التفرع في اتجاهين باستخدام تعليمات قفزة شرطية. يمكن أن تكون القفزة المشروطة إما "غير مأخوذة" وتتابع التنفيذ مع أول فرع من الكود الذي يتبع مباشرة بعد القفزة الشرطية ، أو يمكن "أخذها" والقفز إلى مكان مختلف في ذاكرة البرنامج حيث الفرع الثاني من الكود هو مخزن. ولا يعرف على وجه اليقين ما إذا كانت القفزة الشرطية ستؤخذ أو لا تؤخذ حتى يتم حساب الشرط وقد تجاوزت القفزة المشروطة مرحلة التنفيذ في خط أنابيب التعليمات (انظر الشكل 1).

استنادًا إلى السيناريو الموضح ، قمت بكتابة عرض توضيحي متحرك لإظهار كيفية تنفيذ الإرشادات في خط أنابيب في حالات مختلفة.

  1. بدون توقع الفروع.

دون توقع فرع ، يجب على المعالج الانتظار حتى تجاوزت تعليمات القفزة الشرطية مرحلة التنفيذ قبل أن تدخل التعليمة التالية مرحلة الجلب في خط الأنابيب.

يحتوي المثال على ثلاثة إرشادات وأولها عبارة عن تعليمات قفزة شرطية. يمكن أن تدخل التوجيهات الأخيرة في خط الأنابيب حتى يتم تنفيذ تعليمات القفزة الشرطية.

سوف يستغرق 9 دورات على مدار الساعة لإكمال 3 تعليمات.

  1. استخدام Predictor فرع ولا تأخذ قفزة مشروطة. دعونا نفترض أن التنبؤ لا يأخذ القفزة المشروطة.

سوف يستغرق الأمر 7 دورات على مدار الساعة لإكمال 3 تعليمات.

  1. استخدام Predictor الفرع واتخاذ قفزة مشروطة. دعونا نفترض أن التنبؤ لا يأخذ القفزة المشروطة.

سوف يستغرق 9 دورات على مدار الساعة لإكمال 3 تعليمات.

يساوي الوقت المهدر في حالة سوء فهم الفرع عدد المراحل في خط الأنابيب من مرحلة الجلب إلى مرحلة التنفيذ. تميل المعالجات الحديثة إلى امتلاك خطوط أنابيب طويلة جدًا بحيث يتأخر التأخير الزمني ما بين 10 و 20 دورة ساعة. ونتيجة لذلك ، يزيد مد خط الأنابيب من الحاجة إلى جهاز تنبؤ فرعي أكثر تقدمًا.

كما ترى ، يبدو أنه ليس لدينا سبب لعدم استخدام Predicted Predictor.

إنه عرض توضيحي بسيط يوضح الجزء الأساسي من أداة توقع البريد. إذا كانت هذه الصور المتحركة مزعجة ، فلا تتردد في إزالتها من الإجابة ويمكن للزائرين أيضًا الحصول على العرض التوضيحي من git


في نفس السطر (أعتقد أن هذا لم يتم إبرازه بأي إجابة) من الجيد أن نذكر أنه في بعض الأحيان (خاصة في البرامج التي يكون فيها الأداء مهمًا - كما في Linux kernel) ، يمكنك العثور على بعض العبارات إذا كانت كالتالي:

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

أو بالمثل:

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

كلا likely()و unlikely()هي في وحدات الماكرو الحقيقة التي تم تعريفها باستخدام شيء من هذا القبيل في دول مجلس التعاون الخليجي __builtin_expectلمساعدة المترجم رمز إدراج التنبؤ لصالح حالة مع الأخذ بعين الاعتبار المعلومات المقدمة من قبل المستخدم. تدعم دول مجلس التعاون الخليجي بنى أخرى يمكن أن تغير سلوك البرنامج الجاري أو تصدر تعليمات منخفضة المستوى مثل مسح ذاكرة التخزين المؤقت ، وما إلى ذلك. انظر هذه الوثائق التي تمر من خلال مواطني دول مجلس التعاون الخليجي المتاحة.

عادةً ما يتم العثور على هذا النوع من التحسينات بشكل أساسي في التطبيقات ذات الوقت الفعلي أو الأنظمة المضمنة حيث يكون وقت التنفيذ أمرًا هامًا. على سبيل المثال ، إذا كنت تبحث عن بعض حالات الخطأ التي تحدث فقط في الأوقات 1/10000000 ، فلماذا لا تخبر المترجم بهذا؟ بهذه الطريقة ، افتراضياً ، سيفترض توقع الفرع أن الشرط خاطئ.





branch-prediction