When to Use a Lookup Table

Code often has "hot" spots that are reached repeatedly—and these places may have a branching condition. For example, in a spelling checker, each byte of the input might need to be checked to see if it is part of a word, whitespace, or punctuation.

Lookup tables can be used to reduce the amount of branching done in these places. Usually a lookup table has 256 bytes, one array element for each possible byte, and can store values like a boolean or another byte. In performance, lookup tables occupy space on the processor's level 1 cache. Sometimes, a delay can occur trying to copy the memory to the cache.

For this reason, lookup tables can actually slow down programs—the delay in copying memory is greater than the time saved in reducing branching. Lookup tables still have an advantage in some places:

Benchmarks tend to make lookup tables appear faster than they are, as the table remains in the processor's cache throughout the benchmark run. Still, if enough branches are saved, the lookup table will improve overall performance. My personal rule is that any time a table is accessed more than 20 times in a function, and the results of the table are hard to predict, it is worth using a lookup table.