Скорость итерации по 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 шт):

Автор решения: KoVadim

посмотрел внимательно на это все и есть такие мысли. Их конечно лучше подкрепить кодом от ассемблера.

что такое итерация по списку с точки зрения ассемблера? это к заданному адресу добавить небольшое смещение (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 на фоне вызова конструктора копирования строки.

→ Ссылка