Optimizing Bounds Checking in C/C++

December 11th, 2009 Leave a Comment

I realized that I’ve not been sharing any programming experiences lately due to my focus in traveling and figures. So, let’s discuss a bit on bounds checking today.

Very often, we need to check if an array index is out of range. Normally, we’d write our code similar to the following example.

    const int size = 32; int i;
    // ...
    if(0 <= i || i < size)
    {
        // Do the array operation
        // ...
    }
    else
    {
        // Handle the invalid index i error
        // ...
    }


The above code contains several comparisons. Let’s simplify the code (see example below). Here, we make use of type casting. By casting the variable i to unsigned integer, we can eliminate two compares. If the variable i happened to be a negative number, it will be interpreted as a large positive number after the casting and hence, the error condition will be triggered. In addition, the type casting used here doesn’t generate any extra code at all. As the compare operations reduce, the code will run faster.

    const int size = 32; int i;
    // ...
    if((unsigned int)i < (unsigned int)size)
    {
        // Do the array operation
        // ...
    }
    else
    {
        // Handle the invalid index i error
        // ...
    }


Also, we often need to check whether an integer is within a certain value, see example below.

    const int min = 32, max = 64; int i;
    // ...
    if(min <= i || i <= max)
    {
        // Do the operation
        // ...
    }


The above code can be simplified as follows. Here, we introduced two more arithmetic operations but we reduced the two comparisons. Since the simple arithmetic operations are faster than those comparisons, the code will run faster.

    const int min = 32, max = 64; int i;
    // ...
    if((unsigned int)(i - min) <= (unsigned int)(max - min))
    {
        // Do the operation
        // ...
    }


These are some simple optimization tips that you can use in your daily programming when speed is critical. I hope you find it useful. :)

Tags:
, ,

Leave a Reply


six × 9 =