The Performance and Tuning Doctor by Sturnus

A look-up table is useful whenever a particular calculation or conversion is expensive in terms of resources (processing time, memory etc.), but the input data set is relatively small.

Division

An example of where we might use a look-up table is when performing divide operations. Division is a notoriously time consuming operation; on one particular processor, for example, an integer divide takes up to 17 clock cycles, compared to a multiplication which takes only 3.

Let's look at a trivial example of where we might use a look-up table. Suppose we have a function that takes an integer between 0 and 10 inclusive, and divides it by 3. The result of this calculation for each of the possible input values is as follows:

Since there are only 11 possible input values, this is an ideal candidate for a look-up table. Indeed, the very fact that I have shown the results in a table suggests that this may be an obvious route to take! To demonstrate the performance advantage of using a table, I have created a simple test program, written in C:

/**
 * A simple test program to show the difference in performance between
 * a integer division and a look-up table.
 *
 */


///// Includes /////

#include <stdio.h>
#include <sys/time.h>


///// Definitions /////

#define ITERATIONS 1000000000


///// Look-up table /////

const unsigned int div3Table[ 11 ] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3 };


///// Prototypes /////

int  main          ( int, char *[] );
void display_speed ( struct timeval *, struct timeval *, unsigned int );


///// main /////

int main( int argc, char *argv[] )
  {
  unsigned int counter, dividend, result;
  struct timeval startTimeVal, endTimeVal;


  printf( "%s started\n", argv[0] );


  ///// Run the division test /////

  gettimeofday( &startTimeVal, NULL );

  for ( counter = 0, dividend = 0, result = 0; counter < ITERATIONS; counter ++ )
    {
    // The expensive divide operation
    result += dividend / 3;

    if ( ( ++ dividend ) > 10 ) dividend = 0;
    }

  gettimeofday( &endTimeVal, NULL );

  printf( "Integer divide test completed, result = %u\n", result );

  display_speed( &startTimeVal, &endTimeVal, ITERATIONS );


  ///// Run the look-up table test /////

  gettimeofday( &startTimeVal, NULL );

  for ( counter = 0, dividend = 0, result = 0; counter < ITERATIONS; counter ++ )
    {
    // The less expensive look-up operation
    result += div3Table[ dividend ];

    if ( ( ++ dividend ) > 10 ) dividend = 0;
    }

  gettimeofday( &endTimeVal, NULL );

  printf( "Look-up table test completed, result = %u\n", result );

  display_speed( &startTimeVal, &endTimeVal, ITERATIONS );


  printf( "%s completed\n", argv[0] );

  return ( 0 );
  }


///// display_speed /////

void display_speed( struct timeval *pStartTimeVal,
                    struct timeval *pEndTimeVal,
                    unsigned int    iterations )
  {
  // NB: Won't work across midnight!
  suseconds_t microsecondInterval = ( (suseconds_t)( pEndTimeVal->tv_sec -
                                                     pStartTimeVal->tv_sec ) * 1000000 ) +
                                                   ( pEndTimeVal->tv_usec -
                                                     pStartTimeVal->tv_usec );

  unsigned int speed = iterations / (unsigned int)microsecondInterval;

  printf( "Time = %li us, speed = %u iterations/us\n", (long)microsecondInterval, speed );
  }

The result of compiling and running this program on my laptop is as follows:

$ gcc -O -o lookup lookup.c 
$ time ./lookup 
./lookup started
Integer divide test completed, result = 1363636362
Time = 4808449 us, speed = 207 iterations/us
Look-up table test completed, result = 1363636362
Time = 2877962 us, speed = 347 iterations/us
./lookup completed

real    0m7.689s
user    0m7.089s
sys     0m0.004s

Obviously the result of this test is not particularly earth-shattering, but it does demonstrate the performance advantage of a look-up table, even for relatively inexpensive operations. Naturally, the more expensive the operation that we are performing, the greater the performance improvement. Some more advanced uses of lookup tables might be as follows:

• Performing operations on images (such as increasing the brightness), whilst preventing the RGB values from extending beyond the valid range 0 -> 255.
• Converting strings directly into numeric representations: I used a look-up table to convert a longitude / latitude ASCII string into an integer representation of it.

In terms of the input data, it must either be, or easily converted to, integer values: 0, 1, 2, etc. We cannot perform a table lookup on a fractional value - there is no entry 3.5, for example. It is preferable, though not strictly necessary, for the values to start at 0, and increase to the size of the table. If this is not the case, then the input data must be converted into a suitable table index:

• If the input values can be negative, then they must have an offset added to them to turn them into a table index. If the values range from -15 -> +15, for example, then they must have 15 added to them first: -15 -> 0, -14 -> 1, etc.
• If the input values start at a value greater than 0, then they can either be adjusted down (by subtracting the minimum value), or you may choose to simply leave the unused table entries empty, so as to avoid the extra subtraction operation.

The performance advantage doesn't come for free, of course: the price we pay is the memory that the look-up table consumes. Whether the loss of memory is significant is down to our the size of our table compared to the amount of memory available on our system, and the cost of performing memory look-ups. We can only know this for certain by testing, but obviously an 11-entry table is unlikely to cause memory problems on a desktop or server machine, whereas a 10,000-entry table might well be an issue on an embedded system.

In general, therefore, it is worth using a look-up table when:

• The input data is limited to a manageable range of discrete values.
• The original calculations are more expensive (in terms of resources) than performing table look-ups.
• There are no memory constraints: the loss of memory as a result of the table does not outweigh the advantage of using table look-ups.

Dynamic Look-up Tables

At the beginning of this post, I stated that look-up tables provide the results of calculations "in advance of when they are needed". What we have not talked about yet, however, is when those calculations are performed. In many cases this will be obvious - if a set of look-ups never changes (or doesn't change for the life of a program), then the look-up table may be created when the code is written or auto-generated when it is compiled.

In some cases, however, the values in the table may change during the execution of an application. Suppose that from time-to-time the divisor in my simple test program were to change from 3 to another value, such as 2? When this happens, we can dynamically change the values on the fly - in the application itself. In this scenario, the considerations listed previously will still apply, but we now have an additional constraint that will determine if we want to consider a look-up table:

• The performance improvement from using the table is greater than the cost of populating it.

Dynamic look-up tables might be suitable when one or more input variables change infrequently, such as :

• Encryption / decryption algorithms: these are expensive operations, but the key changes relatively infrequently. Some of the stages in these processes can benefit from using look-up tables, and these can be populated whenever the key is set.
• Quantisation: this is a common stage in many image compression algorithms, but the quantisation values usually depend on the desired quality of the image, which is generally set once.

So if you have a small(ish) set of input values, and an expensive calculation to perform, look-up tables might be the answer.

Back to top