Selectors

This section focuses on selector statements. As there are a variety of different C/C++ statements to enable a program to choose between a set of execution paths, you might wonder what the actual differences between the selector statements are. Certainly almost any selection implementation can be rewritten to use a different statement—replacing a switch with an if..else construction, for instance. However, each statement does have its own specific strengths and weaknesses. When these statement characteristics are understood, it becomes possible to intuitively choose an efficient implementation solution.

This section presents the characteristics of the different selector statements, after which a performance comparison between the different statements is made.

if..else Statement

• if as an expression evaluator

The if check can be used to check several expressions at once. The expressions can be concatenated with logical operators—and (&&), or (||), not (!), and so on. Here is an example of concatenated expressions within an if statement:

if ((lights_out == TRUE) && (response_to_doorbell != TRUE))
  nobody_is_home = TRUE;

There are two very important things to remember with concatenated expressions:

• The expressions are evaluated from left to right.

• No further expressions are evaluated when the result has been determined.

The reason why this is important to realize is that you can take advantage of the time that is won when certain expressions are not evaluated. For instance, when expressions are concatenated with a logical 'and', expression evaluation will stop with the first expression that is false. Remember, for an 'and'to be true, all expressions concatenated into that 'and'have to be true. So, in the preceding example, the expression (response_to_doorbell != TRUE) is never evaluated when lights_out equals FALSE. Similarly, the evaluation of expressions that are concatenated with a logical 'or'will stop after the first expression that is found to be true. Remember, for an 'or'to be true, at least one expression needs to be true. It makes sense, therefore, to order concatenated expressions according to their evaluation speed, with the fastest expression to evaluate being the leftmost (or the one most likely to be false as the leftmost). The following example demonstrates this for a simple if with 'and'-ed expressions:

char a[]="this is a long string of which we want to know the length";
int b    = 0;

// inefficient and.
if ( (strlen(a) > 100) && (b > 100) )
{
    d++;
}

// efficient and.
if ( (b > 100) && (strlen(a) > 100) )
{
    d++;
}

Calculating the length of a string takes time because a function needs to be called and an index and a pointer need to be instantiated, after which a loop will determine the end of the string. Comparing the value of an integer variable with a constant takes considerably less time. This is why the second if in the preceeding example is easily 200 times faster than the first when the expression (b > 100) is not true.

The following example demonstrates the same theory for a simple if with 'or'-ed expressions:

char a[]="this is a long string of which we want to know the length";
int b    = 101;

// inefficient or.
if ( (strlen(a) > 100) || (b > 100) )
{
            d++;
}

// efficient or.
if ( (b > 100) || (strlen(a) > 100) )
{
            d++;
}

Again, when the fastest expression to evaluate is placed first, the if can be many times faster. Because this example uses an 'or'this time, the second if of the preceeding example is easily 200 times faster then the first when the expression (b > 100) is true.

Note that when all expressions of an 'and'are true, evaluation time is no longer influenced by expression order as all expressions are evaluated anyway.

Note that when none of the expressions of an 'or'are true, evaluation time is no longer influenced by expression order as all expressions are evaluated anyway.

Note also that the rules of expression evaluation hide a sneaky pitfall. Often you can be inclined to test and set a variable in an expression:

for (int i = 0; i < MAX; i++)
    if ( (i >= BuffSize) || (EOF == (c = GetNextChar())) )

The second expression in this if will attempt to get a new character from some input and test whether the input has run dry. However, because there is another expression placed to its left, you cannot guarantee that GetNextChar() is called for every loop iteration!

• if as a selector

The if (else) statement is probably the most straightforward selector of C/C++. Via an if an expression is evaluated, after which either the statements belonging to the if itself, or those belonging to the else, are executed. The following example demonstrates this:

if (a < 10)
{
    DoLittle();        // execute when a < 10.
}
else if (a < 100)
{
    DoMore();        // execute when  10 <= a < 100.
}
else if (a < 1000)
{
    DoDa();        // execute when  100 <= a < 1000.
}

First variable a is compared to 10. When a is lower than 10, the function DoLittle() is called. Only when a is equal to or larger than 10 is the second comparison made (a < 100). Similarly, only when a is equal to or larger than 100 is the third comparison made. This means that the more comparisons are specified, the more statements need to be executed in order to reach the final comparison. In the preceeding example, the call to the function DoDa() is reached only after three comparisons have been made. It stands to reason that the implementation of a large number of choices made with the if..else technique can thus result in a rather sluggish piece of code. The first comparisons in the if..else construction are still quite fast, but the deeper you get, the slower the response becomes. This means that the statements that need to be executed most often should be placed as high up in the if..else construction as possible. It also means that the default instructions—the ones executed when none of the other comparisons match—will take the longest to reach.

if (a == 1)
{
    Do1();        // fastest code to reach.
}
else if (a == 2)
{
    Do2();        // still pretty fast.
}
~
~
else if (a == 1000)
{
    Do1000();        // very slow to reach.
}
~
~
else
{
    DoDefault();    // slowest to reach.
}

The power of the if..else really lies in the fact that complicated expressions can be used as the basis of a choice.

Jump Tables

When the range of conditions for the choices can be translated to a continuous range of numbers (0, 1, 2, 3, 4, and so on), a jump table can be used. The idea behind a jump table is that the pointers of the functions to be called are inserted in a table, and the selector is used as an index in that table. The following code example implements a jump table that does much the same thing as the previous example where if..else is used:

// Table definition:
typedef long (*functs)(char c);
functs JumpTable[] = { DoOne,DoTwo,DoThree /* etc*/} ;

// some code that uses the table:
long result = JumpTable[selector](i++);

The first two lines of code in this example define the jump table. The typedef determines the layout of the functions that will be contained by the jump table—in this case, a function which receives a single character as input and which returns a long as a result. The array definition of JumpTable actually places the pointers of the functions in the table. Note that the functions DoOne(), DoTwo(), and DoThree() must be defined elsewhere and should take a character as input parameter and return a long.

The last line of code demonstrates the use of the jump table. The variable i is input for the function that is selected via the variable selector. The variable result will receive the long returned by the selected function. In short, when i contains the character a and selector has the value 2, the following function call is actually made:

long result = DoThree('a'),

The implementation of a jump table solution is equally fast for each possible selection (table entry). The drawback is that the range of selections has to be continuous and a default has to be encoded by hand. It is, of course, possible to specify continuous ranges that do not start at zero. This is done by decreasing the selector in value before accessing the jump table:

// Range 19-56

selector -= 19;
long result = JumpTable[selector](i++);

It is also possible to use several table entries per selector value, by using multiplication of the selector value as in this example:

// 2 functions per selection:

int tabEntry = selector * 2;

long result  = JumpTable[tabEntry](i++);
long result += JumpTable[Tabentry+1](i++);

switch Statement

The switch statement presents a number of cases which contain programming statements. A case can be chosen and executed when its constant expression matches the value of the selector expression that is being evaluated by the switch statement. Listing 7.1 demonstrates this:

Code Listing 7.1. A Simple Switch

switch(b)
{
    case 1:  DoOne();  break;
    case 4:
    case 2:  DoEven(); break;
    default: DoError();
}

Depending on the value of the selector expression (here, variable b), a certain function is called. When b equals 1, DoOne() is called; when b equals 2 or 4, DoEven() is called; and for all other values of b, the function DoError() is called. By adding or omitting the break command, the implementer can decide whether a single case is executed exclusively (break) or whether one or more of the following cases are evaluated (and possibly executed) also (omitting the break).

The implementation of the switch statement is not fixed though. Depending on how it is used in a piece of source code, the switch statement is translated by the compiler using one of the following techniques:

• switch as a Jump Table

A switch without holes in the case continuity will be implemented as a jump table. When, for instance, the following cases are specified

       { case 0, case 1, case 2, case 3, case 4, case 5, case 6, default}

the value of the selector expression can be used as the index in the jump table. Each jump table entry is, of course, a pointer to the implementation of a certain case; however, these cases are not implemented as functions, but as branches. Here it is sufficient to mention that a microprocessor incurs much less overhead when it executes a branch compared to when it executes a function call; the reason for this is that during a branch no context needs to be pushed to, and later popped from, the stack. More will be explained about function calling overhead in Chapter 8, "Functions." For now, it is important to understand only that the overhead of a switch case is a lot less than that of our own jump table, as long as the switch cases directly contain the statements that should be executed. When the cases delegate to other functions, however, as in Listing 7.1, the overhead increases as first a jump to the specific case, and then a call to a function, needs to be executed.

But this switch is even sneakier than you might think. Before reaching the actual jump table, the selector expression is first compared with the maximum of the range of cases. This is done in order to determine if the default should be executed. In this example, a quick if ( b > 6) will determine the validity of the default, making it perhaps unnecessary to even consult the jump table. As you would thus expect, the default is the fastest decision this kind of switch can make.

Even when the continuous cases start at a random number, a jump table can still be used. When the following cases are specified

     { case 19, case 20, case 21, case 22, case 23, default}

the value of the selector expression is simply decreased with the starting number (19) and then used as jump table index.

Of course, the implementation of a jump table introduces a certain overhead; this is why switch statements with a small number of cases will still be implemented by a compiler as an if..else, simply because this is faster.

• switch as an if..else

You will appreciate that a jump table cannot as easily be used for a switch with cases that have seemingly random constant expressions. Consider the following cases:

      { case 55, case 300, case 6, case 12, case 79, case 43, case 3, default}

For this set of cases it is necessary for the compiler to use a number of if..else statements in order to determine exactly which case should be executed. However, not all is lost yet. Although this technique does introduce some overhead, a good compiler will group the if..else values in such a way as to minimize the number of comparisons that need to be made. When the first comparison determines that the selector expression is larger than that for the first case (55), there will, of course, be no need to compare the expression with cases 6, 12, and 3. The if..else construct will contain expressions grouped in such a way that unnecessary comparisons are not done.

When the switch is represented by an if..else construct, the default case will not be the fastest decision made by the switch .

Conclusion: It pays to design a case statement in such a way as to allow the case s to be presented as a continuous range. Then, when possible, the default case should be used for the selection that is executed most often.

Comparing Selector Performance

Now that the workings of the different selectors has been discussed and their strengths and weaknesses are known, let's look at some practical examples and see just how different implementation strategies measure up to one another.

This section uses three test cases to analyze different kinds of implementation:

• Comparing without function call overhead

• Comparing with function call overhead

• Array look-up

The sources used in this section can be found on the Web site. Also, the following paragraphs will highlight the most important concepts used by the sources and explain what exactly is being done.

The examples of this section make use of selectors with numeric values with a continuous range; this way all techniques can be used and thus compared fairly.

• Comparing without function call overhead

This paragraph looks at the execution of selectors that do not delegate to other functions. By this is meant that all the statements to be executed upon selection are included in the body of the selected if or case:

// switch without function delegation:
switch(j)
{
    case 1:
            k+=1;     // Statements to be executed.
            break;
    case 2:   
            k+=3;     // Statements to be executed.
            break;
    ~~

// if..else without function delegation:
if (j==1)
{
    k+=1;             // Statements to be executed.
}
else if (j == 2)
{
    k+=3;             // Statements to be executed.
~~

As shown in the previous paragraphs, delegating to functions creates extra (function call) overhead; it is therefore treated in a separate test case. This is also why jump tables are not included in this test case: Jump tables always use function calls.

The program 07Source01.cpp that can be found on the Web site, uses the timing function time_fn() from the book tools—as discussed in Chapter 5, "Measuring Time and Complexity"—in order to time the differences between the if..else and switch implementations. Although the exact timing results will differ per system, the relations between the if..else measurements and switch measurements should not. Table 7.1 shows the relations discovered with 07Source01.cpp:

Table 7.1 shows timing values of a switch implementation (column 2) and a similar if..else implementation (column 3). The timing values denote the relative time it takes for a certain case to be reached. For instance, in order to reach case 7, the if..else construct needs twice as much time as the switch does. What else do can you see in these results? Apparently, the if..else is faster for the first three cases, after which it starts to lose ground. The switch has a relatively constant value for each of the non-default cases. Remember that the switch is implemented as a branching table in this example, as the number of cases is relatively high. Another prominent number in this table is that for the default case; the switch is clearly much faster than the if..else construct there.

Conclusion: Where possible, the default case of a switch should be the most used case. The cases used most often in an if..else construct should be placed as the first if s of that construct. Sometimes it might even be a good idea to precede a switch by one or two if..else statements.

When neither the design nor the requirements make clear which cases are most important—that is, which cases are executed most often when the program is being used—some static debug counters could be inserted in the various cases in order to determine how often a case is executed during field tests. This information can then be used to optimize case order and implementation. Once again, though, the profiler can give us this information as well (see Chapter 4, "Tools and Languages").

• Comparing with function call overhead

Now that you will be looking at selectors that delegate to other functions, it is fair to add the jump table technique to our set of selectors to examine. The following excerpt shows how the different techniques will be tested:

// switch with function delegation:
switch(j)

{
   case 1: k+=aa();    // Function call.
           break;
   case 2: k+=bb();    // Function call.
           break;

~~

// if..else with function delegation:
if (j==1)
{
  k+=aa();            // Function call.
}
else if (j == 2)
{
  k+=bb();            // Function call.
}
~~

// jump table with functions:
k+=table[j-1]();        // Function call.
~~

The program 07Source02.cpp that can be found on the Web site uses the timing function time_fn() from the book tools—as discussed in Chapter 5—in order to time the differences between the if..else, switch, and jump table implementations. Although the exact timing results will differ per system, the relations between the results for the different techniques should not. Table 7.2 shows the relations discovered with 07Source02.cpp.

Table 7.2 shows timing values of a switch implementation (column 2), a similar if..else implementation (column 3), and a jump table implementation (column 4). The timing values denote the relative time it takes for a certain case to be reached.

As expected, both the switch and the jump table have constant results for the non-default cases. The if..else is still faster than the switch for the first two cases but it does not outdo the jump table . Do not forget, however, that the jump table technique creates some extra overhead that is not represented by this timing data. This overhead is incurred when the jump table is initialized with the function pointers. However, this is done only once and most likely at some point during the start of the program.

Conclusion: When the number of statements to be executed in each case becomes large enough to warrant delegation to functions, the jump table technique is clearly the fastest choice, with the switch coming a close second.

Conclusion 2: When constant lookup time is important, the jump table is definitely the way to go.

• Array lookup

This final bullet examines array lookup. It is not really a fair comparison to set array lookup times next to selector times, which is why it is placed in a separate bullet; however, array lookup is still a very interesting technique simply because it is incredibly fast.

The principle of array lookup is basically creating an array containing results. Then, instead of calling a function in order to obtain a result, the array is simply indexed. Of course, this technique can only be used when all possible function results can be calculated beforehand and an indexing system can be used. A popular and very useful implementation of a lookup array is one containing sine, cosine, or tangent results. Instead of calling an expensive tan() function, an array is created containing the tan results with the needed resolution. The following example illustrates this:

// Look-up Array definition:
short tan[] = { 0,175, 349,524,698,872,1047,1221,1396,1571,1746} ;
~~
// Use of array as if function:
short res = tan[a];

Note that this example also puts into practice some techniques concerning efficient use of vari ables as explained in Chapter 6, "The Standard C/C++ Variables." Table 7.3 shows some timing results.

The fastest times yet, obviously. And, of course, each case (array index) is equally fast. The consideration to be made concerning array lookup is whether its use measures up to the amount of space the array takes up. In this example the decision is clear: Any tan function would be considerably larger than this small array of shorts. And even when the array does become impressively large, it might still justify its existence when the data it contains is needed very often, is very expedient, or both.