Почему использование forward_list с char намного лучше, чем использование long с long?

Я использовал приведенный ниже код для сравнения std::list с std::forward_list

#include <iostream>
#include <list>
#include <forward_list>
#include <windows.h>

int main()
{
    LARGE_INTEGER start_;
    LARGE_INTEGER end_;
    LARGE_INTEGER freq;

    QueryPerformanceFrequency(&freq);
    std::list<long long> list;

    QueryPerformanceCounter(&start_);
    for(long long i=0;i<50000000;i++)
        list.push_front(i);
    QueryPerformanceCounter(&end_);


    std::cout<< (end_.QuadPart - start_.QuadPart) / (freq.QuadPart / 1000) <<"\n";
    cin.get();
}

Я изменил список с forward_list, и измеренные время и размер обоих результатов:

//long long
//              size    time
//forward list 1157.3  2360
//list         1157.3  2450

И я делаю то же самое для этого кода:

int main()
{
    LARGE_INTEGER start_;
    LARGE_INTEGER end_;
    LARGE_INTEGER freq;

    QueryPerformanceFrequency(&freq);
    std::list<char> list;

    QueryPerformanceCounter(&start_);
    for(long long i=0;i<50000000;i++)
        list.push_front('a');
    QueryPerformanceCounter(&end_);


    std::cout<< (end_.QuadPart - start_.QuadPart) / (freq.QuadPart / 1000 )<<"\n";
    std::cin.get();
}

Результат:

//char  
//              size  time
//forward list  773   2185
//list          1157  2400

Вопрос в том, зачем использовать std::forward_list с чаром гораздо лучше, чем использовать его с длинными std::list,

Я знаю, что скорости почти одинаковы, но как насчет размеров контейнеров?

//long long
//             size(mb)    time
//forward list 1157.3      2360
//list         1157.3      2450


//char  
//              size(mb)  time
//forward list  773       2185
//list          1157      2400

2 ответа

Решение

forward_list обычно реализуется как простой односвязный список. Узлы списка имеют один указатель, который обозначает следующий узел в списке, и поле данных, которое содержит фактические пользовательские данные. Размер одного узла forward_list<T> будет тогда sizeof(void*) + sizeof(T) предполагая (1), что все указатели данных имеют одинаковый размер, и (2) T не имеет более строгого выравнивания, чем void*,

list реализован в виде двойного списка. Таким образом, один узел будет иметь поле данных и указатели на следующий и предыдущий узлы списка. Размер list<T> узел, таким образом, 2 * sizeof(void*) + sizeof(T) при тех же предположениях, что и выше.

Распределители памяти обычно выделяют память в блоках, размер которых кратен наибольшему фундаментальному выравниванию. Существует компромисс между предоставлением детализации распределений и количеством накладных расходов на отслеживание. Распределение блоков по кратностям основного выравнивания является хорошей точкой баланса и имеет дополнительный бонус, заключающийся в том, что распределения всегда правильно выровнены для любого типа, который не выровнен.

Давайте сделаем предположение, что ваша программа работает в 32-битной реализации - sizeof(void*) == 4 - и что системный распределитель использует размер блока 8 байтов - sizeof(double), Эти предположения верны для типичной 32-битной Windows C++, реализованной в MS Visual C++. С этими допущениями, размер различных объектов:

  • forward_list<char> узел: sizeof(void*) + sizeof(char) == 5, который распределитель памяти будет округлять до 8 байтов.
  • forward_list<long long> узел: sizeof(void*) + sizeof(long long) == 12, который распределитель памяти округляет до 16 байтов.
  • list<char> узел: 2 * sizeof(void*) + sizeof(char) == 9, который распределитель памяти округляет до 16 байтов.
  • list<long long> узел: 2 * sizeof(void*) + sizeof(long long) == 16, который распределитель памяти не будет округлять, так как 16 уже кратно 8.

Так что из типов в ОП, forward_list<char> выделяет 8 байтов на элемент и все list<char>, list<long long>, а также forward_list<long long> выделить 16 байтов на элемент. Это одно из вероятных объяснений наблюдений за использованием памяти.

Первое, что нужно отметить, это то, что это вряд ли "намного лучше". Разница совершенно незначительная.

Кроме того, я думаю, что совершенно очевидно, что копирование 8 байт займет немного больше времени, чем копирование; плюс, для вашей константы не требуется чтение из регистра / памяти 'a', значение которого может быть жестко запрограммировано в вашем исполняемом файле.

Другие вопросы по тегам