12. تحسين الشيفرة

تحسين الشيفرة (code optimization) هو عملية تحسين برنامج بتقليل حجم شيفرته أو تعقيدها أو استخدامه للذاكرة أو زمن تشغيله (أو مزيج من ذلك) من دون تغيير وظيفته الجوهرية. وتتضمن أنظمة التصريف الكثيرة مُحسِّن شيفرة كخطوة وسيطة. وتحديدًا، يطبّق المصرّف المُحسِّن (optimizing compiler) تحويلات تحسّن الشيفرة كجزء من عملية التصريف. وجميع المصرّفات الحديثة تقريبًا (ومنها GCC) مصرّفات مُحسِّنة. وينفّذ مصرّف GCC للغة C تنوعًا واسعًا من أعلام التحسين (optimization flags) التي تمنح المبرمجين وصولًا مباشرًا إلى مجموعة جزئية من التحسينات المنفَّذة. وتحسّن أعلام تحسين المصرّف الشيفرة على حساب زمن التصريف وسهولة التنقيح. وللتبسيط، يجمّع GCC مجموعة جزئية من أعلام التحسين هذه في مستويات تحسين مختلفة يمكن للمبرمج استدعاؤها مباشرة. فمثلًا، يصرّف الأمر التالي برنامجًا نموذجيًا بتحسينات المستوى 1:

$ gcc -O1 -o program program.c

تنفّذ تحسينات المستوى 1 (-O1 أو -O) في GCC تحسينات أساسية لتقليل حجم الشيفرة وزمن التنفيذ مع محاولة إبقاء زمن التصريف عند أدنى حد. وتشمل تحسينات المستوى 2 (-O2) معظم التحسينات المنفَّذة في GCC التي لا تتضمن مقايضة بين المساحة والأداء. وأخيرًا، ينفّذ المستوى 3 (-O3) تحسينات إضافية (مثل تضمين الدوال الذي نناقشه لاحقًا في هذا الفصل)، وقد يجعل تصريف البرنامج يستغرق وقتًا أطول بكثير. وتوثّق وثائق GCC أعلام التحسين المنفَّذة بالتفصيل.

تتجاوز المناقشة المفصلة للمصرّفات المُحسِّنة وبنائها وتشغيلها نطاق هذا الكتاب؛ ونشجع القراء المهتمين على الاطلاع على الكتاب المرجعي Compilers: Principles, Techniques, and Tools لـ Aho وSethi وUlman. بل إن غرض هذا الفصل هو إبراز بعض الأمور التي تستطيع معظم المصرّفات فعلها (والتي لا تستطيعها)، وكيف يمكن للمبرمجين التعاون مع مصرّفاتهم وأدوات التنميط للمساعدة في تحسين شيفرتهم.

ما تفعله المصرّفات بالفعل

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

طيّ الثوابت

تُقيَّم الثوابت في الشيفرة في زمن التصريف لتقليل عدد التعليمات الناتجة. فمثلًا، في مقطع الشيفرة التالي، يستبدل توسيع الماكرو (macro expansion) العبارة int debug = N-5 بالعبارة int debug = 5-5. ثم يحدّث طيّ الثوابت (constant folding) هذه العبارة إلى int debug = 0.

#define N 5
int debug = N - 5; //constant folding changes this statement to debug = 0;

انتشار الثوابت

يستبدل انتشار الثوابت (constant propagation) المتغيرات بقيمة ثابتة إذا كانت تلك القيمة معروفة في زمن التصريف. فكّر في مقطع الشيفرة التالي:

int debug = 0;

//sums up all the elements in an array
int doubleSum(int *array, int length){
    int i, total = 0;
    for (i = 0; i < length; i++){
        total += array[i];
        if (debug) {
            printf("array[%d] is: %d\n", i, array[i]);
        }
    }
    return 2 * total;
}

سيغيّر المصرّف الذي يستخدم انتشار الثوابت if (debug) إلى if (0).

إزالة الشيفرة الميتة

ليس غريبًا أن يكون برنامج ما مليئًا بمتغيرات أو إسنادات أو عبارات غير مستخدمة. ومع أن هذه العبارات غير اللازمة نادرًا ما تُضاف عن قصد، فهي غالبًا ناتج طبيعي عن التكرار والتحسين المستمرين في دورة تطوير البرمجيات. وإذا بقيت دون اكتشاف، يمكن أن تدفع هذه التسلسلات المعروفة بـ الشيفرة الميتة (dead code) المصرّفات إلى إخراج تعليمات تجميع غير ضرورية تهدد بدورها وقت المعالجة. وتستخدم معظم المصرّفات تقنيات مثل تحليل تدفق البيانات لتحديد مقاطع الشيفرة غير القابلة للوصول وبالتالي إزالتها. وكثيرًا ما تجعل إزالة الشيفرة الميتة (dead code elimination) البرنامج أسرع بتقليص حجم الشيفرة ومجموعة التعليمات المرتبطة بها. وكمثال، لنعد إلى دالة doubleSum التي استخدم فيها المصرّف انتشار الثوابت لاستبدال debug بـ 0 في عبارة if:

int debug = 0;

//sums up all the elements in an array
int doubleSum(int *array, int length){
    int i, total = 0;
    for (i = 0; i < length; i++){
        total += array[i];
        if (0) { //debug replaced by constant propagation by compiler
            printf("array[%d] is: %d\n", i, array[i]);
        }
    }
    return 2 * total;
}

يدرك المصرّف الذي يستخدم تحليل تدفق البيانات أن عبارة if تُقيَّم دائمًا إلى خطأ وأن عبارة printf لا تُنفَّذ أبدًا. ولذلك يحذف المصرّف عبارة if ونداء printf من الملف التنفيذي المصرَّف. كما تحذف مرور أخرى العبارة debug = 0.

تبسيط التعبيرات

بعض التعليمات أغلى من غيرها. فمثلًا، تستغرق التعليمتان الحسابيتان imul وidiv في لغة التجميع وقتًا طويلًا في التنفيذ. وتحاول المصرّفات عادةً تقليل عدد التعليمات الغالية بتبسيط العمليات الرياضية كلما أمكن. فمثلًا، في دالة doubleSum، قد يستبدل المصرّف التعبير 2 * total بالتعبير total + total لأن تعليمة الجمع أقل كلفة من الضرب:

//declaration of debug removed through dead-code elimination

//sums up all the elements in an array
int doubleSum(int *array, int length){
    int i, total = 0;
    for (i = 0; i < length; i++){
        total += array[i];
        //if statement removed through data-flow analysis
    }
    return total + total; //simplifying expression
}

وبالمثل، سيحوّل المصرّف تسلسلات الشيفرة ذات الإزاحة على البتات وعمليات البتات الأخرى لتبسيط التعبيرات. فمثلًا، قد يستبدل المصرّف التعبير total * 8 بالتعبير total << 3، أو التعبير total % 8 بالتعبير total & 7، بما أن عمليات البتات تُنفَّذ بتعليمة سريعة واحدة.

ما لا تستطيع المصرّفات فعله دائمًا: فوائد تعلّم تحسين الشيفرة

بالنظر إلى فوائد المصرّفات المُحسِّنة، قد لا يكون واضحًا فورًا سبب فائدة تعلّم تحسين الشيفرة. وقد يغريك التفكير في المصرّف كصندوق أسود سحري «ذكي». وفي نهاية الأمر، المصرّف قطعة برمجية تنفّذ سلسلة من تحويلات الشيفرة في محاولة لتسريعها. كما أن المصرّفات محدودة في أنواع التحسينات التي تستطيع تنفيذها.

تقليل القوة الخوارزمي مستحيل

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

أعلام تحسين المصرّف لا تضمن جعل الشيفرة «مثالية» (ولا متسقة)

قد لا يؤدي رفع مستوى تحسينات المصرّف (مثلًا من -O2 إلى -O3) دائمًا إلى تقليل زمن تشغيل البرنامج. فأحيانًا قد يكتشف المبرمج أن تحديث أعلام التحسين من -O2 إلى -O3 يبطئ البرنامج، أو لا يحقق أي زيادة في الأداء على الإطلاق. وفي حالات أخرى، قد يكتشف المبرمج أن برنامجًا صُرِّف من دون أعلام التحسين لا يُظهر أخطاء ظاهريًا، بينما يؤدي تصريفه بـ -O2 أو -O3 إلى أخطاء تقسيم أو أخطاء أخرى. ويصعب تنقيح هذه الأنواع من أخطاء البرمجة بصفة خاصة، لأن علم التنقيح في GCC (-g) غير متوافق مع أعلام التحسين فيه (-O)، إذ تتعارض التحويلات التي تجريها تحسينات المصرّف عند مستويات -O مع قدرة المنقّح على تحليل الشيفرة الكامنة. ويطلب العديد من أدوات التنميط الشائعة، مثل GDB وValgrind، العلم -g.

ومن الأسباب الكبيرة للسلوك غير المتسق أن معيار C/C++ لا يقدم توجيهًا واضحًا لحل السلوك غير المعرَّف. ونتيجة لذلك، كثيرًا ما يُترك للمصرّف قرار كيفية حل الغموض. ويمكن أن يؤدي التفاوت في كيفية تعامل مستويات التحسين المختلفة مع السلوك غير المعرَّف إلى تغيّر الإجابات. فكّر في المثال التالي من John Regehr1:

int silly(int a) {
  return (a + 1) > a;
}

لنفترض أن silly شُغّلت بالقيمة a = INT_MAX. في هذه الحالة، ينتج الحساب a 1 فيضًا في العدد الصحيح. لكن معيار C/C++ لا يعرّف كيف ينبغي للمصرّف التعامل مع فيض الأعداد الصحيحة. وفي الواقع، يؤدي تصريف البرنامج من دون تحسينات إلى إعادة الدالة القيمة 0، بينما يؤدي تصريفه بتحسينات -O3 إلى إعادة الدالة القيمة 1.

وباختصار، ينبغي استخدام أعلام التحسين بحذر وبتفكير وعند الحاجة. كما أن تعلّم أعلام التحسين التي ينبغي استخدامها يمكن أن يساعد المبرمج على العمل مع مصرّفه لا ضده.

ملاحظة — لا يُطلب من المصرّف التعامل مع السلوك غير المعرَّف

دالة silly عند تشغيلها بالقيمة a = INT_MAX مثال على السلوك غير المعرَّف. لاحظ أن المخرجات غير المتسقة التي ينتجها المصرّف ليست عيبًا في تصميمه ولا نتيجة لاستخدام أعلام التحسين. فالمصرّفات مصممة تحديدًا لاتباع مواصفة اللغة. ولا يحدد معيار لغة C ما ينبغي للمصرّف فعله عند مصادفته سلوكًا غير معرَّف؛ فقد ينهار البرنامج، أو يفشل في التصريف، أو يولّد نتائج غير متسقة أو غير صحيحة. وفي نهاية الأمر، المبرمج مسؤول عن تحديد السلوك غير المعرَّف في الشيفرة وإزالته. وما إذا كان ينبغي لـ silly أن تعيد 0 أو 1 أو قيمة أخرى قرار يجب أن يتخذه المبرمج في النهاية. ولمعرفة المزيد عن السلوك غير المعرَّف والمسائل المرتبطة به في برامج C، زر الأسئلة الشائعة حول C2 أو مدونة John Regehr1. يمكن أن تكون المؤشرات مشكِلة

تذكّر أن المصرّف يجري تحويلات تُبقي السلوك الجوهري للبرنامج المصدر دون تغيير. وإذا كان التحويل ينطوي على خطر تغيير سلوك البرنامج، فلن يجريه المصرّف. ويصح هذا بصفة خاصة في حالة تراكب أسماء الذاكرة (memory aliasing) حيث يشير مؤشران مختلفان إلى العنوان نفسه في الذاكرة. وكمثال، فكّر في الدالة التالية shiftAdd التي تأخذ مؤشري عددين صحيحين كمُعامِليها. وتضرب الدالة العدد الأول في 10 وتضيف إليه العدد الثاني. فإذا مُرِّرت للدالة shiftAdd العددان 5 و6، كان الناتج 56.

الجدول 1. مقارنة بين دالتين تضرب الأولى العدد الأول في 10 وتضيف إليه الثاني. متاح على هذا الرابط.

نسخة غير مُحسَّنة

void shiftAdd(int *a, int *b){
    *a = *a * 10; //multiply by 10
    *a += *b; //add b
}

نسخة مُحسَّنة

void shiftAddOpt(int *a, int *b){
    *a = (*a * 10) + *b;
}

تحسّن دالة shiftAddOpt دالة shiftAdd بإزالة مرجع ذاكرة إضافي إلى a، ما ينتج مجموعة تعليمات أصغر في التجميع المصرَّف. غير أن المصرّف لن يجري هذا التحسين أبدًا بسبب خطر تراكب أسماء الذاكرة. وللفهم لماذا، فكّر في الدالة main التالية:

int main(void){
    int x = 5;
    int y = 6;
    shiftAdd(&x, &y); //should produce 56
    printf("shiftAdd produces: %d\n", x);

    x = 5; //reset x
    shiftAddOpt(&x, &y); //should produce 56
    printf("shiftAddOpt produces: %d\n", x);

    return 0;

}

وينتج عن تصريف هذا البرنامج وتشغيله المخرجات المتوقعة:

$ gcc -o shiftadd shiftadd.c
$ ./shiftadd
shiftAdd produces: 56
shiftAddOpt produces: 56

لنفترض بدلًا من ذلك أن البرنامج عُدّل بحيث تأخذ shiftAdd الآن مؤشرًا إلى x كمُعامِليها:

int main(void){
    int x = 5;
    shiftAdd(&x, &x); //should produce 55
    printf("shiftAdd produces: %d\n", x);

    x = 5; //reset x
    shiftAddOpt(&x, &x); //should produce 55
    printf("shiftAddOpt produces: %d\n", x);

    return 0;

}

المخرجات المتوقعة هي 55. لكن إعادة تصريف الشيفرة المحدَّثة وإعادة تشغيلها ينتج مخرجتين مختلفتين:

$ gcc -o shiftadd shiftadd.c
$ ./shiftadd
shiftAdd produces: 100
shiftAddOpt produces: 55

ويكشف إعادة تتبع دالتي shiftAdd مع افتراض أن a وb يشيران إلى موقع الذاكرة نفسه عن المشكلة. فضرب a في 10 في shiftAdd يحدّث x إلى 50. ثم تؤدي إضافة a إلى b في shiftAdd إلى مضاعفة x إلى 100. ويكشف خطر تراكب أسماء الذاكرة أن shiftAdd وshiftAddOpt ليستا في الواقع متكافئتين، وإن كان المبرمج قد قصد أن تكونا كذلك. ولإصلاح هذه المشكلة، لاحظ أن المُعامِل الثاني لـ shiftAdd لا يحتاج إلى تمريره كمؤشر. فاستبدال المُعامِل الثاني بعدد صحيح يزيل خطر التراكب ويتيح للمصرّف تحسين إحدى الدالتين إلى الأخرى:

الجدول 2. دالتان محسَّنتان تضربان العدد الأول في 10 وتضيفان إليه الثاني. متاحتان على هذا الرابط.

نسخة (مصحَّحة) غير مُحسَّنة

void shiftAdd(int *a, int b){
    *a = *a * 10; //multiply by 10
    *a += b; //add b
}

نسخة (مصحَّحة) مُحسَّنة

void shiftAddOpt(int *a, int b){
    *a = (*a * 10) + b;
}

وتتيح إزالة مرجع الذاكرة غير اللازم للمبرمج الحفاظ على مقروئية دالة shiftAdd الأصلية مع تمكين المصرّف من تحسين الدالة.

التعاون مع مصرّفك: برنامج نموذجي

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

//helper function: checks to see if a number is prime
int isPrime(int x) {
    int i;
    for (i = 2; i < sqrt(x) + 1; i++) { //no prime number is less than 2
        if (x % i == 0) { //if the number is divisible by i
            return 0; //it is not prime
        }
    }
    return 1; //otherwise it is prime
}

// finds the next prime
int getNextPrime(int prev) {
    int next = prev + 1;
    while (!isPrime(next)) { //while the number is not prime
        next++; //increment and check again
    }
    return next;
}

// generates a sequence of primes
int genPrimeSequence(int *array, int limit) {
    int i;
    int len = limit;
    if (len == 0) return 0;
    array[0] = 2; //initialize the first number to 2
    for (i = 1; i < len; i++) {
        array[i] = getNextPrime(array[i-1]); //fill in the array
        if (array[i] > limit) {
            len = i;
            return len;
        }
    }
    return len;
}

int main(int argc, char **argv) {
  //omitted for brevity
  int *array = allocateArray(limit);
  int length = genPrimeSequence(array, limit);

  return 0;
}

ويعرض الجدول 3 نتائج التوقيت لإنتاج الأعداد الأولية بين 2 و5,000,000 مع أعلام مستويات التحسين المختلفة باستخدام أمر التصريف الأساسي التالي:

$ gcc -o optExample optExample.c -lm

غير مُحسَّن	`-O1`	`-O2`	`-O3`
3.86	2.32	2.14	2.15

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

المراجع

John Regehr. "A Guide to Undefined Behavior in C and C++, Part 1". https://blog.regehr.org/archives/213
C FAQ. "comp.lang.c FAQ list: Question 11.33". http://c-faq.com/ansi/undef.html

«المشكلة الحقيقية أن المبرمجين أنفقوا وقتًا أطول مما ينبغي في القلق على الكفاءة في المواضع والأوقات الخطأ؛ فالتحسين المبكر أصل كل الشرور (أو معظمه على الأقل) في البرمجة.» - Don Knuth، The Art of Computer Programming

من أكبر مخاطر تحسين الشيفرة مفهوم التحسين المبكر (premature optimization). ويحدث التحسين المبكر عندما يحاول المبرمج التحسين بناءً على «إحساس حدسي» بمكان حدوث أوجه قصور الأداء، لا بناءً على بيانات. وكلما أمكن، من المهم قياس زمن تشغيل أجزاء مختلفة من الشيفرة على مدخلات مختلفة قبل بدء التحسين لتحديد نقاط السخونة (hot spots)، أي المناطق في البرنامج التي تحدث فيها أكبر كمية من التعليمات.

لمعرفة كيفية تحسين optExample.c، لنبدأ بإلقاء نظرة أقرب على الدالة main:

int main(int argc, char **argv) {
    // error-handling and timing code omitted for brevity

    int limit = strtol(argv[1], NULL, 10);
    int length = limit;
    int *array = allocateArray(length); //allocates array of specified length

    genPrimeSequence(array, limit, &length); //generates sequence of primes

    return 0;
}

تحتوي الدالة main نداءات إلى دالتين: allocateArray التي تهيّئ مصفوفة بطول يحدده المستخدم (أو حدّ)، وgenPrimeSequence التي تولّد تسلسل أعداد أولية ضمن الحد المحدد (لاحظ أنه بالنسبة إلى أي تسلسل بين 2 وn، لا يمكن أن يكون عدد الأعداد الأولية أكثر من n، وكثيرًا ما يكون أقل بكثير). وتحتوي الدالة main في ملف C شيفرة تقيس زمن كل من الدالتين أعلاه. ويكشف تصريف الشيفرة وتشغيلها مع ضبط limit على 5,000,000 ما يلي:

$ gcc -o optExample optExample.c -lm
$ time -p ./optExample 5000000
Time to allocate: 5.5e-05
Time to generate primes: 3.85525
348513 primes found.
real 3.85
user 3.86
sys 0.00

يستغرق برنامج optExample نحو 3.86 ثانية لاكتماله، مع قضاء كل الوقت تقريبًا في الدالة genPrimeSequence. ولا فائدة من إنفاق الوقت في تحسين allocateArray، لأن أي تحسينات ستكون ضئيلة بالنسبة إلى زمن تشغيل البرنامج ككل. وفي الأمثلة التالية، نركّز بدرجة أكبر على الدالة genPrimeSequence والدوال المرتبطة بها. وتُعاد الدوال إدراجها هنا للتيسير:

// helper function: checks to see if a number is prime
int isPrime(int x) {
    int i;
    for (i = 2; i < sqrt(x) + 1; i++) { //no prime number is less than 2
        if (x % i == 0) { //if the number is divisible by i
            return 0; //it is not prime
        }
    }
    return 1; //otherwise it is prime
}

// finds the next prime
int getNextPrime(int prev) {
    int next = prev + 1;
    while (!isPrime(next)) { //while the number is not prime
        next++; //increment and check again
    }
    return next;
}

// generates a sequence of primes
int genPrimeSequence(int *array, int limit) {
    int i;
    int len = limit;
    if (len == 0) return 0;
    array[0] = 2; //initialize the first number to 2
    for (i = 1; i < len; i++) {
        array[i] = getNextPrime(array[i-1]); //fill in the array
        if (array[i] > limit) {
            len = i;
            return len;
        }
    }
    return len;
}

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

تحاول الدالة genPrimeSequence توليد جميع الأعداد الأولية بين 2 وعدد صحيح ما n. ولأن عدد الأعداد الأولية بين 2 وn لا يمكن أن يتجاوز n، فإن حلقة for في genPrimeSequence تعمل n مرة على الأكثر. ويستدعي كل تكرار من حلقة for الدالة getNextPrime مرة واحدة. وبذلك تعمل getNextPrime n مرة على الأكثر.
تستمر حلقة while في الدالة getNextPrime بالعمل حتى اكتشاف عدد أولي. ومع أنه يصعب تحديد عدد مرات تنفيذ حلقة while في getNextPrime مسبقًا بدلالة n (فالفجوة بين الأعداد الأولية المتعاقبة يمكن أن تكون كبيرة اعتباطيًا)، فمن المؤكد أن isPrime تُنفَّذ في كل تكرار من تكرارات حلقة while.
تحتوي الدالة isPrime حلقة for واحدة بالضبط. ولنفترض أن الحلقة تعمل k تكرارًا إجمالًا. عندئذٍ تُنفَّذ الشيفرة في جسم الحلقة k مرة إجمالًا. تذكّر أن بنية حلقة for تتألف من عبارة تهيئة (تهيّئ متغير الحلقة بقيمة معينة)، وتعبير منطقي (يحدد متى تنتهي الحلقة)، وتعبير خطوة (يحدّث متغير الحلقة في كل تكرار). ويعرض الجدول 1 عدد مرات تنفيذ كل مكوّن من مكوّنات الحلقة في حلقة for تعمل k تكرارًا. ففي كل حلقة for، تحدث التهيئة مرة واحدة بالضبط. ويُنفَّذ التعبير المنطقي k + 1 مرة مقابل k تكرار، لأنه يجب إجراء فحص أخير لإنهاء الحلقة. أما جسم الحلقة وتعبير الخطوة فيُنفَّذ كل منهما k مرة.

عبارة التهيئة	التعبير المنطقي	تعبير الخطوة	جسم الحلقة
1	k+1	k	k

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

12.1.1. استخدام Callgrind للتنميط

في برنامجنا الصغير، كان من السهل نسبيًا استخدام الفحص اليدوي لتكوين فرضية أن الدالة sqrt تقع في «نقطة سخونة» في الشيفرة. لكن تحديد نقاط السخونة قد يصبح أعقد في البرامج الأكبر. وعلى أي حال، من الجيد استخدام التنميط للتحقق من فرضيتنا. وتوفّر أدوات تنميط الشيفرة مثل Valgrind كثيرًا من المعلومات عن تنفيذ البرنامج. ونستخدم في هذا القسم أداة callgrind لفحص مخطط نداءات برنامج OptExample.

لاستخدام callgrind، لنبدأ بإعادة تصريف برنامج optExample بالعلم -g وتشغيل callgrind على مجال أصغر (من 2 إلى 100,000). وكما في تطبيقات Valgrind الأخرى، يعمل callgrind كغلاف حول برنامج، مضيفًا تعليقات مثل عدد مرات تنفيذ الدوال وإجمالي عدد التعليمات المنفَّذة نتيجةً لذلك. وبالتالي، سيستغرق برنامج optExample وقتًا أطول في التنفيذ عند تشغيله مع callgrind.

$ gcc -g -o optExample optExample.c -lm
$ valgrind --tool=callgrind ./optExample 100000
==32590== Callgrind, a call-graph generating cache profiler
==32590== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==32590== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==32590== Command: ./optExample 100000
==32590==
==32590== For interactive control, run 'callgrind_control -h'.
Time to allocate: 0.003869
Time to generate primes: 0.644743
9592 primes found.
==32590==
==32590== Events    : Ir
==32590== Collected : 68338759
==32590==
==32590== I   refs:      68,338,759

تكشف كتابة ls في الطرفية عن ملف جديد يُسمى callgrind.out.xxxxx، حيث xxxxx معرّف فريد. وفي هذه الحالة، الملف هو callgrind.out.32590 (أي الرقم المعروض في العمود الأيسر في المخرجات السابقة). وينتج تشغيل callgrind_annotate على هذا الملف معلومات إضافية عن الدوال الثلاث موضع الاهتمام:

$ callgrind_annotate --auto=yes callgrind.out.32590
 ----------------------------------------------------------------
Profile data file 'callgrind.out.32393' (creator: callgrind-3.11.0)
 ----------------------------------------------------------------
...
  .  //helper function: checks to see if a number is prime
   400,004  int isPrime(int x) {
         .      int i;
36,047,657      for (i = 2; i < sqrt(x)+1; i++) { //no prime is less than 2
13,826,015  => ???:sqrt (2765204x)
16,533,672          if (x % i == 0) { //if the number is divisible by i
   180,818              return 0; //it is not prime
         .          }
         .      }
     9,592      return 1; //otherwise it is prime
   200,002  }
         .
         .  // finds the next prime
    38,368  int getNextPrime(int prev) {
    28,776      int next = prev + 1;
   509,597      while (!isPrime(next)) { //while the number is not prime
67,198,556  => optExample.c:isPrime (100001x)
    90,409          next++; //increment and check again
         .      }
     9,592      return next;
    19,184  }
         .
         .  // generates a sequence of primes
         6  int genPrimeSequence(int * array, int limit) {
         .      int i;
         2      int len = limit;
         2      if (len == 0) return 0;
         2      array[0]=2; //initialize the first number to 2
    38,369      for (i = 1; i < len; i++) {
   143,880          array[i] = getNextPrime(array[i-1]); //fill in the array
67,894,482  => optExample.c:getNextPrime (9592x)
    76,736          if (array[i] > limit){
         2              len = i;
         2              return len;
         .          }
         .      }
         .      return len;
         4  }

تمثّل الأرقام في العمود الأيسر عدد التعليمات المنفَّذة الإجمالي المرتبط بكل سطر. وتشير الأرقام بين قوسين إلى عدد مرات تشغيل دالة معينة. وباستخدام الأرقام في العمود الأيسر، نستطيع التحقق من نتائج فحصنا اليدوي. ففي الدالة genPrimeSequence، أنتجت الدالة getNextPrime أكبر عدد من التعليمات المنفَّذة، وهو 67.8 مليون تعليمة، مقابل 9,592 نداء دالة (لتوليد الأعداد الأولية بين 2 و100,000). ويكشف فحص getNextPrime أن غالبية تلك التعليمات (67.1 مليون، أي 99%) ناتجة من نداء isPrime الذي يُستدعى 100,001 مرة إجمالًا. وأخيرًا، يكشف فحص isPrime أن 13 مليونًا من إجمالي التعليمات (20.5%) ناتجة من الدالة sqrt التي تُنفَّذ 2.7 مليون مرة إجمالًا.

وتؤكد هذه النتائج فرضيتنا الأصلية بأن البرنامج يقضي معظم وقته في الدالة isPrime، وأن الدالة sqrt هي الأكثر تنفيذًا بين جميع الدوال. ويؤدي تقليل إجمالي عدد التعليمات المنفَّذة إلى برنامج أسرع؛ ويشير التحليل أعلاه إلى أنه ينبغي أن تركّز جهودنا الأولية على تحسين الدالة isPrime، وربما تقليل عدد مرات تنفيذ sqrt.

12.1.2. نقل شيفرة ثابت الحلقة

نقل شيفرة ثابت الحلقة (loop-invariant code motion) تقنية تحسين تنقل الحسابات الساكنة التي تحدث داخل حلقة إلى خارجها من دون التأثير في سلوك الحلقة. وتستطيع المصرّفات المُحسِّنة إجراء معظم تحسينات شيفرة ثابت الحلقة تلقائيًا. وتحديدًا، يحاول علم المصرّف -fmove-loop-invariants في GCC (المفعَّل عند المستوى -O1) تحديد أمثلة نقل شيفرة ثابت الحلقة ونقلها خارج حلقاتها.

لكن المصرّف لا يستطيع دائمًا تحديد حالات شيفرة ثابت الحلقة، خصوصًا في حالة نداءات الدوال. ولأن نداءات الدوال يمكن أن تسبب آثارًا جانبية (side effects) غير مقصودة، تتجنّب معظم المصرّفات محاولة تحديد ما إذا كان نداء دالة يعيد النتيجة نفسها باستمرار. ولذلك، حتى مع معرفة المبرمج أن sqrt(x) تعيد دائمًا الجذر التربيعي لمدخل ما x، لن يفترض GCC ذلك دائمًا. فكّر في حالة تحدّث فيها الدالة sqrt متغيرًا عامًا سريًا g. في هذه الحالة، ليس استدعاء sqrt مرة واحدة خارج الدالة (تحديث واحد لـ g) مماثلًا لاستدعائها في كل تكرار من تكرارات الحلقة (n من التحديثات لـ g). وإذا لم يستطع المصرّف تحديد أن دالة تعيد النتيجة نفسها دائمًا، فلن ينقل الدالة sqrt خارج الحلقة تلقائيًا.

لكن المبرمج يعرف أن نقل الحساب sqrt(x) + 1 خارج حلقة for لا يؤثر في سلوك الحلقة. والدالة المحدَّثة معروضة هنا ومتاحة في الملف التالي:

//helper function: checks to see if a number is prime
int isPrime(int x) {
    int i;
    int max = sqrt(x)+1;
    for (i = 2; i < max; i++) { //no prime number is less than 2
        if (x % i == 0) { //if the number is divisible by i
            return 0; //it is not prime
        }
    }
    return 1; //otherwise it is prime
}

يوضح الجدول 2 أن هذا التغيير البسيط يوفر ثانيتين كاملتين (47%) من زمن تشغيل optExample2، حتى قبل استخدام أعلام المصرّف. وفضلًا عن ذلك، يبدو أن المصرّف يجد تحسين optExample2 أسهل قليلًا.

النسخة	غير مُحسَّنة	`-O1`	`-O2`	`-O3`
الأصلية	3.86	2.32	2.14	2.15
مع نقل شيفرة ثابت الحلقة	1.83	1.63	1.71	1.63

وتكشف إعادة تشغيل callgrind على الملف التنفيذي optExample2 سبب ملاحظة هذا التحسن الكبير في زمن التشغيل. ويفترض مقطع الشيفرة التالي أن الملف callgrind.out.30086 يحتوي تعليقات تشغيل callgrind على الملف التنفيذي optExample2:

$ gcc -g -o optExample2 optExample2.c -lm
$ valgrind --tool=callgrind ./optExample2 100000
$ callgrind_annotate --auto=yes callgrind.out.30086
 ------------------------------------------------------------------
Profile data file 'callgrind.out.30086' (creator: callgrind-3.11.0)
 ------------------------------------------------------------------
 ...
   400,004  int isPrime(int x) {
         .      int i;
   900,013      int max = sqrt(x)+1;
   500,000  => ???:sqrt (100001x)
11,122,449      for (i = 2; i < max; i++) { //no prime number is less than 2
16,476,120          if (x % i == 0) { //if the number is divisible by i
   180,818              return 0; //it is not prime
         .          }
         .      }
     9,592      return 1; //otherwise it is prime
   200,002  }
         .
         .  // finds the next prime
    38,368  int getNextPrime(int prev) {
    28,776      int next = prev + 1;
   509,597      while (!isPrime(next)) { //while the number is not prime
29,789,794  => optExample2.c:isPrime (100001x)
    90,409          next++; //increment and check again
         .      }
     9,592      return next;
    19,184  }

إن نقل نداء sqrt خارج حلقة for يقلل عدد مرات استدعاء الدالة sqrt في البرنامج من 2.7 مليون إلى 100,000 (انخفاض بنسبة 96%). ويقابل هذا الرقم عدد مرات استدعاء الدالة isPrime، ما يؤكد أن الدالة sqrt تُنفَّذ مرة واحدة فقط مع كل استدعاء للدالة isPrime.

لاحظ أن المصرّف تمكن من إجراء مستويات كبيرة من التحسين عند تحديد أعلام التحسين، حتى لو لم يُجرِ المبرمج نقل الشيفرة يدويًا. وسبب ذلك في هذه الحالة تعليمة خاصة تُسمى fsqrt تحددها معمارية x86. فعند تشغيل أعلام التحسين، يستبدل المصرّف جميع حالات الدالة sqrt بالتعليمة fsqrt. وتُعرف هذه العملية بـ التضمين (inlining)، ونغطيها بمزيد من التفصيل في القسم التالي. ولأن fsqrt لم تعد دالة، يصبح تحديد طبيعتها كثابت حلقة أسهل على المصرّف، فينقلها خارج جسم الحلقة.

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

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

ثمة مصادر كثيرة على الإنترنت تدعو إلى التنفيذ اليدوي للتقنيات التي نصفها في الأقسام التالية. لكننا نشجع القراء على التحقق مما إذا كانت مصرّفاتهم تدعم التحسينات التالية قبل محاولة تنفيذها يدويًا في شيفرتهم. وجميع التحسينات الموصوفة في هذا القسم منفَّذة في GCC، لكنها قد لا تكون متاحة في المصرّفات الأقدم.

12.2.1. تضمين الدوال

من خطوات التحسين التي تحاول المصرّفات تنفيذها تضمين الدوال (function inlining)، وهو استبدال نداءات دالة بجسم الدالة. فمثلًا، في الدالة main، سيستبدل مصرّف يضمّن الدالة allocateArray نداء allocateArray بنداء مباشر إلى malloc:

الجدول 1. مثال على تضمين المصرّف للدالة allocateArray.

النسخة الأصلية

int main(int argc, char **argv) {
    // omitted for brevity
    // some variables shortened for space considerations
    int lim = strtol(argv[1], NULL, 10);

    // allocation of array
    int *a = allocateArray(lim);

    // generates sequence of primes
    int len = genPrimeSequence(a, lim);

    return 0;
}

نسخة مع تضمين allocateArray

int main(int argc, char **argv) {
    // omitted for brevity
    // some variables shortened for space considerations
    int lim = strtol(argv[1], NULL, 10);

    // allocation of array (in-lined)
    int *a = malloc(lim * sizeof(int));

    // generates sequence of primes
    int len = genPrimeSequence(a, lim);

    return 0;
}

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

ويشير العلم -finline-functions إلى GCC بضرورة تضمين الدوال. وهذا التحسين مفعَّل عند المستوى 3. ومع أنه يمكن استخدام -finline-functions من دون العلم -O3، فهو اقتراح للمصرّف بالبحث عن دوال لتضمينها. وبالمثل، يمكن استخدام الكلمة المفتاحية static inline لاقتراح على المصرّف تضمين دالة معينة. وتذكّر أن المصرّف لن يضمّن جميع الدوال، وأن تضمين الدوال غير مضمون لجعل الشيفرة أسرع.

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

12.2.2. فتح الحلقات

آخر استراتيجية تحسين للمصرّف نناقشها في هذا القسم هي فتح الحلقات. لنعد إلى الدالة isPrime:

// helper function: checks to see if a number is prime
int isPrime(int x) {
    int i;
    int max = sqrt(x) + 1;

    // no prime number is less than 2
    for (i = 2; i < max; i++) {
        // if the number is divisible by i
        if (x % i == 0) {
            return 0; // it's not prime
        }
    }
    return 1; // otherwise it is
}

تُنفَّذ حلقة for ما مجموعه max مرة، حيث max واحد أكبر من الجذر التربيعي للعدد الصحيح x. وعلى مستوى التجميع، يفحص كل تنفيذ للحلقة ما إذا كان i أصغر من max. وإذا كان كذلك، يقفز مؤشر التعليمة إلى جسم الحلقة الذي يحسب عملية باقي القسمة. وإذا نتج عن العملية 0، يخرج البرنامج من الحلقة فورًا ويعيد 0. وإلا، تستمر الحلقة في التنفيذ. ومع أن متنبّئات التفرعات جيدة إلى حد كبير في التنبؤ بنتيجة تعبير شرطي (خصوصًا داخل الحلقات)، فإن التخمينات الخاطئة يمكن أن تضر بالأداء بسبب الاضطرابات في خط أنابيب التعليمات.

وفتح الحلقات (loop unrolling) تحسين تجريه المصرّفات لتقليل أثر التخمينات الخاطئة. والهدف في فتح الحلقات هو تقليل عدد تكرارات الحلقة بمعامل n بزيادة الحمل الذي ينفّذه كل تكرار بمعامل n. فعند فتح حلقة بمعامل 2، يُنصّف عدد التكرارات في الحلقة، بينما يُضاعَف مقدار العمل المنفَّذ في كل تكرار.

لنطبّق يدويًا فتح الحلقات بمعامل 2 على دالتنا isPrime (متاحة في optExample3.c):

// helper function: checks to see if a number is prime
int isPrime(int x) {
    int i;
    int max = sqrt(x)+1;

    // no prime number is less than 2
    for (i = 2; i < max; i+=2) {
        // if the number is divisible by i or i+1
        if ( (x % i == 0) || (x % (i+1) == 0) ) {
            return 0; // it's not prime
        }
    }
    return 1; // otherwise it is
}

لاحظ أنه مع تنصيفنا عدد التكرارات التي تأخذها حلقة for، ينفّذ كل تكرار من الحلقة الآن فحصَي باقي قسمة، ما يضاعف مقدار العمل في كل تكرار. وينتج عن إعادة تصريف البرنامج وتشغيله أوقات تحسّنت تحسنًا هامشيًا (انظر الجدول 2). كما تقل مقروئية الشيفرة. والطريقة الأفضل للاستفادة من فتح الحلقات هي استدعاء علم تحسين المصرّف -funroll-loops الذي يطلب من المصرّف فتح الحلقات التي يمكن تحديد تكراراتها في زمن التصريف. وعلم المصرّف -funroll-all-loops خيار أكثر جرأة يفتح جميع الحلقات سواء تأكد المصرّف من عدد التكرارات أم لا. ويعرض الجدول 2 أزمنة تشغيل فتح الحلقات اليدوي بمعامل 2 (المتاح في optExample3.c) مقارنةً بإضافة علمي تحسين المصرّف -funroll-loops و-funroll-all-loops إلى البرنامج السابق (optExample2.c).

النسخة	غير مُحسَّنة	`-O1`	`-O2`	`-O3`
الأصلية (optExample.c)	3.86	2.32	2.14	2.15
مع نقل شيفرة ثابت الحلقة (optExample2.c)	1.83	1.63	1.71	1.63
مع فتح الحلقات اليدوي بمعامل 2 (optExample3.c)	1.65	1.53	1.45	1.45
مع `-funroll-loops` (optExample2.c)	1.82	1.48	1.46	1.46
مع `-funroll-all-loops` (optExample2.c)	1.81	1.47	1.47	1.46

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

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

تنفّذ الدالة main في البرنامج خطوتين. أولًا، تخصص مصفوفة الإدخال الرياضية ومتجه الإدخال ومصفوفة الإخراج الرياضية وتهيّئها. بعد ذلك، تنفّذ ضرب المصفوفة الرياضية في المتجه. ويكشف تشغيل الشيفرة على أبعاد 10,000 × 10,000 أن الدالة matrixVectorMultiply تستهلك معظم الوقت:

$ gcc -o matrixVector matrixVector.c
$ ./matrixVector 10000 10000
Time to allocate and fill matrices: 1.2827
Time to allocate vector: 9.6e-05
Time to matrix-vector multiply: 1.98402

ولذلك ستركّز مناقشتنا على الدالة matrixVectorMultiply.

12.3.1. تبديل الحلقات

تبدّل تحسينات تبديل الحلقات (loop interchange) ترتيب الحلقتين الداخلية والخارجية في الحلقات المتداخلة لتعظيم محلية الذاكرة المؤقتة. ويصعب على المصرّفات إجراء هذه المهمة تلقائيًا. وفي GCC، يوجد علم المصرّف -floop-interchange لكنه غير متاح افتراضيًا حاليًا. ولذلك من الجيد أن ينتبه المبرمجون إلى كيفية وصول شيفرتهم إلى بنى البيانات المركّبة من الذاكرة مثل المصفوفات والمصفوفات الرياضية. وكمثال، لنلقِ نظرة أقرب على الدالة matrixVectorMultiply في matrixVector.c:

الجدول 1. تبديل الحلقات في الدالة matrixVectorMultiply().

النسخة الأصلية (matrixVector.c)

void matrixVectorMultiply(int **m,
                          int *v,
                          int **res,
                          int row,
                          int col) {
    int i, j;
    //cycles through every matrix column
    //in inner-most loop (inefficient)
    for (j = 0; j < col; j++){
        for (i = 0; i < row; i++){
            res[i][j] = m[i][j] * v[j];
        }
    }
}

نسخة تبديل الحلقات (matrixVector2.c)

void matrixVectorMultiply(int **m,
                          int *v,
                          int **res,
                          int row,
                          int col) {
    int i, j;
    //cycles through every row of matrix
    //in inner-most loop
    for (i = 0; i < row; i++){
        for (j = 0; j < col; j++){
            res[i][j] = m[i][j] * v[j];
        }
    }
}

تُخصَّص مصفوفتا الإدخال والإخراج الرياضيتان ديناميكيًا (الطريقة الثانية المناقشة في فصل C). ونتيجة لذلك، لا تكون الصفوف في المصفوفتين الرياضيتين متتابعة مع بعضها، بينما تكون العناصر في كل صف متتابعة. ويسبب الترتيب الحالي للحلقتين أن يمر البرنامج على كل عمود بدلًا من كل صف. تذكّر أن البيانات تُحمَّل في الذاكرة المؤقتة كتلًا لا عناصر. ونتيجة لذلك، عند الوصول إلى عنصر x في مصفوفة في res أو m، تُحمَّل أيضًا العناصر المجاورة لـ x في الذاكرة المؤقتة. ويمرير كل «عمود» في المصفوفة الرياضية يسبب إخفاقات أكثر في الذاكرة المؤقتة، إذ تُجبر الذاكرة المؤقتة على تحميل كتل جديدة مع كل وصول. ويظهر الجدول 2 أن إضافة أعلام التحسين لا تقلل زمن تشغيل الدالة. لكن مجرد تبديل ترتيب الحلقتين (كما يظهر في أمثلة الشيفرة السابقة وفي matrixVector2.c) يجعل الدالة أسرع بنحو ثماني مرات ويتيح للمصرّف إجراء تحسينات إضافية.

النسخة	البرنامج	غير مُحسَّنة	`-O1`	`-O2`	`-O3`
الأصلية	`matrixVector`	2.01	2.05	2.07	2.08
مع تبديل الحلقات	`matrixVector2`	0.27	0.08	0.06	0.06

وأداة Valgrind المسماة cachegrind (المناقشة في الفصل 11) طريقة ممتازة لتحديد مشكلات محلية البيانات، وهي تكشف الفروق في الوصول إلى الذاكرة المؤقتة بين نسختي الدالة matrixVectorMultiply المعروضتين في المثال السابق.

12.3.2. تحسينات أخرى للمصرّف لتحسين المحلية: التفكيك والدمج

ينتج عن إعادة تشغيل البرنامج المحسَّن على 10,000 × 10,000 عنصر أرقام زمن التشغيل التالية:

$ gcc -o matrixVector2 matrixVector2.c
$ ./matrixVector2 10000 10000
Time to allocate and fill matrices: 1.29203
Time to allocate vector: 0.000107
Time to matrix-vector multiply: 0.271369

الآن، صار تخصيص المصفوفات الرياضية وملؤها يستهلك معظم الوقت. ويكشف توقيت إضافي أن ملء المصفوفات الرياضية هو ما يستهلك معظم الوقت فعلًا. لنلقِ نظرة أقرب على تلك الشيفرة:

//fill matrices
for (i = 0; i < rows; i++){
    fillArrayRandom(matrix[i], cols);
    fillArrayZeros(result[i], cols);
}

لملء مصفوفتي الإدخال والإخراج الرياضيتين، تمر حلقة for على جميع الصفوف، وتستدعي الدالتين fillArrayRandom وfillArrayZeros على كل مصفوفة رياضية. وفي بعض السيناريوهات، قد يكون من المفيد للمصرّف أن يقسم الحلقة الواحدة إلى حلقتين منفصلتين (وهو ما يُعرف بـ تفكيك الحلقات، loop fission)، كما يظهر في الجدول 3.

الجدول 3. مثال على تفكيك الحلقات في حلقة ملء المصفوفات الرياضية في main.

النسخة الأصلية

for (i = 0; i < rows; i++) {
    fillArrayRandom(matrix[i], cols);
    fillArrayZeros(result[i], cols);
}

مع تفكيك الحلقات

for (i = 0; i < rows; i++) {
    fillArrayRandom(matrix[i], cols);
}

for (i = 0; i < rows; i++) {
    fillArrayZeros(result[i], cols);
}

وتُسمى عملية أخذ حلقتين تعملان على المجال نفسه ودمج محتوياتهما في حلقة واحدة (أي عكس تفكيك الحلقات) دمج الحلقات (loop fusion). وتفكيك الحلقات ودمجها مثالان على تحسينات قد يجريها المصرّف لمحاولة تحسين محلية البيانات. وقد تستخدم مصرّفات المعالجات متعددة الأنوية تفكيك الحلقات أو دمجها أيضًا لتمكين الحلقات من التنفيذ بكفاءة على أنوية متعددة. فمثلًا، قد يستخدم المصرّف تفكيك الحلقات لتوزيع حلقتين على نواتين مختلفتين. وبالمثل، قد يستخدم المصرّف دمج الحلقات لدمج عمليات مترابطة في جسم الحلقة وتوزيع مجموعة جزئية من تكرارات الحلقة على كل نواة (بافتراض استقلال البيانات بين التكرارات).

وفي حالتنا، لا يحسّن تطبيق تفكيك الحلقات يدويًا أداء البرنامج مباشرةً؛ فلا تغيير تقريبًا في الوقت اللازم لملء المصفوفة. غير أنه قد يكشف تحسينًا أكثر دقة: فالحلقة التي تحتوي fillArrayZeros غير ضرورية. فتخصيص القيم لكل عنصر في مصفوفة result تقوم به الدالة matrixVectorMultiply؛ ولا حاجة إلى تهيئة مسبقة بجميع الأصفار.

الجدول 4. إزالة النداء غير اللازم إلى fillArrayZeros.

النسخة السابقة (matrixVector2.c)

for (i = 0; i < rows; i++) {
    matrix[i] = allocateArray(cols);
    result[i] = allocateArray(cols);
}

for (i = 0; i < rows; i++) {
    fillArrayRandom(matrix[i], cols);
    fillArrayZeros(result[i], cols);
}

النسخة المحدَّثة مع calloc() (matrixVector3.c)

for (i = 0; i < rows; i++) {
    matrix[i] = allocateArray(cols);
    result[i] = allocateArray(cols);
}

for (i = 0; i < rows; i++) {
    fillArrayRandom(matrix[i], cols);
    //fillArrayZeros(result[i], cols); //no longer needed
}

12.3.3. تنميط الذاكرة باستخدام Massif

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

$ gcc -o matrixVector3 matrixVector3.c
$ ./matrixVector3 10000 10000
Time to allocate matrices: 0.049073
Time to fill matrices: 0.946801
Time to allocate vector: 9.3e-05
Time to matrix-vector multiply: 0.359525

ومع أن كل مصفوفة مخزَّنة في الذاكرة بشكل غير متتابع، تشغل كل منها 10,000 × sizeof(int) بايت، أي 40,000 بايت. ولأن المجموع المخصص 20,000 مصفوفة (10,000 للمصفوفة الرياضية الأولية و10,000 لمصفوفة النتائج)، فإن ذلك يقابل 800 مليون بايت، أي نحو 762 ميغابايت من المساحة. ومن المفهوم أن ملء 762 ميغابايت بأعداد عشوائية يستغرق وقتًا طويلًا. وفي المصفوفات الرياضية، ينمو استخدام الذاكرة تربيعيًا مع حجم الإدخال، ويمكن أن يؤدي دورًا كبيرًا في الأداء.

وتستطيع أداة massif في Valgrind مساعدتك على تنميط استخدام الذاكرة. وكما في أدوات Valgrind الأخرى التي غطيناها في هذا الكتاب (memcheck وcachegrind وcallgrind)، يعمل massif كغلاف حول الملف التنفيذي للبرنامج. وتحديدًا، يأخذ massif لقطات لاستخدام البرنامج للذاكرة عبر البرنامج، وينمّط كيفية تذبذب استخدام الذاكرة. وقد يجد المبرمجون أداة massif مفيدة لتتبع كيفية استخدام برامجهم لذاكرة الكومة، ولتحديد فرص تحسين استخدام الذاكرة. لنشغّل أداة massif على الملف التنفيذي matrixVector3:

$ valgrind --tool=massif ./matrixVector3 10000 10000
==7030== Massif, a heap profiler
==7030== Copyright (C) 2003-2015, and GNU GPL'd, by Nicholas Nethercote
==7030== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==7030== Command: ./matrixVector3 10000 10000
==7030==
Time to allocate matrices: 0.049511
Time to fill matrices: 4.31627
Time to allocate vector: 0.001015
Time to matrix-vector multiply: 0.62672
==7030==

ينتج عن تشغيل massif ملف massif.out.xxxx، حيث xxxx رقم معرّف فريد. وإذا كنت تكتب معنا، اكتب ls لكشف ملف massif المقابل لديك. وفي المثال التالي، الملف المقابل هو massif.out.7030. استخدم الأمر ms_print لعرض مخرجات massif:

$ ms_print massif.out.7030
-----------------------------------------------------------------------------
Command:            ./matrixVector3 10000 10000
Massif arguments:   (none)
ms_print arguments: massif.out.7030
-----------------------------------------------------------------------------

    MB
763.3^                                                ::::::::::::::::::::::#
     |:::::::::::::::::::::::::::::::::::::::::::::::::                     #
     |:                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
     |@                                               :                     #
   0 +-------------------------------------------------------------------->Gi
     0                                                                  9.778

Number of snapshots: 80
 Detailed snapshots: [3, 12, 17, 22, 49, 59, 69, 79 (peak)]

في أعلى المخرجات يقع مخطط استخدام الذاكرة. ويُظهر المحور x عدد التعليمات المنفَّذة. ويُظهر المحور y استخدام الذاكرة. ويشير المخطط أعلاه إلى أن ما مجموعه 9.778 مليار (Gi) تعليمة نُفِّذت أثناء تشغيلنا لـ matrixVector3. وأثناء التنفيذ، أخذ massif ما مجموعه 80 لقطة لقياس الاستخدام على الكومة. وبلغ استخدام الذاكرة ذروته في اللقطة الأخيرة (79). وكانت ذروة استخدام الذاكرة للبرنامج 763.3 ميغابايت، وظلت ثابتة نسبيًا عبر البرنامج.

وتأتي ملخصات جميع اللقطات بعد المخطط. فمثلًا، يقابل الجدول التالي اللقطات حول اللقطة 79:

....

------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)   stacks(B)
------------------------------------------------------------------------------
 70      1,081,926      727,225,400      727,080,000       145,400          0
 71      1,095,494      737,467,448      737,320,000       147,448          0
 72      1,109,062      747,709,496      747,560,000       149,496          0
 73      1,122,630      757,951,544      757,800,000       151,544          0
 74      1,136,198      768,193,592      768,040,000       153,592          0
 75      1,149,766      778,435,640      778,280,000       155,640          0
 76      1,163,334      788,677,688      788,520,000       157,688          0
 77      1,176,902      798,919,736      798,760,000       159,736          0
 78  7,198,260,935      800,361,056      800,201,024       160,032          0
 79 10,499,078,349      800,361,056      800,201,024       160,032          0
99.98% (800,201,024B) (heap allocations) malloc/new/new[], --alloc-fns, etc.
->99.96% (800,040,000B) 0x40089D: allocateArray (in matrixVector3)

يقابل كل صف لقطة معينة، وزمن أخذها، وإجمالي استهلاك ذاكرة الكومة (بالبايتات) عند تلك النقطة، وعدد البايتات التي طلبها البرنامج ("useful-heap") عند تلك النقطة، وعدد البايتات المخصصة زيادةً على ما طلبه البرنامج، وحجم المكدّس. ويكون تنميط المكدّس معطّلًا افتراضيًا (فهو يبطئ massif بدرجة كبيرة). ولتمكين تنميط المكدّس، استخدم الخيار --stacks=yes عند تشغيل massif.

وتكشف أداة massif أن 99.96% من استخدام ذاكرة الكومة في البرنامج حدث في الدالة allocateArray، وأن ما مجموعه 800 مليون بايت خُصّص، وهو ما يتسق مع الحساب التقريبي الذي أجريناه سابقًا. وسيجد القراء على الأرجح أن massif أداة مفيدة لتحديد مناطق الاستخدام المرتفع لذاكرة الكومة في برامجهم، وهو ما يبطئ البرنامج غالبًا. فمثلًا، قد تحدث تسربات الذاكرة (memory leaks) في البرامج عندما يستدعي المبرمجون malloc بتكرار من دون استدعاء free عند أول فرصة صحيحة. وأداة massif مفيدة للغاية في كشف هذه التسربات.

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

اختر بنى بيانات وخوارزميات جيدة

لا بديل عن استخدام الخوارزميات وبنى البيانات المناسبة؛ فالإخفاق في ذلك غالبًا ما يكون السبب الأول لضعف الأداء في الشيفرة. فمثلًا، خوارزمية غربال إراتوستينس (Sieve of Eratosthenes) الشهيرة طريقة أكفأ بكثير لتوليد الأعداد الأولية من خوارزميتنا المخصصة في optExample، وتنتج تحسنًا كبيرًا في الأداء. وتعرض القائمة التالية الوقت اللازم لتوليد جميع الأعداد الأولية بين 2 و5 ملايين باستخدام تطبيق للغربال:

$ gcc -o genPrimes genPrimes.c
$ ./genPrimes 5000000
Found 348513 primes (0.122245 s)

تتطلب خوارزمية الغربال 0.12 ثانية فقط لإيجاد جميع الأعداد الأولية بين 2 و5 ملايين، مقابل 1.46 ثانية يستغرقها optExample2 لتوليد المجموعة نفسها من الأعداد الأولية مع تشغيل أعلام التحسين -O3 (تحسن بمقدار 12 مرة). وتُترك كتابة تطبيق خوارزمية الغربال تمرينًا للقارئ؛ لكن ينبغي أن يكون واضحًا أن اختيار خوارزمية أفضل منذ البداية كان سيوفر ساعات من جهد التحسين المضني. ويوضح مثالنا لماذا تشكّل معرفة بنى البيانات والخوارزميات أساسًا لعلماء الحاسوب.

استخدم دوال المكتبة القياسية كلما أمكن

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

حسّن بناءً على البيانات لا على المشاعر

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

قسّم الشيفرة المعقدة إلى عدة دوال

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

أعط الأولوية لمقروئية الشيفرة

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

انتبه لاستخدام الذاكرة

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

المصرّفات تتحسن باستمرار

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

السابق 11. التخزين وهرم الذاكرة التالي 13. نظام التشغيل