java - لماذا يتم معالجة صفيف مرتبة بشكل أسرع من المصفوفة غير المصنفة؟


هنا هو قطعة من 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);
    }
}

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

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

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


Answers


كنت ضحية لفشل التنبؤ فرع .

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

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

صورة من قبل ميكانيسمو، عبر ويكيمديا كومونس. تستخدم تحت رخصة سيسي-بي-سا 3.0 .

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

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

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

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

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

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

النظر في إف-ستاتيمنت: على مستوى المعالج، هو فرع التعليمات:

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

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

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

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

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

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

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

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

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

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

كما ألمح من أعلاه، الجاني هو هذا إذا بيان:

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

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

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

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

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

هذا يلغي الفرع ويحل محله مع بعض العمليات بيتويز.

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

المعايير: كور i7 920 @ 3.5 غز

C ++ - فيسوال ستوديو 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 ++، الإختراق هو في الواقع أبطأ ببطء من مع الفرع عند فرز البيانات.

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

تحديث:

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

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

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

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

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




فرع التنبؤ.

مع صفيف مرتبة، data[c] >= 128 الحالة data[c] >= 128 هي false أولا لسلسلة من القيم، ثم يصبح true لجميع القيم اللاحقة. هذا من السهل التنبؤ. مع مصفوفة غير مصنفة، تدفع مقابل التكلفة المتفرعة.




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

الآن، إذا نظرنا إلى التعليمات البرمجية

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

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

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

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

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

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

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

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

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

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

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




إذا كنت غريبة عن المزيد من التحسينات التي يمكن القيام بها لهذا الرمز، والنظر في هذا:

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

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

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

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

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

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

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

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

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




لا شك أن البعض منا سوف تكون مهتمة في طرق تحديد التعليمات البرمجية التي تشكل إشكالية لوحدة المعالجة المركزية فرع التنبؤ. أداة 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 فروع المشروطة خطأ (بسم) تحت كاشيغريند فرع التنبؤ نموذج، في حين انها تسبب فقط 10،006 في النسخة المفصولة .

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

perf stat ./sumtest_sorted

مرتبة:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

لم يتم فرزها:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

ويمكن أيضا أن تفعل الشرح شفرة المصدر مع ديساسمبلي.

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

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




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

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

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

الخلفية والسبب

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

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

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

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

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

إنشاء جدول

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

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

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

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

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

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

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

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

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


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



كما يتم توزيع البيانات بين 0 و 255 عند فرز الصفيف، لن يدخل النصف الأول من التكرارات في إف-ستاتيمنت (إذا كان البيان المشترك أدناه).

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

السؤال هو ما يجعل البيان أعلاه لا تنفذ في حالة معينة كما هو الحال في حالة فرز البيانات؟ هنا يأتي "فرع التنبؤ" فرع التنبؤ هو الدائرة الرقمية التي تحاول تخمين الطريقة التي فرع (مثل هيكل إذا ثم ثم آخر) سوف تذهب قبل هذا معروف بالتأكيد. الغرض من فرع التنبؤ هو تحسين تدفق في خط أنابيب التعليمات. فرع التنبؤات تلعب دورا حاسما في تحقيق الأداء الفعال عالية!

دعونا نفعل بعض مقاعد البدلاء بمناسبة لفهم ذلك بشكل أفضل

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

دعونا قياس أداء هذه الحلقة مع ظروف مختلفة:

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

A " سيئة " نمط صحيح كاذبة يمكن أن تجعل إذا-بيان تصل إلى ست مرات أبطأ من نمط " جيد "! وبطبيعة الحال، أي نمط جيد والذي هو سيء يعتمد على التعليمات الدقيقة التي تم إنشاؤها من قبل مترجم وعلى المعالج المحدد.

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




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

ولكن في هذه الحالة، ونحن نعلم القيم في النطاق [0، 255]، ونحن نهتم فقط القيم> = 128. وهذا يعني أننا يمكن بسهولة استخراج بت واحد من شأنها أن تقول لنا ما إذا كنا نريد قيمة أم لا: عن طريق تحويل البيانات إلى اليمين 7 بت، نحن مع اليسار قليلا أو قليلا 1 0، ونريد فقط لإضافة قيمة عندما يكون لدينا بت 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ل "جدول البحث" في التعليمات البرمجية). وهنا رمز 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 بت لمؤشر الجدول. A مؤشر الجدول 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




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

في الواقع، هو تقسيم مجموعة في المنطقة المتاخمة مع data < 128وآخر مع data >= 128. لذلك يجب أن تجد نقطة التقسيم مع بحث dichotomic (باستخدام 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) :-)




يحدث سلوك أعلاه بسبب التنبؤ فرع.

لفهم التنبؤ فرع واحد يجب أن نفهم أولا خط أنابيب التعليمات :

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

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

  1. IF - إحضار التعليمات من الذاكرة
  2. ID - فك تعليمات
  3. EX - تنفيذ التعليمات
  4. WB - كتابة العودة إلى تسجيل CPU

خط أنابيب 4-المرحلة بشكل عام لمدة 2 التعليمات.

الانتقال إلى السؤال أعلاه دعونا النظر في الإرشادات التالية:

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

دون التنبؤ فرع من شأنه أن يحدث ما يلي:

لتنفيذ تعليمات B أو C تعليمات المعالج سوف تضطر إلى الانتظار حتى تعليمات ولا يصل حتى مرحلة EX في خط الأنابيب، حيث أن قرار الذهاب الى تعليمات B أو C تعليم يعتمد على نتيجة التعليم A. حتى خط الانابيب سيبدو هذا.

عندما ترجع إذا شرط صحيح:

عندما اذا كان الشرط ترجع كاذبة:

ونتيجة لانتظار نتيجة التدريس A، مجموع دورات CPU قضى في الحالة المذكورة أعلاه (دون التنبؤ فرع، لكل من الصواب والخطأ) هو 7.

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

وفرع مؤشرا محاولة لتخمين الطريقة التي فرع (بنية إذا-ثم-آخر) سيذهب قبل هذا يعرف على وجه اليقين. انها لن تنتظر لتعليم A للوصول إلى مرحلة EX من خط الانابيب، لكنه لن تخمين القرار وتذهب إلى أن تعليمات (B أو C في حالة مثالنا).

في حالة تخمين الصحيح، خط أنابيب يبدو شيئا من هذا القبيل:

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

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

  1. جميع العناصر أقل من 128
  2. جميع العناصر هي أكبر من 128
  3. بعض العناصر الجديدة ابتداء من أقل من 128 وبعد أن تصبح أكبر من 128

دعونا نفترض أن مؤشرا ستتولى دائما فرع صحيح على الجولة الأولى.

حتى في الحالة الأولى سوف يستغرق دائما فرع صحيح منذ تاريخيا عن توقعاته صحيحة. في حالة 2ND، في البداية سيكون التنبؤ خطأ، ولكن بعد بضع التكرارات سوف التنبؤ بشكل صحيح. في حالة 3RD سيكون التنبؤ بشكل صحيح في البداية حتى العناصر هي أقل من 128. وبعد ذلك سوف تفشل لبعض الوقت والصحيح نفسها عندما نرى فشل التنبؤ فرع في التاريخ.

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

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




ومن شأن رد رسمي من يكون

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

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

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

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

لذلك مؤشرا ستتغير الجانبين باعتبارها std::rand()ضربة.

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




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

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

أو بالمثل:

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

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

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




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

وoverdetermined متغيرات منطقية، بمعنى أن جميع المشغلين التي لديها المتغيرات المنطقية كما الاختيار المدخلات في حالة وجود مدخلات أي قيمة أخرى من 0أو 1، ولكن شركات التي لديها القيم المنطقية كإخراج يمكن أن تنتج أي قيمة أخرى من 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;
}

هذا الرمز هو أبعد ما يكون عن المثالية. الفروع قد يستغرق وقتا طويلا في حالة mispredictions. ويمكن إجراء العمليات المنطقية أكثر كفاءة إذا هو معروف على وجه اليقين أن المعاملات ليس لها أي قيم أخرى غير 0و 1. السبب لا المترجم تجعل مثل هذا الافتراض هو أن المتغيرات قد يكون قيم أخرى إذا كانوا غير مهيأ أو تأتي من مصادر غير معروفة. يمكن أن يكون الأمثل رمز أعلاه إذا aو bتم تهيئة إلى القيم الصالحة أو إذا كانت تأتي من الشركات التي تنتج الانتاج منطقي. رمز الأمثل يبدو مثل هذا:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charيستخدم بدلا من boolمن أجل جعل من الممكن استخدام مشغلي المختصة بالبت ( &و |) بدلا من العوامل المنطقية ( &&و ||). مشغلي المختصة بالبت هي تعليمات واحدة أن تأخذ دورة على مدار الساعة واحدة فقط. المشغل OR ( |) يعمل حتى لو aو bلها قيمة أخرى من 0أو 1. ووالمشغل ( &) والمشغل الحصري OR ( ^) قد تعطي نتائج غير متناسقة إذا كانت المعاملات قيم أخرى غير 0و 1.

~لا يمكن استخدامها لNOT. بدلا من ذلك، يمكنك جعل منطقية 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;

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




وقد سبق الرد على هذا السؤال العديد من ممتاز مرات. ما زلت ترغب في لفت الانتباه المجموعة لبعد تحليل آخر للاهتمام.

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

الرابط هنا هو: http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm




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

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

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

نظرة على صورة I خلق لكم أدناه، والتي سيتم الانتهاء ستعمل الشارع أسرع؟

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

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

1. ثابت

2. ديناميكية

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

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




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

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


في حالة توفر if-else\ switchبيان، والتعبير لابد من تقييمها لتحديد كتلة يجب أن يعدم. في رمز التجميع التي تم إنشاؤها بواسطة المترجم، شرطية فرع تندس التعليمات. في تعليمة فرع يمكن أن يسبب الكمبيوتر لبدء تنفيذ سلسلة تعليمات مختلفة، وبالتالي تنحرف عن السلوك الافتراضي الخاص به من تعليمات تنفيذ في النظام (أي إذا كان التعبير غير صحيح، البرنامج يتخطى رمز لل ifكتلة) اعتمادا على بعض شرط، وهو تقييم التعبير في حالتنا.

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

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

 O       route1  /-------------------------------
/|\             /
 |  ---------##/    
/ \            \ 
                \
         route2  \--------------------------------



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

• فرع مؤشرا هي واحدة من تقنيات تحسين الأداء القديمة التي لا يزال يجد أهمية في أبنية الحديثة. في حين توفر تقنيات التنبؤ بسيطة بحث سريع وكفاءة الطاقة التي تعاني من نسبة عالية misprediction.

• من ناحية أخرى، والتنبؤات فرع معقدة العصبية -either إلى أو متغيرات التنبؤ فرع مستويين -provide تحسين دقة التنبؤ ولكن تستهلك المزيد من القوة والتعقيد يزيد أضعافا مضاعفة.

• وبالإضافة إلى ذلك، في تقنيات التنبؤ معقدة الوقت الذي يستغرقه للتنبؤ الفروع هو في حد ذاته -ranging عالية جدا 2-5 دورات -وهو مشابه لوقت التنفيذ من فروع الفعلية.

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

هناك في الحقيقة ثلاثة أنواع مختلفة من فروع:

فروع الشرطية إلى الأمام - تستند إلى شرط وقت التشغيل، يتم تغيير PC (برنامج مكافحة) للإشارة إلى عنوان قدما في تيار التعليمات.

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

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

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

المراجع:

https://en.wikipedia.org/wiki/Branch_predictor

http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

https://courses.cs.washington.edu/courses/csep548/06au/lectures/branchPred.pdf

https://web.njit.edu/~rlopes/Mod5.3.pdf




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

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

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

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

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

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

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

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

وسوف يستغرق 9 دورات على مدار الساعة لمدة 3 تعليمات على الانتهاء.

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

وسوف يستغرق 7 دورات على مدار الساعة لمدة 3 تعليمات على الانتهاء.

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

وسوف يستغرق 9 دورات على مدار الساعة لمدة 3 تعليمات على الانتهاء.

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

كما ترون، يبدو أننا لم يكن لديك سبب لعدم استخدام فرع التوقع.

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




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

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