Управление памятью в C++

[@Monnoroch]

Здорово! Но, насколько я понял, аллокатор позволяет выделять блоки любого размера? Нельзя ли еще ускорить производительность работы с памятью с помощью пула обьектов фиксированного размера? Было бы очень интересно почитать исследование на эту тему.

[@qw1]

Да, во втором случае, в пуле могуть быть разные объекты, но т.к. удаление запрещено, выделение памяти очень простое и разделение по пулам мне кажется, не даст ускорения (с чего бы...)

[@Monnoroch]

Ну вообще говоря приложение обычно активно как выделяет, так и освобождает память. Я в свое время писал конструкцию попроще: аллокатор больших блоков + пул обьектов фиксированного размера, который был реализован следующим образом: он выделял большой блок памяти на N элементов, и еще один для N указателей, записывал все указатели на каждый из N элементов первого блока во второй, а потом раздавал и принимал обьекты как обычный стек, то есть с практически нулевыми расходами как на выделение, так и на освобождение памяти. И цена за это, конечно, оверхед в виде стека из N указателей. При нехватке же памяти, просто выделяем второй блок и увеличиваем стек вдвое (что накладно, да, но очень редко).
Интересно, насколько ваш подход уступает моему в контексте задачи выделение и освобождения в случайном порядке очень большого числа одинаковых обьектов.

[@qw1]

Ваш подход описан в первой части. Честно говоря, в рабочей версии управление большими страницами я тоже сделал связным списком (данные на следующую страницу — в хидере страницы). Но, чтобы не перегружать статью, переписал на vector<>, на быстродействие это окажет минимальное влияние.

В статье описаны две совершенно разных подхода:
1. Блоки одинакового размера, с активным выделением-освобождением
2. Разношёрстные блоки с быстрым выделением, но освобождаются только все сразу (должны иметь одинаковое время жизни смерти)

[@Monnoroch]

Да, спасибо за комментарий, я теперь понял ваши хитрые манипуляции с указателями, очень интересно!

[@gribozavr]

Отлично, только небольшое замечание по терминологии: второй подход это не «DataPool», а pointer-bump allocator.

[@qw1]

Изобретение велосипеда всегда интересно :)

[@qw1]

Впрочем, переправил везде. Ведь кто-то может научиться кривой терминологии.

[@ElleSolomina]

Просто факт по теме: в DC++ похожая конструкция используется очень давно code.google.com/p/flylinkdc/source/browse/trunk/client/FastAlloc.h

[@gribozavr]

Там даже комментарии те же:
> Avoid hiding placement new that's needed by the stl containers

[@qw1]

Да, этот класс я видел, когда готовил статью ))

[@ElleSolomina]

Только у вас лучше конечная реализация, в DC пул в куче, а у вас использована особенность менеджера памяти Windows и память выделяется в памяти процесса.
p.s: перепишу как нибудь «у нас в DC» :)

[@qw1]

этим открытый код и прекрасен. мелкие наработки аккумулируются

[@ElleSolomina]

Это точно, при этом проводятся ревизии даже тех мест куда никто не лазает обычно.

[@Mercury13]

Выяснилось, что у меня (C++ Builder) многопоточный расчёт работал не быстрее, чем один поток. Стал грешить на менеджер памяти, создал несложный объектный пул и подключил FastMm. Ускорило только тогда, когда я сделал и то, и другое, порознь не работало.
(Сейчас, кстати, вычислительное ядро откомпилировано MinGW и это дало ещё трёхкратный выигрыш в скорости.)

[@qw1]

Эх, FastMM… Юзал в дельфи для поиска утечек памяти. Очень удобно — при закрытии приложения каждая утечка описана со stacktrace-ом, где сделано выделение.

В MSVC всё печальнее — только список утечек, без стека, если включать _CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF)

Может, кто посоветует leak detectors для MSVC.

[@Muxlevator]

Visual Leak Detector же.

[@qw1]

Спасибо огромное. Набросал тестик — работает.
Как я его раньше не видел — ума не приложу

[@kamiram]

а вот может кто подскажет:
с#. дофига немаленьких объектов в памяти(около 100к)
и что характерно — одинаковое время жизни
как бы такбы оптимизировать?

[@qw1]

Маленькие объекты должны быть struct, а не class.
Создать массив достаточной длины из struct, и везде ссылаться на объекты не по ссылке, а по индексу в массиве.

[@kamiram]

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

[@qw1]

100к записей гридам — проблема явно. пользователь не робот, зачем ему столько

[@kamiram]

ну вот и я так думаю. больше 1к — толку показывать нет

[@Mrrl]

Объекты меньше 80К действительно требуют вдвое больше памяти. Сам сталкивался — 20000 массивов int[5000] заняли не 400 М, как положено, а 800M. Пришлось их объединять по 64 штуки, чтобы получилось около мегабайта на объект — и затраты памяти вернулись в норму.

[@kamiram]

во-во
похоже на правду

[@bya]

Спасибо автору. Несколько замечаний.

1. Слишком тривиальный пример. Оптимизирующий компилятор может так все за оптимизировать, что в данном случае и считаться ничего не будет. Об этом, косвенно, говорит время для C# 62 ms. При этом сравнение с C# не совсем уместно, поскольку у него менеджер памяти скорее всего выделен в отдельный процесс и его время не учитывается. Мне кажется, что реализация от Google делающая все тоже для C++ будет эффективней Вашей.

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

3. Слишком тривиальный пример. Вы сделали то, что сразу приходит в голову. Я занимаюсь компьютерной алгеброй и если выделять по Вашему память например для полинома, а с ним затем провести несколько сотен тысяч операций (сложений, умножений и т.д.), а это частая ситуация, не выдуманная, то он просто съест всю оперативную память. В моей статье реализована хоть и не классический GC, но именно сборка мусора, но к моему сожалению до многих не доходит.

4. Слишком тривиальный пример. На моих задачах я тестировал реализацию от Google. Она дает ускорение на 5-20% и в основном за счет использования свободного процессора не машине, если все ядра загружены, то как правило ускорения нет. У меня без использования дополнительного ядра в сравнении со стандартными malloc и free время расчета примера ezfact32_4.shuffled.cnf 669.32 сек, а моим allotor-ом 354.57 сек («сборка мусора» +1.31 сек). Такой же коэффициент и на других примерах. Повторюсь, в проекте много динамических структур данных и все они используют эту реализацию GC: мономы (в виде массивов номеров переменных разной длины), всевозможные списки, красно-черные деревья (моя реализация), деревья Janet и ZDD-диаграммы.

[@qw1]

1. Удаление оптимизатором пустого цикла не происходит, тогда время было бы 0. Тем более, в отдельных случаях я достиг времени, как у CLR, так что сравнение честное.

2. Как раз первый пример и устраняет фрагментацию. Объекты разных типов лежат в непересекающихся пулах, а внутри пула фрагментация значения не имеет. Поиск свободного блока — O(1), все блоки в пуле одинаковые, поэтому нет случая, когда много свободного места по мелочи, а взять нечего.

3. Первый пример предусматривает возврат неиспользуемой памяти, смотрите внимательнее. Если алгоритм съест всю память, то значит она вся нужна (выделена)

4. Ну отлично. Проверьте всё же класс BlockAlloc, ведь переделки программы совсем тривиальные (и ещё вернуть надо в состояние до-GC, когда delete не забывали вызывать)

[@szKarlen]

Спасибо за статью!
Давно не было таких статей!)

[@qw1]

вы правы, сейчас убедился, что на Core2 порядок обхода не важен.
очень давно тестил на Celeron D 320, были другие результаты.

[@Cupper]

Заключение. Статья была написана 1.5 года назад для песочницы, но увы, не понравилась модератору.

А я кажется знаю почему. Потому что они ничего не понял. И я тоже ничего не понял. Наверно если я прочитаю статью раза 3-4 то пойму, но… но это плохо. Лично мне как воздуха не хватает картинок которые бы поясняли, что, где и в каком размере вы выделяем, куда делаем выравнивание, как удаляем, что за список на void* и зачем нужен head.

inline size_t align(size_t x, size_t a) { return ((x-1) | (a-1)) + 1; }
Единственное что мне понятно в этой функции это то, что она встраиваемая и то, что она делает какое то выравнивание, но какое и зачем? Для меня это великая загадка.

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

Ведь статься то наверно рассчитана не на тех кто уже знает это (на статью для тех кто в теме не тянет, совсем), а на тех кто совсем не в теме или тех кто очень слабо в теме.

[@qw1]

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

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

Тривиальные классы я сначала не хотел приводить, затем засунул под спойлер.

[@Cupper]

Что делает вот эта функция FormatNewPage()
1. Выделяем блок памяти GetPage
2. Присваиваем Head указатель на начало блока
3. ??? что делает цикл

[@Cupper]

Видимо мы в начало каждого блока записываем адрес начала следующего блока? **ть калатить… ну хоть бы строчку текста пояснения написали бы на это.

[@Monnoroch]

Да, я тоже только со второго раза понял :)

[@Mrrl]

inline size_t align(size_t x, size_t a) { return ((x-1) | (a-1)) + 1; }

Но это же стандартный прием округления вверх до числа, кратного степени двойки! Код я не читал, но примеров применения встречал довольно много (обычно они относились к определению необходимого для чего-нибудь размера буфера).

[@Nomad1]

Странно. В точности, как у .NET CLR, как будто он возвращает освободившиеся локальные переменные сразу в соответствующий пул, не дожидаясь GC

Уверен, так оно и есть. JIT может по своему усмотрению вызывать Gen 0 сборку для локальных out-of-scope объектов.

Generation 0 collections are the most frequently occurring type of collection and clean up short-lived objects such as local variables.

Что интересно, еще Рихтер писал, что если мы добавим для проверки финалайзер в наш класс (~Node()), то объект будет уже попадать в Gen 1, потому ничего толкового не выйдет.
Хорошо бы проверить с помощью Performance Counters, сколько было Gen 0 сборок на весь цикл. Ну и по-честному, надо было объекты добавлять в массив, чтобы избежать ситуации, когда на самом деле все 10000000 раз объект «создавался» по одному и тому же адресу.

Отдельное «фе» о цикле в С++, где мы создаем 10000000 объектов и теряем на них указатели. В статье об управлении памятью такой код должен быть помечен большими красными буквами: ТАК ДЕЛАТЬ НЕЛЬЗЯ.

[@rtorsten]

Почему нельзя? Если то что выделяет память, является интеллектуальным пулом (garbage collector'ом), то он может сам удалять обьекты при своем разрушении.

struct foo
{
	~foo()
	{
		std::cout << "~foo() called\n";
	}
};

boost::object_pool<foo> FooPool;
foo * f = FooPool.malloc();

Деструктор foo будет вызван, при уничтожении FooPool.

Кстати, говоря я создал аналогичный тест с использованием boost pool (multithreaded) и результаты получились даже чуть лучше.

boost pool example

#include <boost/pool/pool.hpp>
#include <boost/pool/object_pool.hpp>
#include <boost/chrono.hpp>
#include <boost/function.hpp>
#include <iostream>

struct Node
{
    Node * _next;
};

class Timer
{
public:
    Timer(bool isStart = false)
    {
        if (isStart)
            start();
    }

    void start()
    {
        _start = boost::chrono::system_clock::now();
    }

    void stop()
    {
        _end = boost::chrono::system_clock::now();
    }

    double elapsed()
    {
        boost::chrono::duration<double> d = _end - _start;
        return d.count();
    }

private:
    typedef boost::chrono::system_clock::time_point time_point;
    time_point _start;
    time_point _end;
};

class ScopeTimer : public Timer
{
public:
    typedef boost::function<void (double elapsedTime)> Callback;
    ScopeTimer(Callback callback) : Timer(false), _callback(callback)
    {
        start();
    }

    ~ScopeTimer()
    {
        stop();
        _callback(elapsed());
    }

private:
    Callback _callback;    
};

void printElapsedTime(double elapsedTime)
{    
    std::cout << elapsedTime << "\n";
}

int main()
{   
    std::cout.precision(10);
    std::cout.setf(std::ios::fixed, std::ios::floatfield);

    {
	boost::object_pool<Node> NodePool;			
	{
	     ScopeTimer timer(printElapsedTime);
             for (int i = 0; i < 10000000; i++)
		  Node* v = NodePool.malloc();
	}	
	//std::cin.get(); // в диспетчере задач будет видно, что память выделена, т.к. NodePool еще живой
    }
    //std::cin.get(); // в диспетчере задач будет видно, что что память очищена, т.к. NodePool уже уничтожен

    return 0;
}

VS10 со стандартным release билд модом выдает результат ~ 50 мс.
mingw 4.6 с -O2 ~ 60 мс.
Естественно это результаты на моей машине под win7.

[@Vayun]

Использование VirtualAlloc/VirtualFree для выделения пулов это экономия на спичках. Точно также как и использование mmap для этой цели в Линуксе. Совершенно неоправданно класс становится привязан к платформе.

[@qw1]

это сделано не для быстродействия, а чтобы не фрагментировать heap

[@Vayun]

В тексте написано совсем другое

но для большей эффективности (чтобы пропустить лишний уровень абстракции), используем VirtualAlloc/VirtualFree

И с какой стати выделение пула malloc'ом будет «фрагментировать heap»?

[@qw1]

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

[@borisko]

Забыли nothrow new.

[@qw1]

имеется в виду, что все методы, в том числе конструкторы, надо бы отметить как nothrow?

[@borisko]

Нет. Существует три версии new со следующими сигнатурами:
void* operator new(size_t) throw(std::bad_alloc) — обычный
void* operator new(size_t, void*) throw() — размещающий
void* operator new(size_t, const std::nothrow_t&) throw() — оператор, который вместо выкидывания std::bad_alloc при проблемах вернёт нулевой указатель.
Используется последний примерно так:
X *p = new(std::nothrow) X;
if (!p) exit(1);

Хорошим тоном считается при перегрузке операторов выделения памяти перегружать и последний вариант.

[@qw1]

Да, это серьёзная ошибка, которая может сломать некоторый код.

Я в замешательстве. Если исправлять всё это корректно, нужно будет добавлять в класс PagePool функционал, обрабатывающий нехватку памяти, что усложнит учебный пример, и так уже получивший претензии за излишнюю сложность ))))

Пожалуй, я добавлю коммент в класс. Если кто-то пользуется new(nothrow_t), он знает, как доделать.
Если же не пользуется, у него ничего не сломается, как не сломалось в высоконагруженной программе IRainman-a

[@qw1]

да в принципе и так ничего не сломается. просто такие new будут брать объекты не из пула, а из хипа, а соответствующий delete будет возвращать обратно в хип.

[@borisko]

К сожалению, нет. nothrow delete вызывается только в случае, если при вызове nothrow new конструктор выкинул исключение, и за ним нужно почистить память. При вызове delete будет вызвана обычная версия, что приведёт к попытке удаления из пула объекта, заведённого в свободной памяти.

[@qw1]

Охохо. Это значит, я напортачил в классификации операторов. И «вопрос для гуру» был неверным. Ну ничего, я провел серию тестов и переписал неправильные части. Надеюсь, правильно ))

Выходит, если определяется новый оператор new с параметрами, нет никакой возможности определить ему отдельный delete, всегда будет вызываться стандартный delete (кроме случая исключения в конструкторе)

[@borisko]

Да, это так. Типичным способом решения данной проблемы, когда operator delete не пустой, является выделение дополнительного кусочка памяти перед основным вовзращаемым блоком и запись туда служебной информации (вроде адреса аллокатора). Так, например, работают new[] и delete[] — new[] пишет перед выделяемым блоком количество элеметов, а delete[] это считывает и вызывает деструкторы нужное количество раз.

[@qw1]

Чем больше я изучаю c++, тем больше я понимаю, что ничего не знаю ))

[@akalend]

это не только с С++

[@akalend]

круто для песочницы…