جدول التفرع

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

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

يوضح الكود الزائف التالي المفهوم:

... التحقق من صحة x /* تحويل x إلى 0 (غير صالح) أو 1 أو 2 أو 3، حسب القيمة..) */ y = x * 4 ; /* الضرب في طول تعليمات التفرع (مثلاً 4) */ الانتقال إلى التالي + y ; /* التفرع إلى "جدول" تعليمات التفرع */ /* بداية جدول التفرع */ التالي : الانتقال إلى codebad ; /* x= 0 (غير صالح) */ الانتقال إلى codeone ; /* x= 1 */ الانتقال إلى codetwo ; /* x= 2 */ ... باقي جدول التفرع codebad : /* التعامل مع المدخلات غير الصالحة */

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

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

تعتمد الطريقة الفعلية المستخدمة لتنفيذ جدول الفروع عادةً على ما يلي:

• بنية المعالج الذي سيتم تنفيذ الكود عليه،
• سواء كانت لغة مُجمّعة أو مُفسّرة و
• سواء كان الربط المتأخر متضمناً أم لا.

كثيرًا ما يترك المبرمجون قرار إنشاء جدول التفرع للمترجم، معتقدين أنه قادر تمامًا على اختيار المفتاح الصحيح من بين مفاتيح البحث المعروفة. قد يصح هذا في حالة المترجمات المُحسِّنة للحالات البسيطة نسبيًا حيث يكون نطاق مفاتيح البحث محدودًا. مع ذلك، لا تتمتع المترجمات بذكاء البشر، ولا يمكنها امتلاك معرفة عميقة بالسياق، إذ تعتقد أن نطاقًا من قيم مفاتيح البحث الصحيحة، مثل 1، 2، 4، 6، 7، 20، 23، 40، 42، 50، و1000، سيُنتج جدول تفرع يحتوي على عدد هائل من المدخلات الفارغة (أكثر من 900) مقابل فائدة ضئيلة. قد يقوم مترجم مُحسِّن جيد حينها بفرز القيم مسبقًا، ثم يُولِّد شيفرة للبحث الثنائي ، كخيار "ثاني أفضل". في الواقع، قد يكون التطبيق "حساسًا جدًا للوقت"، وقد لا يُمثِّل مُتطلبات الذاكرة مشكلة على الإطلاق. ^{[ 2 ]}

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

• أولاً، اختبر مفتاح البحث = 1000 وقم بتنفيذ الفرع المناسب.
• اسمح للمترجم "بالاختيار" لإنشاء جدول فرعي على مفاتيح البحث المتبقية (1-50).

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

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

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

1. قم بتحويل حرف البيانات الخام إلى ما يعادله رقميًا (مثال: ASCII 'A' ==> 65 عشري، 0x41 سداسي عشري)
2. استخدم القيمة العددية الصحيحة كمؤشر في مصفوفة مكونة من 256 عنصرًا من 2 بايت، للحصول على مؤشر ثانٍ (العناصر غير الصالحة 0؛ تمثل الفجوات، وإلا 1، 2، 3، إلخ).

لن يتجاوز حجم المصفوفة (256 × 2) بايت لتخزين أعداد صحيحة غير مُوقّعة (قصيرة) من 16 بت لجميع البايتات الممكنة ذات 8 بت. في حال عدم اشتراط التحقق من صحة البيانات، واستخدام الأحرف الكبيرة فقط، قد يصل حجم المصفوفة إلى (26 × 2) = 52 بايت.

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

مثال بسيط على استخدام جدول التفرع في لغة التجميع الخاصة بمعالجات PIC من شركة Microchip ذات 8 بت هو:

movf INDEX , W ; انقل قيمة الفهرس من الذاكرة إلى المسجل W (العملي). addwf PCL , F ; أضفها إلى عداد البرنامج. افترض أن تعليمة PIC هي كلمة تعليمة واحدة، لذا لا حاجة لإجراء أي عملية ضرب. ; ستقوم معظم البنى بتحويل الفهرس بطريقة ما قبل ; إضافته إلى عداد البرنامج.جدول ؛ يبدأ جدول الفروع هنا بهذه التسمية . انتقل إلى الفهرس صفر ؛ كل تعليمة من تعليمات الانتقال هذه هي فرع غير مشروط. انتقل إلى الفهرس واحد ؛ من التعليمات البرمجية. انتقل إلى الفهرس اثنان . انتقل إلى الفهرس ثلاثة.index_zero ؛ تمت إضافة الكود هنا لتنفيذ أي إجراء مطلوب عندما يكون INDEX = صفر.index_one ...

ملاحظة: سيعمل هذا الكود فقط إذا كان PCL < (table + index_last). ولضمان هذا الشرط، يمكننا استخدام توجيه "org". إذا كانت GOTO عبارة عن كلمتين تعليميتين (PIC18F على سبيل المثال)، فإن هذا يحد من عدد إدخالات الجدول إلى أقل من 128. يتم توفير البتات العليا التي تتجاوز PCL بواسطة الجزء المقابل من PCLATH.

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

#include <stdio.h> #include <stdlib.h>typedef void ( * Handler )( void ); /* مؤشر إلى دالة معالجة *//* الدوال */ void func3 ( void ) { printf ( "3 \n " ); } void func2 ( void ) { printf ( "2 \n " ); } void func1 ( void ) { printf ( "1 \n " ); } void func0 ( void ) { printf ( "0 \n " ); }Handler jump_table [ 4 ] = { func0 , func1 , func2 , func3 };int main ( int argc , char ** argv ) { int value ;/* تحويل الوسيط الأول إلى عدد صحيح من 0 إلى 3 (باقي القسمة) */ القيمة = atoi ( argv [ 1 ]) % 4 ;/* استدعاء الدالة المناسبة (من func0 إلى func3) */ jump_table [ value ]();return 0 ; }

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

 أعلن عن ملصق المختبر (10)؛ أعلن x كمتغير ثنائي ثابت؛ انتقل إلى المختبر (س)؛ lab(1): /* رمز الخيار 1 */ ; ... lab(2): /* رمز الخيار 2 */ ; ...