Software Optimization Techniques #8: Look-up Tables

Continuing our series of blog posts on optimizing embedded software with the aim of improving (i.e. reducing) worst-case execution times, this week’s subject is look-up tables.

Software optimization techniques which improve worst-case execution times #8: Look-up Tables

Using look-up tables can be a highly effective method of improving worst-case execution times.

Look-up tables are useful in implementing pure functions (by which we mean a function without any side effects) of one or two variables that take a relatively limited range of values and are mapped via some non-trivial code to a value possibly of a different type.

Examples include approximations to trigonometric functions such as sin() and cos().

Example: Switch

Uint32 
switch_code1(Uint32 mode)
{
Uint32 message_id;
switch(mode)
{
case 0:
message_id = 0x55;
break;
case 1:
message_id = 0x66;
break;
case 2:
message_id = 0x77;
break;
}
return message_id;
}

Sometimes switch statements are used to map solely from one variable to another. In this case a more efficient implementation would be to use a look-up table as shown in the example below.

Example: Look-up table rather than switch

const Uint32 g_id_table[3] = 	{0x55,0x66,0x77};
Uint32
lookup_code2(Uint32 mode)
{
return g_id_table[mode];
}

The look-up table implementation has a worst-case execution time that is both shorter and constant. It also requires less code space. The effectiveness of this technique becomes more pronounced with an increasing number of elements required in the mapping.

Look-up table techniques can also be applied very effectively to the “count set bits” example used previously.

Example: Look-up table

const Uint8 bits_table[] =
{0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
Uint32
csb5(Uint32 x)
{
Uint32 set_bits = 0;
while(x)
{
set_bits += bits_table[x & 0xF];
x >>= 4;
}
return set_bits;
}

In the example above, a small look-up table is used to hold pre-computed values for the number of set bits in all the 4-bit values from 0 to 15. On each iteration of the loop, the bottom 4-bits of x are used to index the look-up table and hence count how many of those bits are set. x is then shifted right by 4-bits so that the next 4 least significant bits can be examined, and so on.

Next week: Single path code