HOME BLOG ARCHIVE TAGS

Table Driven Code

June 23, 2013

Good code should be easy to understand, well structured to maintain, and fast to execute. Sometimes, we sacrifice readability, for the sake of speed. In real scenarios, fast often represents the opposite of understandable.

Table driven code is really interesting to use in practice. Most of the time, it’s understandable, maintainable, and fast. A rare set of attributes, we must emphasize.

Code is said to be table driven, when the programmer encodes program logic in a lookup table, instead of using programming language control flow statements (like logical tests and loops). Almost always, arrays are used as the underlying data-structure.

One classical example is presented in Code Complete, where character classification is implemented in a typical way (locales disregarded for simplification):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
if ( (( 'a' <= inputChar ) && ( inputChar <= 'z' )) ||
    (( 'A' <= inputChar ) && ( inputChar <= 'Z' )) ) {

    charType = CharacterType.Letter;
 }
 else if ( (inputChar == ' ' ) || ( inputChar == ',') ||
       (inputChar == '.' ) || ( inputChar == '!') || 
       (inputChar == '(' ) || ( inputChar == ')') ||
       (inputChar == ':' ) || ( inputChar == ';') ||
       (inputChar == '?' ) || ( inputChar == '-')
       ) {

    charType = CharacterType.Punctuation;
 }
 else if ( ( '0' <= inputChar ) && ( inputChar <= '9' ) ) {

    charType = CharacterType.Digit;
 }

The corresponding table driven alternative is much cleaner. Character code is used as an index into a (specially crafted) lookup table:

1
charType = charTypeTable[inputChar];

Astute readers may notice that McConnell compares the “ugliness” of the direct implementation with the “beauty” of the table driven call site (that’s always bothered me too). But the overall idea still holds true: table encoded logic/structure is less complex than long chains of comparisons (not to mention spaghetti code).

One of the challenges of table driven code is finding a good way to leverage data as lookup indicators. Integers fit the task naturally. Unfortunately, there are times we have to deal with constructs like strings and floats. In C/C++, with zero-based arrays , range normalization is not uncommon. Sometimes, unused/wasted table entries are needed as padding.

Table driven code is not always faster. Array sizes and random memory accesses may cause a program to experience undesirable delays, introduced by the fact that CPU caching is being defeated. When this is not the case, and/or we have to deal with complex computations, lookup table on the fly generation/updating is a good measure to increase performance.

Table driven code isn’t just good to simplify program logic. Actions can also be encoded this way, using dispatch tables. Higher level languages can offer more sophisticated action routing options. But usually, under the hood, dispatch tables are employed by compilers/interpreters when translating them to low-level representations (e.g., C++ virtual methods and vtables).