LINUX.ORG.RU

Фрагментация/дефрагментация кучи?

 


1

6

Будет много букв, но проблема довольно сложная и странная.

Есть некоторый замороченный код (числодробилка), работающий на кластере под MPI. В процессе работы в рамках одной итерации накапливается информация (в виде маленьких структурок по 32 байта каждая, будем называть их треками), затем информация перелопачивается нетривиальным образом и все по новой. При этом ключевым ресурсом является доступная память.

Заранее число треков неизвестно, хотя можно строить какие то оценки. Сейчас накопление происходит в контейнеры устроенные как односвязный список блоков, каждый блок по 32К. Когда очередной блок полностью заполнен, при помощи new выделяется новый блок и т.д. Таких списков в рамках одного процесса много, и они заполняются параллельно.

При обработке информации последовательно берется очередной список, треки из него перепаковываются/переупорядочиваются, некоторые выбрасываются, результаты пишутся в обычный вектор который потом будет дальше обработан. Важно что при этом память, выделенная под список, должна быть освобождена - иначе потом ничего не влезет. Общий размер занятой под треки памяти порядка 500-1000М, таких процессов на одном узле пасется несколько (по числу ядер), и кроме этих данных они оперируют еще всяким разным. Поскольку никакой виртуальной памяти (свопа) нет, когда память заканчивается задача крэшится (все 1000 процессов), поэтому прежде чем переходить к очередному этапу процесс сморит сколько в систем свободной памяти вообще, и ждет пока освободится нужное кол-во.

Есть три вопроса:

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

2) На одном из доступных кластеров вообще наблюдается утечка памяти, т.е. память в систему не возвращается. Отличается кластер от остальных древним и странным компайлером - там связка icpc17 и gcc4.2 (нет, я не могу на том кластере выбрать что то более свежее). Может ли утечка быть связана с фрагментацией?

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

★★★★

память в систему не возвращается

Кто сказал? Можно верить только valgrind, и то с опаской.

RazrFalcon ★★★★★
()

google://arena allocation

anonymous
()

Firefox был вынужден бороться с этой проблемой, может быть тебе поможет изучить то, что они делали:

https://blog.mozilla.org/nnethercote/category/memory-allocation/ https://bugzilla.mozilla.org/show_bug.cgi?id=276342 https://bugzilla.mozilla.org/show_bug.cgi?id=666058#c31

На самом деле, насколько я понимаю это именно та ситуация когда ты пишешь свой аллокатор.

(ну или переходишь на managed язык).

Disclaimer: Я ни разу не специалист в этой области, просто пробую помочь чем могу. Я боюсь, если ты будешь решать эту проблему радикально, то ты в результате получишь что-то вроде Metaspace в Java 8: https://dzone.com/articles/java-8-permgen-metaspace

DiKeert ★★
()
man -P 'less -p THRESHOLD' mallopt

По умолчанию glibc использует mmap для блоков больше или равных 128 КиБ. С помощью mallopt это можно изменить, либо же можно начать выделять блоки по 128 КиБ. Если всё будет выделяться через mmap, то каждый delete должен сразу возвращать память системе без дополнительных ухищрений.

xaizek ★★★★★
()
Последнее исправление: xaizek (всего исправлений: 2)

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

Зачем ты вообще отдаешь память системе, если потом надо будет ее опять же у нее просить? Просто не освобождай.

3) Вообще насколько такая фрагментация плоха, и если плоха то как с ней бороться?

Так же, как и в любом сборщике мусора - дефрагментацией.

anonymous
()

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

zamazan4ik ★★
()

Я бы для начала заменил самопальный список на std::deque и включил в проект нестандартный аллокатор памяти (например, tcmalloc https://github.com/gperftools/gperftools). Включил в проект значит включил исходники в репозиторий проекта (возможно, в виде git submodule) и собирал и линковал аллокатор вместе с проектом (статикой или динамикой с rpath). В этом случае будет наплевать на древность gcc и стандартного аллокатора на ноде (tcmalloc нужны лишь системные вызовы sbrk и mmap, которые есть в любом ядре).

Если эти манипуляции не помогут - продумал бы копирование перед очередной итерацией обработанных данных в отдельный участок памяти (выделенный через mmap), вызов передачи свободной памяти OS (MallocExtension::instance()->ReleaseFreeMemory();) и копирование данных обратно (с освобождением mmap'ed памяти).

anonymous
()

Поскольку никакой виртуальной памяти (свопа) нет, когда память заканчивается задача крэшится (все 1000 процессов)

Вот тут тонко. Нельзя путать виртуальную память и своп. Свопа может не быть, но при этом виртуальная память вполне себе может работать как виртуальная - посредством mmap(), которым в Линуксе выделяется как обычная память, так и разделяемая, так и память разделяемых объектов (динамических библиотек). То есть свопа нет, но всё, что mmap выделяет из файлов, работает как своп. Тут важна политика overcommit.

Вообще насколько такая фрагментация плоха, и если плоха то как с ней бороться?

Из написанного не очевидно, что есть какая-то фрагментация. Фрагментация приводит к потерям памяти. Они реально есть? Это как-то замеряется? Линукс сам неплохо борется с фрагментацией посредством страничной памяти. Каждая страница - 4 килобайта. Если внутри этих 4КБ блоков фрагментации нет, то можно считать, что её нет совсем.

asaw ★★★★★
()

может s/одно/дву/g, и по-факту удаления - сохранять связность списков.

etwrq ★★★★★
()

free он по умолчанию не возвращает память системе, он просто помечает ее как не занятую в куче и делает доступной для malloc.

Для того чтобы free возвращал память системы должно быть выполнено много всяких опций, можно почитать:

man mallopt
man malloc_trim

Если настройки кучи не помогают, и проблема исключительно в 32К блоках - можно сами эти блоки выделять не через кучу, а запрашивать прямо у системы через mmap (протокол: PROT_READ|PROT_WRITE, флаги: MAP_ANONYMOUS|MAP_PRIVATE, fd: -1) и освобождать через munmap тогда память будет возвращатся в систему сразу после вызова munmap.

zaz ★★★★
()

Хочешь, чтобы память связного списка лежала по последовательным адресам - пиши свой аллокатор. А так - меряй каким-нибудь профайлером, который выдаёт cache hit/miss статистику и смотри сам.

А malloc/free живут своей жизнью и как они отдают память системе - зависит от реализации.

dzidzitop ★★
()
Ответ на: комментарий от zamazan4ik

Под линуксом только callgrind пользовал для вылизывания кода. Какие там есть ещё и под какие процессоры - не изучал. Для интелов дефолтный выбор должен быть VTune, но он вроде платный.

====

Точнее, cachegrind в данном случае подходит. Но это всё один и тот же valgrind, в любом случае.

dzidzitop ★★
()
Последнее исправление: dzidzitop (всего исправлений: 1)
Ответ на: комментарий от zamazan4ik

Единственное что - там эмулируется сферический процессор в вакууме. Для полу-алгоритмических оптимизаций примерно пофигу, но реальный камень может работать иначе в плане префетчей, предсказания ветвлений и прочей лабуды. Другие профайлеры (тот же VTune) используют хардварные performance counters живого процессора, на котором гоняется код.

dzidzitop ★★
()
Ответ на: комментарий от dzidzitop

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

zamazan4ik ★★
()
Ответ на: комментарий от zamazan4ik

http://valgrind.org/docs/manual/cl-manual.html

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

--I1=<size>,<associativity>,<line size>

--D1=<size>,<associativity>,<line size>

--LL=<size>,<associativity>,<line size>

dzidzitop ★★
()
Последнее исправление: dzidzitop (всего исправлений: 1)
Ответ на: комментарий от DiKeert

это именно та ситуация когда ты пишешь свой аллокатор

this

boo32
()

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

invy ★★★★★
()
Ответ на: комментарий от dzidzitop

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

Используй вектор.

invy ★★★★★
()
Ответ на: комментарий от asaw

Фрагментация приводит к потерям памяти. Они реально есть? Это как-то замеряется?

Да, замеряется и есть (на старом компайлере). На новом есть большой временной лаг между delete и реальной доступностью памяти.

AntonI ★★★★
() автор топика
Ответ на: комментарий от invy

Не получится - для этого придется писать свой менеджер, чего делать совсем не хочется.

на следующем этапе память юзается блоками ну совсем другого размера (и все разные).

Насчет вектора - можно, только придется писать свой аллокатор. Со стандартным оверхет по памяти может быть до 100%, здесь это не канает.

AntonI ★★★★
() автор топика
Ответ на: комментарий от asaw

Ну эти замеры делал не лично я, поэтому под рукой у меня нету. Словами я симптоматику описал.

AntonI ★★★★
() автор топика
Ответ на: комментарий от AntonI

на следующем этапе память юзается блоками ну совсем другого размера (и все разные).

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

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

Со стандартным оверхет по памяти может быть до 100%, здесь это не канает.

Это каким образом?

saifuluk
()
Ответ на: комментарий от saifuluk

Зачем задавать вопрос ставя одни условия, а потом уже выдвигать совершенно другие?

А зачем пацаны пытаются отвечать на вопрос, который им не задавали? Вы Выше написали «хреновая архитектура» - судя по всему у Вас либастрал прокачан?

Это каким образом?

Если push_back-ов будет 2^N+1.

AntonI ★★★★
() автор топика
Ответ на: комментарий от asaw

Вот тут тонко. Нельзя путать виртуальную память и своп.

да (в смысле - тонко). Но в данном случае важно именно отсутствие swap-а. То есть, когда сумма 1) аллокированной памяти всех mpi-процессов, 2) буферов файлов и 3) mpi-обменов достигнет размера физической памяти --- система не сможет выделять больше ни байта. Проблемная ситуация: mpi-процессы аллокировали себе память вычислительного узла, попользовали, вызвали delete, но часть этой памяти системе не вернулась. В результате другой mpi-процесс того же узла не может ее аллокировать.

Фрагментация приводит к потерям памяти. Они реально есть? Это как-то замеряется?

да. Ведется статистика размера основных выделяемых структур данных. Также в ключевые моменты выводятся данные sysinfo. Из сравнения оценивается утечка. В том числе, это делалось и в режиме один mpi-поток на узел. При этом хорошо видно, что после удаления временных данных в конце этого этапа расчета --- часть памяти системе не возвращается. Причём количество количество «зависшей» памяти кардинальным образом зависит от параметров данной реализации расчета (и это, кстати говоря, воспроизводится).

Линукс сам неплохо борется с фрагментацией посредством страничной памяти. Каждая страница - 4 килобайта

немного сомнительный тезис. Если речь об аппаратных страницах виртуальной памяти и трансляции адресов VA<->PA, то там ещё есть 2MB и 1ГБ. Но тут проблема скорее всего программная (алгоритмы работы кучи, mmap и проч.) В этом смысле я написал маленький тест. На той системе память выделяется блоками по ~300КБ. Возможно, это настраивается. Если что, оптимальный размер блока проблемной структуры данных 32KБ.

VLev
()
Ответ на: комментарий от xaizek

man -P 'less -p THRESHOLD' mallopt

да, тоже спасибо. Буду изучать

VLev
()
Ответ на: комментарий от VLev

да (в смысле - тонко). Но в данном случае важно именно отсутствие swap-а. То есть, когда сумма 1) аллокированной памяти всех mpi-процессов, 2) буферов файлов и 3) mpi-обменов достигнет размера физической памяти --- система не сможет выделять больше ни байта.

Ещё раз повторю: даже при отсутствии свопа система отдаст сколько угодно виртуальной памяти при включенном overcommit'е. То есть вызовы malloc(), mmap() и аналогов завершатся успешно. Далее уже при записи в выделенную виртуальную память, при нехватке физической, в дело вступит OOM-killer.

да. Ведется статистика размера основных выделяемых структур данных. Также в ключевые моменты выводятся данные sysinfo. Из сравнения оценивается утечка. В том числе, это делалось и в режиме один mpi-поток на узел. При этом хорошо видно, что после удаления временных данных в конце этого этапа расчета --- часть памяти системе не возвращается. Причём количество количество «зависшей» памяти кардинальным образом зависит от параметров данной реализации расчета (и это, кстати говоря, воспроизводится).

А вам важно именно количество возвращенной системе памяти? То есть 1000 процессов работают на одном узле и нужно чтобы каждый возвращал память как можно скорее? В противном случае интересна статисктика mallinfo() для процесса.

asaw ★★★★★
()
Ответ на: комментарий от asaw

Насколько я понимаю, в нашем случае лучше подождать того момента пока память появится, чем потом напороться на OOM-киллера. Гипотетически мы можем ловить ошибку при выделении памяти, сколько то ждать и потом пытаться повторить выделение, но это будет сложнее и менее эффективно, чем стартовать будучи уверенным что памяти хватит. Иначе ведь память может вообще не появится (ну тупо ее не хватает), а процесс задание уже взял и повис наглухо...

AntonI ★★★★
() автор топика
Ответ на: комментарий от asaw

Ещё раз повторю: даже при отсутствии свопа система отдаст сколько угодно виртуальной памяти при включенном overcommit'е. То есть вызовы malloc(), mmap() и аналогов завершатся успешно. Далее уже при записи в выделенную виртуальную память, при нехватке физической, в дело вступит OOM-killer.

В данном случае это несущественные детали, поскольку вся аллокированная память тут же начинает использоваться. Тем не менее и этот вопрос изучался отдельно (поскольку кроме обсуждаемого 1) есть ещё 2) и 3) ). Конкретно на этом проблемном кластере первым срабатывает std::bad_alloc. Я его могу перехватить, но дальше ничего полезного, кроме вывода диагностики, сделать не могу.

А вам важно именно количество возвращенной системе памяти?

Важно, чтобы вся (ну или почти вся) аллокированная, использованная и освобождённая после этого память возвращалась в систему. Пусть не сразу (речь о десятках секунд), и после «стимуляции» (на других кластерах в качестве стимуляции помогает костыль new [большой блок]/delete [большой блок]).

интересна статисктика mallinfo() для процесса.

да, это я уже понял. спасибо

VLev
()
Последнее исправление: VLev (всего исправлений: 1)
Ответ на: комментарий от VLev

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

Тогда два пути: либо меняйте параметры malloc, как писали выше, чтобы память выделялась через mmap для более мелких блоков, либо переопределяйте глобальные new с delete и там вручную делайте

mmap(0, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
с соответствующим munmap() в delete, как, опять же, писали выше.

asaw ★★★★★
()
Ответ на: комментарий от flyshoot

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

AntonI ★★★★
() автор топика
Ответ на: комментарий от asaw

Всем спасибо - проблема решена

Всё, проблема решена. В принципе, основная добавленная строчка: mallopt(M_MMAP_THRESHOLD, 32*1024);

В принципе, альтернатива malloc_trim(0); но это в нашем коде почему-то иногда (редко, но метко) не работает.

Ну и mallinfo(); полезную информацию даёт.

Спасибо также всем принявшим участие в обсуждении, и особенно xaizek и zaz, давшие правильные советы уже в самом начале дискуссии

VLev
()
Ответ на: Всем спасибо - проблема решена от VLev

«Спасибо также всем принявшим участие в обсуждении, и особенно xaizek и zaz, давшие правильные советы уже в самом начале дискуссии» - поправил (добавил cast). И конечно asaw.

AntonI ★★★★
() автор топика
Ответ на: Всем спасибо - проблема решена от VLev

Твой товарищ опять меня кинул? Спроси у него - почему он такой подлец. Месяц обещал, а потом просто заигнорил и игнорирует эту тему уже 3года. Ладно бы хоть сказал «мне это неинтересно», «ты дурак». Как это называется?

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

Я и не стал эту тему поднимать, и ничего не писал. Не стал ничего выкатывать. Меня из-за этого тут называют балаболом, но я терпел. А мне плевал в лицо человек ради которого я терпел. Как это называется?

saifuluk
()
Ответ на: комментарий от saifuluk

Потом был ответ что у меня нет на это времени. И его с тех пор больше не стало.

Роман, я Вам рекомендовал пойти в какой нить профильный вуз - это все что я могу для Вас сделать. Простите.

AntonI ★★★★
() автор топика
Ответ на: комментарий от anonymous

Спросите у него самого?:-)

AntonI ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.