Multiway branch

Multiway branch

Multiway branch is a computer science term used to describe 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.)


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.
"Structured Programming with go to Statements" by Donald Knuth

See also


External links

Wikimedia Foundation. 2010.

Нужно решить контрольную?

Look at other dictionaries:

  • Control table — This simple control table directs program flow according to the value of the single input variable. Each table entry holds a possible input value to be tested for equality (implied) and a relevant subroutine to perform in the action column. The… …   Wikipedia

  • goto — This article is about the programming statement. For other uses, see Goto (disambiguation). goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one way transfer of… …   Wikipedia

  • множественное ветвление — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN multiway branch …   Справочник технического переводчика

  • List of terms relating to algorithms and data structures — The [ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Conditional (programming) — Conditional statement redirects here. For the general concept in logic, see Material conditional. In computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform …   Wikipedia

  • Control flow — Not to be confused with Flow control. In computer science, control flow (or alternatively, flow of control) refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”