Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. The speed gain can be significant, since retrieving a value from memory is often faster than undergoing an expensive computation.

Related Topics:
Computer science - Data structure - Array - Associative array

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A classic example is a trigonometry table. Calculating the sine of a value every time such a sine is needed can be prohibitively slow in some applications. To avoid this, the application can take a few seconds when it first starts to precalculate the sine of a number of values, for example for each whole number of degrees. Later, when the program wants the sine of a value, it uses the lookup table to retrieve the sine of a nearby value from a memory address instead of calculating it using a mathematical formula.

Related Topics:
Trigonometry - Sine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Before the advent of computers, similar tables were used by people to speed up hand calculations. Particularly prevalent were tables of values for trigonometry, logarithms, and statistical density functions. Another device used to speed hand calculations was the slide rule.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There are intermediate solutions that use tables in combination with a small amount of computation, often using interpolation. This allows better accuracy for values falling between two precomputed values. This requires slightly more time but can greatly enhance accuracy in applications that require it. Depending on the values being precomputed, this technique can also be used to shrink the lookup table size while retaining about the same accuracy.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In image processing, lookup tables are often called LUTs, and they link index numbers to output values. One common LUT, called the colormap, is used to determine the colors and intensity values with which a particular image will be displayed.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It's important to note that, while often effective, lookup tables can result in a severe penalty if the computation it replaces is relatively simple, not only because retrieving the result from memory may require more time, but also because it may increase memory requirements and pollute the cache. If the table is large, each table access will almost certainly cause a cache miss. This is increasingly becoming an issue as processors outrace memory. A similar issue appears in rematerialization, a compiler optimization. In some environments, such as the Java programming language, table lookups can be even more expensive due to mandatory bounds checking involving an additional comparison and branch for each lookup.

Related Topics:
Cache - Cache miss - Rematerialization - Compiler optimization - Java programming language

~ ~ ~ ~ ~ ~ ~ ~ ~ ~