http://telegra.ph/Ideya-allokatora-01-15
Обсудите пожалуйста.
P.S. Похоже идея не взлетела: чтобы она работала, надо как-то подправлять offset-ы на перемещённые куски, а реализация этого обернётся полной жопою, съедающей все выгоды. Да и косвенный доступ снижает производительность. Автор тупой упырь и не читал литературу по аллокаторам, например http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf
Сформулирую задачу.
Есть множество объектов, каждый из которых выделяет себе в пределе до 16 строк произвольной длины. Объекты делают это в разное время. Условно говоря, объект - это коннект до юзера и строка выделяется когда юзер пишет месагу в чатик. Когда накапливается условно 16 строк, объект их освобождает разом.
Вот ищется максимально производительный аллокатор под такое.
Можно забацать килобайт памяти каждому объекту - мол, выделяй там сколько хочешь и как хочешь - тоже решение, но коннектов очень много и жалеко не каждый из них что-то в этом килобайте будет держать.
Для Ъ (пост из тынца выше)
Обсудите такую идею аллокатора. Юзкейс - выделять объекты размером не более, допустим, 4КБ и иметь минимум оверхеда на служебные структуры. Применять в in-memory nosql хранилке ключей key=value.
Выделяем объекты любого размера (до 4kb) последовательно в странице (как арена аллокатор) (макс размер объекта = не более страницы), при заполнении страницы берём у ОС новую и продолжаем. При освобождении объекта, помечаем его в странице как свободный, но выделение в этой точке невозможно - выделялка максимально тупая и берёт всегда только с конца «текущей».
В процессе освобождения очередного элемента проверяем страницу Q (в которой он только что был освобождён) на суммарное количество свободных фрагментов sum_free. Если sum_free достигает некого критического уровня (скажем, 0.4 от общего размера страницы) - делаем compaction - вытряхиваем все несвободные фрагменты из страницы Q в новую чистую страницу (линейное время), подменяем новой страницей страницу Q, убиваем страницу Q. Помещаем нашу новую страницу в множество страниц где снова можно выделять память с конца (при этом её конец будет уже не в начале, т.к. какое-то кол-во памяти там уже сожрано).
Чтобы работала подмена страниц, юзеры такого аллокатора ссылаются на свои данные не просто указателем, а парой (page_idx, offset), где page_idx - индекс страницы в таблице страниц. То есть, подмена страниц будет делаться заменой указателя в нужном индексе этой таблицы. page_idx и offset могут быть размера 32 bit и 16 bit (если страница на неск. КБ), что суммарно будет не жирнее pointer. Для доступа к своему куску: data_ptr = table[page_idx] + offset. Доступ юзеру к началу страницы нужен, чтобы освобождающий поток мог делать работу с заголовком страницы по увеличению счётчика sum_free.
Перемещено tailgunner из development