Struct vulkano::memory::allocator::suballocator::FreeListAllocator

pub struct FreeListAllocator { /* private fields */ }

A suballocator that uses the most generic free-list.

The strength of this allocator is that it can create and free allocations completely dynamically, which means they can be any size and created/freed in any order. The downside is that this always leads to horrific external fragmentation the more such dynamic allocations are made. Therefore, this allocator is best suited for long-lived allocations. If you need to create allocations of various sizes, but can’t afford this fragmentation, then the BuddyAllocator is your best buddy. If you need to create allocations which share a similar size, consider an allocation pool. Lastly, if you need to allocate very often, then BumpAllocator is best suited.

See also the Suballocator implementation.

Algorithm

The free-list stores suballocations which can have any offset and size. When an allocation request is made, the list is searched using the best-fit strategy, meaning that the smallest suballocation that fits the request is chosen. If required, the chosen suballocation is trimmed at the ends and the ends are returned to the free-list. As such, no internal fragmentation occurs. The front might need to be trimmed because of alignment requirements and the end because of a larger than required size. When an allocation is freed, the allocator checks if the adjacent suballocations are free, and if so it coalesces them into a bigger one before putting it in the free-list.

Efficiency

The free-list is sorted by size, which means that when allocating, finding a best-fit is always possible in O(log(n)) time in the worst case. When freeing, the coalescing requires us to remove the adjacent free suballocations from the free-list which is O(log(n)), and insert the possibly coalesced suballocation into the free-list which has the same time complexity, so in total freeing is O(log(n)).

There is one notable edge-case: after the allocator finds a best-fit, it is possible that it needs to align the suballocation’s offset to a higher value, after which the requested size might no longer fit. In such a case, the next free suballocation in sorted order is tried until a fit is successful. If this issue is encountered with all candidates, then the time complexity would be O(n). However, this scenario is extremely unlikely which is why we are not considering it in the above analysis. Additionally, if your free-list is filled with allocations that all have the same size then that seems pretty sus. Sounds like you’re in dire need of an allocation pool.

Trait Implementations

impl Debug for FreeListAllocator

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Suballocator for FreeListAllocator

fn new(region: Region) -> Self

Creates a new FreeListAllocator for the given region.

fn allocate( &self, layout: DeviceLayout, allocation_type: AllocationType, buffer_image_granularity: DeviceAlignment ) -> Result<Suballocation, SuballocatorError>

Creates a new suballocation within the region.

unsafe fn deallocate(&self, suballocation: Suballocation)

Deallocates the given suballocation.

fn free_size(&self) -> DeviceSize

Returns the total amount of free space that is left in the region.

fn cleanup(&mut self)

Tries to free some space, if applicable.