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

Question

[LamerFromSpace]

Я новичок в программировании, изучаю структуры данных, написал свою реализацию 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++;
}

Comments

[Максим Мосейчук]

Вы тестировали с включенными оптимизациями компилятора?

[LamerFromSpace]

Максим Мосейчук, с выключенными

UPD: включил оптимизацию, время добавления элементов сравнялось, потребление памяти упало на обоих до 176 МБ

Answer 1

[Роман]

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

Comments

[Максим Мосейчук]

> Между разными нодами есть память, которая выделена процессу, но не занята полезными данными.

Это как так? 100 мегабайт?

Компилятор не добавлять никакую информацию для анализа утечек памяти. Иначе шуткок про отстреленную ногу не было бы.

В clang можно включить санитайзеры, но это нужно сделать явно.

А вот отладочную информацию добавляет.

[Роман]

Про "не занята полезными данными" я погорячился.

Компилятор не добавлять никакую информацию для анализа утечек памяти. Иначе шуткок про отстреленную ногу не было бы.

В Visual Studio добавляет. https://docs.microsoft.com/en-us/visualstudio/debu...

Answer 2

[Максим Мосейчук]

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

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