Pull to refresh

Comments 39

Недавно появилась заметка о простой и эффективной «ручной» сборке мусора в С++. Вполне допускаю, что локальная сборка мусора внутри какого-то сложного класса (где идёт активная низкоуровневая работа с указателями) может быть оправдана. Но в масштабах большой программы ...

Я как автор, предыдущей заметки рад дискуссии. Я также с Вами согласен, что Может и не «серебряная пуля», но для абсолютного большинства применений, вполне достаточно. Я не согласен с фразой Но в масштабах большой программы ....

1. Это использовалось в программе, в которой любая ошибка с памятью приведет к ее остановке либо будет получен неправильный результат. Его легко проверить по входным данным и можно воспользоватся другими программами для задачи построения базисов Грёбнера. Они есть практически в любой системе компьютерной алгебры, а также полно специализированных пакетов. У меня конечно бывают ошибки, в том числе и с выделением памяти, но я их всегда быстро находил и исправлял без всяких отладчиков (в моих задачах они практически бесполезны) и тем более менеджеров памяти. Для этого достаточно грамотно писать код+использование пред/постусловий в виде assert+набор тестов.

2. Основная идея мой методики это ускорение вычислений. Ускорение более чем в два раза, а поскольку задачи часто считаются сутками, согласитесь 24 часа или 48, это большая разница. Заодно правда получается и проверка, но она не являлась целью.

3. В проекте много динамических структур данных и все они используют эту реализацию GC: мономы (в виде массивов номеров переменных разной длины), всевозможные списки, красно-черные деревья, деревья Janet и ZDD-диаграммы (все это моей собственной реализации и на GC). Добавлю что все эти структуры работают в очень сложных алгоритмах и большом количестве классов. Объем документации, которую дает doxygen примерно 10 000 страниц A4.

4. Эти программы сложны и в момент выполнения. Алгоритмы построения базисов Грёбнера экспоненциальны, как по времени выполнения, так и по требуемой памяти. При этом идет постоянно выделение памяти для объектов (их счет идет в текущий момент вычислений на миллионы) и освобождение. Именно за счет такой оптимизации с помощью GC и происходит ускорение.
PS. 1000 страниц. Опечатка.
Вам в комментариях к статье уже намекнули на то, что у вас не GC, а всего лишь пул памяти.

Когда я вижу эту конструкцию (взята из предыдущей статьи):

new(allocator) Array(allocator);


то меня слегка передергивает: мало того, что аллокатор передается в двух местах, так и каждая функция и контейнер должны включать в себя этот аллокатор. Для больших проектов это просто неприемлимо. Здесь же представлен простой и понятный концепт: есть владелец, который может измениться, если это необходимо, что предотвращает утечки.
Что тут непонятного, и контейнер и его элементы (которые сами могут быть сложно устроенны) берут память из одного аллокатора (в данном случае Array выступает в качестве элемента контейнера). Поэтому и такой вызов. Эта частая ситуация в сложно устроенных структурах данных.

Я же оговорился в начале статьи, что это не классический GC. И уж тем более не пул памяти. Придумайте название, скажу спасибо.

В моих программах утечек памяти нет, иначе они через 2-3 сек просто сожрали бы всю оперативку. Мне вообще непонятны поэтому Ваши рассуждения по поводу утечек. Их у меня не было и без GC, и нет и с ним. Для начинающих Ваш подход вполне адекватен. Меня интересует быстродействие, а не утечки.

Чтобы не быть голословным Users guide, Developers guide.
В самом начале статьи я написал, что внутри каких-то сложных объектов с определённой спецификой, наверное, создание аллокатора с GC может иметь смысл. Мы с Вами говорим немного о разных вещах: я за то, чтобы внутри специфических объектов было то, что им нужно. И я за то, чтобы это не просачивалось наружу. Потому что снаружи, с моей точки зрения, «ручные» GC вредны. Почему — я написал.
Отсюда, ваш подход — вполне возможно, хорош внутри вашего специфического объекта (максимум — пула объектов). Что касается программ «с птичьего полёта» — то подход другой.
Я же оговорился в начале статьи, что это не классический GC. И уж тем более не пул памяти. Придумайте название, скажу спасибо.

Это называется объектный пул. Единственное отличие — это в том, что объекты пулом не создаются, а только им уничтожаются. А вообще, можно, конечно, оговариваться, но заголовок «Простая и эффективная «сборка мусора» (garbage collection) на C++» явно не соответствует содержанию.
1. Я прочитал что называется объектный пул. Там нет слова о перераспределении памяти. У меня оно есть. Оно есть только при «сборке мусора».

2. В чем не соответствует «Простая и эффективная «сборка мусора» (garbage collection) на C++».
а) Простая, потому-что нужно определить конструктор-копирования и написать swap. И потом написать GC<имя класса>
б) Эффектная, поскольку ускоряет программу минимум в 2 раза о огромном классе задач (где происходит постоянное выделение памяти и его перераспределение).

3. Мне странно все это слышат от закончившего ФизТех (я там сам хотел учится и у меня оттуда много друзей, правда им всем за 60) и от к.ф.м.н. Я конечно плохо объясняю, поскольку думаю не как все, но в этом и есть моя ценность как ученого и как специалиста. Но Вы же тоже специалист, думайте.
Небольшой комментарий по поводу контейнеров U++. Данные контейнеры реализуют так называемую pick семантику, т.е. традиционная операция копирования делает перемещение объекта в новый. При этом старый объект помечается специальным образом таким образом, чтобы его нельзя было использовать без предварительного очищения, что позволяет задетектировать ошибку неправильного использования. При этом присутствует возможность и глубокого копирования, однако по умолчанию применяется именно pick семантика. Надо также отметить, что подобный подход есть и в новом стандарте, для этого надо выполнить следующую конструкцию:

std::vector<A> va1;
va1.push_back(A(...));
...
std::vector<A> va2 = std::move(va1);


При этом va2 становится владельцем контейнера va1, а va1 становится пустым. Преимущество такого подхода в том, что такая операция переноса практически ничего не стоит. Это же относится и к pick семантике.
Привет программерам U++! )
Pick- называю более «привычным» термином «разрушающее копирование» в 4 пункте, попутно разбирая семантику этого действия в нашем контексте. В одной из предыдущих статей меня поправили, что, пользуясь необщепринятыми понятиями, я путаю аудиторию. Тогда я перевёл всё на стандартный язык.
Возможно, тут спутали 2 вещи: pick и peek. Если первая переводится как «отбирать, срывать», то вторая как «заглядывать». Также я бы сделал одно дополнение: pick и move семантика немного отличаются друг от друга: обе производят разрушающее копирование, однако move очищает исходный объект, в то время как pick переводит его в «особое» состояние, описанное чуть выше.
Согласен, товарищ мог перепутать.
В отличие от pick, Moveable вообще не имеет общепринятого названия, т.к. подход мало распространён. Я бы предложил перевести его как «переносимый объект».
void UpdateUI(Window *window)
window можно объявить константным указателем, чтобы гарантировать невозможность его удаления и прочих нехороших действий
С поправкой согласен.
Хочу только заметить, что здесь важнее само соглашение. Иначе, Вы прекрасно сами понимаете: есть 100500 способов обойти любую константность и прочее, сделав всё что угодно.
Поправка: вот здесь говорят, что const вообще ничем не помощник, увы.
Да, обратил внимание на это. Здесь интересное обсуждение этого факта:
К сожалению, далеко не всегда у объекта может быть один владелец.
Точнее так: в вашей идее предполагается, что у каждого объекта есть объект-владелец, который живет гарантированно дольше своих потомков. На верхнем уровне этим владельцем является стэк функции main().
Для обычных «пакетных» программ так оно и есть чаще всего. Для программ, модель данных которых можно представить в виде дерева объектов — тоже.
Проблемы начинаются в многопоточных и/или асинхронных программах, а также если модель данных есть граф, а не дерево. Пример первого случая: над объектом нужно выполнить несколько асинхронных/параллельных операций, а затем уничтожить. Но вы не знаете, какая из операций закончится последней. Пример второго случая: граф, в который постоянно добавляются и удаляются вершины и ребра между ними. Вершина в графе должна быть удалена, когда у нее не останется связей (ребер) с другими вершинами (вариант — не останется пути в графе до некоторой «корневой» вершины, см. циклические ссылки), но вы не знаете заранее, какое из ребер будет удалено последним. Решая задачу сборки мусора в этих двух случаях, вы так или иначе получите свой велосипедмеханизм GC.
Я пишу существенно многопоточные программы (10+ потоков с разным функционалом, которые активно взаимодействуют друг с другом, а также, зачастую, число потоков заранее неизвестно на этапе компиляции и зависит от настроек — в зависимости от режима работы и т.д.) И этот подход себя прекрасно зарекомендовал.

Пожалуйста, приведите конкретный пример из практики, где, по-вашему, этот подход не работает. Постараюсь ответить.
Окай, из практики.
Софт по обработке графики. N+1 потоков, где N=количество ядер, плюс в отдельном потоке гуй. Алгоритмы сложные, изображения могут быть и гигапиксельные, время работы — минуты, а то и часы.
Большинству алгоритмов для работы требуются некие «промежуточные слои» или ещё какие-то объекты, которые непосредственно к итогу операции не относятся, но нужны для хранения промежуточных результатов вычислений. Доступ к этим данным нужен всем N+1 потокам (интерфейсу — для preview; кроме того, пользователь может жамкнуть кнопку «считай в бэкраунде» и делать что-то еще).

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

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

Разумеется, для хранения всего этого мусора назначается один специальный объект-хозяин, деструктор которого освобождает память. Проблема в том, что неизвестно, кому именно принадлежит сам этот «хозяин».
Можно конечно сломать себе мозг, разбирая все возможные варианты запуска и завершения алгоритма и выясняя для каждого случая, кто должен убить хозяина. А можно просто взять банальные «умные указатели» с подсчетом ссылок (циклов в этой конкретной задаче быть не может), мозг, соответственно, себе не ломать, зато потратить время на что-то более полезное. PROFIT!
Может я что-то не так понял — тогда поправьте. Пока всё получается довольно тривиально. Единственное, работу менеджера вынес в отдельный поток, т.к. любые расчёты в GUI — плохая практика.

class IntermediateSource
{
public:
	virtual const IntermediateData &GetSource(const String &) = 0;
};

class GUIReporter
{
public:
	virtual GUIData GetState() = 0;
};

class Renderer
{
public:
	Renderer(IntermediateSource *_source) :source(_source), shutdown(false)
	{
		//thread -> Renderer::Work()
	}
	void Shutdown() {shutdown = true;}
public: 
	//thread: renderer
	void Work()
	{
		const IntermediateData &data = source->GetSource(/*...*/);
		while (!shutdown)
		{
			//...
		}
	}
private:
	IntermediateSource *source;
	volatile bool       shutdown;
};

class RenderManager : public IntermediateSource, public GUIReporter
{
public:
	RenderManager()
	{
		//thread -> RenderManager::Run()
	}
	~RenderManager()
	{
		Shutdown();
		for (int i=0; i<renderers.GetCount(); ++i)
			renderers[i].Wait();
		managerThread.Wait();
	}
	void Shutdown()
	{
		managerThread.Shutdown();
		for (int i=0; i<renderers.GetCount(); ++i)
			renderers[i].Shutdown();
	}
	
	//thread: manager
	void Run()
	{
		//...
		Renderer &newRenderer = renderers.Add(new Renderer(this));
		//...
	}
	
	//thread: renderer[i]
	virtual const IntermediateData &GetSource(const String &k)
	{
		intermediateDataMutex.Enter();
		const IntermediateData &out = intermediateData.GetAdd(k);
		intermediateDataMutex.Leave();
		return out;
	}
	
	//thread: main
	virtual GUIData GetCurrentState()
	{
		//...
	}
private:
	Thread                            managerThread;
	Vector<Renderer>                  renderers;
	Mutex                             intermediateDataMutex;
	ArrayMap<String,IntermediateData> intermediateData;
};

class GUI()
{
public:
	void OnTick() //OnTick() - если по таймеру, либо что-то вроде OnIdle()
	{
		GUIData guiData = guiReporter->GetCurrentState();
		UpdateGUI(guiData);
	}
private:
	GUIReporter *guiReporter;
};

int main()
{
	RenderManager manager;
	GUI           gui(&manager);
	
	gui.Run();
}
забыл конструктор GUI написать с аргументом GUIReporter * — но думаю, Вы и сами поняли.
По сути вы сделали синхронную обертку вокруг асинхронного кода.
Да, так сделать можно, только зачем? Зачем писать лишний код, зачем создавать отдельный поток «менеджера», зачем заморачиваться головной болью по синхронизации этого потока с другими потоками, зачем все эти лишнии wait(), если достаточно просто смартпоинтера с подсчетом ссылок прямо из STL, который точно потокобезопасный, точно самый быстрый для данной платформы? В чем профит-то?
Ваш метод оптимален в 95% случаев — отлично, вот и надо его использовать для этих 95% случаев. Именно поэтому в С++0х ввели слабые указатели и &&. Но для оставшихся случаев есть другие методы — подсчет ссылок для 4% и spanning tree для последнего 1%.
Практически единственный на сегодняшний день плюс Си++ — это как раз возможность выбирать наиболее оптимальное решение в каждом конкретном случае, а не лупить spanning tree для вообще всех объектов.
Тогда вы не совсем чётко описали задачу.
Что конкретно нужно? Чтобы было совсем просто, без обратной связи? Уберите всю лишнее, а промежуточные данные дайте менеджеру в массив (можно ассоциативный). Это будет 7 строчек.
Чем это будет сложнее вашего кода?
Тогда покажите, упрощённо, что есть у вас, чтобы можно было сравнить.
Ну да, да. «Менеджер» (у нас правда «таск») хранит в себе весь мусор и умеет его удалять в функции CleanUp(), которая вызывается в том числе из его деструктора.
Гуй (или скрипт-интерпретатор) создает новый таск и ссылается на него из класса своего диалога обычным shared_ptr-ом, который недавно переехал из буста в STL.
Воркеры обращаются к планировщику и получают TaskPart-ы, в которых есть shared_ptr на соответствующий таск.
Если пользователь, например, жамкнут «Отмена», ну или скажем диалог вылетел с исключением (мы не боги), гуй убивает этот диалог, а вместе с ним — shared_ptr на таск (но не сам таск).
Воркеры заканчивают свои ТаскПарты и убивают их вместе с shared_ptr-ом на таск. Кто из них окажется последним, тому выпадет честь убивать и сам таск и подчищать память. Причем это произойдет даже при неперхваченном исключении.
Эм… А чем не угодил auto_ptr и intrusive_ptr (из буста)?
судя по тому как развиваются события, скоро мы увидим еще одну концепцию GC.
Собираетесь писать статью по теме?
называть это GC будет только человек, который не понимает что такое GC
Встречный вопрос: зачем использовать то, без чего можно обойтись? Зачем переносить проблемы владения с высокого уровня (где известна семантика) на низкий (за счёт перестраховки и снижения производительности)?
Наконец, зачем проблемы циклических ссылок, микширования с обычными указателями?
Зачем отказываться от детерминированности этапа уничтожения объектов, особенно в случаях, когда нужно гарантировать определённый порядок их уничтожения (опять же исходя из семантики отношений)?
Чтобы подрастающему поколению не пришлось ломать ноги об эти велосипеды.
Этому «велосипеду» лет ничуть не меньше, чем intrusive_ptr, просто вы о нём только что узнали и судите по принципу: «это плохо, потому что я привык по-другому».
А вопросы мои к вам всё ещё актуальны. Не ответив на них, обосновать объективную необходимость применения вашего велосипеда, вам будет трудновато. Но я всё ещё надеюсь получить от вас серьёзные, респектабельные ответы.
Bro, были бы вопросы корректными, ответил бы.

p.s. По поводу контейнеров с подсчетом ссылок — так это еще со времен COM длится с его IUnknown. Но только там это было жизненно необходимо, а тут так, поиграться.
Позиционирование функционала на определённый уровень иерархии системы — один из базовых вопросов проектирования. Проблема последовательности зачистки глобальных переменных в единицах трансляции — также широко известна. Проблемы умных указателей — тоже. Что в них некорректного, понять отказываюсь.

Не понял по поводу контейнеров со счётчиком ссылок. Вы точно читали статью?
Да, читал. Честно признаюсь, понравилась и напомнила про COM, поэтому и упомянул.

p.s. Тут проблема немного в другой плоскости, как она видится мне. Я рационализатор. И, понимаете, при использовании описанного подхода мне нужно постоянно помнить о нем, думать об использовании разного рода конструкций. Важное требование: я, разработчик, не хочу об этом помнить. И, если вспомните, то это требование и легло в основу GC в Java. Думаю, было бы справедливо, чтобы при использовании прежних терминов, суть их все же не менялась. auto_ptr в этом отношении ближе, чем все эти кастомные шаблоны.
В статье и примерах нет никаких счётчиков ссылок — уточняю на всякий случай.

Что касается Явы, то я отлично помню и захватил её зарождение. К моменту выхода JDK 1.2, у меня как раз появилась возможность сравнить её с С++. Хвалёная стабильность, которую якобы должны были обеспечить счётчики ссылок и мусоросборщик, на деле оказалась если и не маркетинговым ходом, то, будем более осторожны, решением, работающим далеко не всегда.

Потом я попал в одну достаточно крупную контору, затем другую — и там с головой окунулся с большие проекты на умных указателях. Довольно скоро выяснилось, что в сложных случаях они не только вызывают известные проблемы — это ещё пол беды. Самое неприятное, что эти ситуации оказывалось очень сложно повторить, а значит отладить. Так, на западе уже достаточно давно и правильно считают, что умные указатели — вовсе не «серебряная пуля», как это принято считать у некоторых.

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

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

Но это моё мнение, мой опыт и тот подход, который я предлагаю.
А это значит, что даже если владелец передаёт «наружу» ссылку или указатель на объект, получатель может просить этот объект поучаствовать в каком-то функционале (путём вызова открытых функций-членов объекта). Но не может этот объект удалить, так как не является его владельцем:

Один вопрос, а что делать если объект передали «использователю» а владелец застрелился?

Сдается мне что это уже спрашивали выше, но как то это было не очень внятно ясно для меня.
Короткий и простой ответ таков: методика, сама по себе, гарантирует уничтожение всех объектов, но она не гарантирует необходимое время жизни объекта.
Если же эту методику объединить с упомянутой в статье идеей строгой инкапсуляции, то в большинстве случаев и эта проблема будет решена. Строгая инкапсуляция говорит о том, что объект передаёт указатели на свои члены в ходе исполнения своих функций-членов. То есть, вне жизни объекта, доступа к указателям на его члены просто не будет, ещё на этапе компиляции.
Возможно, мой дзен проектирования не так крут, поэтому в сложных динамических случаях я пару раз сталкивался с необходимостью передавать указатель на объект, не имея возможности гарантировать его существования в момент, когда (отложенный) обрабатывающий код будет выполнен. В этих случаях я пользовался штатным классом фреймворка, который по сути представляет собой вариант умного указателя, который обнуляет внутренний указатель при вызове деструктора объекта. Вполне допускаю, что возможно более правильно спроектировать систему, чтобы умные указатели не были нужны даже в этом случае.
Для архива — это все реализовано в Qt и работает уже более десяти лет. «Parent-child relationships» — все наследовано от QObject и любой QObject можно создавать с указанием родителя — тогда при разрешении родителя будут разрушены и потомки. «Implicit sharing» — большая часть объектов это «smart pointer» с автоматическим copy on write.
Sign up to leave a comment.

Articles