c++ - لماذا تكون الإضافات المكونة للعنصر أسرع بكثير في الحلقات المنفصلة عن الحلقات المركبة؟




performance compiler-optimization (7)

الحلقة الأولى بالتناوب الكتابة في كل متغير. أما النوعان الثاني والثالث ، فيجعلان قفزات صغيرة من حجم العنصر.

حاول كتابة خطين متوازيين من 20 صليب مع قلم ورقية مفصولة 20 سم. حاول مرة واحدة الانتهاء من واحد ثم السطر الآخر ومحاولة مرة أخرى عن طريق كتابة صليب في كل سطر بالتناوب.

لنفترض a1 ، b1 ، c1 ، و d1 نقطة إلى ذاكرة كومة ، ورمز رقمي يحتوي على الحلقة الأساسية التالية.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

يتم تنفيذ هذه الحلقة 10،000 مرة عن طريق الخارجي الآخر للحلقة. لتسريع الأمر ، قمت بتغيير الرمز إلى:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

تجميعها على MS Visual C ++ 10.0 مع التحسين الكامل وتمكين SSE2 لـ 32 بت على Intel Core 2 Duo (x64) ، المثال الأول يأخذ 5.5 ثانية ومثال مزدوج الحلقة يستغرق 1.9 ثانية فقط. سؤالي هو: (يرجى الرجوع إلى سؤالي المعاد صياغته في الأسفل)

ملاحظة: لست متأكداً ، إذا كان هذا يساعد:

تبدو عملية التفكيك للحلقة الأولى بشكل أساسي كالتالي: (تتكرر هذه الكتلة خمس مرات تقريبًا في البرنامج الكامل):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

ينتج كل حلقة من مثال الحلقة المزدوجة هذا الرمز (يتم تكرار الكتلة التالية حوالي ثلاث مرات):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

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

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

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

PPS: هنا هو الرمز الكامل. ويستخدم TBB Tick_Count أعلى دقة ، والتي يمكن تعطيلها عن طريق عدم تحديد TBB_TIMING ماكرو:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(يُظهر FLOP / s لقيم مختلفة من n .)


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


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

على افتراض سياسة التخزين المؤقت LIFO بسيطة ، هذا الكود:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

سيؤدي أولاً إلى تحميل b و b في ذاكرة الوصول العشوائي ومن ثم العمل بشكل كامل في ذاكرة الوصول العشوائي. عندما تبدأ الحلقة الثانية ، يتم تحميل c و d من القرص إلى RAM وتشغيلها.

الحلقة الأخرى

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

سوف يخرج صفحتين وصفحة في الآخرتين في كل مرة حول الحلقة . من الواضح أن هذا سيكون أبطأ بكثير .

ربما لا ترى التخزين المؤقت للقرص في اختباراتك ولكنك ربما ترى الآثار الجانبية لبعض أشكال التخزين المؤقت الأخرى.

يبدو أن هناك بعض الارتباك / سوء الفهم هنا ، لذا سأحاول وضع القليل باستخدام مثال.

قل n = 2 ونحن نعمل مع بايت. في السيناريو الخاص بي ، لدينا 4 بايت فقط من ذاكرة الوصول العشوائي ، وبقية ذاكرتنا تكون أبطأ بكثير (لنقل 100 مرة أطول).

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

  • مع

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • تخزين a[0] و a[1] ثم b[0] و b[1] وتعيين a[0] = a[0] + b[0] في ذاكرة التخزين المؤقت - يوجد الآن أربعة بايت في ذاكرة التخزين المؤقت ، a[0], a[1] و b[0], b[1] . التكلفة = 100 + 100.

  • اضبط a[1] = a[1] + b[1] في ذاكرة التخزين المؤقت. التكلفة = 1 + 1.
  • كرر لـ c و d .
  • التكلفة الإجمالية = (100 + 100 + 1 + 1) * 2 = 404

  • مع

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • تخزين a[0] و a[1] ثم b[0] و b[1] وتعيين a[0] = a[0] + b[0] في ذاكرة التخزين المؤقت - يوجد الآن أربعة بايت في ذاكرة التخزين المؤقت ، a[0], a[1] و b[0], b[1] . التكلفة = 100 + 100.

  • إخراج a[0], a[1], b[0], b[1] من ذاكرة التخزين المؤقت وذاكرة التخزين المؤقت c[0] و c[1] ثم d[0] و d[1] وتعيين c[0] = c[0] + d[0] في ذاكرة التخزين المؤقت. التكلفة = 100 + 100.
  • أظن أنك بدأت ترى أين سأذهب.
  • التكلفة الإجمالية = (100 + 100 + 100 + 100) * 2 = 800

هذا هو السيناريو الكلاسيكي thrash مخبأ.


حسنا ، الجواب الصحيح بالتأكيد أن تفعل شيئا مع ذاكرة التخزين المؤقت وحدة المعالجة المركزية. ولكن استخدام حجة ذاكرة التخزين المؤقت يمكن أن يكون صعبًا للغاية ، خاصة بدون بيانات.

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

لقد أقنعت جواب Mysticial الكثير من الناس (بما فيهم أنا) ، ربما لأنها كانت الوحيدة التي بدت معتمدة على الحقائق ، لكنها كانت "نقطة بيانات" واحدة فقط للحقيقة.

هذا هو السبب في أنني جمعت اختباره (باستخدام تخصيص مستمر مقابل منفصل) ونصيحةJames's Answer.

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

لاحظ أن سؤالي الأول كان في n = 100.000 . هذه النقطة (عن طريق الصدفة) تُظهر سلوكًا خاصًا:

  1. وهو يمتلك أكبر تباين بين الإصدار الواحد والثاني من الحلقات (تقريبا ثلاثة عوامل)

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

النتيجة باستخدام البيانات المبدئية:

النتيجة باستخدام بيانات غير مهيأة (وهذا هو ما تم اختباره Mysticial):

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

اقتراح

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


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

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

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


السؤال الأصلي

لماذا حلقة واحدة أبطأ بكثير من الحلقتين؟

استنتاج:

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

النظر إليها من هذا النوع من المقاربة دون إشراك الكيفية التي تعمل بها الأجهزة ، ونظام التشغيل ، والمترجم (المربعات) معًا لتنفيذ عمليات تخصيص الكومة التي تتضمن العمل مع ذاكرة الوصول العشوائي ، وذاكرة التخزين المؤقت ، وملفات الصفحات ، وما إلى ذلك ؛ الرياضيات التي هي في أساس هذه الخوارزميات تبين لنا أي من هذين هو الحل الأفضل. يمكننا استخدام القياس الذي يكون فيه Boss أو Summation الذي سيمثل For Loop التي يجب أن تنتقل بين العاملين A & B يمكننا أن نرى بسهولة أن الحالة 2 هي 1/2 على الأقل بسرعة إن لم تكن أكثر بقليل من الحالة 1 بسبب الفرق في المسافة المطلوبة للسفر والوقت الذي يستغرقه العمال. هذه الرياضيات تصطف تقريبا تقريبا وبشكل مثالي مع كل من مارك تايمز تايمز فضلا عن مقدار الاختلافات في تعليمات التجميع.

سأبدأ الآن في توضيح كيف يعمل كل هذا أدناه.

تقييم المشكلة

كود OP:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

و

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

النظر

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

التقرب

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

وجهة نظر

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

ماذا نعرف

نحن نعلم أن دائرته ستعمل 100 ألف مرة.ونحن نعلم أيضا أن a1، b1، c1وd1هي مؤشرات على بنية 64 بت. ضمن C ++ على جهاز 32 بت كافة المؤشرات 4 بايت وعلى جهاز 64 بت أنها 8 بايت في حجم منذ مؤشرات طول ثابت. نحن نعلم أن لدينا 32 بايت يتم تخصيصها في كلتا الحالتين. والفرق الوحيد هو أننا نقوم بتخصيص 32 بايت أو مجموعتين من 2 - 8 بايت لكل تكرار حيث في الحالة الثانية نقوم بتخصيص 16 بايت لكل تكرار لكل من الحلقات المستقلة. لذلك لا يزال يساوي كلا الحلقتين 32 بايت في إجمالي التخصيصات. مع هذه المعلومات دعونا نمضي قدما وإظهار الرياضيات العامة ، خوارزمية وقياس لها. نحن نعرف مقدار المرات التي يجب أن يتم فيها نفس المجموعة أو مجموعة العمليات في كلتا الحالتين. نحن نعرف مقدار الذاكرة التي يجب تخصيصها في كلتا الحالتين.يمكننا أن نقارن أن الحمل الكلي للعمل من التخصيصات بين كلتا الحالتين سيكون تقريبا نفس الشيء.

ما لا نعرفه

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

دعونا التحقيق

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

تأكيداتنا:

  • سنجعل الحلقة وتكرارها عبارة عن ملخص يبدأ من 1 وينتهي عند 100000 بدلاً من البدء بـ 0 كما هو الحال في الحلقات لأننا لسنا بحاجة إلى القلق بشأن نظام الفهرسة 0 لمعالجة الذاكرة حيث أننا مهتمون فقط الخوارزمية نفسها.
  • في كلتا الحالتين لدينا 4 وظائف للعمل مع مكالمتين وظيفتين مع إجراء 2 عمليات في كل استدعاء دالة. ولذا فإننا سوف ضبط هذه وظائف وظيفة وتدعو إلى أن يكون F1()، F2()، f(a)، f(b)، f(c)و f(d).

الخوارزميات:

الحالة الأولى: - تجميع واحد فقط ولكن اثنين من المكالمات وظيفة مستقلة.

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

الحالة الثانية: - جمع اثنين ولكن كل مكالمة وظيفية خاصة بها.

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

إذا لاحظت F2()وجود له إلا في Sumعلى حد سواء حيث Sum1و Sum2يحتوي فقط F1(). كما سيتضح ذلك لاحقًا أيضًا عندما نبدأ في استنتاج أن هناك نوعًا من التحسين يحدث من الخوارزمية الثانية.

التكرار من خلال Sumالدعوات الحالة الأولى f(a)التي ستضيف إلى الذات f(b)ثم يدعو f(c)أنه سوف تفعل الشيء نفسه ولكن إضافة f(d)إلى نفسه لكل منهما 100000 iterations. في الحالة الثانية لدينا Sum1و Sum2وكلاهما يتصرف كما لو كانوا بنفس وظيفة يطلق عليها مرتين على التوالي. في هذه الحالة يمكن أن نعالج Sum1و Sum2أنها مجرد سهل القديمة Sumحيث Sumفي هذه الحالة يبدو مثل هذا: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }والآن هذا يبدو وكأنه الأمثل حيث يمكن أن نعتبر مجرد أن يكون نفس الوظيفة.

موجز مع القياس

مع ما رأيناه في الحالة الثانية ، يبدو الأمر كما لو كان هناك تحسين ، حيث أن كلا الحلقتين لهما نفس التوقيع بالضبط ، لكن هذه ليست القضية الحقيقية. المسألة ليست العمل الذي تقوم به f(a)، f(b)، f(c)و f(d)في كلتا الحالتين والمقارنة بين الاثنين هو الفرق في المسافة التي الجمع أن السفر في كلتا الحالتين والتي تمنحك الفرق في تنفيذ الوقت.

فكر For Loopsفي Summationsأن تكون التكرارات هي Bossالتي تعطي الأوامر لشخصين Aو Bأن وظائفهم هي اللحوم Cو Dعلى التوالي و التقاط بعض الطرود منها و إعادتها. في القياس هنا ، لا يمثل التكرار أو التكرار التجميعي للحلقات نفسها Boss. ما يمثل في الواقع Bossهنا ليس من خوارزميات رياضية الفعلية مباشرة، ولكن من المفهوم الفعلي Scopeو Code Blockضمن روتين أو روتين فرعي، طريقة، وظيفة، وحدة الترجمة، الخ الخوارزمية الأولى عدد 1 نطاق حيث الخوارزمية 2ND بها 2 نطاقات متتالية.

في الحالة الأولى في كل قسيمة اتصال ، يتم الانتقال Bossإلى الأمر Aويعطيه Aويذهب إلى إحضار B'sالحزمة ثم Bossيذهب إلى Cويعطي أوامر للقيام بنفس الشيء وتلقي الحزمة من Dكل التكرار.

في الحالة الثانية Bossتعمل مباشرة مع Aالذهاب وجلب B'sالعبوة حتى يتم استلام جميع الطرود. ثم Bossيعمل مع Cنفس الشيء للحصول على جميع D'sالحزم.

بما أننا نعمل باستخدام مؤشر 8 بايت والتعامل مع تخصيص الكومة دعنا نأخذ هذه المشكلة بعين الاعتبار هنا. دعونا نقول إن Bossهو 100 قدم من Aوأن Aحوالي 500 قدم من C. لا داعي للقلق بشأن المدى الذي وصلنا إليه في Bossالبداية Cبسبب ترتيب عمليات الإعدام. في كلتا الحالتين Bossيسافر في البداية من Aأول ذلك إلى B. هذا التشبيه لا يعني أن هذه المسافة دقيقة. إنه مجرد سيناريو حالة اختبار لإظهار عمل الخوارزميات. في العديد من الحالات عند القيام بتخصيصات كومة الذاكرة المؤقتة والعمل مع ذاكرة التخزين المؤقت وملفات الصفحات ، قد لا تختلف هذه المسافات بين مواقع العناوين إلى حد كبير في الاختلافات أو يمكن أن تعتمد بشكل كبير على طبيعة أنواع البيانات وأحجام الصفيف.

حالات الاختبار:

الحالة الأولى: في التكرار الأول لBossديه للذهاب في البداية 100 قدم لإعطاء زلة لAوAيذهب ويفعل له شيئا، ولكن بعد ذلكBossيضطر إلى السفر 500 قدم إلىCلمنحه له زلة النظام. ثم على التكرار التالي وكل التكرار الآخر بعدBossأن يذهب ذهابا وإيابا 500 قدم بين الاثنين.

الحالة الثانية: The Boss يجب أن تسافر لمسافة 100 قدم على التكرار الأولA، ولكن بعد ذلك يكون هناك بالفعل وينتظر فقطAالعودة حتى يتم ملء جميع القصاصات. ثمBossيجب أن يسافر 500 قدم على التكرار الأولCلأنهC500 قدمAمنذBoss( Summation, For Loop )أن يتم استدعاء هذا الحق بعد العمل معAثم ينتظر فقط مثل ما فعلهAحتى يتم كلC'sزلات النظام.

الفرق في المسافات سافر

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

مقارنة القيم التعسفية

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

لذا من خلال هذه الأرقام ، ستبدو كما لو أن الخوارزمية One يجب أن تكون أبطأ بنسبة 99٪ من الخوارزمية Two ؛ ومع ذلك، هذه ليست سوى The Boss'sجزء أو مسؤولية الخوارزميات وأنها لا تمثل العمال الفعلي A، B، C، و Dوما يتعين عليهم القيام به في كل تكرار للحلقة. وبالتالي فإن عمل الرؤساء لا يمثل سوى حوالي 15 إلى 40٪ من إجمالي العمل الذي يتم إنجازه. وبالتالي فإن الجزء الأكبر من العمل الذي يتم من خلال العمال له تأثير أكبر قليلا نحو الحفاظ على نسبة فروق سرعة السرعة إلى حوالي 50-70 ٪

الملاحظة: - الاختلافات بين الخوارزميتين

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

The OPs المعدل (الأسئلة)

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

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

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

فيما يتعلق بهذه الأسئلة

كما أثبتت من دون أدنى شك ، هناك مشكلة أساسية حتى قبل أن تصبح الأجهزة والبرامج المعنية. الآن فيما يتعلق بإدارة الذاكرة والتخزين المؤقت إلى جانب ملفات الصفحات ، إلخ. التي تعمل جميعها معًا في مجموعة متكاملة من الأنظمة بين: The Architecture{Hardware و Firmware وبعض برامج التشغيل المضمنة ونماذج تعليمات ASM و} ، The OS{File and Memory Management systems وبرامج التشغيل والسجل} ، The Compiler{وحدات الترجمة والتحسينات الخاصة بالكود المصدري} ، وحتى Source Codeنفسها مع مجموعة (مجموعات) الخوارزميات المميزة ؛ يمكننا أن نرى بالفعل أن هناك عنق زجاجة يحدث داخل الخوارزمية الأولى قبل أن نطبقها على أي جهاز مع أي تعسفي Architecture، OS، وProgrammable Languageمقارنة مع الخوارزمية الثانية. لذلك هناك بالفعل مشكلة قبل إشراك جوهر الكمبيوتر الحديث.

نتائج النهاية

ومع ذلك؛ لا يعني ذلك أن هذه الأسئلة الجديدة ليست ذات أهمية لأنهم هم أنفسهم وهم يلعبون دورًا بعد كل شيء. فهي تؤثر على الإجراءات والأداء العام وهذا واضح مع مختلف الرسوم البيانية والتقييمات من العديد من الذين أعطوا إجابتهم (إجاباتهم) أو تعليق (تعليقات). إذا كنت تدفع الانتباه إلى تشبيه Bossواثنين من العمال Aو Bالذين اضطروا إلى الذهاب واسترداد حزم من Cو Dعلى التوالي، ونظرا لتدوين رياضي من خوارزميات المذكورين ترون أنه من دون حتى تورط جهاز الكمبيوتر Case 2ما يقرب من 60٪ اسرع منCase 1 وعندما تنظر إلى الرسوم البيانية والمخططات بعد تطبيق هذه الخوارزميات على الكود المصدري ، والتي يتم تجميعها وتحسينها وتنفيذها من خلال نظام التشغيل لإجراء عمليات على الجهاز المعين ، فإنك ترى مزيدًا من التدهور بين الاختلافات في هذه الخوارزميات.

الآن ، إذا كانت مجموعة "البيانات" صغيرة إلى حد ما ، فقد لا يبدو الأمر سيئًا تمامًا في البداية ، ولكن نظرًا لأن Case 1الأمر 60 - 70%أبطأ مما Case 2يمكننا من النظر إلى نمو هذه الوظيفة باعتبارها من حيث الاختلافات في عمليات تنفيذ الوقت:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

وهذا التقريب هو متوسط ​​الفرق بين هذين الحلقتين على حد سواء باستخدام العمليات الحسابية والعمليات الآلية التي تتضمن تحسينات البرامج وتعليمات الماكينة. لذلك عندما تنمو مجموعة البيانات خطياً ، كذلك الفرق في الوقت بين الاثنين. خوارزمية 1 لديه المزيد من عمليات الجلب من خوارزمية (2) الذي هو واضح عندما Bossاضطر إلى السفر ذهابا وإيابا المسافة القصوى بين Aو Cلكل التكرار بعد التكرار الأول بينما خوارزمية 2 Bossزيارتها للسفر إلى Aمرة واحدة ثم بعد ذلك مع Aانه اضطر الى السفر المسافة القصوى مرة واحدة فقط عند الانتقال من Aإلى C.

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


قد يكون من C ++ القديمة والتحسينات. على جهاز الكمبيوتر الخاص بي حصلت على نفس السرعة تقريبا:

حلقة واحدة: 1.577 مللي ثانية

حلقتان: 1.507 مللي ثانية

أقوم بتشغيل Visual Studio 2015 على معالج E5-1620 3.5 غيغاهرتز مع ذاكرة الوصول العشوائي 16 غيغابايت.







vectorization