Improve FindMemoryTypeIndex by storing hashed creation parameters for buffers or images as key with memory type index as value

[IAmNotHanni]

This is based on an idea from @adam-sawicki-a and @papazhang66 which came up in #419.

Intro

Currently, when FindMemoryTypeIndex is called, it has to do quite some work to get find right memory type for the specified creation parameters:

VkResult VmaAllocator_T::FindMemoryTypeIndex(
    uint32_t memoryTypeBits,
    const VmaAllocationCreateInfo* pAllocationCreateInfo,
    VkFlags bufImgUsage,
    uint32_t* pMemoryTypeIndex) const
{
    memoryTypeBits &= GetGlobalMemoryTypeBits();

    if(pAllocationCreateInfo->memoryTypeBits != 0)
    {
        memoryTypeBits &= pAllocationCreateInfo->memoryTypeBits;
    }

    VkMemoryPropertyFlags requiredFlags = 0, preferredFlags = 0, notPreferredFlags = 0;
    if(!FindMemoryPreferences(
        IsIntegratedGpu(),
        *pAllocationCreateInfo,
        bufImgUsage,
        requiredFlags, preferredFlags, notPreferredFlags))
    {
        return VK_ERROR_FEATURE_NOT_PRESENT;
    }

    *pMemoryTypeIndex = UINT32_MAX;
    uint32_t minCost = UINT32_MAX;
    for(uint32_t memTypeIndex = 0, memTypeBit = 1;
        memTypeIndex < GetMemoryTypeCount();
        ++memTypeIndex, memTypeBit <<= 1)
    {
        // This memory type is acceptable according to memoryTypeBits bitmask.
        if((memTypeBit & memoryTypeBits) != 0)
        {
            const VkMemoryPropertyFlags currFlags =
                m_MemProps.memoryTypes[memTypeIndex].propertyFlags;
            // This memory type contains requiredFlags.
            if((requiredFlags & ~currFlags) == 0)
            {
                // Calculate cost as number of bits from preferredFlags not present in this memory type.
                uint32_t currCost = VMA_COUNT_BITS_SET(preferredFlags & ~currFlags) +
                    VMA_COUNT_BITS_SET(currFlags & notPreferredFlags);
                // Remember memory type with lowest cost.
                if(currCost < minCost)
                {
                    *pMemoryTypeIndex = memTypeIndex;
                    if(currCost == 0)
                    {
                        return VK_SUCCESS;
                    }
                    minCost = currCost;
                }
            }
        }
    }
    return (*pMemoryTypeIndex != UINT32_MAX) ? VK_SUCCESS : VK_ERROR_FEATURE_NOT_PRESENT;
}

Improvement

The idea would be to hash all parameters used for buffer or image creation in an std::unordered_map with the parameters as key and an std::uint32_t as value for the memory type index. You can write your own hashing function for std::unordered_map (by specifying it as third parameter), and using such a cache with an underlying hash system is very common for other Vulkan objects pipelines or descriptor set layouts (for example, here is a nice tutorial which describes an abstraction for descriptor set layouts: https://vkguide.dev/docs/extra-chapter/abstracting_descriptors).

How much this improves performance is something that would have to be measured. On the one side the hashing will take a little time, but so does calling FindMemoryTypeIndex currently. In general, performance is something that must always be measured instead of being estimated. This could easily analyzed by writing a test for it when implementing this feature. There are also other frameworks like Google Benchmark for advanced benchmarking. It is likely that the exact performance improvement depends a lot on the actual parameters, the hardware, and more factors.

This brings me to another question:
@adam-sawicki-a Are there other parts in the code where you think such a cache with hashed values could improve performance?

best regards
Johannes

[IAmNotHanni]

I just realized two more things:

1. Testing

Since the result of FindMemoryTypeIndex depends on the actual gpu that is used, testing might be not that easy. We could implement it so that we a function which uses the cache and another one which doesn't, but that would introduce duplicated code. Another option would be to expose the use of the cache as a bool parameter which is true by default:

VkResult VmaAllocator_T::FindMemoryTypeIndex(
    uint32_t memoryTypeBits,
    const VmaAllocationCreateInfo* pAllocationCreateInfo,
    VkFlags bufImgUsage,
    uint32_t* pMemoryTypeIndex,
    bool useCache = true) const // Note that default parameters must be last
{ // ...

(like bool use_cache = true), which would allow to run tests with cache enabled and cache disabled, and to check if the results are the same as they should be. Yet another option would be conditional compilation for using the cache like

VkResult VmaAllocator_T::FindMemoryTypeIndex(
    uint32_t memoryTypeBits,
    const VmaAllocationCreateInfo* pAllocationCreateInfo,
    VkFlags bufImgUsage,
    uint32_t* pMemoryTypeIndex) const
{
#ifdef VMA_USE_FIND_MEMORY_TYPE_INDEX_CACHE
// Early lookup in cache here ...
if(CacheLookupMemoryTypeIndex(memoryTypeBits, pAllocationCreateInfo, bufImgUsage, pMemoryTypeIndex)) {
   return result;
}
#endif

2. Preparing indices in advance at startup?

Can't we just look the matching memory type index (or indices) for all possible permutations of create parameters in advance at startup? This should be somewhat possible, right? Because then, FindMemoryTypeIndex would only need to look up in the cache at runtime. I guess the memory types don't change at runtime.

best regards
Johannes

[adam-sawicki-a]

What makes you think that the performance of function VmaAllocator_T::FindMemoryTypeIndex and FindMemoryPreferences is bad? It is just some logic with integer and bitwise operations, conditions, and a loop over memory types, which is typically just a few, never more than 32.

I am not convinced that hashing parameters and using a hash map would be faster than that. I would consider implementing this cache only if it can be proven or if many users complain that that the current implementation is a performance problem and that the cache is significantly faster.

Besides this, as you can see in the documentation, "Frequently asked questions" chapter, VMA doesn't use STL containers. I will not break this rule by using std::unordered_map just to implement this caching.

Ticket #419 was not about the performance of the function you mentioned here. It was about the need to create a dummy buffer to query for memory requirements, which is a separate topic and may indeed have some performance penalty.

I appreciate your contribution to this project, but please limit the amount of additions you propose to it. The faster it grows, the faster I abandon it as non-manageable.

BTW, did you use AI to generate this ticket?

[IAmNotHanni]

Alright, ok. No, I don't use any AI, I just look for stuff to implement manually.

[papazhang66]

our environment is on streaming. currently every vkCreateBuffer is synchronous call from guest to host. this take long time than native system. we may thinking add the hash at top level if it is too complicated at library.