ब्रांच टेबल
कंप्यूटर प्रोग्रामिंग में, ब्रांच टेबल या जंप टेबल प्रोग्राम कंट्रोल (ब्रांच (कंप्यूटर विज्ञान)) को प्रोग्राम के दूसरे भाग (या एक अलग प्रोग्राम जो गतिशील रूप से लोड हो सकता है) को ब्रांच या जंप इंस्ट्रक्शन की टेबल का उपयोग करके स्थानांतरित करने की एक विधि है। (कंप्यूटर विज्ञान। यह मल्टीवे ब्रांच का एक रूप है। सभा की भाषा में प्रोग्रामिंग करते समय ब्रांच टेबल कंस्ट्रक्शन का सामान्य रूप से उपयोग किया जाता है, लेकिन संकलक द्वारा भी उत्पन्न किया जा सकता है, विशेष रूप से जब ऑप्टिमाइज्ड स्विच स्टेटमेंट्स को लागू किया जाता है, जिनके मान एक साथ घनी तरह से भरे होते हैं।[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 codetwo; /* x= 2 */
... rest of branch table
codebad: /* deal with invalid input */
पतों का उपयोग करके वैकल्पिक कार्यान्वयन
ब्रांच तालिका को लागू करने का एक अन्य तरीका सूचक (कंप्यूटर प्रोग्रामिंग) की एक ऐरे डेटा संरचना के साथ है जिसमें से आवश्यक फ़ंक्शन (कंप्यूटिंग) फ़ंक्शन का पता पुनर्प्राप्त किया जाता है। मूल रूप से ट्रांसफर वेक्टर के रूप में जाना जाता है, इस विधि को हाल ही में प्रेषण तालिका या आभासी विधि तालिका जैसे विभिन्न नामों से भी जाना जाता है, लेकिन अनिवार्य रूप से एक ही उद्देश्य का प्रदर्शन करता है। इस पॉइंटर फ़ंक्शन विधि के परिणामस्वरूप एक मशीन निर्देश सहेजा जा सकता है, और अप्रत्यक्ष जम्प (ब्रांच निर्देशों में से एक) से बचा जा सकता है।
कार्यों के लिए पॉइंटर्स की परिणामी सूची लगभग प्रत्यक्ष रूप से थ्रेडेड कोड के समान है, और वैचारिक रूप से एक नियंत्रण तालिका के समान है।
ब्रांच तालिका को लागू करने के लिए उपयोग की जाने वाली वास्तविक विधि सामान्य रूप से निम्न पर आधारित होती है:
- प्रोसेसर का संरचना जिस पर कोड निष्पादित किया जाना है,
- चाहे वह संकलित या व्याख्या की गई भाषा हो और
- देर से बाँधना सम्मिलित है या नहीं।
इतिहास
कंप्यूटिंग के प्रारम्भिक दिनों में ब्रांच तालिकाओं और अन्य कच्चे डेटा एन्कोडिंग का उपयोग सामान्य था जब मेमोरी (कंप्यूटर) महंगा था, सेन्ट्रल प्रोसेसिंग यूनिट मंद थे और कॉम्पैक्ट डेटा प्रतिनिधित्व और विकल्पों की कुशल चयन महत्वपूर्ण थी। आजकल, वे सामान्य रूप से अभी भी उपयोग किए जाते हैं:
- अंतः स्थापित प्रणाली प्रोग्रामिंग
- ऑपरेटिंग सिस्टम का विकास। कई ऑपरेटिंग सिस्टमों में, सिस्टम कॉल और लाइब्रेरी (कंप्यूटर विज्ञान) दोनों प्रकार्यों को एक पूर्णांक अनुक्रमणिका द्वारा एक ब्रांच तालिका में संदर्भित किया जा सकता है।
- कुछ कंप्यूटर संरचना जैसे IBM/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 ; each of these goto instructions is an unconditional branch
goto index_one ; of code.
goto index_two
goto index_three
index_zero
; Code is added here to perform whatever action is required when INDEX = zero
return
index_one
...
नोट: यह कोड तभी काम करेगा जब PCL <(टेबल + index_last)। इस स्थिति को सुनिश्चित करने के लिए हम एक संगठन निर्देश का उपयोग कर सकते हैं। और यदि GOTO (उदाहरण के लिए PIC18F) 2 बाइट्स है, तो यह तालिका प्रविष्टियों की संख्या को 128 से कम तक सीमित कर देता है।
== सी == में जंप टेबल उदाहरण
एक और सरल उदाहरण, इस बार केवल ब्रांच टेबल के अतिरिक्त जंप टेबल का प्रदर्शन। यह वर्तमान में सक्रिय प्रक्रिया/फ़ंक्शन के बाहर प्रोग्राम ब्लॉक को कॉल करने की स्वीकृत देता है:
#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;
}
== पीएल/आई == में जंप टेबल उदाहरण
PL/I लेबल वेरिएबल्स की एक सरणी के रूप में एक जंप टेबल लागू करता है। सबस्क्रिप्टेड स्टेटमेंट लेबल का उपयोग करके इन्हें असामान्य तरीके से आरंभ किया जा सकता है। पीएल/आई लेबल वेरिएबल्स केवल बयान का पता नहीं हैं, लेकिन सामान्य रूप से कोड ब्लॉक की स्थिति पर अतिरिक्त जानकारी होती है जिससे वे संबंधित होते हैं। असामान्य इनिशियलाइज़ेशन के बिना, इसे कॉल और एंट्री वेरिएबल्स की एक सरणी के साथ कोडित भी किया जा सकता है।
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) पर एक ब्रांच तालिका बनाने के लिए 'चुनने' की स्वीकृत दें।
समान रेखाओं के साथ विविधताओं का उपयोग उन मामलों में किया जा सकता है जहां श्रेणियों के बीच बड़े अंतराल के साथ छोटी श्रेणियों के दो सेट होते हैं।
संगणित GoTo
जबकि तकनीक को अब 'ब्रांच टेबल' के रूप में जाना जाता है, प्रारम्भिक कंपाइलर उपयोगकर्ताओं ने कार्यान्वयन को 'कंप्यूटेड गोटो' कहा, जो कंपाइलरों की फोरट्रान श्रृंखला में पाए गए निर्देश का जिक्र करते हैं।[3][4] निर्देश को अंततः फोरट्रान 90 (स्रोत स्तर पर SELECT & CASE स्टेटमेंट के पक्ष में) में बहिष्कृत कर दिया गया था।[5]
ब्रांच टेबल के लिए इंडेक्स बनाना
जहां एक ब्रांच तालिका के लिए कोई स्पष्ट पूर्णांक मान उपलब्ध नहीं है, फिर भी इसे अंकगणितीय परिवर्तन के किसी रूप द्वारा खोज कुंजी (या खोज कुंजी का हिस्सा) से बनाया जा सकता है, या यह केवल डेटाबेस या प्रविष्टि संख्या की पंक्ति संख्या हो सकती है कुंजी के पूर्व सत्यापन के समय मिली खोज कुंजी वाली सरणी में।
कुछ मामलों में इंडेक्स बनाने के लिए हैश तालिका की आवश्यकता हो सकती है। हालांकि, एकल बाइट इनपुट मान जैसे ए-जेड (या लंबी कुंजी का पहला बाइट) के लिए, बाइट की सामग्री (कच्चा डेटा) का उपयोग दो-चरणीय, तुच्छ हैश फ़ंक्शन में किया जा सकता है, अंतिम सूचकांक प्राप्त करने की प्रक्रिया शून्य अंतराल वाली ब्रांच तालिका के लिए।
- अपरिष्कृत डेटा वर्ण को उसके सांख्यिक समकक्ष में बदलें (उदाहरण 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 IBM 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
