ब्रांच टेबल
कंप्यूटर प्रोग्रामिंग में, ब्रांच सारणी (टेबल) या जंप सारणी प्रोग्राम नियंत्रण (ब्रांचिंग) को प्रोग्राम के दूसरे भाग (या एक अलग प्रोग्राम जो गतिशील रूप से लोड हो सकता है) को ब्रांच या जंप निर्देशों का उपयोग करके स्थानांतरित करने की एक विधि है। यह मल्टीवे ब्रांच का एक रूप है। असेंबली भाषा में प्रोग्रामिंग करते समय ब्रांच सारणी निर्माण का सामान्य रूप से उपयोग किया जाता है, लेकिन संकलक द्वारा भी उत्पन्न किया जा सकता है, विशेष रूप से अनुकूलित स्विच विवरण (स्टेटमेंट) को प्रयुक्त करते समय जिनके मूल्य एक साथ सघनतापूर्वक आपस मे जुड़े होते हैं।[1]
विशिष्ट कार्यान्वयन
एक ब्रांच सारणी में बिना शर्त ब्रांच निर्देशों की एक सीरियल सूची होती है जो निर्देश लंबाई (प्रत्येक ब्रांच निर्देश द्वारा प्रग्रहण कर लिए गए मेमोरी में बाइट्स की संख्या) द्वारा अनुक्रमिक सूचकांक को गुणा करके बनाई गई ऑफ़सेट का उपयोग करने में सम्मिलित होती है। यह इस तथ्य पर निर्भर करता है कि ब्रांचिंग के लिए मशीन कोड निर्देशों की एक निश्चित लंबाई होती है और इसे अधिकांश हार्डवेयर द्वारा अत्यंत कुशलता से निष्पादित किया जा सकता है, और असंसाधित डेटा मानों से सम्पर्क के समय सबसे उपयोगी होता है जिसे आसानी से अनुक्रमिक सूचकांक मानों में परिवर्तित किया जा सकता है। इस तरह के डेटा को देखते हुए, एक ब्रांच सारणी अधिकतम कुशल हो सकती है। इसमें सामान्य रूप निम्नलिखित 3 चरण होते हैं:
- वैकल्पिक रूप से डेटा सत्यापन इनपुट डेटा को यह सुनिश्चित करने के लिए स्वीकार्य है (यह अगले चरण के भाग के रूप में कीमत के बिना हो सकता है, यदि इनपुट एक बाइट है और 256 बाइट अनुवाद सारणी का उपयोग प्रत्यक्ष रूप से नीचे ऑफसेट प्राप्त करने के लिए किया जाता है)। साथ ही, यदि इनपुट के मानो के बारे में कोई संदेह नहीं है, तो इस चरण को छोड़ा जा सकता है।
- डेटा को ऑफसेट (कंप्यूटर विज्ञान) में ब्रांच सारणी में रूपांतरित करें। इसमें सामान्य रूप से निर्देश लंबाई को ध्यान में रखने के लिए गुणा या स्थानांतरण (प्रभावी रूप से 2 की पावर से गुणा करना) सम्मिलित होता है। यदि एक स्थिर अनुवाद सारणी का उपयोग किया जाता है, तो यह मल्टीप्लेइंग मैन्युअल रूप से या संकलक द्वारा बिना किसी रन टाइम कीमत के किया जा सकता है।
- ब्रांच सारणी के आधार एड्रैस और अभी-अभी उत्पन्न ऑफसेट से बने एड्रैस पर ब्रांच करना। इसमें कभी-कभी प्रोग्राम काउंटर रजिस्टर पर ऑफ़सेट जोड़ना सम्मिलित होता है (जब तक, कुछ निर्देश समुच्चय में, ब्रांच निर्देश एक अतिरिक्त इंडेक्स रजिस्टर की स्वीकृत नहीं देता है)। यह अंतिम एड्रैस सामान्य रूप से अप्रतिबंधित ब्रांच निर्देशों के अनुक्रम या उनके तुरंत बाद के निर्देश (सारणी में एक प्रविष्टि को छोड़ते हुए) में से एक को इंगित करता है।
निम्नलिखित स्यूडोकोड अवधारणा को दर्शाता है
... validate x /* transform x to 0 (invalid) or 1,2,3, according to value..) */
y = x * 4; /* multiply by branch instruction length (e.g. 4 ) */
goto next + y; /* branch into 'table' of branch instructions */
/* start of branch table */
next: goto codebad; /* x= 0 (invalid) */
goto codeone; /* x= 1 */
goto codeone; /* x= 1 */
goto codetwo; /* x= 2 */
... rest of branch table
codebad: /* deal with invalid input */
एड्रैस का उपयोग करके वैकल्पिक कार्यान्वयन
ब्रांच सारणी को प्रयुक्त करने का एक अन्य तरीका पॉइंटर्स (कंप्यूटर प्रोग्रामिंग) की एक ऐरे डेटा संरचना के साथ है जिसमें से आवश्यक फ़ंक्शन (कंप्यूटिंग) फ़ंक्शन का एड्रैस पुनर्प्राप्त किया जाता है। मूल रूप से स्थनान्तरण वेक्टर के रूप में जाना जाता है, इस विधि को हाल ही में प्रेषण सारणी ("डिस्पैच टेबल") या आभासी विधि सारणी ("वर्चुअल मेथड टेबल") जैसे विभिन्न नामों से भी जाना जाता है, लेकिन अनिवार्य रूप से एक ही उद्देश्य का प्रदर्शन करता है। इस पॉइंटर फ़ंक्शन विधि के परिणामस्वरूप एक मशीन निर्देश संग्रह किया जा सकता है, और अप्रत्यक्ष जम्प (ब्रांच निर्देशों में से एक) से संशोधन किया जा सकता है।
फ़ंक्शन के लिए पॉइंटर्स की परिणामी सूची लगभग प्रत्यक्ष रूप से थ्रेडेड (सूत्रित) कोड के समान है, और वैचारिक रूप से एक नियंत्रण सारणी के समान है।
ब्रांच सारणी को प्रयुक्त करने के लिए उपयोग की जाने वाली वास्तविक विधि सामान्य रूप से निम्न पर आधारित होती है:
- प्रोसेसर का संरचना जिस पर कोड निष्पादित किया जाना है,
- चाहे वह संकलित या व्याख्या की गई भाषा हो और
- बिलंबित बाइंडिंग सम्मिलित है या नहीं।
इतिहास
कंप्यूटिंग के प्रारम्भिक दिनों में ब्रांच सारणियों और अन्य असंसाधित डेटा एन्कोडिंग का उपयोग सामान्य था जब मेमोरी (कंप्यूटर) कीमती था, सेन्ट्रल प्रोसेसिंग यूनिट मंद थे और कॉम्पैक्ट डेटा प्रतिनिधित्व और विकल्पों की कुशल चयन महत्वपूर्ण थी। वर्तमान मे, वे सामान्य रूप से अभी भी उपयोग किए जाते हैं:
- अंतर्निहित प्रोग्रामिंग (एम्बेडेड प्रोग्रामिंग)
- ऑपरेटिंग सिस्टम का विकास। कई ऑपरेटिंग सिस्टमों में, सिस्टम कॉल और लाइब्रेरी (कंप्यूटर विज्ञान) फ़ंक्शंस दोनों को एक पूर्णांक अनुक्रमणिका द्वारा एक ब्रांच सारणी में संदर्भित किया जा सकता है।
- कुछ कंप्यूटर संरचना जैसे अंतर्राष्ट्रीय व्यापार मशीन (आईबीएम)/360 इंटरप्ट भेजने के लिए ब्रांच सारणी का उपयोग करते हैं
लाभ
ब्रांच सारणियों के लाभों में सम्मिलित हैं:
- कॉम्पैक्ट कोड संरचना (बार-बार ब्रांच ऑपकोड के होते हुए भी)
- कम हुए स्रोत विवरण (बनाम पुनरावृत वाले
Ifकथन) - व्यक्तिगत रूप से प्रतिकृति कोड का परीक्षण करने की आवश्यकता कम हो गई है (यदि बाद के प्रोग्राम संचालन को निर्धारित करने के लिए कॉल साइट पर उपयोग किया जाता है)
- एल्गोरिथम दक्षता और कोड दक्षता (डेटा को सिर्फ एक बार कोडित करने की आवश्यकता होती है और ब्रांच सारणी कोड सामान्य रूप से कॉम्पैक्ट होता है), और उच्च डेटा संपीड़न अनुपात प्राप्त करने की संभावना होती है। उदाहरण के लिए, देश के नामों को देश कोड में संपीड़ित करते समय, "सेंट्रल अफ़्रीकी रिपब्लिक" जैसी शृंखला को एकल इंडेक्स ( विषय सूची) में संपीड़ित किया जा सकता है, जिसके परिणामस्वरूप बड़ा संग्रह होता है - विशेष रूप से जब शृंखला कई बार दिखाई देती है। इसके अतिरिक्त, इसी इंडेक्स का उपयोग संबंधित डेटा को अलग-अलग सारणियों में अभिगम्य करने के लिए किया जा सकता है, जिससे भंडारण आवश्यकताओं को और कम किया जा सकता है।
लाइब्रेरी (कंप्यूटर विज्ञान) फ़ंक्शंस के लिए, जहां उन्हें एक पूर्णांक द्वारा संदर्भित किया जा सकता है:
- बाद के सॉफ़्टवेयर संस्करणों के साथ संगतता में सुधार करें। यदि किसी फ़ंक्शन का कोड और उसके प्रवेश बिंदु का एड्रैस परिवर्तित कर दिया गया है, तो ब्रांच सारणी में सिर्फ ब्रांच निर्देश को समायोजित करने की आवश्यकता है; लाइब्रेरी या ऑपरेटिंग सिस्टम के लिए संकलित एप्लिकेशन सॉफ़्टवेयर में संशोधन की आवश्यकता नहीं है।
इसके अतिरिक्त, सामान्य एप्लिकेशन प्रोग्रामिंग में कुछ स्थितियों में संख्या (सारणी में सूचकांक) द्वारा फ़ंक्शन को कॉल करना कभी-कभी उपयोगी हो सकता है।
दोष
- संकेत का अतिरिक्त स्तर, जो सामान्य रूप से छोटे प्रदर्शन को प्रभावित करता है।
- कुछ प्रोग्रामिंग भाषाओं में प्रतिबंध, हालांकि सामान्य रूप से मल्टीवे ब्रांचिंग की मूल अवधारणा को प्रयुक्त करने के वैकल्पिक तरीके हैं।
उदाहरण
8-बिट पेरिफ़ेरल इंटरफ़ेस नियंत्रक माइक्रोचिप असेंबली भाषा में ब्रांच सारणी के उपयोग का एक सरल उदाहरण है:
movf INDEX,W ; Move the index value into the W (working) register from memory
addwf PCL,F ; add it to the program counter. Each PIC instruction is one byte
; so there is no need to perform any multiplication.
; Most architectures will transform the index in some way before
; adding it to the program counter.
table ; The branch table begins here with this label
goto index_zero x; each of these goto instructions is an unconditional branch
goto index_one e; of code.
goto index_two
goto index_three
index_zero
e; Code is added here to perform whatever action is required when INDEX = zero
return
index_one
...
नोट: यह कोड तभी काम करेगा जब प्रिंटर नियंत्रण भाषा <(table + index_last) होगी। इस स्थिति को सुनिश्चित करने के लिए हम एक ''संस्था'' निर्देश का उपयोग कर सकते हैं। और यदि जीओटीओ (उदाहरण के लिए पेरिफ़ेरल इंटरफ़ेस नियंत्रक18एफ) 2 बाइट्स है, तो यह सारणी प्रविष्टियों की संख्या को 128 से कम तक सीमित कर देता है।
C में जंप सारणी उदाहरण
एक अन्य सरल उदाहरण, इस बार सिर्फ ब्रांच सारणी के अतिरिक्त जंप सारणी का प्रदर्शन करता है। यह वर्तमान में सक्रिय प्रक्रिया/फ़ंक्शन के बाहर प्रोग्राम ब्लॉक को कॉल करने की स्वीकृत देता है:
#include <stdio.h>
#include <stdlib.h>
typedef void (*Handler)(void); /* A pointer to a handler function */
/* The functions */
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;
/* Convert first argument to 0-3 integer (modulus) */
value = atoi(argv[1]) % 4;
/* Call appropriate function (func0 thru func3) */
jump_table[value]();
return 0;
}
प्रोग्रामिंग भाषा/आई में जंप सारणी उदाहरण
प्रोग्रामिंग भाषा/आई लेबल वेरिएबल्स की एक सरणी के रूप में एक जंप सारणी प्रयुक्त करता है। सबस्क्रिप्टेड विवरण लेबल का उपयोग करके इन्हें असामान्य तरीके से आरंभ किया जा सकता है। प्रोग्रामिंग भाषा/आई लेबल वेरिएबल्स सिर्फ विवरण का पता नहीं हैं, लेकिन सामान्य रूप से कोड ब्लॉक की स्थिति पर अतिरिक्त जानकारी होती है जिससे वे संबंधित होते हैं। असामान्य इनिशियलाइज़ेशन ( प्रारंभिकीकरण) के बिना, इसे कॉल और प्रविष्टि(एंट्री) वेरिएबल्स की एक सरणी के साथ कोडित भी किया जा सकता है।
declare lab (10) label;
declare x fixed binary;
goto lab(x);
lab(1): /* code for choice 1 */ ;
...
lab(2): /* code for choice 2 */ ;
संकलक उत्पन्न ब्रांच सारणियाँ
प्रोग्रामर प्रायः कंपाइलर के लिए ब्रांच सारणी बनाने या न बनाने का निर्णय छोड़ देते हैं, यह मानते हुए कि यह ज्ञात जांच कुंजियों से सही विकल्प बनाने में पूरी तरह से सक्षम है। यह अपेक्षाकृत सरल स्थितियों के लिए संकलक के अनुकूलन के लिए सही हो सकता है जहां जांच कुंजियों की सीमा सीमित है। हालाँकि, कंपाइलर मनुष्यों की तरह बुद्धिमान नहीं होते हैं और उन्हें 'संदर्भ' का गहन ज्ञान नहीं हो सकता है, यह मानते हुए कि 1, 2, 4, 6, 7, 20, 23, 40, 42 जैसे संभावित जांच कुंजी पूर्णांक मानों की एक श्रृंखला है। 50 और 1000 बहुत कम लाभ के लिए अत्यधिक बड़ी संख्या में रिक्त प्रविष्टियों (900+) के साथ एक ब्रांच सारणी उत्पन्न करेंगे। एक अच्छा ऑप्टिमाइज़िंग कंपाइलर तब मानो को निर्धारित कर सकता है और बाइनरी चॉप जांच के लिए 'दूसरे सर्वश्रेष्ठ' विकल्प के रूप में कोड उत्पन्न कर सकता है। वास्तव में, एप्लिकेशन अत्यधिक समय के लिए महत्वपूर्ण हो सकता है और कंप्यूटर डेटा भंडारण आवश्यकता वास्तव में कोई समस्या नहीं हो सकती है।[2]
हालांकि, अल्प 'सामान्य बुद्धि' इस विशेष स्थिति और इसी तरह के कई अन्य स्थितियों को बहुत बड़ी संभावित संग्रह के साथ एक सरल दो-चरणीय प्रक्रिया में परिवर्तित कर सकता है, जबकि अभी भी अंततः संकलक के लिए अंतिम विकल्प छोड़ रहा है लेकिन 'इसके निर्णय की सहायता' कर रहा है :
- सबसे पहले, जांच कुंजी = 1000 का परीक्षण करें और उपयुक्त ब्रांच का प्रदर्शन करें।
- संकलक को शेष जांच कुंजियों (1-50) पर एक ब्रांच सारणी बनाने के लिए 'चयन' करने की स्वीकृत दें।
समान रेखाओं के साथ विविधताओं का उपयोग उन स्थितियों में किया जा सकता है जहां श्रेणियों के बीच बड़े अंतराल के साथ छोटी श्रेणियों के दो सेट होते हैं।
कंप्यूटेड(संगणित) जीओटीओ
जबकि तकनीक को अब 'ब्रांच सारणी' के रूप में जाना जाता है, प्रारम्भिक कंपाइलर उपयोगकर्ताओं ने कार्यान्वयन को 'कंप्यूटेड गोटो' कहा जाता है, जो कंपाइलरों की फोरट्रान श्रृंखला में पाए गए निर्देश को संदर्भित करते हैं।[3][4] निर्देश को अंततः फोरट्रान 90 (स्रोत स्तर पर एसईएलईसीटी & सीएएसई विवरण के पक्ष में) में बहिष्कृत कर दिया गया था।[5]
ब्रांच सारणी के लिए इंडेक्स बनाना
जहां एक ब्रांच सारणी के लिए कोई स्पष्ट पूर्णांक मान उपलब्ध नहीं है, फिर भी इसे अंकगणितीय परिवर्तन के किसी रूप द्वारा जांच कुंजी (या जांच कुंजी का भाग) से बनाया जा सकता है, या यह सिर्फ डेटाबेस या प्रविष्टि संख्या कुंजी के पूर्व सत्यापन के समय मिली जांच कुंजी वाली सरणी में पद संख्या हो सकती है ।
कुछ स्थितियों में इंडेक्स बनाने के लिए हैश सारणी की आवश्यकता हो सकती है। हालांकि, एकल बाइट इनपुट मान जैसे A-Z (या लंबी कुंजी का पहला बाइट) के लिए, बाइट की सामग्री (असंसाधित डेटा) का उपयोग अंतिम इंडेक्स प्राप्त करने की प्रक्रिया शून्य अंतराल वाली ब्रांच सारणी के लिए दो-चरणीय, सामान्य हैश फ़ंक्शन में किया जा सकता है।
- अपरिष्कृत डेटा वर्ण को उसके सांख्यिक समतुल्य में (उदाहरण ASCII 'A' ==> 65 दशमलव, 0x41 हेक्साडेसिमल) रूपांतरित करें
- दूसरी अनुक्रमणिका प्राप्त करने के लिए 256 बाइट सरणी में अंकीय पूर्णांक मान का उपयोग करें (अमान्य प्रविष्टियां 0; अंतराल का प्रतिनिधित्व करना, अन्यथा 1, 2, 3 आदि)
सभी संभव 16-बिट अहस्ताक्षरित (लघु) पूर्णांकों को रखने के लिए सरणी (256 x 2) बाइट्स से बड़ी नहीं होगी। यदि कोई सत्यापन आवश्यक नहीं है, और सिर्फ ऊपरी स्थिति का उपयोग किया जाता है, तो सरणी का आकार (26 x 2) = 52 बाइट्स जितना छोटा हो सकता है।
तकनीक के अन्य उपयोग
हालांकि ब्रांच सारणी का उपयोग करके ब्रांचिंग की तकनीक का उपयोग प्रायः सिर्फ प्रोग्राम संचालन को परिवर्तित करने के उद्देश्य से किया जाता है - एक प्रोग्राम लेबल पर जंप के लिए जो एक अप्रतिबंधित ब्रांच है - उसी तकनीक का उपयोग अन्य उद्देश्यों के लिए किया जा सकता है। उदाहरण के लिए, इसका उपयोग पुनरावृत किए गए निर्देशों के अनुक्रम में एक प्रारम्भिक बिंदु का चयन करने के लिए किया जा सकता है जहां ड्रॉप थ्रू मानक और सुविचारित है। इसका उपयोग उदाहरण के लिए लूप अनोलिंग में कंपाइलर्स या समय-समय पर संकलन को अनुकूलित करके किया जा सकता है।
यह भी देखें
- डिस्पैच (प्रेषण) सारणी एक ब्रांच सारणी को दूसरे नाम से विलंबित बाइंडिंग के लिए उपयोग किया जाता है
- ब्रांच सारणियों में उपयोग किए जाने वाले फंक्शन के लिए एड्रैस के फंक्शन पॉइंटर सरणियाँ
- अप्रत्यक्ष ब्रांच
- लुकअप सारणी मिलान किए जाने वाले वस्तुओं की एक सरणी, कभी-कभी पूर्व-परिकलित परिणाम रखती है
- स्विच विवरण एक उच्च स्तरीय भाषा सशर्त विवरण है जो एक ब्रांच सारणी उत्पन्न कर सकता है
- डिस्पैचिंग के लिए गतिशील रूप से समनुदेशित किए गए पॉइंटर्स के साथ वर्चुअल मेथड टेबल एक अन्य नाम से एक ब्रांच टेबल (डिस्पैच टेबल देखें)
संदर्भ
- ↑ Page, Daniel (2009). A Practical Introduction to Computer Architecture. Springer Science & Business Media. p. 479. ISBN 9781848822559.
- ↑ Jones, Nigel (1 May 1999). "How to Create Jump Tables via Function Pointer Arrays in C and C++". Archived from the original on 12 February 2012. Retrieved 12 July 2008.
- ↑ "Alternate Entry Points (ENTRY)". Using and Porting GNU Fortran. Free Software Foundation. 2001-06-07. Retrieved 2016-11-25.
- ↑ Thomas, R.E. (1976-04-29). "FORTRAN Compilers and Loaders". ACD: Engineering Paper No 42. ACD. Retrieved 2009-04-10.
- ↑ "A Brief Introduction to Fortran 90". Decremental/Deprecated/Redundant Features. Retrieved 2009-04-10.
बाहरी संबंध
- [1] Example of branch table in Wikibooks for अंतर्राष्ट्रीय व्यापार मशीन (आईबीएम) S/360
- [2] Examples of, and arguments for, Jump Tables via Function Pointer Arrays in C/C++
- [3] Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.
- [4] Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise.
- [5] "Arrays of Pointers to Functions" by Nigel Jones
