У меня есть следующий код для профилирования производительности std :: vector и std :: list для различных N.
void vectorPerf(size_t n)
{
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
std::vector<size_t> cache;
for (size_t i = 0; i < n; i++) {
cache.push_back(i);
}
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();
std::cout << duration << " us." << "\n";
return;
}
void listPerf(size_t n)
{
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
std::list<size_t> cache;
for (size_t i = 0; i < n; i++) {
cache.push_back(i);
}
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();
std::cout << duration << " us." << "\n";
return;
}
int main(int argc, char** argv)
{
if (argc != 2) {
return -1;
}
std::stringstream ss(argv[1]);
size_t n;
ss >> n;
vectorPerf(n);
std::cout << "\n";
listPerf(n);
std::cout << "\n";
}
Для нескольких прогонов одного и того же набора N я получаю результаты, в которых результаты последовательно имеют тот же порядок, что и числа ниже:
N std::vector std::list
1000 46 116
2000 85 217
5000 196 575
10000 420 1215
100000 3188 10497
1000000 34489 114330
Мне интересно, почему производительность std :: list постоянно хуже, чем std :: vector. Для std :: vector я ожидал, что производительность будет амортизироваться O (N), потому что внутренний объект, лежащий в основе std :: vector, должен будет время от времени изменять размер. Поскольку все, что я делаю, это вставляю элемент в конец списка, я ожидал, что std :: list будет O (1). Таким образом, можно предположить, что std :: list будет работать лучше, чем std :: vector, но, похоже, верно обратное.
Буду признателен, если кто-нибудь сможет пролить свет на то, почему это происходит. Я компилирую MacOS 10.12.6 с использованием g ++ на MBP 2015 года.
Спасибо.
РЕДАКТИРОВАТЬ: теперь я понимаю, что std :: vector :: push_back () амортизируется O (1). Однако мне непонятно, почему std :: list :: push_back () работает стабильно хуже, чем std :: vector :: push_back ()?
std::vector/list<size_t> cache(n)
, чтобы исключить выделение памяти для сравнения. - person Ken Y-N   schedule 26.12.2017std::vector
в большинстве ситуаций. - person Phil1970   schedule 26.12.2017push_back()
s заключаются в том, что код заканчивает запись в последовательные адреса памяти. Вот что такое вектор. Современные процессоры просто очень, очень хороши в последовательном доступе к последовательным адресам памяти. В std :: list каждый элемент в конечном итоге распределяется в случайных фрагментах памяти, поэтому профиль производительности хуже. - person Sam Varshavchik   schedule 26.12.2017-O2
или-O3
в командной строке, включив таким образом оптимизацию? - person PaulMcKenzie   schedule 26.12.2017