فك الحلقة

تتمثل إحدى العمليات في برنامج حاسوبي في حذف 100 عنصر من مجموعة. ويتم ذلك عادةً باستخدام forحلقة تكرارية تستدعي الدالة remove(item_number) . إذا كان الهدف من هذا الجزء من البرنامج هو تحسينه، وكانت تكلفة الحلقة التكرارية أعلى بكثير من تكلفة الدالة remove(x) ، فيمكن استخدام تقنية فك التكرار لتسريع العملية.

for ( int x = 0 ; x < 100 ; x ++ ) { remove ( x ); }

for ( int x = 0 ; x < 100 ; x += 5 ) { remove ( x ); remove ( x + 1 ); remove ( x + 2 ); remove ( x + 3 ); remove ( x + 4 ); }

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

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

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

for i := 1:8 do إذا كان باقي قسمة i على 2 يساوي صفرًا، فقم بتنفيذ الدالة do_even_stuff(i). وإلا قم بتنفيذ الإجراءات الغريبة (i)؛ التالي i؛

do_odd_stuff(1); do_even_stuff(2); do_odd_stuff(3); do_even_stuff(4); do_odd_stuff(5); do_even_stuff(6); do_odd_stuff(7); do_even_stuff(8);

لكن بالطبع، لا يشترط أن يكون الكود المُنفذ عبارة عن استدعاء إجراء، وهذا المثال التالي يتضمن متغير الفهرس في الحساب:

x(1) := 1; for i := 2:9 do x(i) := x(i - 1) * i; اطبع i، x(i)؛ التالي i؛

x(1) := 1; x(2) := x(1) * 2; print 2, x(2); x(3) := x(2) * 3; print 3, x(3); x(4) := x(3) * 4; print 4, x(4); ... إلخ.

قد ينتج عن تجميع هذا الكود الكثير من التعليمات البرمجية ( وخاصةً عبارات الطباعة )، ولكن يمكن تحسينه أكثر. يشير هذا المثال فقط إلى x(i) و x(i - 1) في الحلقة (الأخيرة فقط لتحديد القيمة الجديدة x(i) ). لذلك، نظرًا لعدم وجود أي إشارة لاحقة إلى المصفوفة x المُنشأة هنا، يمكن استبدال استخداماتها بمتغير بسيط. مع ذلك، يعني هذا التغيير متغيرًا بسيطًا تتغير قيمته ، بينما في حال استخدام المصفوفة، قد يلاحظ محلل المُجمِّع أن قيم المصفوفة ثابتة، كل منها مُشتق من قيمة ثابتة سابقة، وبالتالي يحتفظ بالقيم الثابتة، ليصبح الكود كالتالي:

اطبع 2، 2؛ اطبع 3، 6؛ اطبع 4، 24؛ ...إلخ.

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

لنفترض وجود حلقة WHILE في الشفرة الزائفة مشابهة لما يلي:

طالما (الشرط) افعل فعل نهاية الحلقة . . . . . .

طالما (الشرط) افعل فعل إذا لم يتحقق الشرط، فانتقل إلى نقطة الخروج. فعل إذا لم يتحقق الشرط، فانتقل إلى نقطة الخروج. فعل نهاية الحلقة فاصل في التصنيف: .

إذا (الشرط) يكرر فعل إذا لم يتحقق الشرط، فانتقل إلى نقطة الخروج. فعل إذا لم يتحقق الشرط، فانتقل إلى نقطة الخروج. فعل بينما (شرط) فاصل في التصنيف:

في هذه الحالة، يكون فك الحلقة أسرع لأن ENDWHILE (القفز إلى بداية الحلقة) سيتم تنفيذه بنسبة 66٪ أقل.

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

هذا المثال مخصص لمجمعات IBM/360 أو Z/Architecture ويفترض أنه سيتم نسخ حقل بحجم 100 بايت (عند الإزاحة صفر) من المصفوفة FROM إلى المصفوفة TO - وكلاهما يحتوي على 50 إدخالًا بأطوال عناصر تبلغ 256 بايت لكل منهما.

* عنوان المرسل موجود في R14. * تهيئة السجلات R15 و R0 و R1 و R2 من البيانات المحددة في نهاية * البرنامج الذي يبدأ بالعلامة INIT/MAXM1.  LM R15,R2,INIT Set R15 = الحد الأقصى لعدد MVC * التعليمات (MAXM1 = 16)، * R0 = عدد عناصر المصفوفة، * R1 = عنوان مصفوفة 'FROM'، و * R2 = عنوان مصفوفة 'TO'. * * تبدأ الحلقة من هنا. LOOP EQU * تعريف تسمية الحلقة. * في هذه المرحلة، سيحتوي R15 دائمًا على الرقم 16 (MAXM1).  SR R15,R0 اطرح العدد المتبقي من * المدخلات في المصفوفة (R0) من R15.  إذا لم تكن قيمة R15 موجبة، فهذا يعني أننا * يوجد أكثر من 16 إدخالًا متبقيًا * في المصفوفة، انتقل لتنفيذ العملية بأكملها * تسلسل MVC ثم كرر. * * احسب الإزاحة (من بداية تسلسل MVC) للتفرع غير المشروط إلى * حلقة MVC "غير الملتفة" أدناه. إذا كان عدد العناصر المتبقية في المصفوفات صفرًا، فإن R15 ستكون 16، لذا * سيتم تجاوز جميع تعليمات MVC.  MH R15,=AL2(ILEN) اضرب R15 في طول واحد * تعليمات MVC.  B ALL(R15) انتقل إلى ALL+R15، عنوان * تم حساب تعليمات MVC المحددة * مع إمكانية الانتقال إلى البقية. * * تعليمات MVC 'table'. * يحتوي الإدخال الأول على أقصى إزاحة مسموح بها مع سجل واحد = F00 سداسي عشري * (15*256) في هذا المثال. * جميع تعليمات MVC (نقل الحرف) الـ 16 التالية تستخدم أساسًا بالإضافة إلى إزاحة * يتم تحديد العناوين، ويقل كل إزاحة من/إلى بمقدار طول عنصر واحد من عناصر المصفوفة. * (256). هذا يتجنب الحاجة إلى حساب المؤشرات لكل عنصر حتى a * أقصى إزاحة مسموح بها ضمن تعليمات FFF السداسية العشرية * (15*256+255). التعليمات مرتبة حسب تناقص الإزاحة، لذا فإن الأخيرة * يتم نقل العنصر الموجود في المجموعة أولاً. ALL MVC 15*256(100,R2),15*256(R1) انقل 100 بايت من المدخل السادس عشر من * المصفوفة 1 إلى المصفوفة 2 (مع * (التمرير السريع). ILEN EQU *-ALL اضبط طول ILEN على الطول السابق * تعليمات MVC.  MVC 14*256(100,R2),14*256(R1) نقل 100 بايت من المدخل الخامس عشر.  MVC 13*256(100,R2),13*256(R1) نقل 100 بايت من الإدخال الرابع عشر.  MVC 12*256(100,R2),12*256(R1) نقل 100 بايت من المدخل الثالث عشر.  MVC 11*256(100,R2),11*256(R1) نقل 100 بايت من المدخل الثاني عشر.  MVC 10*256(100,R2),10*256(R1) نقل 100 بايت من المدخل الحادي عشر.  MVC 09*256(100,R2),09*256(R1) نقل 100 بايت من المدخل العاشر.  MVC 08*256(100,R2),08*256(R1) نقل 100 بايت من الإدخال التاسع.  MVC 07*256(100,R2),07*256(R1) نقل 100 بايت من الإدخال الثامن.  MVC 06*256(100,R2),06*256(R1) نقل 100 بايت من الإدخال السابع.  MVC 05*256(100,R2),05*256(R1) نقل 100 بايت من الإدخال السادس.  MVC 04*256(100,R2),04*256(R1) نقل 100 بايت من الإدخال الخامس.  MVC 03*256(100,R2),03*256(R1) نقل 100 بايت من الإدخال الرابع.  MVC 02*256(100,R2),02*256(R1) نقل 100 بايت من الإدخال الثالث.  MVC 01*256(100,R2),01*256(R1) نقل 100 بايت من الإدخال الثاني.  MVC 00*256(100,R2),00*256(R1) نقل 100 بايت من الإدخال الأول. *  S R0,MAXM1 تقليل عدد الإدخالات المتبقية * للمعالجة.  BNPR R14 إذا لم تكن هناك إدخالات أخرى للمعالجة، فقم بالعودة * لمعالجة هذا الأمر في R14.  AH R1,=AL2(16*256) قم بزيادة مؤشر المصفوفة 'FROM' إلى ما بعد * المجموعة الأولى.  AH R2,=AL2(16*256) قم بزيادة مؤشر المصفوفة 'TO' إلى ما بعد القيمة المحددة * المجموعة الأولى.  L R15,MAXM1 أعد تحميل الحد الأقصى لعدد المركبات الآلية * تعليمات لكل دفعة في R15 * (تم تدميرها بواسطة الحساب في * أول تعليمة في الحلقة).  B LOOP نفّذ الحلقة مرة أخرى. * * الثوابت والمتغيرات الثابتة (يمكن تمريرها كمعاملات، باستثناء * MAXM1). تهيئة DS 0A 4 عناوين (مؤشرات) لتكون * مُحمّل مسبقًا بتعليمات "LM" * في بداية البرنامج. MAXM1 DC A(16) الحد الأقصى لعدد تعليمات MVC * يتم التنفيذ لكل دفعة. N DC A(50) عدد العناصر الفعلية في المصفوفة (أ * متغير، يتم تعيينه في مكان آخر).  DC A(FROM) عنوان بداية المصفوفة 1 * (مؤشر).  DC A(TO) عنوان بداية المصفوفة 2 * (مؤشر). * * المصفوفات الثابتة (يمكن الحصول عليها ديناميكيًا). FROM DS 50CL256 مصفوفة من 50 مدخلاً، كل منها بحجم 256 بايت. TO DS 50CL256 مصفوفة من 50 مدخلاً، كل منها بحجم 256 بايت. 

في هذا المثال، يتطلب الأمر حوالي 202 تعليمة باستخدام حلقة تكرار تقليدية (50 تكرارًا)، بينما يتطلب الكود الديناميكي المذكور أعلاه حوالي 89 تعليمة فقط (أي توفيرًا بنسبة 56% تقريبًا). حتى لو احتوت المصفوفة على عنصرين فقط، فسيستغرق التنفيذ نفس الوقت تقريبًا الذي تستغرقه الحلقة الأصلية غير المُكررة. الزيادة في حجم الكود لا تتجاوز 108 بايتات ، حتى مع وجود آلاف العناصر في المصفوفة. 

يمكن استخدام تقنيات مماثلة عند وجود تعليمات متعددة، شريطة تعديل طول التعليمات الإجمالي وفقًا لذلك. على سبيل المثال، في هذا المثال نفسه، إذا كان من المطلوب مسح باقي عناصر المصفوفة وتحويلها إلى قيم فارغة مباشرةً بعد نسخ الحقل ذي الـ 100 بايت، فيمكن إضافة تعليمة مسح إضافية مباشرةً بعد كل MVC في التسلسل (حيث يتطابق مع القيمة في MVC أعلاه).XC xx*256+100(156,R1),xx*256+100(R2)xx

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

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

#include <stdio.h>// عدد المدخلات التي تتم معالجتها في كل تكرار للحلقة. // لاحظ أن هذا الرقم ثابت، وهو ما يعكس الكود أدناه. constexpr int BUNCHSIZE = 8int main ( void ) { int i = 0 ; // عداد int entries = 50 ; // العدد الإجمالي للعناصر المراد معالجتها // إذا كان عدد العناصر لا يقبل القسمة على BUNCHSIZE، // احصل على عدد مرات التكرار المطلوبة لإجراء معظم المعالجة في حلقة whileint repeat = ( entries / BUNCHSIZE ); // عدد مرات التكرار int left = ( entries % BUNCHSIZE ); // حساب الباقي// فكّ الحلقة في مجموعات من 8 بينما ( كرر -- ) { printf ( "process(%d) \n " , i ); printf ( "process(%d) \n " , i + 1 ); printf ( "process(%d) \n " , i + 2 ); printf ( "process(%d) \n " , i + 3 ); printf ( "process(%d) \n " , i + 4 ); printf ( "process(%d) \n " , i + 5 ); printf ( "process(%d) \n " , i + 6 ); printf ( "process(%d) \n " , i + 7 );// تحديث الفهرس حسب الكمية التي تمت معالجتها دفعة واحدة i += BUNCHSIZE ; }// استخدم عبارة switch لمعالجة العناصر المتبقية بالانتقال إلى تسمية الحالة // عند التسمية التي ستؤدي بعد ذلك إلى إكمال المجموعة switch ( left ) { case 7 : printf ( "process(%d) \n " , i + 6 ); // المعالجة والاعتماد على الانتقال case 6 : printf ( "process(%d) \n " , i + 5 ); case 5 : printf ( "process(%d) \n " , i + 4 ); case 4 : printf ( "process(%d) \n " , i + 3 ); case 3 : printf ( "process(%d) \n " , i + 2 ); case 2 : printf ( "process(%d) \n " , i + 1 ); // عنصران متبقيان case 1 : printf ( "process(%d) \n " , i ); // عنصر واحد متبقٍ للمعالجة case 0 : break ; // لا يوجد عناصر متبقية } }

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

المصدر: ^{[ 9 ]}

سيحسب المثال التالي حاصل الضرب النقطي لمتجهين A و B مكونين من 100 عنصر من النوع double. إليك الكود بلغة C:

double dotProduct = 0 ;for ( int i = 0 ; i < 100 ; i ++ ) {dotProduct += A [ i ] * B [ i ];}

الحلقة 3:دينار بحريني $f10 , 0 ( $5 ) ؛ $f10 ← أ[i]ld $f12 , 0 ( $6 ) ; $f12 ← B[i]mul.d $f10 , $f10 , $f12 ; $f10 ← أ[i]*ب[i]أضف $f8 ، $f8 ، $f10 ؛ $f8 ← $f8 + A[i]*B[i]addi $5 , $5 , 8 ; زيادة مؤشر A[i] بمقدار الحجم؛ من النوع المزدوج.addi $6 , $6 , 8 ; زيادة مؤشر B[i] بمقدار الحجم؛ من النوع المزدوج.addi $7 , $7 , -1 ; إنقاص عدد التكراراتامتحان:bgtz $7 , loop3 ; استمر إذا كان عدد مرات التكرار > 0

الحلقة 3:ld $f10 , 0 ( $5 ) ; تكرار مع إزاحة 0ld $f12 , 0 ( $6 )mul.d $f10 , $f10 , $f12add.d $f8 , $f8 , $f10ld $f10 , 8 ( $5 ) ; تكرار مع إزاحة 8ld $f12 , 8 ( $6 )mul.d $f10 , $f10 , $f12add.d $f8 , $f8 , $f10ld $f10 , 16 ( $5 ) ; تكرار مع إزاحة 16ld $f12 , 16 ( $6 )mul.d $f10 , $f10 , $f12add.d $f8 , $f8 , $f10ld $f10 , 24 ( $5 ) ; تكرار مع إزاحة 24ld $f12 , 24 ( $6 )mul.d $f10 , $f10 , $f12add.d $f8 , $f8 , $f10أضف 5 دولارات ، 5 دولارات ، 32أدي 6 دولارات ، 6 دولارات ، 32أضف 7 دولارات ، 7 دولارات ، -4امتحان:bgtz $7 , loop3 ; استمر في الحلقة إذا كان $7 > 0