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

Question

Почему использование 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

1

c++c++11 forward-list list optimization

Решение

Другие решения

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

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

6

Источник

Accepted Answer

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 байтов на элемент. Это одно из вероятных объяснений наблюдений за использованием памяти.

3