@LamerFromSpace
Студент-быдлокодер

Почему собственная реализация связного списка выполняет добавление элемента в начало быстрее forward_list?

Я новичок в программировании, изучаю структуры данных, написал свою реализацию linked list чтобы понять, как оно работает, "потрогать ручками".
Заметил, что при 10кк элементов программа потребляет 611 МБ памяти. Думал, что где то имею утечки памяти, подключил STL forward_list, добавил столько же элементов, тоже 611 МБ. Но добавлялись эти элементы 20 сек, в то время как в моей реализации 2 сек. Почему так?

Также я посчитал, что один элемент класса Node занимает 8 байт для типа данных int в x86 конфигурации, значит 10кк элементов займут ~76 МБ памяти, у меня же 611 МБ, в чём дело?
// Класс
template <typename T>
class D1List
{
public:
	D1List();
	~D1List();
	int getSize();

	void push_back(T newData);
	void push_front(T newData);

	T getSum();
	T getAvg();
	T getMin();
	T getMax();
	T operator[](int idx);

private:
	template <typename T>
	class Node
	{
	public:
		T data;
		Node* nextNode;
		Node(T newData = T(), Node* newNextNode = nullptr)
		{
			this->data = newData;
			this->nextNode = newNextNode;
		};
	};
	Node<T>* head;
	int size;
};


// Реализация добавления Node в начало списка
template<typename T>
void D1List<T>::push_front(T newData)
{
	if (head == nullptr) {
		head = new Node<T>(newData);
	}
	else {
		head = new Node<T>(newData, head);
	}
	this->size++;
}
  • Вопрос задан
  • 283 просмотра
Решения вопроса 1
WNeZRoS
@WNeZRoS
включил оптимизацию, время добавления элементов сравнялось, потребление памяти упало на обоих до 176 МБ


Размер не соответствует расчётному из-за того что аллокации через new происходит не плотно. Между разными нодами есть память, которая выделена процессу, но не занята полезными данными.

Можно подсчитать размер потерянной в пустую памяти кодом (для x86):
std::vector<uint32_t> ptrs;
ptrs.reserve(list.size);
for (auto node = list.head; node != nullptr; node = node->nextNode) {
    ptrs.push_back((uint32_t)node);
}

std::sort(ptrs.begin(), ptrs.end());

uint32_t wastedSpace = 0;
for (uint32_t i = 1; i < ptrs.size(); i++) {
    wastedSpace += ptrs[i] - ptrs[i - 1] - sizeof(D1List<int>::Node);
}


В Debug, forward_list работает медленнее потому что внутри у него много вызовов функций. В Release они оптимизируются и инлайнятся.
Скорее всего, памяти в Debug используется больше для анализа утечек памяти.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
При выделении памяти в куче перед этими 8 байтами выделяется место под служебную информацию. Из-за этого такие большие накладные расходы в 100 мегабайт.

Для оптимального расходования памяти нужно использовать кастомный аллокатор, который будет выделять память большими кусками сразу, а потом уже использовать этот кусок для кучи маленьких объектов.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы