Почему использование 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'
, значение которого может быть жестко запрограммировано в вашем исполняемом файле.