This uses Knuth boundary tags to allow constant-time coalescing. The
allocator remains first fit, but with this implementation, all of the
O(n) loops have been removed except for the scan for first fit, which
can exit early.
The free list has been altered to search for chunks in FIFO order; from
Wilson's survey, this is an excellent strategy compared to other simple
approaches, since it maximizes the amount of time a chunk is available
to be coalesced. This minimizes fragmentation, which increases the
expected speed of the first fit scan.
A typical boundary tag implementation requires a boolean tag on each
chunk indicating whether the previous chunk is free. We do this the
usual way: chunks are aligned to 2, and the prev_free tag is the LSB of
the size.
The minimum allocation size remains 8 bytes. Two bytes are used per
allocated chunk for the size and prev_free bit, and one byte of padding
is used at the end for odd sized requests. Other than this, there is now
no additional wasted space to maintain the free list, since the list is
now maintained entirely using the free portions of the heap.
The cost is a modestly increased implementation size. This also includes
an implementation of aligned_alloc. But broadly, this is more in line
with what's expected from a modern malloc implementation. The main
improvement possible at this point would be to achieve constant time
allocations using size-segregated free lists, but this would need actual
measurement.
This uses Knuth boundary tags to allow constant-time coalescing. The allocator remains first fit, but with this implementation, all of the O(n) loops have been removed except for the scan for first fit, which can exit early.
The free list has been altered to search for chunks in FIFO order; from Wilson's survey, this is an excellent strategy compared to other simple approaches, since it maximizes the amount of time a chunk is available to be coalesced. This minimizes fragmentation, which increases the expected speed of the first fit scan.
A typical boundary tag implementation requires a boolean tag on each chunk indicating whether the previous chunk is free. We do this the usual way: chunks are aligned to 2, and the prev_free tag is the LSB of the size.
The minimum allocation size remains 8 bytes. Two bytes are used per allocated chunk for the size and prev_free bit, and one byte of padding is used at the end for odd sized requests. Other than this, there is now no additional wasted space to maintain the free list, since the list is now maintained entirely using the free portions of the heap.
The cost is a modestly increased implementation size. This also includes an implementation of
aligned_alloc. But broadly, this is more in line with what's expected from a modern malloc implementation. The main improvement possible at this point would be to achieve constant time allocations using size-segregated free lists, but this would need actual measurement.