Branch table: Difference between revisions

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Revision as of 17:02, 29 October 2019 edit Abd.nh (talk \| contribs) 68 edits m Undid revision 923607763 by Abd.nh (talk) Tag: Undo ← Previous edit		Revision as of 11:47, 29 September 2022 edit undo Chatul (talk \| contribs) Extended confirmed users 7,257 edits →‎Alternative implementation using addresses: transfer vector Tag: Visual edit Next edit →
(10 intermediate revisions by 7 users not shown)
Line 1: {{short description\|Method of transferring program control to another part of a program}} {{original research\|date=November 2016}} In [[computer programming]], a '''branch table''' or '''jump table''' is a method of transferring program control ([[Branch (computer science)\|branching]]) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump [[Instruction (computer science)\|instruction]]s. It is a form of [[multiway branch]]. The branch table construction is commonly used when programming in [[assembly language]] but may also be generated by [[compiler]]s, especially when implementing optimized [[switch statement]]s whose values are densely packed together.<ref>{{cite book \|last1=Page \|first1=Daniel \|title=A Practical Introduction to Computer Architecture \|date=2009 \|publisher=Springer Science & Business Media \|isbn=9781848822559 \|page=479}}</ref> Line 21 ⟶ 22: ==Alternative implementation using addresses== Another method of implementing a branch table is with an [[Array data structure\|array]] of [[Pointer (computer programming)\|pointers]] from which the required [[Function (computing)\|function's]] address is retrieved. ~~This~~Originally known as '''transfer vector''', this method is also more recently known under such different names as "[[dispatch table]]" or "[[virtual method table]]" but essentially performing exactly the same purpose. This pointer function method can result in saving one machine instruction, and avoids the indirect jump (to one of the branch instructions). The resulting list of pointers to functions is almost identical to direct [[threaded code]], and is conceptually similar to a [[control table]]. Line 48 ⟶ 49: ==Disadvantages== * Extra level of [[indirection]], which incurs a usually small performance hit. * Restrictions in some programming languages, (although there are usually alternative ways of implementing the basic concept of multiway branching). ==Example== A simple example of branch table use in the 8-bit [[PIC microcontroller\|Microchip PIC]] assembly language is: <syntaxhighlight lang="nasm"> movf INDEX,W ; ~~move~~Move the index value into the W (working) register from memory addwf PCL,F ; add it to the program counter. ~~each~~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~~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~~Code is added here to perform whatever action is required when INDEX = zero return Line 96 ⟶ 97: /* Convert first argument to 0-3 integer (modulus) / value = ((atoi(argv[1]~~) % 4) + 4~~) % 4; / Call appropriate function (func0 thru func3) / Line 119 ⟶ 120: ==Compiler generated branch tables== Programmers frequently leave the decision of whether or not to create a branch table to the compiler, believing that it is perfectly capable of making the correct choice from the known search keys. This may be true for optimizing compilers for relatively simple cases where the range of search keys is limited. However, compilers are not as intelligent as humans and cannot have a deep knowledge of 'context', believing that a range of possible search key integer values such as 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 would generate a branch table with an excessively large number of empty entries (900+) for very little advantage. (A good optimizing compiler may then presort the values and generate code for a [[binary chop]] search, as a 'second best' option.) In fact, the application may be highly "time critical" and [[Computer data storage\|memory]] requirement may not really be an issue at all.<ref>{{cite web\|url=http://www.netrino.com/node/137\|title=How to Create Jump Tables via Function Pointer Arrays in C and C++\|first=Nigel\|last=Jones\|date=1 May 1999\|publisher=\|access-date=12 July 2008\|archive-url=https://web.archive.org/web/20120212110151/http://www.netrino.com/node/137\|archive-date=12 February 2012\|url-status=dead}}</ref> However, a little 'common sense' can transform this particular case, and many other similar cases, to a simple two-step process with very large potential savings~~ –~~, while still eventually leaving the ultimate choice to the compiler~~ –~~, but 'assisting its decision' considerably: First, test for search key=1000 and perform appropriate branch. Line 158 ⟶ 159: {{Commonscat}} [http://en.wikibooks.org/wiki/360_Assembly/Branch_Instructions] Example of branch table in [[Wikibooks]] for [[IBM S/360]] [https://web.archive.org/web/20120212110151/http://www.netrino.com/node/137] Examples of, and arguments for, Jump Tables via Function Pointer Arrays in [[C (programming language)\|C]]/[[C++]] [http://www.eventhelix.com/realtimemantra/Basics/CToAssemblyTranslation3.htm] Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE. [http://www.eventhelix.com/realtimemantra/Basics/CToAssemblyTranslation2.htm] Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise. Line 167 ⟶ 168: [[Category:Conditional constructs]] [[Category:Articles with example C code]] [[Category:Control flow]]