Как написать код выделения памяти

@zx_gamer · Регистрация: 07.04.2020

Студворк — интернет-сервис помощи студентам

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

В частности интересует несколько вопросов:
1. В какую структуру данных запоминать выделенные участки? (Очевидно, что она не должна требовать выделения на каждое добавление, т.к. в таком случае она просто не имеет смысла)

2. Как производить поиск уже выделенных участков? (Очевидно, хочется что-то быстрее O(n))

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

Verevkin · 20.01.2024, 21:28

Сообщение от zx_gamer

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

Нахрена?
Думаешь, что так быстрее будет? (спойлер: нет). Функции работы с памятью - это функции ядра ОС. Они оптимизированы до совершенства и быстрее ты ничего не придумаешь.
---------
А если ты написал код, который занимается перераспределением памяти 100500 раз в секунду, то это ты ССЗБ.

@Aledveu · 20.01.2024, 23:56

Сообщение от zx_gamer

чтобы не делать на каждое выделение системный вызов

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

Сообщение от Verevkin

Думаешь, что так быстрее будет

зависит от задачи. ТС не описал что ему надо - аллокатор общего пользования или специальный.

Сообщение от zx_gamer

В какую структуру данных запоминать выделенные участки

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

Сообщение от zx_gamer

Как производить поиск уже выделенных участков?

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

Сообщение от zx_gamer

Как осуществлять "дефрагментирование" по возможности?

никак. максимум что делается - применяется либо "first-fit" или "best-fit" стратегия поиска свободного места при выделении нового блока памяти.

А вообще - ТС - напиши что тебе надо а не отдельные вопросы которые кусочками затрагивают сложную тему.
какой тип аллокатора надо?
стратегия его использования?
чем не устраивает malloc при вашей стратегии использования ? - вот тут особо надо постараться с точностью формулировок.

@pechka_ne_sed · 21.01.2024, 06:57

Сообщение от Verevkin

Функции работы с памятью - это функции ядра ОС. Они оптимизированы до совершенства и быстрее ты ничего не придумаешь.

1. - Системный вызов,

~1000-1500 тактов - довольно тяжелая операция
2. - Это, как довольно точно выразился Aledveu, т.н. "аллокаторы общего назначения", они неспособны часто выделять маленькие объемы памяти.
3. - Довольно общий, и может быть, неточный пример, зачем тогда в Intel TBB несколько своих аллокаторов?

@pechka_ne_sed · 21.01.2024, 07:10

zx_gamer, если участки имеют одинаковый размер, то вы описали идиому Pool Allocator.
Смысл в чем: храниться список адресов свободных участков памяти. При выделении памяти просто берем оттуда адрес (O(1)), при освобождении памяти кладем адрес туда обратно (O(1)). Конструктор, выполняющий изначальную инициализацию списка свободными адресами работает за O(n).

Алексей1153 · 21.01.2024, 07:13

zx_gamer, глянь вот это Полиморфные аллокаторы

@pechka_ne_sed · 21.01.2024, 07:27

zx_gamer, согласен с Aledveu, нужны конкретные сценарии использования аллокатора.
Например, пусть вы пишете игровой движок и вам надо быстро выделять, скажем, дескрипторы объектов движка (если у вас движок, например, на базе ECS, то это числовые идентификаторы), то они зачастую, одинакового размера и идиома Pool Allocator, на мой взгляд, наиболее предпочтительна.

Добавлено через 7 минут
Алексей1153, интересная штука, когда 2 года назад этим интересовался, не знал, что стандартная библиотека уже предлагает свою реализацию чего-то типа прослойки для контейнеров. Но по-моему лучше уметь реализовывать свои STL аллокаторы, ибо виртуальные функции не всегда приемлемы, да и 17 стандарт все еще не повсеместен

.

Алексей1153 · 21.01.2024, 07:43

Сообщение от pechka_ne_sed

17 стандарт все еще не повсеместен

да ладно, он уже повсюду. Если, конечно, не принимать во внимание дикие легаси (а свои я некоторыми усилиями перетащил на 17

)

Добавлено через 3 минуты

Сообщение от pechka_ne_sed

виртуальные функции не всегда приемлемы

вызов виртуальной функции всяко легче реаллокации на куче

@pechka_ne_sed · 21.01.2024, 09:01

Алексей1153, я про некоторые embedded платформы.

Добавлено через 4 минуты

Сообщение от Алексей1153

вызов виртуальной функции всяко легче реаллокации на куче

-fno-rtti может быть просто захардкоден в проприетарном компиляторе.

@zx_gamer · 21.01.2024, 10:34 **[ТС]**

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

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

Добавлено через 7 минут
Если честно, мне больше нравится идея перегрузить operator new и operator delete, потому что использование аллокаторов вынуждает писать operator== и т.п. шаблонными, что сильно раздует конечный бинарник (каждый с каждым будет реализован заново).

И соответственно выбирать политику аллокации в рантайнме. Условно, если void* operator new(size_t n) получил n, большее мегабайта (1048576), то просто malloc, если меньше или равно, то по описанному выше сценарию.

Добавлено через 14 минут

Сообщение от Алексей1153

да ладно, он уже повсюду. Если, конечно, не принимать во внимание дикие легаси (а свои я некоторыми усилиями перетащил на 17 )

Ну как) Я для себя до сих предпочитаю C++98. Код пишешь проще, не отвлекаешься на всякую ненужную требушатину. Хоть и выглядит он не так симпатично, но читать его проще, в языке ещё нет "магии".

Алексей1153 · 21.01.2024, 11:57

Сообщение от zx_gamer

Код пишешь проще

можно писать абсолютно так же, никто не запрещает

насчёт проще - это нет. Язык всё время упрощается. 98 - сложный, 17 - намного проще

@Именч · 21.01.2024, 12:28

Память, это тоже самое что и char*array; Вы можете зарезервировать максимальное количество, либо заполнять постепенно, выделяя каждый раз ровные участки по 16-32-65-128. В производительности выделения вы не потеряете, но и не будете тем самым жадным человеком, который забрал все игрушки себе, а играется со своим носом).

@pechka_ne_sed · 21.01.2024, 15:09

Сообщение от zx_gamer

весом 50 байт

Душню, но на самом деле 64

Добавлено через 9 минут

Сообщение от zx_gamer

Я для себя до сих предпочитаю C++98.

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

Сообщение от zx_gamer

в языке ещё нет "магии".

Вся "магия" упирается в очень ограниченный набор паттернов, причем ее интерфейс, зачастую, не требует знать как все устроено под капотом.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@zx_gamer 0 / 0 / 0 Регистрация: 07.04.2020 Сообщений: 27

	Как написать код выделения памяти 20.01.2024, 20:49. Показов 1986. Ответов 12 Метки allocator, free, malloc, operator delete, operator new (Все метки) Подскажите пожалуйста, как написать код, который маллочит несколько мегабайт памяти, а потом выдает небольшие кусочки, чтобы не делать на каждое выделение системный вызов? В частности интересует несколько вопросов: 1. В какую структуру данных запоминать выделенные участки? (Очевидно, что она не должна требовать выделения на каждое добавление, т.к. в таком случае она просто не имеет смысла) 2. Как производить поиск уже выделенных участков? (Очевидно, хочется что-то быстрее O(n)) 3. Как осуществлять "дефрагментирование" по возможности? (Т.е. выделили первый, второй и третий участки. Второй освободили. Следующее выделение по возможности должно занять место второго участка.) 0

@pechka_ne_sed 27 / 24 / 4 Регистрация: 20.11.2023 Сообщений: 131
	21.01.2024, 07:10
	zx_gamer, если участки имеют одинаковый размер, то вы описали идиому Pool Allocator. Смысл в чем: храниться список адресов свободных участков памяти. При выделении памяти просто берем оттуда адрес (O(1)), при освобождении памяти кладем адрес туда обратно (O(1)). Конструктор, выполняющий изначальную инициализацию списка свободными адресами работает за O(n). 0

Алексей1153 фрилансер 6461 / 5663 / 1130 Регистрация: 11.10.2019 Сообщений: 15,079
	21.01.2024, 07:13
	zx_gamer, глянь вот это Полиморфные аллокаторы 1

@pechka_ne_sed 27 / 24 / 4 Регистрация: 20.11.2023 Сообщений: 131
	21.01.2024, 07:27
	zx_gamer, согласен с Aledveu, нужны конкретные сценарии использования аллокатора. Например, пусть вы пишете игровой движок и вам надо быстро выделять, скажем, дескрипторы объектов движка (если у вас движок, например, на базе ECS, то это числовые идентификаторы), то они зачастую, одинакового размера и идиома Pool Allocator, на мой взгляд, наиболее предпочтительна. Добавлено через 7 минут Алексей1153, интересная штука, когда 2 года назад этим интересовался, не знал, что стандартная библиотека уже предлагает свою реализацию чего-то типа прослойки для контейнеров. Но по-моему лучше уметь реализовывать свои STL аллокаторы, ибо виртуальные функции не всегда приемлемы, да и 17 стандарт все еще не повсеместен . 0

@Именч 168 / 146 / 32 Регистрация: 03.09.2018 Сообщений: 499
	21.01.2024, 12:28
	Память, это тоже самое что и char*array; Вы можете зарезервировать максимальное количество, либо заполнять постепенно, выделяя каждый раз ровные участки по 16-32-65-128. В производительности выделения вы не потеряете, но и не будете тем самым жадным человеком, который забрал все игрушки себе, а играется со своим носом). 0