Менеджер памяти своими руками

Добавил пользователь Евгений Кузнецов
Обновлено: 03.09.2024

Это статья о том, как написать простой memory allocator на языке C. Мы реализуем malloc(), calloc(), realloc() и free().

Как работает виртуальная память

Память, занимаемая скомпилированной программой, делится на пять сегментов:

Сегмент кода. Сегмент кода иногда также называют сегментом text. В нем располагаются машинные команды программы.

Сегмент данных и BSS. Сегмент данных (data) и сегмент BSS(Block Started by Symbol) предназначены для хранения глобальных и статических переменных программы. В сегменте data хранятся инициализированные глобальные и статические переменные, а в bss — такие же переменные без инициализации. Эти сегменты доступны для записи, но их размер также фиксирован.

Сегмент кучи. Сегмент кучи (heap) непосредственно доступен программисту. Он может выделять в этом сегменте блоки памяти и использовать их по своему усмотрению. Примечательная особенность кучи — ее непостоянный размер, способный увеличиваться или уменьшаться по мере необходимости.

Сегмент стека. Сегмент стека (stack) — тоже переменного размера; он служит временным хранилищем локальных переменных и контекстов функций при их вызове. Когда программа вызывает некоторую функцию, та получает собственный набор переданных ей переменных, а код функции располагается по отдельному адресу в сегменте текста (кода). Поскольку при вызове функции изменяются контекст и EIP, в стек помещаются передаваемые переменные, адрес, к которому EIP должен вернуться по завершении работы функции, и локальные переменные этой функции. Все эти данные хранятся вместе на стеке в так называемом кадре стека. Стек содержит много кадров.

Ну и теперь, если мы хотим выделить память в куче, нам нужно попросить систему сдвинуть brk вверх. Аналогично, если мы хотим освободить память, то нужно сдвинуть brk вниз.

Для работы с указателем program brake на Unix-like системах доступен системный вызов sbrk():

Вызов sbrk(0) возвращает адрес конца кучи.
Вызов sbrk(x), где x > 0 — увеличивает brk на x байт.
Вызов sbrk(x), где x

Здравствуйте, INsideR, Вы писали:

INR>Недавно услышал, что стандартные средства для управления памяти не годятся для больших проектов, не могли бы вы сказать, где почитать про менеджеры памяти своими руками, или готовый исходник дать. Язык C++.

INR>Недавно услышал, что стандартные средства для управления памяти не годятся для больших проектов, не могли бы вы сказать, где почитать про менеджеры памяти своими руками, или готовый исходник дать. Язык C++.

А что ж тот, кто тебе это сказал, не прдлохил тебе своего знатного менеджера?
Я так понимаю, что скорее всего, стандартный менеджер все таки хорош.

Здравствуйте, , Вы писали:

А>А что ж тот, кто тебе это сказал, не прдлохил тебе своего знатного менеджера?
А>Я так понимаю, что скорее всего, стандартный менеджер все таки хорош.
До определенного момента — да. Но ьбывает, что прижимает. К примеру: в виндовз (W2k Sp3, тестировались VC6 и MinGW 3.2) менеджер памяти по умолчанию выделаяет блоки кусками по 16 байт (по моим наблюдениям и без учета сервисной информации). Есть задачи, для которых это очень плохо. Например, построение дома для XML (для чего, собсно я все это и заварил).

При допущении, что подавляющее большинство объектов — меньше 16 байт, был применен Loki-like allocator(он самый, но переписанный с std::vector на наш вектор (организационные причины)).

Выигрыш в объеме памяти составил прмерно 300%: 270 Mb vs 70 на тесте. Однако, скорости это не прибавило ни капли (если не считать эффект убиения своппинга, т.к. его считать тяжело, и не честно). Так-что, выигрыш не на лицо. Однако, стоит заметить, что отпимизация не проиграла в скорости только благодаря однопоточной архитектуре (иначе требуются блокировки, и тут в скорости со стандартным аллокатором будет тяжко бороться.

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

Здравствуйте, MaximE, Вы писали:

ME>Здравствуйте, Kaa, Вы писали:

Kaa>>До определенного момента — да. Но ьбывает, что прижимает. К примеру: в виндовз (W2k Sp3, тестировались VC6 и MinGW 3.2) менеджер памяти по умолчанию выделаяет блоки кусками по 16 байт (по моим наблюдениям и без учета сервисной информации). Есть задачи, для которых это очень плохо. Например, построение дома для XML (для чего, собсно я все это и заварил).

ME>Откуда информация про блоки по 16 байт?

ME>

Hасколько проще была бы жизнь, если бы она была в исходниках.

I> Недавно услышал, что стандартные средства для управления памяти не
I> годятся для больших проектов, не могли бы вы сказать, где почитать про
I> менеджеры памяти своими руками, или готовый исходник дать. Язык C++.
Все зависит от того, зачем это нужно. Мое мнение — в большинстве случаев собственный менеджер памяти это вид оптимизации. А преждевременная оптимизация, как известно ни к чему хорошем не приводит. Так что нужно сначала определиться, дейсвительно ли есть проблемы с памятью.
Есть еще второй вариант — писать собственный менеджер со специфическими фичами — сборка мусора например, или общая для нескольких процессов память. Тут уже надо думать и смотреть по ситуации.

Вывод: меньше слушай, больше думай и экспериментируй

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

Здравствуйте, Kaa, Вы писали:

Kaa>При допущении, что подавляющее большинство объектов — меньше 16 байт, был применен Loki-like allocator

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

Могу добавить что тот-же Loki-like allocator (он самый, только упрощенный и заточенный под конкретную задачу) дал прибавку в скорости раза эдак в 4-ре. Речь идет об обработке реал-тайм цен, выделение и освобождение порядка 50000 небольших (100-200 байт) объектов в секунду. На счет блокировок в многопоточной архитектуре вопрос спорный, стандартный аллокатор в любом случае использует блокировки, а использование своего снимает нагрузку (кол-во блокировок) со стандартного.

There are 10 types of people in the world, those who don't understand binaries, those who do, and those who understand not only binaries.

Здравствуйте, Slamin, Вы писали:

S>На счет блокировок в многопоточной архитектуре вопрос спорный, стандартный аллокатор в любом случае использует блокировки, а использование своего снимает нагрузку (кол-во блокировок) со стандартного.

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

Здравствуйте, Kaa, Вы писали:

Kaa>До определенного момента — да. Но ьбывает, что прижимает. К примеру: в виндовз (W2k Sp3, тестировались VC6 и MinGW 3.2) менеджер памяти по умолчанию выделаяет блоки кусками по 16 байт (по моим наблюдениям и без учета сервисной информации). Есть задачи, для которых это очень плохо. Например, построение дома для XML (для чего, собсно я все это и заварил).

Откуда информация про блоки по 16 байт?

Здравствуйте, MaximE, Вы писали:

ME>Откуда информация про блоки по 16 байт?
Я ж сказал: мерял 1000000 объектов по одному байту занимают столько же памяти, сколько 1000000 объектов по 16.

Можешь попробовать сам:

W2k SP3 VC6 SP5 и MinGW 3.2.2 дают:
1 — 16 байт == 27 Mb
17 — уже 43

Здравствуйте, Sergeem, Вы писали:

S>Здравствуйте, INsideR, Вы писали:

INR>>Недавно услышал, что стандартные средства для управления памяти не годятся для больших проектов, не могли бы вы сказать, где почитать про менеджеры памяти своими руками, или готовый исходник дать. Язык C++.

S>Есть очень хороший менеджер памяти — Doug Lea malloc. Есть исходники
S>и некоторые объяснения по поводу алгоритма работы. Правда, у этого
S>аллокатора есть проблема с очень маленькими объектами (

Я провёл тест с этим аллокатором, он у меня получился быстрее чем VC 7.0 более чем в 10 раз, а можно его использовать, для переопределения new и delete, new[] и delete[]

Здравствуйте, Sergeem, Вы писали:

S>Есть очень хороший менеджер памяти — Doug Lea malloc. Есть исходники
S>и некоторые объяснения по поводу алгоритма работы. Правда, у этого
S>аллокатора есть проблема с очень маленькими объектами (

Похоже, что это не проблема, а ограничение всех универсальных менеджеров памяти. Вот что пишет сам Doug Lea:

Здравствуйте, INsideR, Вы писали:

INR>Я провёл тест с этим аллокатором, он у меня получился быстрее чем VC 7.0 более чем в 10 раз, а можно его использовать, для переопределения new и delete, new[] и delete[]

Что за тест? Ultimate Test?

Я прочитал эту статью. Мне она показалась немного наивной для такого
сурьезного издания как CUJ. Например, как решается проблема фрагментации
памяти?

Вообще, все эти "быстрые" аллокаторы, сделанные на коленке,
у меня вызывают подозрение, что где-то внутри прячутся ТАКИЕ
грабли, наступить на которые в большом проекте будет
очень-очень больно.

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

Во вторых, при постоянном выделение-освобождение памяти идет ее фрагментация. Если в системе ограниченный объем памяти, то наступит момент, когда не удастся выделить новый кусок связной памяти. Причем у вас может быть свободно 50 мегабайт, а выделить не удастся даже 10.

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

2. Используйте хранилища данных

Храните объекты вместе в одном куске памяти. Особенно если у вас есть коллекция объектов, с которыми вы будете работать одновременно. Пробегаться по такой коллекции будет значительно эффективнее, если все объекты будут последовательно в памяти.

Получение данных из памяти идет блоком в 64 байта. Это значит что нельзя получить меньше. Когда вы идете по коллекции объектов, то при получении первого объекта, получаются 64 байта начиная с первого байта объекта (это не всегда так, но в данном случае это не важно).

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

Обращение к L1 — 20 тактов.
Обращение к L2 — 100 тактов.
Обращение к общей памяти — 600 тактов.

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

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

3. Храните одинаковые данные вместе

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

Ну и конечно где нибудь будет коллекция таких объектов, например такая:

При проходе по такой коллекции для получения каждого нового элемента будет обращение к памяти. Более того, если нужно будет всего лишь найти объекты у которых m_life == false, то нужно будет грузить в память все целиком.

Решением является хранение однотипных данных в общих хранилищах. Создаем массив для Matrix4x4 и для BoundingSphere, где будут находиться данные от всех объектов. Каждый объект будет содержать указатель на свои данные. Наш объект изменится таким образом:

Одна только эта реорганизация ускорила выполнение GetBoundingSphere для всех объектов на 30 процентов. Это произошло не только потому, что размер объекта стал меньше (больше влазит в кеш) и математические данные лежат в смежной памяти, поэтому и проводить вычисления с ними значительно быстрее.

4. Работайте не с объектами а с коллекциями объектов

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

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

5. Поблочное выделение памяти

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

Для начала реорганизуем структуру в соответствии с пунктом 3.

Неправильный вариант выделения памяти:

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

6. Учитывайте выравнивание

Учитывайте выравнивание типов. Располагайте наиболее большие типы вначале структуры. Группируйте типы с равным размером, располагая переменные подряд. Помните, что double выравнивается минимум по 8.

7. Знайте размер типов

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

Данные методы имеют отношение к технике, называемой Data oriented design. Можете почитать про это более подробно тут: Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf.

Я бы хотел написать собственный менеджер памяти. Целевой язык - это С++, и цель менеджера памяти заключается в основном в отладке. Он должен обнаруживать двойные разряды, перезапись памяти и т.д. И, конечно же, я хотел бы узнать об управлении памятью.

Может ли кто-нибудь дать мне подсказку, так что ресурсы, где я могу научиться писать такой менеджер памяти?

Благодарим вас за помощь.

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

Кроме того, поскольку вы упоминаете, что хотите создать диспетчер памяти, который полезен для отладки, вам может потребоваться прочитать эту статью разработчики Memcheck/Valgrind (замечательный отладчик памяти для Linux). В нем подробно описывается, как они отслеживают все метаданные (независимо от того, определен ли конкретный байт, проинтегрирован и т.д.) В memchck. Он немного подробный, но он хорошо читает о том, как сделать масштабируемую и эффективную динамическую проверку памяти.

Читайте также: