Multiway branch

Multiway branch is the change to a program's control flow based upon a value matching a selected criteria. It is a form of conditional statement. A multiway branch is often the most efficient method of passing control to one of a set of program labels, especially if an index has been created beforehand from the raw data.

Examples

• Branch table
• Switch statement - see also alternatives below
• Multiple dispatch - where a subroutine is invoked and a return is made

Alternatives

A multiway branch can, frequently, be replaced with an efficient indexed table lookup (using the data value itself or a calculated derivative of the data value, as the index of an array)^[1]

"...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 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

Multiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if tests. Peter Naur recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have studied.

— Donald Knuth, Structured Programming with go to Statements

See also

• Conditional (programming)
• Lookup table

References

1. "Archived copy" (PDF). Archived from the original (PDF) on 2012-02-27. Retrieved 2009-11-18.{{cite web}}: CS1 maint: archived copy as title (link)

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