Loops

This section focuses on loop statements. Loops have a way of making a source code listing look relatively compact as repetitions of statements are coded only once. This is where loops present a danger to performance as well; any small inefficiency in the body of a loop will be incurred as many times as the loop body is iterated over. A loop that has one superfluous statement and that is iterated over 10,000 times will, of course, cause 10,000 superfluous statements to be executed. Consequently, loops are the places where most often a lot of performance can be won. This section presents several techniques that can be used to optimize loops.

Aborting Loops

Often, loops are implemented with termination conditions, as shown in the following examples:

// typical loop termination conditions:
for (j = 0; j <  arraySize; j++)
{ ~~}

while (q < nrOfElems )
{ ~~}

do { ~~}
while (countDown > 0);

These are typical uses of loops for iterating over the elements of arrays, databases, and lists. They are syntactically correct, of course, but can be wildly inefficient. Consider an array of which each element is, on average, accessed an equal amount of times during program execution; a loop as specified like this will thus, on average, execute 50% of its iterations in vain. Only when the element that the loop is "looking for" happens to be the last element in the array does the loop actually have to iterate over all the array elements. This is why often a second stop clause is added to the loop, enabling it to stop when it has found what it is looking for. Listing 7.2 demonstrates this.

Code Listing 7.2. Aborting a Loop with a Flag

void DB::FindId(int searchId)
{
    int Found = 0;

    for (int i=0; i<Index && !Found; i++)
    {
        if (base.GetId(i) == searchId)     // abort criteria.
        {
            //Found.
            Found = 1;
        }
        ~~ other loop statements ~~
    }

    base.ExecuteElement(i);
~~

The flag Found is added to the stop condition of the for loop in order to abort further iteration when the job has been done. As can be seen in this example, two comparisons are needed to determine an early stop. The first comparison is made in the body of the loop in order to determine whether you have found what you are looking for—in which case the Found flag is set. The second comparison is made in the header of the loop in order to check up on the status of the Found flag. This already gains us some performance as the average number of iterations is now brought down by 50% (for loops in which each element is used the same number of times on average). However, when the loop does not find what it is looking for, all iterations are, of course, still performed and two statements of overhead were added to every iteration! A better way to abort a loop is presented in Listing 7.3.

Code Listing 7.3. Aborting a Loop with a Break

void DB::FindId(int searchId)
{
    for (int i=0; i < Index ; i++)
    {
        if (base.GetId(i) == searchId)     // abort criteria.
        {
            //Found.
            break;
        }
        ~~ other loop statements ~~
    }

    base.ExecuteElement(i);
~~

By using break (Listing 7.3), you can eliminate one of the two comparisons used in Listing 7.2.

When the abort criterion is satisfied (GetId(I) == searchId ), the break takes program execution to the first statement following the loop, which is base.ExecuteElement(i) in Listing 7.3. Not only does the code in Listing 7.3 use fewer comparisons per iteration, it is also faster when the abort criterion is reached. This is because the break causes the rest of the statements in the loop to be skipped (~~ other loop statements ~~), and the loop header is not evaluated a last time.

Note that the stop criterion in the header of the loop itself could also be replaced by an if..break combination; however, this is unlikely to affect the loop performance as compilers will generate the same, or very similar, code for both solutions.

In practice, complicated loops will often take up most of a function, with the function result being a pointer (or reference) to the found element. In these cases, it is, of course, best to abort the loop by immediately returning the found object. The following example illustrates this:

void DB::FindId(int searchId)
{
    for (int i=0; i < Index ; i++)

    {
        if (base.GetId(i) == searchId)     // abort creteria.
        {
            //Found.
            return base.GetObjectRef(i);
        }
        ~~ other loop statements ~~
    }
}

Skipping Parts of the Loop

In the previous section, you saw how to speed up loops by skipping unnecessary iterations. This section will explain how to speed up loop iteration by skipping unnecessary statements within the loop body. Basically, it comes down to finding out whether the iteration will be useful as early on as possible. If it is not, the rest of the statements of the loop body are skipped and the next iteration is started. This technique is a valuable time saver; it should especially be considered for large or work-intense loops. The code in Listing 7.4 looks very similar to that of Listing 7.3, where break was used to abort a loop. The results, however, are fundamentally different.

Code Listing 7.4. Aborting an Iteration of a Loop

void DB::ServiceProblems(int threshold)
{
    int size = baseSize;        // local copy of a member variable.

    for (int i=0; i < size ; i++)
    {
        EL *element = GetObject(i);   // local pointer.

        if (element->GetPressure() < threshold)     // skip criteria.
        {
            // not an interesting element.
            continue;
        }
        ~~ other loop statements ~~
    }
}

The example in Listing 7.4 iterates over all database elements and performs some actions for each element that has a pressure value greater than that of the specified threshold. An if..continue combination was added to discard any element with a safe pressure value. Consequently, for safe elements the ~~ other loop statements ~~ will be skipped, as the continue forces the next iteration to be started immediately. Notice that, in this example, the if..continue could have easily been replaced by an if..else construct. This is basically always the case; however, more complex loops can become much easier to read when continue is used instead. Notice also that some techniques discussed in Chapter 6 are used here.