In computer science, a lookup table (LUT) is an array that replaces runtime computation of a mathematical function with a simpler array indexing operation, in a process termed as direct addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated (or "pre-fetched") as part of a program's initialization phase (memoization), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid (or invalid) items in an array and, in some programming languages, may include pointer functions (or offsets to labels) to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality. LUTs differ from hash tables in that, to retrieve a value v {\displaystyle v} with key k {\displaystyle k} , a hash table would store the value v {\displaystyle v} in the slot h ( k ) {\displaystyle h(k)} where h {\displaystyle h} is a hash function i.e. k {\displaystyle k} is used to compute the slot, while in the case of LUT, the value v {\displaystyle v} is stored in slot k {\displaystyle k} , thus directly addressable.
History
Before the advent of computers, lookup tables of values were used to speed up hand calculations of complex functions, such as in trigonometry, logarithms, and statistical density functions. In ancient (499 AD) India, Aryabhata created one of the first sine tables, which he encoded in a Sanskrit-letter-based number system. In 493 AD, Victorius of Aquitaine wrote a 98-column multiplication table which gave (in Roman numerals) the product of every number from 2 to 50 times and the rows were "a list of numbers starting with one thousand, descending by hundreds to one hundred, then descending by tens to ten, then by ones to one, and then the fractions down to 1/144" Modern school children are often taught to memorize "times tables" to avoid calculations of the most commonly used numbers (up to 9 × 9 or 12 × 12). Early in the history of computers, input/output operations were particularly slow – even in comparison to processor speeds of the time. It made sense to reduce expensive read operations by a form of manual caching by creating either static lookup tables (embedded in the program) or dynamic prefetched arrays to contain only the most commonly occurring data items. Despite the introduction of systemwide caching that now automates this process, application level lookup tables can still improve performance for data items that rarely, if ever, change. Lookup tables were one of the earliest functionalities implemented in computer spreadsheets, with the initial version of VisiCalc (1979) including a LOOKUP function among its original 20 functions. Microsoft Excel includes multiple specialized lookup functions, with VLOOKUP for vertical lookup (as in a traditional lookup book), HLOOKUP for horizontal lookup, and (since 2019) XLOOKUP for outputting multiple output columns at once.
Limitations Although the performance of an LUT is a guaranteed O ( 1 ) {\displaystyle O(1)} for a lookup operation, no two entities or values can have the same key k {\displaystyle k} . When the size of universe U {\displaystyle U} —where the keys are drawn—is large, it might be impractical or impossible to be stored in memory. There are several ways to work around this, including using a hash table if many keys share a value, or if the keys represent a numeric value with some precision, lowering that precision may shrink the universe enough, and then interpolation can be used to correct for the error due to precision loss.
Examples
Trivial hash function For a trivial hash function lookup, the unsigned raw data value is used directly as an index to a one-dimensional table to extract a result. For small ranges, this can be amongst the fastest lookup, even exceeding binary search speed with zero branches and executing in constant time.
Counting bits in a series of bytes One discrete problem that is expensive to solve on many computers is that of counting the number of bits that are set to 1 in a (binary) number, sometimes called the population function. For example, the decimal number "37" is "00100101" in binary, so it contains three bits that are set to binary "1". A simple example of C code, designed to count the 1 bits in a int, might look like this:
The above implementation requires 32 operations for an evaluation of a 32-bit value, which can potentially take several clock cycles due to branching. It can be "unrolled" into a lookup table which in turn uses trivial hash function for better performance. The bits array, bits_set with 256 entries is constructed by giving the number of one bits set in each possible byte value (e.g. 0x00 = 0, 0x01 = 1, 0x02 = 1, and so on). Although a runtime algorithm can be used to generate the bits_set array, it's an inefficient usage of clock cycles when the size is taken into consideration, hence a precomputed table is used—although a compile time script could be used to dynamically generate and append the table to the source file. Sum of ones in each byte of the integer can be calculated through trivial hash function lookup on each byte; thus, effectively avoiding branches resulting in considerable improvement in performance.
Lookup tables in image processing
… excerpt ends here. Continue reading the full article.
