| >> |
No.27977
Файл: 104037347_p0.png -(4403 KB, 1668x2343, 104037347_p0.png)
>>27974
Был свой и теперь свой, я даже идеи не крал, а переизобретал как естественные решения найденных проблем, кроме того, что вот сейчас ещё заставил себя разобраться, что же всё-таки FastMM делает со средними блоками и зачем ему битовые поля, понял, что так и правда лучше по совокупности (я бы сказал, плюс-минус то же самое, но тай-брейк для меня — −1,3 Кб кода), и украл: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/1029.
Современные Менеджеры Памяти™ работают примерно одинаково в своей исходной сути, то есть в самом по себе выделении памяти. Делим блоки на МАЛЕНЬКИЕ, СРЕДНИЕ, и БОЛЬШИЕ.
— МАЛЕНЬКИЕ округляются вверх до определённых размеров (у меня это 16 взятых с потолка значений: 16, 32, 48, ..., 480, 544) и выделяются в аренах, рассчитанных на N блоков такого же размера. 800-байтная арена для 100-байтных блоков может выглядеть как
[#0:100][#1:100][#2:100 своб][#3:100][#4:100][#5:100 своб][#6:100][#7:100]
freelist: #2, #5 Такой подход позволяет выделять и освобождать такие блоки, в среднем, мгновенно: просто взять из freelist или вернуть во freelist. Что полезно, т. к. они встречаются гораздо чаще бо́льших: в таком варианте ≤540 байт — в ≈100 раз, а FastMM считает «маленькими» ≤≈2'600 байт, так что там, наверное, ещё на порядок-два чаще.
Я самой же первой переделкой, которая «просто переписывание старого менеджера», сделал, чтобы этот freelist вёлся вот такой свой в каждой арене, а не глобально на все арены под этот размер; наиболее очевидная для переизобретения идея, этот пункт в описании mimalloc говорит ровно о ней же:
>free list sharding: instead of one big free list (per size class) we have many smaller lists per "mimalloc page" which reduces fragmentation and increases locality -- things that are allocated close in time get allocated close in memory. (A mimalloc page contains blocks of one size class and is usually 64KiB on a 64-bit system).
— и это даже странно, потому что, во-первых, это делают все, а во-вторых, неделание этого влечёт более очевидные проблемы, чем абстрактные fragmentation и locality: старый менеджер с глобальным freelist должен был, если захочет переиспользовать пустую арену под другой размер или окончательно освободить, сначала выдрать все её блоки из глобального freelist, что сильно замедляло пограничные случаи. Впрочем, это отдельная проблема, связанная с тем, что свежевыделенная арена сперва полностью нарезалась на эти блоки и добавляла их все в глобальный freelist — если бы она этого не делала и умела быть частично размеченной, как у меня / FastMM / везде, то выдирание было бы амортизированным O(1), но всё равно это как минимум скучное занятие, полностью избегаемое поаренными freelist-ами.
— СРЕДНИЕ блоки (у меня до 512 Кб) выделяются в той конструкции из Boost.Interprocess, которая первой и приходит на ум, если подумать об управлении памятью. Если взять 64 Кб ОС-блок и выделить в нём 1'000, 2'000, 3'000, 4'000, 5'000 байт, а затем освободить средние 2'000 и 3'000, получится:
[1'000][5'000 своб][4'000][5'000][50'536 своб] Эквивалент «freelist» на этот раз вынужден быть глобальным, и желательно умеющим быстро искать минимальный по размеру свободный блок, умещающий заданный размер. Минимальность желательна, потому что снижает фрагментацию: в этом примере запросы ≤5'000 лучше выделять из свободного блока на 5'000, чем из 50'536, чтобы подольше сохранить 50'536 для потенциального GetMem(50'000).
Для такого поиска можно использовать дерево, но все используют многоуровневое битовое поле и я теперь тоже сделал многоуровневое битовое поле. Идея в том, что мы разделяем размеры блоков свободного пространства на группы, подобно маленьким размерам (только их намного больше, чем маленьких; в FastMM4 — 1024 с шагом по 256, у меня — 320 с шагами от 32 до 16'384). Для каждого размера ведётся связный список свободных блоков этого размера, и над этими списками — много(ну, двух)уровневое битовое поле:
L1: uint32; // Бит L1[i] = 1, если L0[i] <> 0.
L0: array[0 .. MediumSizesCount div 32 - 1] of uint32; // Бит L0[i][b] = 1, если mediumFreelist[32 * i + b] <> nil.
mediumFreelist: array[0 .. MediumSizesCount - 1] of pFreeMediumBlock; позволяющее найти (примерно) минимальный блок одним-двумя побитовыми find first set.
— БОЛЬШИЕ блоки спрашиваются напрямую у ОС.
И вот, во всём этом только 1,5 места для принципиальных различий: алгоритм поиска свободных средних блоков (и то, фишку с битовыми полями можно считать стандартной), и подход к многопоточности. FPC использует одновременно лучший (склоняюсь к этому) и худший способ: всё thread-local, то есть у каждого потока свой менеджер, в предположении, что обычно память освобождает тот же поток, что выделял, это минимизирует разбирательства с многопоточностью как таковой, но легко построить контрпример; FastMM4 использует другую крайность — единственный глобальный менеджер и его блокировки, по одной на каждый маленький размер, одну на все средние, и одну на все большие, говорят, неприятно; в среднем используется нечто гибридное.
...Кхм, я сейчас попробовал в доказательство этого спекулятивного утверждения про гибридный подход полистать по диагонали исходники mimalloc, и мало того, что не нашёл чего-либо не thread-local, так ещё в его функции _mi_page_abandon, соответствующей моей ThreadState.Orphan, не нашёл треть того, что делает моя, и понял, что она и в самом деле не должна этого делать: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/1036, нормально.
|
