This is the code that shows the access behavior of std::vector slows down when std::vector is sorted by std::sort().
#include <cstdio>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cstring>
#include <algorithm>
constexpr auto NUM_KEYS(24000000);
constexpr auto CLOCK_MILI(CLOCKS_PER_SEC/1000);
constexpr auto CHARS("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
static int x = 0;
void insert(void* obj) {
std::size_t len = std::strlen((const char*)obj);
for(std::size_t i=0; i<len; ++i)
for(std::size_t j=0; j<len; ++j)
++x;
}
int main(void) {
std::vector<void*> list;
auto seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937_64 rng(seed);
std::uniform_int_distribution<int> rand_ch(0, 25);
std::uniform_int_distribution<std::size_t> rand_len(8, 16);
// Generate random string
for(std::size_t i=0; i<NUM_KEYS; ++i) {
std::size_t len = rand_len(rng);
char* buf = new char[len+1]();
for(std::size_t j=0; j<len; ++j)
buf[j] = CHARS[rand_ch(rng)];
list.push_back(buf);
}
// First traverse the list
std::clock_t cl = std::clock();
for(auto obj : list)
insert(obj);
printf("Time 1 = %ld miliseconds\n", (clock()-cl)/CLOCK_MILI);
// Sorting the list
std::sort(list.begin(), list.end(),
[](const void* a, const void* b) {
return std::strcmp((const char*)a, (const char*)b)<0;
});
// Second traverse the list
cl = std::clock();
for(auto obj : list)
insert(obj);
printf("Time 2 = %ld miliseconds\n", (clock()-cl)/CLOCK_MILI);
// Destroy the strings
for(auto obj : list)
delete[] (char*)obj;
return EXIT_SUCCESS;
}
There are 2 iterations trying to traverse the list while calling insert(). The insert() function does not modify the data. The first iteration is done without std::sort(), and the second iteration is done after std::sort().
The result obtained at runtime executed on option -std=c++17 -O3 with GCC 11.1.0:
Time 1 = 101 miliseconds
Time 2 = 909 miliseconds
Likewise, the result when std::sort() is omitted at run:
Time 1 = 102 miliseconds
Time 2 = 101 miliseconds
Access to list is 9 times slower when list is modified by std::sort(). Similar results occur when std::sort() is replaced with std::random_shuffle(), or some code that modifies list.
- So what really happened?
- Why does traversal of
std::vectorslow down after modification?