This is regarding the TLSF implementation's CreateAllocationRequest method- the way this method seems to work is that it will attempt to locate the best free block with enough available space. However, there is a problem when there is not a free block with enough available space. The implementation has a number of fast escapes in this situation- in particular, it will fast escape if the total free space in the metadata is not enough to support the new allocation, or if there are no free blocks at all.
However, in situations where there's some fragmentation and there is enough total space among free blocks to support the new allocation, but there is no free block with enough space, we have an issue. The TLSF algorithm makes it very easy to determine that we are in this state, but we don't do a particularly good job of responding.
Iif we can't find a good block in the two buckets that most closely fit our requested size, we will do a brute force search of larger buckets (https://github.com/GPUOpen-LibrariesAndSDKs/VulkanMemoryAllocator/blob/master/include/vk_mem_alloc.h#L10409). This isn't an issue. However, the method that retrieves the correct free list index to search in will return 0 if no free blocks large enough to support our requested size are present (https://github.com/GPUOpen-LibrariesAndSDKs/VulkanMemoryAllocator/blob/master/include/vk_mem_alloc.h#L10796). As a result, if there are no blocks large enough to support the requested allocation, we will do a full search of all blocks too small to support the requested size. This has slightly serious performance implications, especially during defragmentation.
I recommend that we do not do a full search in cases where we were unable to find any next* blocks during the initial stages of the search.
This is regarding the TLSF implementation's CreateAllocationRequest method- the way this method seems to work is that it will attempt to locate the best free block with enough available space. However, there is a problem when there is not a free block with enough available space. The implementation has a number of fast escapes in this situation- in particular, it will fast escape if the total free space in the metadata is not enough to support the new allocation, or if there are no free blocks at all.
However, in situations where there's some fragmentation and there is enough total space among free blocks to support the new allocation, but there is no free block with enough space, we have an issue. The TLSF algorithm makes it very easy to determine that we are in this state, but we don't do a particularly good job of responding.
Iif we can't find a good block in the two buckets that most closely fit our requested size, we will do a brute force search of larger buckets (https://github.com/GPUOpen-LibrariesAndSDKs/VulkanMemoryAllocator/blob/master/include/vk_mem_alloc.h#L10409). This isn't an issue. However, the method that retrieves the correct free list index to search in will return 0 if no free blocks large enough to support our requested size are present (https://github.com/GPUOpen-LibrariesAndSDKs/VulkanMemoryAllocator/blob/master/include/vk_mem_alloc.h#L10796). As a result, if there are no blocks large enough to support the requested allocation, we will do a full search of all blocks too small to support the requested size. This has slightly serious performance implications, especially during defragmentation.
I recommend that we do not do a full search in cases where we were unable to find any next* blocks during the initial stages of the search.