Быстрый мультизадачный менеджер памяти

[bondkim137]

Под менеджером памяти здесь будем понимать классический менеджер памяти, работающий с непереносимыми блоками. Такой, какой используется в классических реализациях C++, Pascal и т.д. Задача менеджера памяти - уметь выделять в куче блок памяти запрашиваемого размера, освобождать его и переаллоцировать (изменять размер) - при необходимости, с переносом.

Необходимо создать действительно быстрый менеджер памяти для решения локальных задач - он должен обрабатывать десятки миллионов операций в секунду при миллиарде живых объектов в куче. Наиболее быстрый из доступных был найден в томах Кнута - сложность в худшем случае логарифмическая от кол-ва объектов. За такую скорость у него приходится платить округлением размера выделяемого блока до степени двойки. Это слишком дорого - хотелось бы ограничиться 20-30%

Дополнительную проблему создает необходимость работы в мультипоточном режиме - такой поток обращений даже с логарифмической сложностью сложно обработать на одном ядре современного PC.

Известны ли конкретные реализации и/или опыт написания подобных менеджеров памяти?

[Progger]

А у Вас все объекты разного размера или есть известное множество возможных размеров?

[sup]

bondkim137 в сообщении #1073842 писал(а):

За такую скорость у него приходится платить округлением размера выделяемого блока до степени двойки. Это слишком дорого - хотелось бы ограничиться 20-30%

Это вы про buddy allocator (метод напарников) говорите? Если так, то теоретически вместо степеней 2 можно использовать числа Фибоначчи. Я, правда, ни серьезных обсуждений, ни реализаций не видел. По моим прикидкам вместо внутренней фрагментации в этом случае получается внешняя. Короче, шило на мыло, и много доп. возни.
Но мне другое любопытно. Это что же за задачи Вы хотите решать.

bondkim137 в сообщении #1073842 писал(а):

он должен обрабатывать десятки миллионов операций в секунду при миллиарде живых объектов в куче

Ну, то есть, если у вас объекты всего лишь с полсотни байт, то речь идет уже о сотнях Гиг памяти. Да и программа, похоже, вместо содержательной работы занимается только лишь выделением памяти и ее освобождением. А еще и синхронизация между потоками. А что там по этому поводу "железо" думает?
Для управления такими потоками данных желание использовать "классический менеджер памяти" выглядит как-то странно.
Вы не подумайте чего плохого. Мне в самом деле любопытно. Где Вы собираетесь использовать такую "кувалду"?

[bondkim137]

Progger в сообщении #1073872 писал(а):

А у Вас все объекты разного размера или есть известное множество возможных размеров?

Все размеры недетерминированные. Большая часть - строки

-- 16.11.2015, 14:23 --

sup в сообщении #1073874 писал(а):

Это вы про buddy allocator (метод напарников) говорите? Если так, то теоретически вместо степеней 2 можно использовать числа Фибоначчи. Я, правда, ни серьезных обсуждений, ни реализаций не видел. По моим прикидкам вместо внутренней фрагментации в этом случае получается внешняя. Короче, шило на мыло, и много доп. возни.

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

sup в сообщении #1073874 писал(а):

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

Задач несколько, самая больная - это специфический HTTP-сервер, обрабатывающий большое число обращений. На каждое обращение создается довольно сложный ответ. Большая часть выделяемых элементов - маленькие строки из различных темплейтов и чисел.
Средний размер блока значительно меньше, чем пол сотни байт. Общий полезный размер кучи болтается в районе 20-30GB

sup в сообщении #1073874 писал(а):

Да и программа, похоже, вместо содержательной работы занимается только лишь выделением памяти и ее освобождением. А еще и синхронизация между потоками. А что там по этому поводу "железо" думает?

Не все время, но ориентировочно больше половины. Однопоточный менеджер памяти однозначно становится узким звеном, т.к. остальная работа сравнительно легко параллелится. Ситуацию частично исправляет использование пулов с несколькими наперед заданными фиксированными размерами объектов - сложность падает до $O(1)$, но оверхед увеличивается. Помимо нехватки памяти, в наиболее активном участке 'котла', где все безумно варится, появляется нелинейная просадка по скорости, связанная с нехваткой кеша памяти какого-то из уровней.
Железо трещит Преимущественно - это ферма из EX40 серверов в Hetzner. Там по 32GB на i7-4770 стоит.

sup в сообщении #1073874 писал(а):

Для управления такими потоками данных желание использовать "классический менеджер памяти" выглядит как-то странно.
Вы не подумайте чего плохого. Мне в самом деле любопытно. Где Вы собираетесь использовать такую "кувалду"?

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

[aa_dav]

bondkim137 в сообщении #1073959 писал(а):

появляется нелинейная просадка по скорости, связанная с нехваткой кеша

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

[bondkim137]

aa_dav в сообщении #1073974 писал(а):

Я бы думал в сторону кеш-френдли схемы и прогибал бы аллокатор в эту сторону, чтобы все строки обработки одного запроса были локально упакованы.

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

[aa_dav]

bondkim137 в сообщении #1073984 писал(а):

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

А что за структуры в целом? Это может быть важно. Если кеш трещит, то все мысли должны быть о кеш-френдли.

[bondkim137]

aa_dav в сообщении #1073991 писал(а):

А что за структуры в целом? Это может быть важно. Если кеш трещит, то все мысли должны быть о кеш-френдли.

АВЛ-деревья, хеши, нецикличные графы.
Кеш вроде не трещит, если строки не округлять до 64 байт, когда есть огромное кол-во токенов из 5-7 символов..

[sup]

Ну, в таком случае без организационных мер не обойтись. Числа Фибоначчи в Вашем случае может даже и покатят (как ни странно). Но я бы присоветовал лучше иметь два (или несколько) стандартных аллокатора с напарниками, но с разными размерами атома. Например у одного, X, а у другого 3X/2. В "обычной жизни" нет оснований считать, что у одного будет густо запросов, а у другого пусто. Более того, мне кажется, что у Вас и так не один, а несколько аллокаторов (или вся память одним куском ). Кроме того. Все "мелкие" размеры должны отрабатываться индивидуально. Тут, правда, появляется другая проблема. Как по указателю быстро определить что это за зверь и кому принадлежит.

В Вашем случае есть еще одна особенность. Характерный размер блока меньше 8 байт. Возникает одна специфическая проблема.
В описании метода напарников как-то не особо освещается проблема хранения всяких флагов состояния куска памяти. Свободен, занят, размер. В принципе, должно хватать одного байта. Но где его хранить? Если в самом блоке, то для 8-байтовых кусков идет "заметная" потеря. А если надо в точности 8 байт? (А такое часто бывает). Тогда вообще приходится выделять 16. Что удручает. А если не так, то где хранить такую информацию?
Я в своей реализации использовал отдельную битовую строку. По одному биту на 8 байт. Накладные расходы - полтора процента. Этим битом можно кодировать и состояние и размер. Кроме того, служебная информация частично отделена от данных, что немножко повышает защиту от записи за границы массива. Плата за это - дополнительная нагрузка на кэш. Чего она стоит - сказать затрудняюсь. Да и вообще. Стоит ли это делать - не знаю.
В любом случае выделение 4-х и 8-байтовых кусков производилось специальным методом, который использовал куски по 256 байт и уже там резвился. Возможно, надо подобную штуку проделать и с другими размерами. Все-таки для малых размеров прокручивать всю эту мясорубку, наверное, накладно.
Как бы то ни было, но учитывая серьезные размеры задачи, я бы на "серебряную пулю" не рассчитывал.

[bondkim137]

sup в сообщении #1074060 писал(а):

лучше иметь два (или несколько) стандартных аллокатора с напарниками, но с разными размерами атома. Например у одного, X, а у другого 3X/2. В "обычной жизни" нет оснований считать, что у одного будет густо запросов, а у другого пусто.

Идея хорошая. А это и неважно - все равно менеджер памяти реально у системы берет несколько кусков и начинает их шинковать.

sup в сообщении #1074060 писал(а):

Кроме того. Все "мелкие" размеры должны отрабатываться индивидуально. Тут, правда, появляется другая проблема. Как по указателю быстро определить что это за зверь и кому принадлежит.

Можно совать в минус первый байт. Хотя это и дорого для маленьких объектов - ведь еще аккуратно надо с выравниванием - к менеджеру памяти есть требования по выравниванию адресов (важно для некоторых SIMD-инструкций и всех ARM)..
Для совсем мелких можно брать адрес по модулю 256, и перед ним паковать системные данные - полагаю, как сделали Вы, но я пока не заморачивался.

sup в сообщении #1074060 писал(а):

В Вашем случае есть еще одна особенность. Характерный размер блока меньше 8 байт. Возникает одна специфическая проблема.

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

sup в сообщении #1074060 писал(а):

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

У текущего коктейля довольно много magic-настроек. Хочется их минимизировать.
Ну и мультизадачность - по ней все плохо, только на уровне быстрого определения, чей блок (или чей будет блок) и затем уже локального лока под-менеджера памяти.

[slavav]

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

[sup]

bondkim137 в сообщении #1074069 писал(а):

Можно совать в минус первый байт

Вот этого то и не хочется. Если кто-то грязными сапогами небрежно прогуляется по своему куску памяти - то конец этой информации. Но это ладно. А вот что делать с выравниванием. Если это просто байтовые строки - то ладно. А если это память под структуры с содержательными объектами, то тут все не очень просто.
Для объектов я всегда имею спец. аллокаторы, которые только этим и занимаются. Скажем, для деревьев ноды и листья - расходный материал. Они всегда нужны. Для них проще всего иметь специальный аллокатор, который уже привязан к бадди-аллокатору. Тут, конечно, есть варианты. Разумеется, можно сделать специализацию не по типу, а по размеру. Принципиальной разницы я не вижу.
Насчет мультизадачности. Я писал свои собственные lock-и. Вариации на тему spin-lock. Речь шла о сотнях (и тысячах) объектов, нуждающихся в синхронизации, в то время как работало не более десятка потоков. Например, кэш неких объектов. И на каждый надо свой lock. Но это было в ситуации, когда я доподлинно понимал что там внутри происходит. Поэтому давать Вам советы на эту тему не возьмусь. А вообще любопытная задача. Можно ли избежать полной блокировки бадди-аллокатора при выделении или освобождении памяти?
В конечном итоге я как-то обходился без магии. Но задачи все же у меня были совсем не такого масштаба.

slavav в сообщении #1074081 писал(а):

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

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

[slavav]

sup в сообщении #1074084 писал(а):

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

Двум процессам на двух ядрах не надо согласовывать кеши. Один процесс на нескольких ядрах всегда согласовывает кеши.
Внутри однозадачного процесса вы не занимаетесь синхронизацией - всё работает быстрее.
Обычная рекомендация по многозадачности в Unix: выбирать архитектуру из большого количества однозадачных процессов.
Бонус - защита от распространения ошибок.
Операционные системы лучше исполняют параллельно несколько процессов, так есть аппаратная поддержка для управления памятью. Внутри одного процесса ничего такого нет, все решения программные, более медленные.
Можно поставить эксперимент - многотредовость против многопроцессности.

[sup]

Трудно спорить с такими доводами.
Но это мне напомнило "детские" споры про каратиста и боксера.
Иными словами, у меня есть понимание процесса и его специфики. Но нет доступа к тонкому системному управлению.
У системы есть преимущество в системных средствах и аппаратной поддержке. Но она не знает какую задачу ей следует решать.
Кто победит в таких условиях - предсказать весьма трудно.
Обычно я за интеллект и против "грубой силы" . Хотя и был случай, когда система справилась лучше. Но это была весьма специфическая задача.

[bondkim137]

slavav в сообщении #1074081 писал(а):

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

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

slavav в сообщении #1074081 писал(а):

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

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