ब्रांच टेबल

कंप्यूटर प्रोग्रामिंग में, ब्रांच टेबल या जंप टेबल प्रोग्राम कंट्रोल (ब्रांच (कंप्यूटर साइंस)) को प्रोग्राम के दूसरे भाग (या एक अलग प्रोग्राम जो गतिशील रूप से लोड हो सकता है) को ब्रांच या जंप इंस्ट्रक्शन की टेबल का उपयोग करके स्थानांतरित करने की एक विधि है। (कंप्यूटर विज्ञान। यह मल्टीवे शाखा का एक रूप है। सभा की भाषा में प्रोग्रामिंग करते समय ब्रांच टेबल कंस्ट्रक्शन का आमतौर पर इस्तेमाल किया जाता है, लेकिन संकलक्स द्वारा भी उत्पन्न किया जा सकता है, खासकर जब ऑप्टिमाइज्ड स्विच स्टेटमेंट्स को लागू किया जाता है, जिनके मान एक साथ घनी तरह से भरे होते हैं।

विशिष्ट कार्यान्वयन

एक शाखा तालिका में बिना शर्त शाखा निर्देशों की एक सीरियल सूची होती है, जो कई (गणित) द्वारा बनाए गए ऑफसेट (कंप्यूटर विज्ञान) का उपयोग करके निर्देश लंबाई (प्रत्येक शाखा निर्देश द्वारा कब्जा की गई मेमोरी में बाइट्स की संख्या) द्वारा अनुक्रमिक सूचकांक का उपयोग करती है। यह इस तथ्य पर निर्भर करता है कि ब्रांचिंग के लिए मशीन कोड निर्देश समुच्चयकंप्यूटर साइंस) की एक निश्चित लंबाई होती है और इसे अधिकांश हार्डवेयर द्वारा अत्यंत कुशलता से निष्पादित किया जा सकता है, और कच्चे डेटा मानों से निपटने के दौरान सबसे उपयोगी होता है जिन्हें आसानी से अनुक्रमिक सूचकांक मानों में परिवर्तित किया जा सकता है। इस तरह के डेटा को देखते हुए, एक ब्रांच टेबल बेहद कुशल हो सकती है। इसमें आमतौर पर निम्नलिखित 3 चरण होते हैं:

1. वैकल्पिक रूप से डेटा सत्यापन इनपुट डेटा को यह सुनिश्चित करने के लिए स्वीकार्य है (यह अगले चरण के भाग के रूप में लागत के बिना हो सकता है, यदि इनपुट एक बाइट है और 256 बाइट अनुवाद तालिका का उपयोग सीधे नीचे ऑफसेट प्राप्त करने के लिए किया जाता है)। साथ ही, यदि इनपुट के मूल्यों के बारे में कोई संदेह नहीं है, तो इस चरण को छोड़ा जा सकता है।
2. डेटा को ऑफसेट (कंप्यूटर साइंस) में ब्रांच टेबल में बदलें। इसमें आमतौर पर निर्देश लंबाई को ध्यान में रखने के लिए गुणा या बिट शिफ्ट # बिट शिफ्ट (प्रभावी रूप से 2 की शक्ति से गुणा करना) शामिल होता है। यदि एक स्थिर अनुवाद तालिका का उपयोग किया जाता है, तो यह गुणा मैन्युअल रूप से या संकलक द्वारा बिना किसी रन टाइम लागत के किया जा सकता है।
3. शाखा तालिका के आधार पते और अभी-अभी उत्पन्न ऑफसेट से बने पते पर ब्रांच करना। इसमें कभी-कभी कार्यक्रम गणक प्रोसेसर रजिस्टर पर ऑफ़सेट जोड़ना शामिल होता है (जब तक, कुछ निर्देश सेटों में, शाखा निर्देश एक अतिरिक्त इंडेक्स रजिस्टर की अनुमति देता है)। यह अंतिम पता आमतौर पर बिना शर्त शाखा निर्देशों के अनुक्रम में से एक को इंगित करता है, या उनके तुरंत बाद के निर्देश (तालिका में एक प्रविष्टि को सहेजते हुए)।

निम्नलिखित स्यूडोकोड अवधारणा को दर्शाता है <वाक्यविन्यास प्रकाश लैंग = सी>

... वैलिडेट x /* मान के अनुसार x को 0 (अमान्य) या 1,2,3 में बदलें..) */
      वाई = एक्स * 4; /* ब्रांच इंस्ट्रक्शन लेंथ से गुणा करें (उदाहरण के लिए 4 ) */
      गोटो नेक्स्ट + वाई; / * शाखा निर्देशों की 'तालिका' में शाखा * /
/ * शाखा तालिका की शुरुआत * /
अगला: गोटो कोडबैड; /* x= 0 (अवैध) */
      गोटो कोडोन; /* एक्स= 1 */
      गोटो कोडटू; /* एक्स= 2 */
... बाकी ब्रांच टेबल
कोडबैड: / * अमान्य इनपुट से निपटें * /

</वाक्यविन्यास हाइलाइट>

पतों का उपयोग करके वैकल्पिक कार्यान्वयन

शाखा तालिका को लागू करने का एक अन्य तरीका सूचक (कंप्यूटर प्रोग्रामिंग) की एक ऐरे डेटा संरचना के साथ है जिसमें से आवश्यक फ़ंक्शन (कंप्यूटिंग) | फ़ंक्शन का पता पुनर्प्राप्त किया जाता है। मूल रूप से ट्रांसफर वेक्टर के रूप में जाना जाता है, इस विधि को हाल ही में प्रेषण तालिका या आभासी विधि तालिका जैसे विभिन्न नामों से भी जाना जाता है, लेकिन अनिवार्य रूप से एक ही उद्देश्य का प्रदर्शन करता है। इस पॉइंटर फ़ंक्शन विधि के परिणामस्वरूप एक मशीन निर्देश सहेजा जा सकता है, और अप्रत्यक्ष छलांग (शाखा निर्देशों में से एक) से बचा जा सकता है।

कार्यों के लिए पॉइंटर्स की परिणामी सूची लगभग सीधे थ्रेडेड कोड के समान है, और वैचारिक रूप से एक नियंत्रण तालिका के समान है।

शाखा तालिका को लागू करने के लिए उपयोग की जाने वाली वास्तविक विधि आमतौर पर निम्न पर आधारित होती है:

• प्रोसेसर का आर्किटेक्चर जिस पर कोड निष्पादित किया जाना है,
• चाहे वह संकलित या व्याख्या की गई भाषा हो और
• देर से बाँधना शामिल है या नहीं।

इतिहास

कंप्यूटिंग के शुरुआती दिनों में शाखा तालिकाओं और अन्य कच्चे डेटा एन्कोडिंग का उपयोग आम था जब मेमोरी (कंप्यूटर) महंगा था, CPU धीमे थे और कॉम्पैक्ट डेटा प्रतिनिधित्व और विकल्पों की कुशल पसंद महत्वपूर्ण थी। आजकल, वे आमतौर पर अभी भी उपयोग किए जाते हैं:

• अंतः स्थापित प्रणाली प्रोग्रामिंग
• ऑपरेटिंग सिस्टम का विकास। कई ऑपरेटिंग सिस्टमों में, सिस्टम कॉल और लाइब्रेरी (कंप्यूटर विज्ञान) दोनों प्रकार्यों को एक पूर्णांक अनुक्रमणिका द्वारा एक शाखा तालिका में संदर्भित किया जा सकता है।
• कुछ कंप्यूटर आर्किटेक्चर जैसे IBM/360 बाधा डालना भेजने के लिए ब्रांच टेबल का उपयोग करते हैं

लाभ

शाखा तालिकाओं के लाभों में शामिल हैं:

• कॉम्पैक्ट कोड संरचना (बार-बार शाखा ऑपकोड के बावजूद)
• कम स्रोत विवरण (बनाम दोहराव If कथन)
• व्यक्तिगत रूप से रिटर्न कोड का परीक्षण करने की आवश्यकता कम हो गई है (यदि बाद के कार्यक्रम प्रवाह को निर्धारित करने के लिए कॉल साइट पर उपयोग किया जाता है)
• एल्गोरिथम दक्षता और कोड दक्षता (डेटा को केवल एक बार कोडित करने की आवश्यकता होती है और शाखा तालिका कोड आमतौर पर कॉम्पैक्ट होता है), और उच्च डेटा संपीड़न अनुपात प्राप्त करने की क्षमता। उदाहरण के लिए, देश के नामों को देश कोड में संपीड़ित करते समय, मध्य अफ़्रीकी गणराज्य जैसी स्ट्रिंग को एक इंडेक्स में संपीड़ित किया जा सकता है, जिसके परिणामस्वरूप बड़ी बचत होती है - विशेष रूप से जब स्ट्रिंग कई बार दिखाई देती है। इसके अलावा, इसी इंडेक्स का उपयोग संबंधित डेटा को अलग-अलग तालिकाओं में एक्सेस करने के लिए किया जा सकता है, जिससे भंडारण आवश्यकताओं को और कम किया जा सकता है।

लाइब्रेरी (कंप्यूटर विज्ञान) कार्यों के लिए, जहां उन्हें एक पूर्णांक द्वारा संदर्भित किया जा सकता है:

• बाद के सॉफ़्टवेयर संस्करणों के साथ संगतता में सुधार करें। यदि किसी फ़ंक्शन का कोड और उसके प्रवेश बिंदु का पता बदल दिया गया है, तो शाखा तालिका में केवल शाखा निर्देश को समायोजित करने की आवश्यकता है; लाइब्रेरी या ऑपरेटिंग सिस्टम के लिए संकलित एप्लिकेशन सॉफ़्टवेयर में संशोधन की आवश्यकता नहीं है।

इसके अलावा, सामान्य एप्लिकेशन प्रोग्रामिंग में कुछ मामलों में संख्या (तालिका में सूचकांक) द्वारा फ़ंक्शन को कॉल करना कभी-कभी उपयोगी हो सकता है।

नुकसान

• अतिरिक्त स्तर का संकेत, जो आमतौर पर छोटे प्रदर्शन को प्रभावित करता है।
• कुछ प्रोग्रामिंग भाषाओं में प्रतिबंध, हालांकि आमतौर पर मल्टीवे ब्रांचिंग की मूल अवधारणा को लागू करने के वैकल्पिक तरीके हैं।

उदाहरण

8-बिट तस्वीर माइक्रोकंट्रोलर असेंबली लैंग्वेज में ब्रांच टेबल के उपयोग का एक सरल उदाहरण है: <वाक्यविन्यास प्रकाश लैंग = nasm>

    मूव इंडेक्स, डब्ल्यू; मेमोरी से इंडेक्स वैल्यू को डब्ल्यू (वर्किंग) रजिस्टर में ले जाएं
    एडडब्ल्यूएफ पीसीएल, एफ; इसे प्रोग्राम काउंटर में जोड़ें। प्रत्येक PIC निर्देश एक बाइट है
                        ; इसलिए कोई गुणा करने की आवश्यकता नहीं है।
                        ; अधिकांश आर्किटेक्चर इंडेक्स को पहले किसी तरह से बदल देंगे
                        ; इसे प्रोग्राम काउंटर में जोड़ना।

मेज                   ; इस लेबल के साथ शाखा तालिका यहाँ शुरू होती है
    गोटो index_zero; इनमें से प्रत्येक गोटो निर्देश एक बिना शर्त शाखा है
    गोटो index_one; कोड का।
    गोटो index_two
    गोटो index_three

index_zero
    ; INDEX = शून्य होने पर जो भी कार्रवाई आवश्यक है, उसे करने के लिए यहां कोड जोड़ा गया है
    वापस करना

index_one
...

</वाक्यविन्यास हाइलाइट>

नोट: यह कोड तभी काम करेगा जब PCL <(टेबल + index_last)। इस स्थिति को सुनिश्चित करने के लिए हम एक संगठन निर्देश का उपयोग कर सकते हैं। और यदि GOTO (उदाहरण के लिए PIC18F) 2 बाइट्स है, तो यह तालिका प्रविष्टियों की संख्या को 128 से कम तक सीमित कर देता है।

== सी == में जंप टेबल उदाहरण एक और सरल उदाहरण, इस बार केवल ब्रांच टेबल के बजाय जंप टेबल का प्रदर्शन। यह वर्तमान में सक्रिय प्रक्रिया/फ़ंक्शन के बाहर प्रोग्राम ब्लॉक को कॉल करने की अनुमति देता है: <वाक्यविन्यास प्रकाश लैंग = सी>

1. शामिल <stdio.h>
2. शामिल <stdlib.h>

टाइपपीफ शून्य (* हैंडलर) (शून्य); / * हैंडलर फ़ंक्शन के लिए एक सूचक * /

/ * कार्य * / शून्य func3 (शून्य) {प्रिंटफ (3\n); } शून्य func2 (शून्य) {प्रिंटफ (2\n); } शून्य func1 (शून्य) {प्रिंटफ (1\n); } शून्य func0 (शून्य) {प्रिंटफ (0\n); }

हैंडलर जंप_टेबल [4] = {func0, func1, func2, func3};

इंट मेन (int argc, char **argv) {

   इंट वैल्यू;

   /* पहले तर्क को 0-3 पूर्णांक (मापांक) में बदलें */
   मान = अटोई (आर्गव [1])% 4;

   /* उपयुक्त फ़ंक्शन को कॉल करें (func0 func3 के माध्यम से) */
   जंप_टेबल [मान] ();

   वापसी 0;

} </वाक्यविन्यास हाइलाइट>

== पीएल/आई == में जंप टेबल उदाहरण PL/I लेबल वेरिएबल्स की एक सरणी के रूप में एक जंप टेबल लागू करता है। सबस्क्रिप्टेड स्टेटमेंट लेबल का उपयोग करके इन्हें असामान्य तरीके से आरंभ किया जा सकता है। पीएल/आई लेबल वेरिएबल्स केवल बयान का पता नहीं हैं, लेकिन आमतौर पर कोड ब्लॉक की स्थिति पर अतिरिक्त जानकारी होती है जिससे वे संबंधित होते हैं। असामान्य इनिशियलाइज़ेशन के बिना, इसे कॉल और एंट्री वेरिएबल्स की एक सरणी के साथ कोडित भी किया जा सकता है। <पूर्व>

   लैब (10) लेबल घोषित करें;
   एक्स फिक्स्ड बाइनरी घोषित करें;
   गोटो लैब (एक्स);
 प्रयोगशाला (1): /* पसंद 1 के लिए कोड */;
   ...
 प्रयोगशाला (2): /* पसंद 2 के लिए कोड */;
   ...

</पूर्व>

संकलक उत्पन्न शाखा तालिकाएँ

प्रोग्रामर अक्सर कंपाइलर के लिए ब्रांच टेबल बनाने या न बनाने का निर्णय छोड़ देते हैं, यह मानते हुए कि यह ज्ञात खोज कुंजियों से सही विकल्प बनाने में पूरी तरह से सक्षम है। यह अपेक्षाकृत सरल मामलों के लिए संकलक के अनुकूलन के लिए सही हो सकता है जहां खोज कुंजियों की सीमा सीमित है। हालाँकि, कंपाइलर मनुष्यों की तरह बुद्धिमान नहीं होते हैं और उन्हें 'संदर्भ' का गहरा ज्ञान नहीं हो सकता है, यह मानते हुए कि 1, 2, 4, 6, 7, 20, 23, 40, 42 जैसे संभावित खोज कुंजी पूर्णांक मानों की एक श्रृंखला है। 50 और 1000 बहुत कम लाभ के लिए अत्यधिक बड़ी संख्या में खाली प्रविष्टियों (900+) के साथ एक शाखा तालिका उत्पन्न करेंगे। एक अच्छा ऑप्टिमाइज़िंग कंपाइलर तब मूल्यों को निर्धारित कर सकता है और बाइनरी चॉप खोज के लिए 'दूसरे सर्वश्रेष्ठ' विकल्प के रूप में कोड उत्पन्न कर सकता है। वास्तव में, एप्लिकेशन अत्यधिक समय के लिए महत्वपूर्ण हो सकता है और कंप्यूटर डेटा भंडारण आवश्यकता वास्तव में कोई समस्या नहीं हो सकती है। हालांकि, थोड़ा सा 'सामान्य ज्ञान' इस विशेष मामले और इसी तरह के कई अन्य मामलों को बहुत बड़ी संभावित बचत के साथ एक सरल दो-चरणीय प्रक्रिया में बदल सकता है, जबकि अंततः संकलक को अंतिम विकल्प छोड़ देता है, लेकिन 'इसके निर्णय में सहायता' करता है। काफी:

• सबसे पहले, खोज कुंजी = 1000 का परीक्षण करें और उचित शाखा का प्रदर्शन करें।
• संकलक को शेष खोज कुंजियों (1-50) पर एक शाखा तालिका बनाने के लिए 'चुनने' की अनुमति दें।

समान रेखाओं के साथ विविधताओं का उपयोग उन मामलों में किया जा सकता है जहां श्रेणियों के बीच बड़े अंतराल के साथ छोटी श्रेणियों के दो सेट होते हैं।

संगणित GoTo

जबकि तकनीक को अब 'ब्रांच टेबल' के रूप में जाना जाता है, शुरुआती कंपाइलर उपयोगकर्ताओं ने कार्यान्वयन को 'कंप्यूटेड गोटो' कहा, जो कंपाइलरों की फोरट्रान श्रृंखला में पाए गए निर्देश का जिक्र करते हैं। निर्देश को अंततः फोरट्रान 90 (स्रोत स्तर पर SELECT & CASE स्टेटमेंट के पक्ष में) में बहिष्कृत कर दिया गया था।

ब्रांच टेबल के लिए इंडेक्स बनाना

जहां एक शाखा तालिका के लिए कोई स्पष्ट पूर्णांक मान उपलब्ध नहीं है, फिर भी इसे अंकगणितीय परिवर्तन के किसी रूप द्वारा खोज कुंजी (या खोज कुंजी का हिस्सा) से बनाया जा सकता है, या यह केवल डेटाबेस या प्रविष्टि संख्या की पंक्ति संख्या हो सकती है कुंजी के पूर्व सत्यापन के दौरान मिली खोज कुंजी वाली सरणी में।

कुछ मामलों में इंडेक्स बनाने के लिए हैश तालिका की आवश्यकता हो सकती है। हालांकि, एकल बाइट इनपुट मान जैसे ए-जेड (या लंबी कुंजी का पहला बाइट) के लिए, बाइट की सामग्री (कच्चा डेटा) का उपयोग दो-चरणीय, तुच्छ हैश फ़ंक्शन में किया जा सकता है, अंतिम सूचकांक प्राप्त करने की प्रक्रिया शून्य अंतराल वाली शाखा तालिका के लिए।

1. अपरिष्कृत डेटा वर्ण को उसके सांख्यिक समकक्ष में बदलें (उदाहरण ASCII 'A' ==> 65 दशमलव, 0x41 हेक्साडेसिमल)
2. दूसरी अनुक्रमणिका प्राप्त करने के लिए 256 बाइट सरणी में अंकीय पूर्णांक मान का उपयोग करें (अमान्य प्रविष्टियां 0; अंतराल का प्रतिनिधित्व करना, अन्यथा 1, 2, 3 आदि)

सभी संभव 16-बिट अहस्ताक्षरित (लघु) पूर्णांकों को रखने के लिए सरणी (256 x 2) बाइट्स से बड़ी नहीं होगी। यदि कोई सत्यापन आवश्यक नहीं है, और केवल ऊपरी मामले का उपयोग किया जाता है, तो सरणी का आकार (26 x 2) = 52 बाइट्स जितना छोटा हो सकता है।

तकनीक के अन्य उपयोग

हालांकि ब्रांच टेबल का उपयोग करके ब्रांचिंग की तकनीक का उपयोग अक्सर केवल प्रोग्राम फ्लो को बदलने के उद्देश्य से किया जाता है - एक प्रोग्राम लेबल पर कूदने के लिए जो एक बिना शर्त शाखा है - उसी तकनीक का उपयोग अन्य उद्देश्यों के लिए किया जा सकता है। उदाहरण के लिए, इसका उपयोग दोहराए गए निर्देशों के अनुक्रम में एक शुरुआती बिंदु का चयन करने के लिए किया जा सकता है जहां ड्रॉप थ्रू मानक और जानबूझकर है। इसका उपयोग उदाहरण के लिए लूप अनोलिंग में कंपाइलर्स या समय-समय पर संकलन कंपाइलर्स को अनुकूलित करके किया जा सकता है।

यह भी देखें

• डिस्पैच टेबल एक ब्रांच टेबल को दूसरे नाम से लेट बाइंडिंग के लिए इस्तेमाल किया जाता है
• शाखा तालिकाओं में उपयोग किए जाने वाले कार्यों के लिए पतों के फंक्शन पॉइंटर सरणियाँ
• अप्रत्यक्ष शाखा
• लुकअप तालिका मिलान किए जाने वाले आइटमों की एक सरणी, कभी-कभी पूर्व-परिकलित परिणाम रखती है
• स्विच स्टेटमेंट एक उच्च स्तरीय भाषा सशर्त बयान है जो एक शाखा तालिका उत्पन्न कर सकता है
• वर्चुअल मेथड टेबल एक ब्रांच टेबल को दूसरे नाम से डिस्पैच करने के लिए डायनामिक रूप से असाइन किए गए पॉइंटर्स के साथ (डिस्पैच टेबल देखें)

बाहरी संबंध

• [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