>>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 должен был, если захочет переиспользовать пустую арену под другой размер или окончательно освободить, сначала выдрать все её блоки из глобал
