Multiway branch explained

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) can be replaced, using a "safe-hashing" technique, with - unsigned int t = x | 2; switch (t) 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-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

• Conditional (programming)
• Lookup table

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

Notes and References

1. Web site: Archived copy . 2009-11-18 . https://web.archive.org/web/20120227064827/http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf . 2012-02-27 . dead .