- Branch table
computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch instructions. The branch table construction is commonly used when programming in assembly languagebut may also be generated by a compiler.
A branch table consists of a serial list of
unconditional branchinstructions that is branched into using an offset created by multiplying a sequentialindex by the instruction length (the number of bytes in memory occupied by each branch instruction). It makes use of the fact that machine codeinstructions for branching have a fixed length and can be executed extremely efficiently by most hardware, and is most useful when dealing with raw datavalues that may be easily converted to sequentialindex values. Given such data, a branch table can be extremely efficient; it usually consists of the following steps: optionally validating the input data to ensure it is acceptable; transforming the data into an offset into the branch table, this usually involves multiplying or shiftingit to take into account the instruction length; and branching to an address made up of the base of the table and the generated offset: this often involves an additionof the offset onto the program counterregister.
Another method of implementing a branch table is with an
arrayof pointers from which the required function's address is retrieved. This method is also more recently known under such different names as " dispatch table" or " virtual method table" but essentially performing the exact 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 actual method used to implement a branch table is usually based on the architecture of the processor on which the code is to be run, whether it is a compiled or interpreted language and whether late bindingis involved or not.
Use of branch tables and other
raw dataencoding was common in the early days of computing when memory was expensive, CPUs were slower and compact data representation and efficient choice of alternatives were important. Nowadays, they are commonly used in embedded programming and operating systemdevelopment. In many operating systems, both system calls and library functions may be referenced by an integerindex into a branch table. This can improve compatibility with subsequent software versions: if the code of a function and the address of its entry pointis changed, only the branch instruction in the branch table needs to be adjusted, application software compiled against the library or for the operating system does not need modification. In addition, calling functions by number (the index into the table), can be useful for some cases when programming. In addition, some computer architectures use branch tables for dispatching interrupts .
Advantages of branch tables include: algorithmic and code efficiency (data need only be
encoded once and branch table code is usually compact), and the potential to attain high data compressionratios. For example, when compressing country names to country codes, a string such as "Central African Republic" can be compressed to a single index, resulting in large savings—particularly when the string appears many times. In addition, this same index can be used to access related data, reducing storage requirements further. Disadvantages include an extra level of indirectionand restrictions in some programming languages.
A simple example of branch table use in the 8-bit Microchip PIC assembly language is: movf INDEX,W ; move the index value into the W (working) register from the INDEX memory location addwf PCL,F ; add it onto the program counter register (PCL). 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 to a different section 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 was equal to zero return index_one ...
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 chopsearch, as a 'second best' option). If fact, the application may be highly "time critical" and memory requirement may not really be an issue at all.
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.
* Allow the compiler to 'choose' to generate a branch table on the remaining search keys (1-50).
Variations along similar lines can be used in cases where there are two sets of short ranges with a large gap between ranges.
Creating the index for the branch table
Where there is no obvious integer value available for a Branch table it can nevertheless be created from a search key (or part of a search key) by some form of arithmetic transformation or could simply be the row number of a database or the entry number in an array containing the search key found during earlier validation of the key. A
hash tablemay be required to form the index in some cases. However, for single byte input values such as A-Z (or the first byte of a longer key), the contents of the byte itself can be used in a two-step process to obtain a final index for a branch table with zero gaps.
* step 1. Convert the character to its decimal equivalent (example
ASCII'A' => 041)
* step 2. Use the derived decimal integer value as index on array to obtain 2nd index (invalid entries 0; representing gaps , otherwise 1,2, 3 etc)The array would be no larger than (256 x 2) bytes - to hold all possible 16-bit unsigned (short) integers. If no validation is required the array need actually be only (26 x 2) = 52 bytes.
An example of when this technique can be useful is looking up a country name. A single table containing a list of possible country names could be used for holding all of the approximately 190 entities. However, if the list is split alphabetically into separate tables using the countries first letter as an index to 26 pointers - to the start of each table - using the technique above, the list to search can be shrunk significantly (to around a maximum of 32 for countries beginning with 'S'). Placing the most frequently occuring countries near the top of each shorter list (sorted by frequency, not name) ,a simple linear search may produce a shorter
instruction path lengththan a binary searchin many cases, having already cut down the search size by a factor of 6 with no comparisons.
Dispatch tablea branch table by another name used for late binding
Function pointera term used to describe arrays of addresses to functions as used in branch tables
Lookup tablean array of items to be matched, sometimes holding pre-calculated results
Switch statementa high level language conditional statement that may generate a branch table
Virtual method tablea branch table by another name with dynamically assigned pointers for dispatching (see Dispatch table)
* [http://en.wikibooks.org/wiki/360_Assembly/Branch_Instructions] Example of branch table in
Wikibooksfor IBM S/360
* [http://www.netrino.com/node/137] Examples of, and arguments for, Jump Tables via Function Pointer Arrays in 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
arrayindexing if structure size is divisible by powers of 2 or otherwise.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Branch (disambiguation) — A branch is a part of a woody plant.Branch or branching may also refer to:Computing* Branch (computer science), a point in a computer program where program flow may change depending on a condition. **Branch predictor, the part of a processor that … Wikipedia
Branch (computer science) — For other uses, see Branch (disambiguation). A branch is sequence of code in a computer program which is conditionally executed depending on whether the flow of control is altered or not (at the branching point). The term can be used when… … Wikipedia
Branch Prediction — [dt. »Verzweigungsvorhersage«, »Sprungvorhersage«] die, eine von Intel erstmals im Pentium Prozessor eingesetzte Technik zur Erhöhung der Arbeitsgeschwindigkeit. Branch Prediction setzt auf der Prefetch Technik (Prefetch) auf, bei welcher der… … Universal-Lexikon
Branch predictor — In computer architecture, a branch predictor is the part of a processor that determines whether a conditional branch in the instruction flow of a program is likely to be taken or not. This is called branch prediction. Branch predictors are… … Wikipedia
Table Top Mountain (New York) — Infobox Mountain Name = Table Top Mountain (south peak) Photo = Caption = Elevation = convert|1345|m|ft|0|lk=on Prominence = convert|130|m|ft| 1|abbr=on [Key col elevation between 1,210 and 1,220 m.] Location = Essex County, New York Range =… … Wikipedia
Branch-Prediction — Die Sprungvorhersage (engl. branch prediction) wird in der (Mikro )Rechnerarchitekur verwendet und behandelt das Problem von Mikroprozessoren, alle Stufen ihrer Pipeline möglichst immer und sinnvoll auszulasten. Inhaltsverzeichnis 1 Übersicht 2… … Deutsch Wikipedia
Branch Prediction — Die Sprungvorhersage (engl. branch prediction) wird in der (Mikro )Rechnerarchitekur verwendet und behandelt das Problem von Mikroprozessoren, alle Stufen ihrer Pipeline möglichst immer und sinnvoll auszulasten. Inhaltsverzeichnis 1 Übersicht 2… … Deutsch Wikipedia
Branch prediction — Die Sprungvorhersage (engl. branch prediction) wird in der (Mikro )Rechnerarchitekur verwendet und behandelt das Problem von Mikroprozessoren, alle Stufen ihrer Pipeline möglichst immer und sinnvoll auszulasten. Inhaltsverzeichnis 1 Übersicht 2… … Deutsch Wikipedia
branch — An offshoot; in anatomy, one of the primary divisions of a nerve or blood vessel. A b.. See ramus, artery, nerve, vein. SYN: ramus (1) [TA]. accessory meningeal b. SYN: pterygomeningeal artery … Medical dictionary
Table Mountain (New York) — Infobox Mountain Name = Table Mountain Photo = Caption = Elevation = convert|3847|ft|m|0|lk=on Prominence = convert|660|ft|m| 1|abbr=on [Key col elevation between 3,180 and 3,200 ft. ] Location = Ulster County, New York Range = Catskill Mountains … Wikipedia