Lecture
Lookup table (LUT) (LUT) — is a data structure that stores the results of function interpolation. It is usually an array or an associative array used to replace computation with a simple lookup operation. The speed increase can be significant, since retrieving data from memory is often faster than performing time-consuming computations.
A classic example of using lookup tables is computing the values of trigonometric functions, for example, sine. Its direct computation can significantly slow down an application. To avoid this, on first launch the application precomputes a certain number of sine values in advance, for example, for all integer degrees. Later, when the program needs a sine value, it uses the lookup table to get an approximate value of sine from memory, instead of computing its value (for example, using series). Lookup tables are also used in math coprocessors; an error in the lookup table in Intel's Pentium processors led to the infamous bug that reduced the precision of the division operation.
Long before lookup tables appeared in programming, they were already used by people to facilitate manual calculations. Tables of logarithms, as well as trigonometric and statistical functions, were especially widespread.
There is an intermediate solution, where a lookup table is used together with simple computations — interpolation. This allows values between two precomputed points to be found more accurately. The time cost increases slightly, but greater computational accuracy is achieved in return. This technique can also be used to reduce the size of the lookup table without loss of accuracy.
Lookup tables are also widely used in computer image processing (in this field the corresponding tables are usually called «palettes»).
It is important to note that using lookup tables in tasks where they are ineffective leads to a decrease in performance. This happens not only because retrieving data from memory turns out to be slower than computing it, but also because the lookup table may occupy the entire memory and overflow the cache. If the table is large, each access to it is likely to result in a cache miss. In some programming languages (for example, Java), accessing a lookup table can be even more «expensive» due to mandatory bounds checking, which includes additional comparisons and branching for each lookup operation.
There are two fundamental limitations on creating lookup tables. The first is the total amount of available memory: the table must fit within the available volume, although it is possible to place a lookup table on disk as well, thereby increasing the time of the lookup operation. The other limitation is the time required to build the lookup table on first launch — although this operation is usually needed only once, it can take too much time, which makes the use of lookup tables an unsuitable solution.
Before the advent of computers, reference tables of values were used to speed up manual calculations of complex functions, such as trigonometry, logarithms, and statistical density functions.
In ancient (499 AD) India, Aryabhata created one of the first sine tables, which he encoded in the Sanskrit alphabetic numeral system. In 493 AD, Victorius of Aquitaine wrote a multiplication table of 98 columns, which gave (in Roman numerals) the product of every number from 2 to 50 times, and the rows represented «a list of numbers starting at one thousand and decreasing by hundreds down to one». hundreds, then in decreasing order by tens down to ten, then decreasing by ones down to 1, and then by fractions down to 1/144" . Modern schoolchildren are often taught to memorize "multiplication tables" to avoid computing the most frequently used numbers (up to 9 x 9 or 12 x 12).
In the early history of computers, input-output operations were especially slow — even compared to the processor speeds of that time. It makes sense to reduce costly read operations through manual caching by creating either static lookup tables (built into the program) or dynamic prefetched arrays containing only the most frequently occurring data elements. Despite the introduction of system-wide caching, which now automates this process, application-level lookup tables can still improve performance for data elements that rarely change, if they change at all.
Lookup tables were one of the first features implemented in computer spreadsheets, with the original version of VisiCalc (1979) including the LOOKUP function among the original 20 functions. Subsequent spreadsheets followed, such as Microsoft Excel, supplemented with specialized VLOOKUPand HLOOKUPfunctions to simplify lookup in a vertical or horizontal table. In Microsoft Excel the XLOOKUP function has been rolled out since August 28, 2019.
LimitationsEdit
Although LUT performance is guaranteedO(1) 
for the lookup operation, no two entities or values can have the same keyk 
. When the size of the universe ∪
— from which the keys are drawn — is large, storing it in memory may be impractical or impossible. Consequently, in this case a hash table would be the preferable alternative. [
Most computers support only basic arithmetic operations and cannot compute the value of sine directly. Instead, to compute the value of sine with a high degree of accuracy, they use the CORDIC method or the Taylor series:
However, such a computation can take a long time, especially on a slow processor, and there are many applications, for example computer graphics, that need to compute the value of thousands of sines every second. A common solution is to precompute a table of sine values, and then finding the sine of a number reduces to selecting the argument in the table closest to that number (the corresponding function value will be close to the correct value, because sine is a continuous and bounded function). For example:
real array sine_table[-1000..1000]
for x from -1000 to 1000
sine_table[x] := sine(pi * x / 1000)
function lookup_sine(x)
return sine_table[round(1000 * x / pi)]
Linear interpolation of the sine function over a certain range.
The table requires a lot of memory — for example, if double-precision floating-point numbers are used, 16,000 bytes will be needed. A smaller number of points can be used, but then the accuracy will drop. A good practice in this case is linear approximation.
Here is an example of linear approximation:
function lookup_sine(x)
x1 := floor(x*1000/pi)
y1 := sine_table[x1]
y2 := sine_table[x1+1]
return y1 + (y2-y1)*(x/1000/pi-x1)
When using interpolation, it is often beneficial to use a non-uniform distribution of data points: in places where the function is closest to a straight line, take few points to compute the function, while if the curvature of the function is large — take more points from that range, so that the approximation more closely resembles the real curve (see also Interpolation).
Example of a sine table (in the C programming language):
// 8-bit sine table
Here the sine values from [-1;1] are mapped to the integer range from a minimum of 0 to a maximum of 255, with zero corresponding to 128. On the vast majority of CPUs, operations with integers happen significantly faster than with floating-point numbers.
For a trivial lookup hash function, the raw unsigned data value is used directly as an index into a one-dimensional table to retrieve the result. For small ranges this can be one of the fastest lookups, even exceeding the speed of a binary search with zero branches and constant-time execution
«Lookup tables (LUTs) are an excellent method for optimizing the estimation of functions that are expensive to compute and inexpensive to cache. ... For data queries that fall between table samples, an interpolation algorithm can generate reasonable approximations by averaging neighboring samples. ."
In data analysis applications, such as image processing, a lookup table (LUT) is used to convert input data into a more desirable output format. For example, a grayscale image of the planet Saturn would be converted into a color image to emphasize the differences in its rings.
A classic example of reducing computation at runtime using interpolation tables is obtaining the result of a trigonometric computation, such as the sine of a value. Computing trigonometric functions can significantly slow down the operation of a computing application. The same application can finish much earlier if it precomputes the sine of a series of values, for example, for every integer number of degrees (the table can be defined as static variables at compile time, which reduces repeated runtime costs). When the program needs the sine of a value, it can use the lookup table to retrieve the nearest sine value from a memory address, and can also perform interpolation up to the sine of the desired value instead of computing it using a mathematical formula. Thus, lookup tables are used by math coprocessors in computer systems. An error in the lookup table was the cause of the infamous Intel floating-point division bug.
Functions of a single variable (such as sine and cosine) can be implemented with a simple array. Functions involving two or more variables require multidimensional array indexing methods. Thus, in the latter case, a two-dimensional array power[x][y] can be used to replace the computation of the function x y for a limited range of values of x and y. Functions that have more than one result can be implemented using lookup tables that are arrays of structures.
As already mentioned, there are intermediate solutions that use tables in combination with a small amount of computation, often using interpolation. Precomputation combined with interpolation can provide higher accuracy for values falling between two precomputed values. This method takes slightly more time to execute, but can significantly increase accuracy in applications requiring higher precision. Depending on the precomputed values, precomputation with interpolation can also be used to reduce the size of the lookup table while preserving accuracy.
In image processing, lookup tables are often called LUT (or 3DLUT) and give an output value for each range of index values. One common LUT, called a color map or palette, is used to determine the colors and intensity values with which a particular image will be displayed. In computed tomography, «windowing» refers to a related concept for determining how to display the intensity of measured radiation.
Although using a lookup table is often efficient, it can nevertheless incur a serious penalty if the computation that the LUT replaces is relatively simple. Memory retrieval time and memory requirement complexity can increase the application's running time and the system's complexity compared to what would be needed for direct computation of the formula. The possibility of cache pollution can also become a problem. Accesses to large tables will almost certainly result in a cache miss. This phenomenon is becoming an increasingly serious problem as processors outpace memory. A similar problem arises with rematerialization, a compiler optimization. In some environments, such as the Java programming language, a table lookup can be even more costly due to mandatory bounds checking, which includes an additional comparison and branch for each lookup.
There are two fundamental limitations on when a lookup table can be created for a required operation. One is the amount of available memory: it is impossible to create a lookup table exceeding the space available for the table, although lookup tables can be created on disk at the expense of lookup time. The other is the time required to compute the table's values the first time; although this usually needs to be done only once, if it takes too much time, this can make the use of a lookup table an unsuitable solution. However, as noted earlier, in many cases tables can be defined statically.
Storage caches (including disk caches for files or processor caches for code or data) also work as a lookup table. The table is built using very fast memory instead of being stored in slower external memory, and maintains two pieces of data for a subrange of the bits making up the external memory (or disk) address (specifically, the least significant bits of any possible external address):
A single (fast) lookup is performed to read the tag in the lookup table at the index given by the least significant bits of the desired external memory address, and to determine whether the memory address hit the cache. When a hit is found, no access to external memory is required (except for write operations, when an asynchronous update of the cached value to slower memory may be required after some time, or if the cache position needs to be replaced to cache another address).
In digital logic, an interpolation table can be implemented using a multiplexer, whose select lines are controlled by the address signal and whose inputs are the values of the elements contained in the array. These values can either be hardwired, as in an ASIC whose purpose depends on the function, or provided by D-latches, which allow the values to be configured. (ROM, EPROM, EEPROM, or RAM.)
an n-bit LUT can encode any n-input logic function by storing the function's truth table in the LUT. This is an efficient way to encode Boolean logic functions, and LUTs with 4-6 bits per input are in fact a key component of modern field-programmable gate arrays (FPGAs), which provide reconfigurable hardware logic capabilities.
In data acquisition and control systems, lookup tables are typically used to perform the following operations:
In some systems, polynomials can also be defined instead of lookup tables for these computations.
Comments