Branch Table¶

A constant-time multiway dispatch structure that maps a validated selector through a dense table of code addresses or branch instructions to one of several control-flow targets.

Version: v1 · 2026-08-30 · History
Domain-specific #: 1409
Origin domain: computer science
Subdomain: systems programming
Aliases: Jump table, Branch vector, Transfer vector

Core Idea¶

A Branch Table, commonly called a jump table, implements multiway control transfer by converting a selector into an index and using that index to obtain or reach a code target. Entries may be branch instructions placed at fixed spacing, absolute or relative code addresses, function pointers, or compiler-specific relocation records. After optional normalization and bounds checking, dispatch performs table lookup/address arithmetic followed by an indirect jump or call.^[1]

Compilers often generate branch tables for dense switch statements. If case values cover a compact integer range, direct indexing can select a target in essentially constant time, avoiding a linear chain or logarithmic comparison tree. Sparse keys can make a naive table wasteful because every missing value needs an entry or default mapping. The compiler therefore balances range density, table bytes, relocation cost, target architecture, branch prediction, position-independent code, and optimization goals.

The locked identity is: finite multiway control alternatives + selector normalized to bounded index + indexed table entry encoding a code destination + indirect control transfer -> selected execution path. A data lookup that returns a value but does not transfer control is not a branch table, even when generated from the same switch source.

Structural Signature¶

the selector — runtime value choosing among alternatives;
the case domain — finite recognized selector values and default/invalid behavior;
the normalization step — subtract minimum, remap symbols, hash, or otherwise create an index;
the bounds validation — proves the index lies within the allocated table;
the table base — address of the first entry;
the entry width — fixed-size branch instruction, pointer, or relative offset;
the indexed address calculation — base + index×entry_size or equivalent hardware addressing;
the target representation — code label/address, branch stub, or displacement;
the indirect jump or call — control transfer using the selected target;
the default target — route for invalid or unrepresented selectors;
the layout/relocation policy — absolute versus relative addresses and position-independent constraints;
the density decision — cost comparison among table, comparison tree, bit tests, or hybrid dispatch;
the security boundary — index validation and control-flow target integrity;
the continuation structure — targets may return, merge later, tail-call, or never rejoin.

Recognition requires the table to select a control-flow target. An array of constants indexed by the same selector is a lookup table but not a branch table.

What It Is Not¶

Not a source-level switch statement. A compiler may lower switch to a jump table, a decision tree, bit tests, or other code.
Not every lookup table. Data retrieval alone does not branch.
Not a chain of conditional branches. Both implement choice, but the dispatch topology and performance differ.
Not a hash table. Hashing may create the index for sparse keys, but the branch table is the final dispatch structure.
Not a virtual method table exactly. A vtable is an object-oriented late-binding structure whose entries are methods selected partly by dynamic type; it is a related dispatch-table variant.
Not direct threaded code. Threaded interpreters repeatedly dispatch through instruction tokens; one branch table can participate without defining the whole execution model.
Not safe without bounds proof. An unchecked selector can read an unintended target and redirect control.
Not automatically faster. Cache misses, indirect-branch prediction, mitigations, and code size can outweigh fewer comparisons.

Scope of Application¶

Branch tables occur in compiler lowering, assembly programming, interpreters, embedded firmware, operating-system syscall and interrupt dispatch, protocol parsers, finite-state machines, bytecode virtual machines, and performance-critical command handling. They are especially natural when selectors are small integers or can be cheaply normalized.

Two canonical implementations differ. An instruction table lays out equal-width unconditional branches and jumps into the chosen entry. An address table loads a pointer or relative displacement and performs one indirect transfer. Some architectures support PC-relative table branches or compact instructions designed for this purpose. Position-independent executables often prefer relative offsets to reduce relocations or writable absolute pointers.

Compilers use target-specific heuristics. GCC explicitly supports jump tables for switch lowering and exposes -fno-jump-tables for cases where tables are undesirable, including some position-independent code contexts.^[2] The source language therefore supplies semantics, while the backend selects the implementation.

Clarity¶

For cases {10,11,12,13}, normalization may compute i=x−10, verify 0≤i<4, then transfer through table[i]; an out-of-range selector goes to default. If the cases are {1,1000}, the same scheme would allocate about a thousand entries for two destinations. A comparison sequence or hybrid special-case-plus-small-table layout is usually smaller.

Entry interpretation matters. A table of addresses uses target=table[i]; a table of relative displacements uses target=base+table[i]; a table of fixed branch instructions computes the address of the selected instruction itself. These have different relocation, alignment, and security properties despite the same abstraction.

prime:branching_and_merging covers flow splitting into alternatives and possible later joining. It does not provide selector normalization, indexed memory layout, machine targets, or indirect transfer. The candidate survives as a low-level domain-specific implementation of multiway branching.

Manages Complexity¶

A chain of n tests embeds selection logic in n comparisons and branches. A branch table separates mapping from execution: data layout maps selectors to destinations, while one generic dispatch sequence performs the transfer. This makes adding a dense case an entry-level change and bounds dispatch work independently of the number of alternatives.

The compression has a dual cost. Runtime decisions shrink, but memory layout materializes the selector range. Dense domains favor time; sparse domains favor comparisons or compressed maps. The table also concentrates control-flow integrity in one critical validation and indirect branch, making both performance tuning and security review more localized.

Abstract Reasoning¶

If case keys form a contiguous range, direct indexing requires constant dispatch operations after one bounds check.
If the key span is far larger than the case count, table space grows with span rather than populated cases.
Subtracting the minimum key reduces table size without changing selection, provided underflow and bounds are handled safely.
Relative offsets can improve position independence and shrink entries when all targets lie within representable range.
Omitting validation is safe only when prior control flow proves the selector range; otherwise the table becomes a control-flow vulnerability.
Duplicate destinations can occupy multiple entries cheaply, making ranges of values converge on one handler.
Indirect-branch prediction can make a table slower than a well-predicted comparison for skewed selectors.
A compiler may split out rare distant keys and table-dispatch the dense remainder, combining methods.
A data table replacing a branch with computed values is an optimization of behavior but no longer a branch table.
Control-flow integrity can restrict selected addresses to the intended target set without changing the table's functional mapping.

Knowledge Transfer¶

Exact transfer holds across architectures and languages when selector, bounded index, table target, and control transfer remain literal. Instruction tables, address tables, computed gotos, and compiler-generated switch tables are implementation variants.

Database indexes and organizational routing tables share selector-to-destination mapping but do not instantiate this node unless the destination is executable control flow. The portable parents are Indexed Lookup and Branching.

Examples¶

dense switch: integer cases 0–15 dispatch through sixteen target entries;
computed goto interpreter: a bytecode opcode indexes an array of label addresses and jumps to its handler;
interrupt vector: interrupt number selects a handler address through a protected vector table;
system-call dispatch: validated syscall number indexes permitted kernel entry points;
hybrid sparse switch: one remote case is tested separately and the dense cluster uses a table;
non-example—constant lookup: indexing an array to return a color or number changes data, not program control.

Structural Tensions¶

dispatch speed vs. table size — constant-time selection can materialize many unused entries;
direct layout vs. relocation cost — absolute pointers are simple while relative offsets are more position-friendly;
single indirect branch vs. prediction quality — fewer instructions can create a harder prediction target;
omitted check vs. control-flow safety — proof-based elision saves work but errors are severe;
compiler autonomy vs. programmer knowledge — backend heuristics see target costs while programmers may know workload distributions.

Structural–Framed Character¶

Branch Table is structural. Machine instruction semantics, address arithmetic, memory bounds, and control transfer determine operation. Calling related tables dispatch vectors or jump tables is conventional but does not create the mechanism.

Structural Core vs. Domain Accent¶

The core is selector -> bounded index -> stored destination -> dispatch. The domain accent is executable code addresses, machine layout, indirect branches, compiler lowering, and control-flow security. Removing it yields a generic Lookup Table.

Branching and Merging — one control state fans out to multiple alternatives.
Indexing — a normalized selector provides direct table access.
Indirection — an entry determines the actual execution target.
Space–Time Tradeoff — table bytes replace comparison work.

The prospective DAG uses composition under prime:branching_and_merging.

Relationships to Other Abstractions¶

Current abstraction Branch Table Domain-specific

Parents (1) — more general patterns this builds on

Branch Table is part of Branching and Merging Prime

one control state fans out to multiple alternatives.

Hierarchy paths (2) — routes to 2 parentless roots

Branch Table → Branching and Merging → State and State Transition → Phase Space

Show alternative path (1)

Neighborhood in Abstraction Space¶

Branch Table sits in a sparse region of the domain-specific corpus (90^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Compiler Code Generation & Allocation (5 abstractions)

Nearest neighbors

Far Pointer — 0.79
Register allocation — 0.79
Flat memory model — 0.78
Blocking set — 0.78
Bounds checking — 0.78

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

source-level switch;
conditional branch chain;
ordinary lookup table;
hash table;
virtual method table without qualification;
direct threaded interpreter as a whole;
unchecked arbitrary indirect jump.

Notes¶

[n1] Intel Corporation, Intel 64 and IA-32 Architectures Software Developer's Manual, sections on indirect branches and addressing.

References¶

[1] GNU Compiler Collection, “Labels as Values,” example of a label-address jump table, https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html. registry ↩

[2] GNU Compiler Collection, “Code Generation Options,” -fno-jump-tables, https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html. registry ↩

[3] “Branch table,” Wikipedia, frozen evidence packet, https://en.wikipedia.org/wiki/Branch_table. registry