Использование памяти Linux на вершине при использовании std::vector против std::list

Question

Я заметил интересное поведение в 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);
}

Answer 1

Освобождение памяти осуществляется на основе фрагментов. Вполне возможно, что когда вы используете список, память фрагментируется на мелкие кусочки.

Когда вы выделяете с помощью вектора, все элементы хранятся в одном большом фрагменте, поэтому для кода освобождения памяти легко сказать: "Боже, у меня здесь очень большая свободная область, я собираюсь выпустить ее обратно в ОПЕРАЦИОННЫЕ СИСТЕМЫ". Также вполне возможно, что при увеличении вектора распределитель памяти переходит в "режим больших чанков", в котором используется метод выделения, отличный от "режима маленьких чанков" - например, если вы выделяете более 1 МБ, код выделения памяти может видеть, что как хорошее время, чтобы начать использовать другую стратегию, и просто спросить у ОС "идеально подходящую" часть памяти. Этот большой блок очень легко вернуть обратно в ОС, когда он освобождается.

С другой стороны, если вы добавляете в список, вы постоянно запрашиваете небольшие биты, поэтому распределитель использует другую стратегию: запрашивать большой блок, а затем выдавать небольшие порции. Убедиться в том, что ВСЕ блоки в блоке были освобождены, сложно и отнимает много времени, поэтому распределитель вполне может "не беспокоиться", поскольку есть вероятность, что в нем есть некоторые области, "все еще используемые", и тогда он может в любом случае не быть освобожденным.

Я также хотел бы добавить, что использование "top" в качестве меры памяти не является особенно точным методом и очень ненадежным, поскольку очень сильно зависит от того, что делает ОС и библиотека времени выполнения. Память, принадлежащая процессу, может не быть "резидентной", но процесс все еще не освободил ее - она ​​просто "не присутствует в реальной памяти" (вместо этого в разделе подкачки!)

И на ваш вопрос "это где-то определено", я думаю, что это в том смысле, что исходный код библиотеки C/C++ определяет его. Но это не определено в том смысле, что где-то написано: "Вот как это должно работать, и мы обещаем никогда не передавать его". Библиотеки, поставляемые как glibc и libstdC++, не скажут, что они изменят внутреннюю часть malloc, free, new и delete по мере изобретения новых технологий и идей - некоторые могут сделать вещи лучше, другие могут сделать это хуже для данного сценарий.

Как было отмечено в комментариях, память не привязана к процессу. Если ядро ​​считает, что память лучше использовать для чего-то другого [и здесь ядро ​​всемогуще], то оно "украдет" память у одного запущенного процесса и передаст ее другому. Особенно память, которая не была "затронута" в течение долгого времени.

Answer 2

1 И std::vector, и std::list используют std::allocator. Даже если std::vector выполняет пакетное перераспределение, разве std:: allocator не распределяет память почти в том же порядке, что и std::list и std::vector? В конце концов, эта программа однопоточная.

Ну и в чем отличия?

• 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 так сильно влияет на это поведение?

Есть несколько уровней, которые могут вас заинтересовать:

1. Собственная схема размещения контейнера: которая, как мы надеемся, описана выше
   • обратите внимание, что в реальных приложениях способ использования контейнера также важен
2. std::allocator сам, который может обеспечить уровень буферизации для небольших выделений
   • Я не думаю, что это требуется стандартом, так что это зависит от вашей реализации
3. Основной распределитель, который зависит от вашего std::allocator реализация (это может быть, например, mallocоднако это реализовано вашим libc)
4. Схема виртуальной машины, используемая ядром, и ее взаимодействие с тем, что в конечном итоге использует syscall (3)

---

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

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

Теперь рассмотрим, что распределения узлов списка чередуются 1:1 с Foo экземпляров. Даже если распределитель выполнил некоторое пакетирование, кажется, что куча гораздо более фрагментирована, чем в std::vector дело. Поэтому, когда вы освобождаете выделенные записи, потребуется определенная работа, чтобы выяснить, свободна ли нижележащая страница, и нет особой причины ожидать, что это произойдет (если последующее большое выделение не поощрит объединение записей кучи).

Answer 3

Ответ - оптимизация malloc "fastbins". std::list создает крошечные (менее 64 байтов) выделения, и когда он освобождает их, они фактически не освобождаются - но переходят в пул fastblock. Такое поведение означает, что куча остается фрагментированной даже после того, как список очищен и, следовательно, он не возвращается в систему.

Вы можете использовать malloc_trim(128*1024), чтобы принудительно очистить их. Или используйте mallopt(M_MXFAST, 0), чтобы вообще отключить fastbins.

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

Answer 4

Меньшие куски проходят через brk и корректируют сегмент данных и постоянное разбиение и слияние, а более крупные куски отображают процесс немного меньше. больше информации ( PDF)

также исходный код ptmalloc.