Multiway branch is a computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 term used to describe the change to a program's control flow

Control flow

In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....

 based upon a value matching a selected criteria. It is a form of conditional statement

Conditional statement

In computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform different computations or actions depending on whether a programmer-specified boolean condition evaluates to true or false...

. A multiway branch is often the most efficient

Algorithmic efficiency

In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...

 method of passing control to one of a set of program labels, especially if an index

Index (information technology)

In computer science, an index can be:# an integer that identifies an array element# a data structure that enables sublinear-time lookup -Array element identifier:...

 has been created beforehand from the raw data

Raw data

'\putang inaIn computing, it may have the following attributes: possibly containing errors, not validated; in sfferent formats; uncoded or unformatted; and suspect, requiring confirmation or citation. For example, a data input sheet might contain dates as raw data in many forms: "31st January...

.

Examples

• Branch table
  Branch table
  In computer programming, a branch table is a term used to describe an efficient method of transferring program control to another part of a program using a table of branch instructions. It is a form of multiway branch...
  
  
• Switch statement
  Switch statement
  In computer programming, a switch, case, select or inspect statement is a type of selection control mechanism that exists in most imperative programming languages such as Pascal, Ada, C/C++, C#, Java, and so on. It is also included in several other types of languages...
  
    - see also alternatives below
• Multiple dispatch
  Multiple dispatch
  Multiple dispatch or multimethods or function overloading is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time type of more than one of its arguments...
  
   - where a subroutine is invoked and a return is made

Alternatives

A multiway branch can, frequently, be replaced with an efficient indexed table lookup

Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...

 (using the data value itself or a calculated derivative of the data value, as the index of an array)

"...the implementation of a switch statement has been equated with that of a multiway branch. However, for many uses of the switch statement in real code, it is possible to avoid branching altogether and replace the switch with one or more table look-ups. For example,the Has30Days example [presented earlier] can be implemented as the following:[C example]"

"A Superoptimizer Analysis of Multiway Branch Code Generation" by Roger Anthony Sayle
switch (x) { /* x is month no */
case 4: /* April */
case 6: /* June */
case 9: /* September */
case 11: /* November */
return true;
}
can be replaced, using a "safe-hashing" technique, with -
unsigned int t = x | 2;
switch (t) {
case 6:
case 11:
return true;
}
or it can be replaced, using an index mapping

Index mapping

Index mapping is a computer science term that is used to describe the mapping of raw data, used directly as in array index, for an array. The technique can be most effective for mapping data with a small range...

 table lookup, with -
x %= 12; /* to ensure x is in range 0-11*/
static const int T[12] ={0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0' */
return T[x]; /* return with boolean 1 = true, 0=false */
(in view of the simplicity of the latter case, it would be preferable to implement it in-line, since the overhead of using a function call may be greater than the indexed lookup itself.)

Quotations

External links

• Coding Multiway Branches Using Customized Hash functions by H. G. Dietz
• Learning Python By Mark Lutz
• Programming in C++ By Nell B. Dale, Chip Weems
• A Superoptimizer Analysis of Multiway Branch Code Generation by Roger Anthony Sayle