Как распределить смехотворные объемы памяти в C?

Question

Я пытаюсь исследовать практичность алгоритма поиска d-мерного диапазона, который, как доказано, хорош в асимптотических случаях, но имеет большие константы, связанные с ним. Это означает, что мне нужно иметь возможность изменять количество точек в d-мерном пространстве до некоторых очень больших значений. Использование 1<<20 (от 2 до 20) точек начинает заставлять мои malloc с возвращать нулевые указатели. Я знаю, как можно чаще, насколько я могу, и я делаю то, что могу сэкономить на нескольких местах, но я бы хотел, чтобы я смог приблизиться к значениям ближе к 1<<28. Существует ли обычный способ обработки блоков памяти такого размера?

Answer 1

Если вы работаете на 32-битном процессоре и/или операционной системе или компилируете для 32 бит, а не 64, то вы не можете и даже если вы работаете на 64-битном процессоре и компилируете для него, вам понадобятся чтобы иметь много физической памяти - malloc пытается для непрерывного блока, поэтому файлы подкачки вам не подходят. SIZE_MAX сообщит вам максимальное число, которое может быть выделено, но ошибки зависят от физических ограничений.

Answer 2

Вы говорите, что выделение таких больших блоков начинается с, чтобы вернуть нулевые указатели. Для меня это означает, что он работает какое-то время, что вы выделяете и освобождаете немало из них с течением времени, и что после того, как вы сделали несколько МНОЖЕ, вы начинаете получать нули.

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

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

Моя реализация перемещаемой памяти работала примерно так: в начале выполнения программы я выделил самый большой единый блок памяти. (mmap - ваш друг.) Если бы я не мог найти свободный фрагмент, где я мог бы удовлетворить запрос на распределение, я бы нашел блок с куском свободного пространства до и после него и переместил его в местоположение предыдущего свободного места. Я бы планировал этот шаг, чтобы получившийся свободный блок был достаточно большим для вновь запрошенного распределения.

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

Answer 3

2^28 = 256 МБ.

Должно быть выполнено в 32-разрядных или 64-разрядных системах, если у вас достаточно физической памяти. Чтобы проверить, делаете вы это или нет, получите вывод cat /proc/meminfo и найдите строку MemFree.

API-интерфейс, я рекомендовал бы mmap() (анонимное отображение) вместо malloc()

http://man7.org/linux/man-pages/man2/mmap.2.html

mmap это системный вызов, который запрашивает ОСА непосредственно на память. Это то, что использует malloc().

Answer 4

Если malloc() начинает терпеть неудачу, тогда вы можете столкнуться (слегка произвольно). Вы должны быть в состоянии немного расслабиться (см. ulimit в bash); но имейте в виду, что эти ограничения настроены на то, чтобы помочь стабильной и предсказуемой системе в использовании общего назначения. Кроме того, будьте осторожны с overcommit, где OS может позволить вам запрашивать больше памяти, чем она может обеспечить, а затем убивает вас, если вы попытаетесь ее использовать.

Если у вас действительно закончилось адресное пространство, и вы создаете 32-битное приложение, переключитесь на 64-разрядный.

Если у вас заканчивается адресное пространство в 64-битном приложении, я бы предположил, что вы не используете свои распределения. Это много данных для заполнения, и я ожидаю, что у вас закончится время до истечения адресного пространства. В этом случае вам, вероятно, следует подумать, как вы используете пространство.

Если вам нужно большее адресное пространство, чем доступно в вашей системе, вы можете создать файл (или много файлов) и mmap() фрагментов этих файлов по мере необходимости. Это позволяет ОС кэшировать файл (ы), насколько это возможно, и если у него заканчивается как физическая память, так и своп (всегда риск с такими проектами), то у нее есть где-то, где можно вывести данные из не впадая в панику и убивая ваше приложение.

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