Linear search throught vector[i] yealds 0ms response whilst vector.at(i) yealds time

Question

I must add: I am calling my linear search 15 000 times and the lowest range i am looking within is up to 50 000 with each iteration. Thus meaning there are 15 000 * 50 000 look ups on the first iteration. This should take longer than 0ms.

I have this basic Linear search:

bool linearSearch(std::vector<int>&primes, int number, int range) {

    for (int i = 0; i < range; i++) {
        if (primes[i] == number)
            return true;
    }
    return false;
}

I take time using:

void timeLinearSearch(std::vector<int>& primes) {
    clock_t start, stop;
    size_t NRND = 15000;    //  15000 primes per clock

    for (int N = 50000; N <= 500000; N += 50000)    // increase by 50k each iteration
    {
        for (int repeat = 0; repeat < 5; repeat++) {
            start = clock();
            for (int j = 0; j < NRND; j++) {
                linearSearch(primes, rand(), N);
            }
            stop = clock();
            std::cout << stop - start << ", " << N << std::endl;
        }

    }
}

The problem here is that the time taken is 0ms. The vector 'primes' has roughly 600 000 elements in it so the search stays within range.

In the linear search, if I change:

if(primes[i] == number)

to:

if(primes.at(i) == number)

then I get time > 0 taken for the search.

I have compared my linear search with the primes.at(i) to std::find() by:

for (int j = 0; j < NRND; j++) {
    std::find(primes.begin(), primes.begin() + N, rand());
}

and this is roughly 200ms faster than my .at() find.

Why is my search with std::vector[i] giving me 0ms time?

Answer 1

When the compiler can see into the implementation of linearSearch, it can optimize it out entirely when you use operator[], because there are no side effects. That is why you see zero time.

at(..), on the other hand, has a side effect (throwing when the index is out of bounds) so the compiler has no option of optimizing it out.

You can fix your benchmark to ensure that the call is kept in place, for example, by counting the number of matches:

int count = 0;
for (int j = 0; j < NRND; j++) {
    count += linearSearch(primes, rand(), N);
}
std::cout << stop - start << ", " << N << " " << count << std::endl;

Answer 2

You do need to be careful with writing comparison code like this; do make sure you have a statistically rigourous way of interpreting your data. Assuming you do have this, here's an explanation:

[i] does not have to check if i is within the bounds of a vector, whereas at(i) must check.

That explains the difference in the speed: your compiler is able to generate faster code for [].