Снова пространный вопрос про аллокаторы. О статистике. Предположим, аллокатор должен

активно выделять-освобождать строки 1...50КБ. Некий однопоточный аллокатор "общего назначения" с неизвестным заранее распределением запросов.
Какой процент памяти считается нормальным выкинуть впустую на незанятые куски блоков, оверхед и прочее? Скажем 85.5% памяти использовать с пользой в таком случае - сильно плохой результат?

я бы сказал - малодостижимый :)

Вопрос на небольшое научное исследование. А может и на большое.

Запилил несложную идею и она показала этот результат. Идея такая: 1. Выделяем только фиксированные куски от 16 байт с шагом 16 байт. 2. Для каждого размера на старте создаём пустую "таблицу блоков" - Table. Table - пустой массив из, скажем, 4-8 поинтеров на блоки, плюс "next" (показать на новую Table, когда эта кончится). Всего 3199 Table для шага 16 (кажется) (от 16 до 1024*50 байт). 3. На запрос alloc: определить индекс нужной Table . Ну то есть, до 16 байт - это 0, до 32 байт - это 1 и т.п. Этакий "класс запроса". 4. Лезем в Table, бежим по блокам в ней. В начале там пусто, так что создаём первый блок и кладём туда. Но если говорить о том, что там не пусто, то это фуллскан. Тут для скорости аллокаций возможны приколы с перемешиванием этих поинтеров в Table потом, сейчас не суть. 5. Block порублен ровно на 512 кусков своего размера. Ну то есть, Block класса 0 имеет размер 512 * 16. В начале блока лежит таблица из 512 бит (прибавьте 64 байта к размеру блока, да). Влезает в кеш-линию - получается достаточно бесплатно делать с ней что хочешь. Это маркеры занятости сегментов. 1 - свободно. С помощью какой-нибудь gcc-buitin находилки самого младшего единичного бита в машинном слове или вообще с помощью наркомании AVX можно в блоке быстро найти где у него свободная дыра и туда сесть. 6. В целом архитектура такая: на старте лежат много Table - своя под каждый размер. Каждая Table показывает на массу Block-ов своего размера. Если в Table массив, то при последовательных аллокациях он склонен содержать в начале занятые блоки, поэтому можно иногда тасовать этот массив, но если деаллокации в природе существуют, то дырок понаделается естественным путём. 7. Память конечна, а удаления блоков разных классов не предусмотрено - против фрагментации "реальной кучи" тут приёма не придумано. Предполагается, что стартовый прогрев определяет некое распределение. Далее, если всё же нужны какие-то "классы размеров", которых раньше было недостаточно, то надо думать. Можно начать выделять классы бОльшего ближайшего доступного размера. Возможно можно создать два экземпляра аллокатора и в какой-то момент перелить из старого в новый, грохнув старый с забыванием старого неактуального распределения.

если я правильно понял, то при выделении исключительно 1-байтных блоков степень использования ОЗУ будет 6.25%. т.е. мы с вами видимо по разному понимаем "85.5% памяти использовать с пользой"

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

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

на моменте 1:12:27 не оно? https://youtu.be/LIb3L4vKZ7U