Re: Joy of this, Joy of that

On Wed, 27 Nov 2024 17:20:44 +0000, The Natural Philosopher wrote:

... my instinct would be to hold a long list of pointers to allocated
blocks.

Actually you want a list of free blocks. Structures that include allocated
blocks would be for consistency-checking purposes.

Then you have to decide on what to do if an allocation request doesn’t
exactly match the size of an available free block: do you do “first-fit”
(allocate part of the first block that’s big enough, and return the
remainder to the free list) or “best-fit” (allocate part of the smallest
available block that’s big enough, and return any leftover to the free
list)? The latter might minimize fragmentation, but take more work.

Then you might have “lookaside lists” for common block sizes, to speed up
allocations of those sizes.

Then you realize that having a single list becomes a bottleneck in a
multithreaded program, so you really need multiple free lists. Then you
have to watch out for certain lists shrinking while others grow, and
figure out how to rebalance them once in a while.

There’s a whole lot more to the issue, but you start to get the idea.