что представляет собой фрагментированная память

Алёна C++

программирование для прагматиков

понедельник, июня 29, 2015

Фрагментация памяти в C++ приложениях

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

Чем это плохо? Во-первых, память может внезапно закончиться. Во-вторых может просесть производительность. Вот тут можно почитать историю как это выглядит на практике: Out of memory

Boost.Pool. Там есть несколько разных интерфейсов, я использовала object_pool, который помогает эффективнее создавать и удалять большое количество сравнительно маленьких объектов.

Также я видела разное креативное использование placement new, как правило его можно заменить Boost.Pool’ом.

10 коммент.:

А как же слаб алокейторы?

А как же слаб алокейторы?

Это нечто Linux-специфичное, а я-то под Windows пишу. По фунциональности это примерно то же, что и object_pool.

SLAB это не Linux-specific(вообще впервые появился в Solaris).
Насколько я понимаю Boost.Pool довольно нетривиально использовать в контексте singleton так как вручную приходится освобождать выделенную pool’ом память. И если я правильно понимаю то будет создано 2 независимых pool’а для int и bool, и что еще хуже, для int и struct .
Я бы рекомендовал использовать jemalloc. Вроде есть сборки и под MS Windows.

slab / arena / pool дают отличный результат, если система изначально строилась с учетом кастомных аллокаторов. Если есть уже работающий код с, например, STL контейнерами (дающими иллюзию легкой кастомизации аллокаторов), то кроме jemalloc можно попробовать tcmalloc.
Для полноты картины надо упомянуть, что, кажется, с седьмой винды, (2013 сервер), в винде low fragmentation heap включен по дефолту, и он старается делать примерно то же, что и jemalloc / tcmalloc. Только имплементация у него закрытая, на статистику его не взглянешь, и я знаю как минимум один большой виндовый проект, на котором tcmalloc в тестах показал себя сильно лучше.

В Windows есть Low-fragmentation Heap, которая весьма неплохо справляется с фрагментацией. Бороться с фрагментацией приходится только в весьма специфичных случаях. Хотя куча в таком режиме по умолчанию работает в Vista, а в более ранних версиях ее можно включить, но реально хорошо это работает начиная с Windows 7. Поэтому в большинстве случаев лучше не пытаться решать проблему фрагментации, пока не ясно, что она реально будет проявляться. Это просто потому, что может выйти хуже, чем если ничего не делать.

Win7 вообще довольно удачная вышла в плане разных плюшек. Тот же пул потоков в Windows 7 работает гораздо лучше, чем в Windows XP. Просто потому, что в WinXP он не умеет адекватно использовать более 2-х ядер процессора.

И еще хотел бы отметить насчет того, что не только С++ программист управляет памятью самостоятельно. При разработке серьезных приложений, в общем случае неплохо бы понимать что происходит за кулисами. Создавая программы на C# тоже можно легко попасть в неприятную ситуацию с памятью.

tcmalloc неплохая вещь, некоторый эффект даёт.

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

В общем это больше проблема x32 легаси приложений, которые по каким то причинам пока
не получается перевести на x64.
как я понимаю для x64 приложений такой проблемы быть не должно.
Представте себе что у вас изза фрагментации на x32 адресном пространстве иногда заканчиваются
непрерывные номерки. А теперь представьте себе что вы работаете с x64 адресным пространством,
где адресного пространства в 4 миллиарда раз больше.

Если всетаки вынуждены работать с x32 и есть такая проблема, то есть рекомендации
«хранить» отельно объекты с разным временем жизни. То есть отделять долгоживущие от
короткоживущих в адресном пространстве. Для этого можно завести отдельную кучу например и хранить
там всю долгоживущую мелочь к примеру чтоб она не била пространство где живут к примеру
короткоживущие большие объекты. Использование разных куч как то гарантирует разделенность
в пространстве разных по природе объектов.

упомянутый выше LFH флаг помог только в плане увеличить производительность аллокаций на win 2003 server (x32)
когда на «свежей» куче загрузка отрабатывала скажем за 5 сек, а потом уже тупила 20-40-60 сек.

Источник

Фрагментация (вычисления)

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

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

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

Внутренняя фрагментация

Внешняя фрагментация

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

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

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

Фрагментация данных

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

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

Фрагментация 0% означает, что вся свободная память находится в одном большом блоке; фрагментация составляет 90% (например), когда имеется 100 МБ свободной памяти, но самый большой свободный блок памяти для хранения составляет всего 10 МБ.

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

Сбой хранилища

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

Снижение производительности

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

Некоторые файловые системы флеш-памяти имеют несколько различных видов внутренней фрагментации, включая «мертвое пространство» и «темное пространство». [5]

Источник

СОДЕРЖАНИЕ

Типы фрагментации

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

Основной принцип

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

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

Внутренняя фрагментация

Внешняя фрагментация

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

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

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

Фрагментация данных

Обзор

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

Фрагментация 0% означает, что вся свободная память находится в одном большом блоке; фрагментация составляет 90% (например), когда имеется 100 МБ свободной памяти, но самый большой свободный блок памяти для хранения составляет всего 10 МБ.

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

Проблемы

Сбой хранилища

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

Снижение производительности

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

Аналогичные явления

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

Источник

Что такое фрагментация памяти?

Я слышал, что термин «фрагментация памяти» используется несколько раз в контексте распределения динамической памяти С++. Я нашел несколько вопросов о том, как иметь дело с фрагментацией памяти, но не может найти прямой вопрос, который касается этого. Итак:

11 ответов

Представьте, что у вас есть «большое» (32 байта) пространство свободной памяти:

Теперь выделите часть (5 распределений):

Теперь освободите первые четыре выделения, но не пятые:

Теперь попробуйте выделить 16 байт. К сожалению, я не могу, хотя там почти вдвое больше свободного.

В системах с виртуальной памятью фрагментация представляет собой менее сложную проблему, чем вы думаете, потому что большие распределения должны быть только смежными в виртуальном адресном пространстве, а не в физическом адресном пространстве. Итак, в моем примере, если бы у меня была виртуальная память с размером страницы в 2 байта, я мог бы сделать 16-байтовое распределение без проблем. Физическая память будет выглядеть так:

тогда как виртуальная память (намного больше) может выглядеть так:

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

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

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

Что такое фрагментация памяти?

Как узнать, является ли фрагментация памяти проблемой для моего приложения? Какая программа, скорее всего, пострадает?

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

Каковы хорошие общие способы борьбы с фрагментацией памяти?

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

Предположим, что для простого примера игрушек у вас есть десять байт памяти:

Теперь выделите три трехбайтовых блока, имена A, B и C:

Теперь освободите блок B:

Теперь, что произойдет, если мы попытаемся выделить четырехбайтовый блок D? Ну, у нас есть четыре байта свободной памяти, но у нас нет четырех непрерывных байтов свободной памяти, поэтому мы не можем выделить D! Это неэффективное использование памяти, потому что мы должны были бы хранить D, но мы не смогли. И мы не можем перемещать C, чтобы освободить место, потому что очень вероятно, что некоторые переменные в нашей программе указывают на C, и мы не можем автоматически находить и изменять все эти значения.

Как вы знаете, что это проблема? Наилучшим образом, самым большим признаком является то, что размер вашей виртуальной памяти вашей программы значительно больше, чем объем памяти, который вы фактически используете. В реальном мире у вас будет много более десяти байтов памяти, поэтому D просто получит выделение, начиная с байта 9, а байты 3-5 останутся неиспользованными, если вы позже не выделили что-то три байта или меньше.

В этом примере 3 байта не так много, чтобы тратить их, но рассмотрим более патологический случай, когда два распределения пары байтов, например, на десять мегабайт в памяти, и вам нужно выделить блок размер 10 мегабайт + 1 байт. Вы должны обратиться к ОС за более чем 10 мегабайтами больше виртуальной памяти, чтобы сделать это, даже если вы просто один байт застенчивый от наличия достаточно пространства.

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

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

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

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

Используйте хороший распределитель памяти. IIRC, те, кто использует стратегию «наилучшего соответствия», как правило, намного превосходят, избегая фрагментации, если немного медленнее. Однако было также показано, что для любой стратегии распределения существуют патологические наихудшие случаи. К счастью, типичные шаблоны распределения большинства приложений на самом деле относительно мягки для обработки распределителей. Там есть куча бумаг, если вас интересуют детали:

Обновление:
Google TCMalloc: Thread-Caching Malloc
Было обнаружено, что неплохо справляется с фрагментацией в продолжительном процессе.

Я разрабатываю серверное приложение, у которого были проблемы с фрагментацией памяти на HP-UX 11.23/11.31 ia64.

Это выглядело так. Был процесс, который делал выделение памяти и освобождение памяти и работал в течение нескольких дней. И даже несмотря на отсутствие утечек памяти, потребление памяти в процессе продолжало расти.

Источник