Скорость итерации по std::vector и std::list
Просто для интереса решил сравнить скорость итерации по вектору и листу с доставанием значения из каждого элемента с присвоением другой переменной:
#include <iostream>
#include <list>
#include <ctime>
#include <vector>
#include <string>
int main()
{
std::list<std::string>my_list_string_1;
std::vector<std::string>my_vector_string_1;
my_list_string_1.push_back("1");
my_list_string_1.push_back("2");
my_list_string_1.push_back("3");
my_list_string_1.push_back("4");
my_list_string_1.push_back("5");
my_list_string_1.push_back("6");
my_list_string_1.push_back("7");
my_list_string_1.push_back("8");
my_list_string_1.push_back("9");
my_list_string_1.push_back("10");
my_vector_string_1.push_back("1");
my_vector_string_1.push_back("2");
my_vector_string_1.push_back("3");
my_vector_string_1.push_back("4");
my_vector_string_1.push_back("5");
my_vector_string_1.push_back("6");
my_vector_string_1.push_back("7");
my_vector_string_1.push_back("8");
my_vector_string_1.push_back("9");
my_vector_string_1.push_back("10");
int clock1;
int clock2;
size_t cntr = 9999999;
std::string my_string_list_temp;
std::string my_string_vector_temp;
clock1 = clock();
for (size_t i = 0; i < cntr; i++)
{
for (size_t y = 0; y < 10; y++)
{
my_string_vector_temp = my_vector_string_1[y];
}
}
clock2 = clock();
std::cout << my_string_vector_temp << std::endl;
std::cout << "time_vector_string:" << clock2 - clock1 << std::endl;
std::list<std::string>::iterator list_iter;
list_iter = my_list_string_1.begin();
clock1 = clock();
for (size_t i = 0; i < cntr; i++)
{
list_iter = my_list_string_1.begin();
for (size_t y = 0; y < 10; y++)
{
my_string_list_temp = *list_iter;
list_iter++;
}
}
clock2 = clock();
std::cout << my_string_list_temp << std::endl;
std::cout << "time_list_string:" << clock2 - clock1 << std::endl;
Результаты на x86, release, VS2019: (мерял по отдельности, комментируя секцию вектора и листа)
-вектор: 866 мс
-лист: 742 мс
Результаты на x64, release, VS2019: (мерял по отдельности, комментируя секцию вектора и листа)
-вектор: 615 мс
-лист: 613 мс
Подскажите, почему данный код на x86 работает быстрей для листа, а на x64 разницы нет ?
Ответы (1 шт):
посмотрел внимательно на это все и есть такие мысли. Их конечно лучше подкрепить кодом от ассемблера.
что такое итерация по списку с точки зрения ассемблера? это к заданному адресу добавить небольшое смещение (4 или 8), что бы взять адрес указателя на следующий елемент и прочитать с него значение. Все. Если список маленький и локальный (то есть, весь в кеше), этот процесс очень быстрый. Так как Вы много-много раз бегаете по одному и тому же списку, то он с второй итерации скорее всего весь и будет в кеше.
в 64битном режиме студия генерит вот такое - очень кратко:)
mov rbx, QWORD PTR [rbx]
что такое итерация по вектору/массиву? это вычисление по формуле начало массива + индекс * размер элемента. Обычно реализуется одной командой LEA, которая эффективна, когда размер элемента кратен 2, 4 или 8. Но в примере в коде это std::string, который обычно 24 или 32 байта (насколько я знаю, стандарт не требует определенного размера) и придется умножать ручками. А это уже немного сложнее.
Если посмотреть в код, то компилятор в 64битном режиме оказался хитрее, и просто к текущему адресу плюсует 32
add rbx, 32
то есть, в 64битном режиме на самом деле бенчмаркаем mov vs add. Контейнеры? не не слышали:)
а что же в 32битном режиме? для списка студия сделала так
mov esi, DWORD PTR [esi]
не очень и отличается. просто регистры другие.
для вектора
add esi, 24
других явных отличий я не увидел. Код который перекладывает строку в переменную явно потребляет большую часть времени цикла.
Почему же такие результаты? да ничего необычного. Хотелось потестировать скорость итерации по контейнерам, а по факту тестировалась разница в mov/add на фоне вызова конструктора копирования строки.