|
|
|
|
|
|
by sb
4783 days ago
|
|
|
Managing free memory is indeed an interesting problem. Besides the simple free-list approach sketched by the author (sidestepping the first-fit vs. best-fit search strategy, which affects fragmentation, too), I always found the buddy-list to be particularly interesting: https://en.wikipedia.org/wiki/Buddy_memory_allocation Unfortunately, the article is not a very good explanation, I remember having seen a drawing of the data structure, but cannot recall from where... edit: It turns out that the mentioned jemalloc internally uses buddy lists as well. |
|
|
The free-list was for small object allocations; it maintained free-lists of different sizes. (Say, the 8 byte free list, the 16 byte free list, the 32 byte free list, etc.) However, I obtained the memory for these lists from a page manager, and that page manager used the buddy system. The relationship here is that the small-object part of the allocation obtained its memory from the page allocator; the page allocator obtained its memory from the operating system. This system allowed me to have the benefits of a free-list (good cache behavior for small objects allocated and used together), but low overall fragmentation and good reuse of the free lists.
Full details are in our paper: http://www.scott-a-s.com/files/ismm06.pdf I have portions of a draft of a more detailed explanation that I never got around to finishing and publishing.