CODEWITHSUNDEEP
c++pointersvectorc++builder
VLL
VLL

Reputation: 10155

Why are STL algorithms much faster with pointers than std::vector iterators?

Why does std::nth_element() run so much faster, when it is given pointers instead of iterators? I would expect std::vector and STL algorithms to be quite optimized, but my measurements show execution time drops by 75% when I change iterators to pointers.

Using iterators, the following code (not including allocation of the vector) ran in 1200 milliseconds:

std::vector<uint16_t> data(/* 50 million values */);

const double alfa = 0.01;
const double beta = 0.95;

std::nth_element(data.begin(), data.begin() + int(data.size() * alfa), data.end());
const uint16_t x = *(data.begin() + int(data.size() * alfa));

std::nth_element(data.begin(), data.begin() + int(data.size() * beta), data.end());
const uint16_t y = *(data.begin() + int(data.size() * beta));

Using pointers, the following code (not including allocation of the vector) ran in 350 milliseconds:

std::vector<uint16_t> data(/* 50 million values */);

const double alfa = 0.01;
const double beta = 0.95;

std::nth_element(&data.front(), &data.front() + int(data.size() * alfa),
    &data.front() + data.size());
const uint16_t x = *(data.begin() + int(data.size() * alfa));

std::nth_element(&data.front(), &data.front() + int(data.size() * beta),
    &data.front() + data.size());
const uint16_t y = *(data.begin() + int(data.size() * beta));

I observed similar speed increase with std::sort() as well. The examples were compiled with Embarcadero C++ Builder XE8 version 22.0.19027.8951, Release build and "Generate fastest possible code" setting. These tests were ran during different executions so they should not affect each other.

Upvotes: 3

Views: 643

Answers (1)

Galik
Galik

Reputation: 48615

My guess is the compiler is either not doing a great job of optimizing or else you are building in debug mode and the compiler uses special, debug (slow), versions of the STL containers.

Upvotes: 6

Related Questions