Is bounds checking in C or C++ expensive?

Question

Bound checking is expensive (> x2 times runtime overhead)

I got this point above from one of my professors. I am confused about that. As I know, the most time-consuming part of a program is IO(from network and from hard disks).

But bounds checking in C or C++ are not always related with those 2 input sources. For example, I copy the content of one buff to another in C using memcpy(dest, src, length(src)). Before that, I check the size of src in order to prevent from a heap overflow. The precess I can image is: Get the start-address of src and the \x00 byte in src(in the view of assembly language, I copy the content of src one by one and see if the byte is equivalent with \x00). After getting the 2 address, just substract them to get the length of src. I read the content of src from the memory. We all know reading things from memory is fast.

Answer 1

I just ran a program I had with iterator bounds checking turned on.

The running time went from 789 ms to 2608 ms.

So yes, it can matter. Not all the time, but certainly more than never.

In particular, bound-checked iterators require at least twice as much storage as simple pointers, and furthermore, are not as easily optimized. In theory they're simple and efficient, but in practice you simply don't want to do work that you don't need to.

Oh, and did I mention the compile time went from 7.72 seconds to 13.21 seconds as well?

---

For the many nonbelievers among you... a miniature example takes 0.92 seconds without bounds checking and 1.96 seconds with.

---

Since there's a lot of skepticism about everything, including vector's efficiency... here's another one:

#include <cstdio>
#include <ctime>

template<class T> struct Vector
{
    T *b, *e;
    Vector(size_t n) : b(new T[n]), e(b + n) { }
    T &operator[](size_t i) { return b[i]; }
    T &at(size_t i) { if (i >= e - b) { throw "invalid"; } return b[i]; }
};

#define at operator[]  // Comment this out to enable bounds-checking

int main(int argc, char **argv)
{
    Vector<size_t> v(1 << 16);
    for (size_t *p = v.b; p != v.e; ++p) { *p = 1; }
    clock_t begin = clock();
    for (int j = 0; j < 1 << 12; ++j)
    {
        for (size_t i = 8, n = v.e - v.b; i < n; ++i)
        {
            v.at(i) += v.at(i - 8);
            v.at(i) ^= v.at(i - 7);
            v.at(i) -= v.at(i - 6);
            v.at(i) ^= v.at(i - 5);
            v.at(i) += v.at(i - 4);
            v.at(i) ^= v.at(i - 3);
            v.at(i) -= v.at(i - 2);
            v.at(i) ^= v.at(i - 1);
        }
    }
    clock_t end = clock();
    fprintf(stderr, "%u\n", clock() - begin);
}

2.09 seconds vs. 0.88 seconds.

Answer 2

That used to be true—up until the 1980s.

With modern code generation and highly pipelined CPU architectures, bounds checking can be done for zero or very little additional execution cost. This is because the bounds check can occur in parallel with memory fetch.