Multiway branch

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.



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


See also[edit]


External links[edit]