Использование памяти Linux на вершине при использовании std :: vector против std :: list
Я заметил интересное поведение в Linux в отношении использования памяти (RES), сообщенное top, Я приложил следующую программу, которая распределяет пару миллионов объектов в куче, каждый из которых имеет буфер размером около 1 килобайта. Указатели на эти объекты отслеживаются либо std::listили std::vector, Интересно, что я заметил, что если я использую std::list, использование памяти сообщается top никогда не меняется во время сна. Однако, если я использую std::vectorиспользование памяти упадет почти до 0 во время этих снов.
Моя тестовая конфигурация:
Fedora Core 16
Ядро 3.6.7-4
g ++ версия 4.6.3
Что я уже знаю:
1. std :: vector перераспределяет (удваивая свой размер) по мере необходимости.
2. std :: list (я верю) выделяет свои элементы по 1 за раз
3. и std :: vector, и std :: list по умолчанию используют std :: allocator для получения своей фактической памяти
4. Программа не подтекает; Valgrind заявил, что утечки невозможны.
Что меня смущает:
1. И std :: vector, и std :: list используют std :: allocator. Даже если std :: vector выполняет пакетное перераспределение, разве std :: allocator не будет передавать память почти в одинаковом порядке для std :: list и std :: vector? В конце концов, эта программа однопоточная.
2. Где я могу узнать о поведении распределения памяти в Linux. Я слышал заявления о том, что Linux хранит ОЗУ для процесса даже после его освобождения, но я не знаю, гарантируется ли такое поведение. Почему использование std :: vector так сильно влияет на это поведение?
Большое спасибо за чтение этого; Я знаю, что это довольно нечеткая проблема. «Ответ», который я ищу здесь, заключается в том, является ли это поведение «определенным» и где я могу найти его документацию.
#include <string.h>
#include <unistd.h>
#include <iostream>
#include <vector>
#include <list>
#include <iostream>
#include <memory>
class Foo{
public:
Foo()
{
data = new char[999];
memset(data, 'x', 999);
}
~Foo()
{
delete[] data;
}
private:
char* data;
};
int main(int argc, char** argv)
{
for(int x=0; x<10; ++x)
{
sleep(1);
//std::auto_ptr<std::list<Foo*> > foos(new std::list<Foo*>);
std::auto_ptr<std::vector<Foo*> > foos(new std::vector<Foo*>);
for(int i=0; i<2000000; ++i)
{
foos->push_back(new Foo());
}
std::cout << "Sleeping before de-alloc\n";
sleep(5);
while(false == foos->empty())
{
delete foos->back();
foos->pop_back();
}
}
std::cout << "Sleeping after final de-alloc\n";
sleep(5);
}
Решение
Освобождение памяти осуществляется на основе фрагментов. Вполне возможно, что когда вы используете список, память фрагментируется на мелкие кусочки.
Когда вы выделяете с помощью вектора, все элементы хранятся в одном большом фрагменте, поэтому коду освобождения памяти легко сказать: «Боже, у меня здесь очень большая свободная область, я собираюсь выпустить ее обратно в ОПЕРАЦИОННЫЕ СИСТЕМЫ». Также вполне возможно, что при увеличении вектора распределитель памяти переходит в «режим больших чанков», в котором используется метод выделения, отличный от «режима маленьких чанков» — например, если вы выделяете более 1 МБ, код выделения памяти может видеть, что как хорошее время, чтобы начать использовать другую стратегию, и просто попросить у ОС «идеально подходящую» часть памяти. Этот большой блок очень легко вернуть обратно в ОС, когда он освобождается.
С другой стороны, если вы добавляете в список, вы постоянно запрашиваете маленькие биты, поэтому распределитель использует другую стратегию: запрашивать большой блок, а затем выдавать маленькие порции. Убедиться в том, что ВСЕ блоки внутри чанка освобождены, сложно и отнимает много времени, поэтому распределитель вполне может «не беспокоиться», поскольку есть вероятность, что в нем есть некоторые области, «все еще используемые», а затем он может в любом случае не должен быть освобожден.
Я также добавил бы, что использование «top» в качестве меры памяти не является особенно точным методом и очень ненадежным, так как очень сильно зависит от того, что делает ОС и библиотека времени выполнения. Память, принадлежащая процессу, может не быть «резидентной», но процесс все еще не освободил ее — она просто «не присутствует в реальной памяти» (вместо этого в разделе подкачки!)
И на ваш вопрос «это где-то определено», я думаю, что это в том смысле, что исходный код библиотеки C / C ++ определяет его. Но это не определено в том смысле, что где-то написано, что «это то, как это должно работать, и мы обещаем никогда не передавать это». Библиотеки, поставляемые как glibc и libstdc ++, не скажут, что они изменят внутреннюю часть malloc, free, new и delete по мере изобретения новых технологий и идей — некоторые могут сделать вещи лучше, другие могут сделать это хуже, для данного случая. сценарий.
Как было отмечено в комментариях, память не привязана к процессу. Если ядро считает, что память лучше использовать для чего-то другого [и ядро здесь всемогуще], то оно «украдет» память из одного запущенного процесса и передаст ее другому. Особенно память, которая не была «затронута» в течение долгого времени.
Другие решения
1 И std :: vector, и std :: list используют std :: allocator. Даже если std :: vector выполняет перераспределение пакетов, std :: allocator не будет
раздача памяти почти в том же порядке в std :: list и
станд :: вектор? В конце концов, эта программа однопоточная.
Ну и в чем отличия?
-
std::listраспределяет узлы один за другим (каждому узлу нужны два указателя в дополнение к вашемуFoo *). Кроме того, он никогда не перераспределяет эти узлы (это гарантируется требованиями недействительности итератора дляlist). Итакstd::allocatorзапросит последовательность фрагментов фиксированного размера из базового механизма (возможно,mallocкоторый в свою очередь будет использоватьsbrkили жеmmapсистемные вызовы). Эти чанки фиксированного размера могут быть больше, чем узел списка, но в этом случае все они будут иметь одинаковый размер чанка по умолчанию, используемыйstd::allocator, -
std::vectorвыделяет непрерывный блок указателей без затрат на ведение бухгалтерского учета (это все в родительском объекте вектора). Каждый разpush_backпереполнит текущее распределение, вектор выделит новый, больший фрагмент, переместит все в новый блок и освободит старый. Теперь новый кусок будет примерно в два раза (или в 1,6 раза, или что-то еще) размером со старым, что требуется для сохранения амортизированное постоянное время гарантия дляpush_back, Итак, довольно быстро, я ожидаю, что размеры, которые он запрашивает, превысят любой разумный размер блока по умолчанию дляstd::allocator,
Итак, интересные взаимодействия различны: один между std::vector и основной механизм распределителя, и один между std::allocator сам и этот основной механизм.
2 Где я могу узнать о поведении распределения памяти в Linux. Я слышал заявления о том, что Linux хранит ОЗУ для процесса
даже после того, как это освобождает его, но я не знаю, если это поведение
гарантировано. Почему использование std :: vector так сильно влияет на это поведение?
Есть несколько уровней, которые могут вас заинтересовать:
- Собственная схема размещения контейнера: которая, как мы надеемся, описана выше
- обратите внимание, что в реальных приложениях способ контейнера используемый так же важно
std::allocatorсам, который может обеспечить уровень буферизации для небольших выделений- Я не думаю, что это требуется стандартом, так что это зависит от вашей реализации
- Основной распределитель, который зависит от вашего
std::allocatorреализация (это может быть, например,mallocоднако это реализовано вашим libc) - Схема виртуальной машины, используемая ядром, и ее взаимодействие с тем, что в конечном итоге использует syscall (3)
В вашем конкретном случае я могу подумать о возможном объяснении того, что вектор явно высвобождает больше памяти, чем список.
Предположим, что вектор заканчивается одним непрерывным распределением, и множество Foos также будут распределены непрерывно. Это означает, что когда вы освобождаете всю эту память, довольно легко понять, что большинство нижележащих страниц действительно бесплатны.
Теперь рассмотрим, что распределения узлов списка чередуются 1: 1 с Foo экземпляров. Даже если распределитель выполнил некоторое пакетирование, кажется, что куча гораздо более фрагментирована, чем в std::vector дело. Поэтому, когда вы освобождаете выделенные записи, потребуется определенная работа, чтобы выяснить, свободна ли нижележащая страница, и нет особой причины ожидать, что это произойдет (если последующее большое выделение не поощрит объединение записей кучи).
Ответ — оптимизация malloc «fastbins».
std :: list создает крошечные (менее 64 байт) выделения, и когда он освобождает их, они фактически не освобождаются — но переходят в пул fastblock.
Такое поведение означает, что куча остается фрагментированной даже после того, как список очищен и, следовательно, он не возвращается в систему.
Вы можете использовать malloc_trim (128 * 1024), чтобы принудительно очистить их.
Или используйте mallopt (M_MXFAST, 0), чтобы вообще отключить fastbins.
Я считаю, что первое решение будет более правильным, если вы его называете, когда вам больше не нужна память.
Меньшие куски проходят через brk и корректируют сегмент данных и постоянное разбиение и слияние, а более крупные куски отображают процесс немного меньше. больше информации (PDF)
также исходный код ptmalloc.