Lookup Table Precomputation

Lookup Table Precomputation

Lookup tables are so widely used in AI engines that they're usually abbreviated as LUTs. The aim is to precompute results and replace frequently called costly function evaluations with table lookup (i.e. array references). Note that this use of precalculation is only worthwhile if some calculations are repeated and computing the same result.

As an example, we can replace a call to “sqrtf” with a precalculated table of square roots. In the subsequent calculations where square root is needed, a call to the sqrtf function is replaced by a table lookup.

The precalculation uses two separate functions: one to perform the precalculation, and another to access the values by table lookup. The precalculate function must be called once via a global initialization routine for the class. Alternatively, every call to the square_root function could self-check a static Boolean flag indicating whether the values have been precalculated yet, and call the precalculate function if not, but this is needlessly slower for every access.

Even more efficient is to use “offline precomputation” before your program even runs. This is a more efficient method whereby the data is not precalculated during initialization of the program, but is done earlier in an “offline” mode (e.g. as part of your build process). For example, the precomputed results are either stored to a data file, or converted to a C++ source file that is linked.

Another good example of precalculation is the Boolean functions on characters (e.g. isupper). To improve performance, it is possible to implemented these functions as a precomputed array of 256 bool values, or 256 bytes with 0 if isupper is false, and 1 if isupper is true. Then isupper is evaluated by indexing the character into the precomputed table:

    #define isupper(ch) ( precomputed_array[ch] )

In fact, many C++ compilers implement isupper and other functions in <ctype.h> as a table lookup over the 256 characters (plus an extra one for EOF), with a precalculated single bit flag per function — that is, one bit indicating isupper, another bit for islower, etc.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++