Optimization: dedicated allocations are on an intrusive double linked list not sorted vector
Added class VmaIntrusiveLinkedList, struct VmaDedicatedAllocationListItemTraits.
diff --git a/src/vk_mem_alloc.h b/src/vk_mem_alloc.h
index 4876538..629f411 100644
--- a/src/vk_mem_alloc.h
+++ b/src/vk_mem_alloc.h
@@ -6009,6 +6009,222 @@
#endif // #if VMA_USE_STL_LIST
////////////////////////////////////////////////////////////////////////////////
+// class VmaIntrusiveLinkedList
+
+/*
+Expected interface of ItemTypeTraits:
+struct MyItemTypeTraits
+{
+typedef MyItem ItemType;
+static ItemType* GetPrev(const ItemType* item) { return item->myPrevPtr; }
+static ItemType* GetNext(const ItemType* item) { return item->myNextPtr; }
+static ItemType*& AccessPrev(ItemType* item) { return item->myPrevPtr; }
+static ItemType*& AccessNext(ItemType* item) { return item->myNextPtr; }
+};
+*/
+template<typename ItemTypeTraits>
+class VmaIntrusiveLinkedList
+{
+public:
+ typedef typename ItemTypeTraits::ItemType ItemType;
+ static ItemType* GetPrev(const ItemType* item) { return ItemTypeTraits::GetPrev(item); }
+ static ItemType* GetNext(const ItemType* item) { return ItemTypeTraits::GetNext(item); }
+ // Movable, not copyable.
+ VmaIntrusiveLinkedList() { }
+ VmaIntrusiveLinkedList(const VmaIntrusiveLinkedList<ItemTypeTraits>& src) = delete;
+ VmaIntrusiveLinkedList(VmaIntrusiveLinkedList<ItemTypeTraits>&& src) :
+ m_First(src.m_First), m_Last(src.m_Last), m_Count(src.m_Count)
+ {
+ src.m_First = src.m_Last = VMA_NULL;
+ src.m_Count = 0;
+ }
+ ~VmaIntrusiveLinkedList()
+ {
+ VMA_HEAVY_ASSERT(IsEmpty());
+ }
+ VmaIntrusiveLinkedList<ItemTypeTraits>& operator=(const VmaIntrusiveLinkedList<ItemTypeTraits>& src) = delete;
+ VmaIntrusiveLinkedList<ItemTypeTraits>& operator=(VmaIntrusiveLinkedList<ItemTypeTraits>&& src)
+ {
+ if(&src != this)
+ {
+ VMA_HEAVY_ASSERT(IsEmpty());
+ m_First = src.m_First;
+ m_Last = src.m_Last;
+ m_Count = src.m_Count;
+ src.m_First = src.m_Last = VMA_NULL;
+ src.m_Count = 0;
+ }
+ return *this;
+ }
+ void RemoveAll()
+ {
+ if(!IsEmpty())
+ {
+ ItemType* item = m_Back;
+ while(item != VMA_NULL)
+ {
+ ItemType* const prevItem = ItemTypeTraits::AccessPrev(item);
+ ItemTypeTraits::AccessPrev(item) = VMA_NULL;
+ ItemTypeTraits::AccessNext(item) = VMA_NULL;
+ item = prevItem;
+ }
+ m_Front = VMA_NULL;
+ m_Back = VMA_NULL;
+ m_Count = 0;
+ }
+ }
+ size_t GetCount() const { return m_Count; }
+ bool IsEmpty() const { return m_Count == 0; }
+ ItemType* Front() { return m_Front; }
+ const ItemType* Front() const { return m_Front; }
+ ItemType* Back() { return m_Back; }
+ const ItemType* Back() const { return m_Back; }
+ void PushBack(ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(ItemTypeTraits::GetPrev(item) == VMA_NULL && ItemTypeTraits::GetNext(item) == VMA_NULL);
+ if(IsEmpty())
+ {
+ m_Front = item;
+ m_Back = item;
+ m_Count = 1;
+ }
+ else
+ {
+ ItemTypeTraits::AccessPrev(item) = m_Back;
+ ItemTypeTraits::AccessNext(m_Back) = item;
+ m_Back = item;
+ ++m_Count;
+ }
+ }
+ void PushFront(ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(ItemTypeTraits::GetPrev(item) == VMA_NULL && ItemTypeTraits::GetNext(item) == VMA_NULL);
+ if(IsEmpty())
+ {
+ m_Front = item;
+ m_Back = item;
+ m_Count = 1;
+ }
+ else
+ {
+ ItemTypeTraits::AccessNext(item) = m_Front;
+ ItemTypeTraits::AccessPrev(m_Front) = item;
+ m_Front = item;
+ ++m_Count;
+ }
+ }
+ ItemType* PopBack()
+ {
+ VMA_HEAVY_ASSERT(m_Count > 0);
+ ItemType* const backItem = m_Back;
+ ItemType* const prevItem = ItemTypeTraits::GetPrev(backItem);
+ if(prevItem != VMA_NULL)
+ {
+ ItemTypeTraits::AccessNext(prevItem) = VMA_NULL;
+ }
+ m_Back = prevItem;
+ --m_Count;
+ ItemTypeTraits::AccessPrev(backItem) = VMA_NULL;
+ ItemTypeTraits::AccessNext(backItem) = VMA_NULL;
+ return backItem;
+ }
+ ItemType* PopFront()
+ {
+ VMA_HEAVY_ASSERT(m_Count > 0);
+ ItemType* const frontItem = m_Front;
+ ItemType* const nextItem = ItemTypeTraits::GetNext(frontItem);
+ if(nextItem != VMA_NULL)
+ {
+ ItemTypeTraits::AccessPrev(nextItem) = VMA_NULL;
+ }
+ m_Front = nextItem;
+ --m_Count;
+ ItemTypeTraits::AccessPrev(frontItem) = VMA_NULL;
+ ItemTypeTraits::AccessNext(frontItem) = VMA_NULL;
+ return frontItem;
+ }
+
+ // MyItem can be null - it means PushBack.
+ void InsertBefore(ItemType* existingItem, ItemType* newItem)
+ {
+ VMA_HEAVY_ASSERT(newItem != VMA_NULL && ItemTypeTraits::GetPrev(newItem) == VMA_NULL && ItemTypeTraits::GetNext(newItem) == VMA_NULL);
+ if(existingItem != VMA_NULL)
+ {
+ ItemType* const prevItem = ItemTypeTraits::GetPrev(existingItem);
+ ItemTypeTraits::AccessPrev(newItem) = prevItem;
+ ItemTypeTraits::AccessNext(newItem) = existingItem;
+ ItemTypeTraits::AccessPrev(existingItem) = newItem;
+ if(prevItem != VMA_NULL)
+ {
+ ItemTypeTraits::AccessNext(prevItem) = newItem;
+ }
+ else
+ {
+ VMA_HEAVY_ASSERT(m_Front == existingItem);
+ m_Front = newItem;
+ }
+ ++m_Count;
+ }
+ else
+ PushBack(newItem);
+ }
+ // MyItem can be null - it means PushFront.
+ void InsertAfter(ItemType* existingItem, ItemType* newItem)
+ {
+ VMA_HEAVY_ASSERT(newItem != VMA_NULL && ItemTypeTraits::GetPrev(newItem) == VMA_NULL && ItemTypeTraits::GetNext(newItem) == VMA_NULL);
+ if(existingItem != VMA_NULL)
+ {
+ ItemType* const nextItem = ItemTypeTraits::GetNext(existingItem);
+ ItemTypeTraits::AccessNext(newItem) = nextItem;
+ ItemTypeTraits::AccessPrev(newItem) = existingItem;
+ ItemTypeTraits::AccessNext(existingItem) = newItem;
+ if(nextItem != VMA_NULL)
+ {
+ ItemTypeTraits::AccessPrev(nextItem) = newItem;
+ }
+ else
+ {
+ VMA_HEAVY_ASSERT(m_Back == existingItem);
+ m_Back = newItem;
+ }
+ ++m_Count;
+ }
+ else
+ return PushFront(newItem);
+ }
+ void Remove(ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(item != VMA_NULL && m_Count > 0);
+ if(ItemTypeTraits::GetPrev(item) != VMA_NULL)
+ {
+ ItemTypeTraits::AccessNext(ItemTypeTraits::AccessPrev(item)) = ItemTypeTraits::GetNext(item);
+ }
+ else
+ {
+ VMA_HEAVY_ASSERT(m_Front == item);
+ m_Front = ItemTypeTraits::GetNext(item);
+ }
+
+ if(ItemTypeTraits::GetNext(item) != VMA_NULL)
+ {
+ ItemTypeTraits::AccessPrev(ItemTypeTraits::AccessNext(item)) = ItemTypeTraits::GetPrev(item);
+ }
+ else
+ {
+ VMA_HEAVY_ASSERT(m_Back == item);
+ m_Back = ItemTypeTraits::GetPrev(item);
+ }
+ ItemTypeTraits::AccessPrev(item) = VMA_NULL;
+ ItemTypeTraits::AccessNext(item) = VMA_NULL;
+ --m_Count;
+ }
+private:
+ ItemType* m_Front = VMA_NULL;
+ ItemType* m_Back = VMA_NULL;
+ size_t m_Count = 0;
+};
+
+////////////////////////////////////////////////////////////////////////////////
// class VmaMap
// Unused in this version.
@@ -6222,6 +6438,8 @@
m_MapCount = (pMappedData != VMA_NULL) ? MAP_COUNT_FLAG_PERSISTENT_MAP : 0;
m_DedicatedAllocation.m_hMemory = hMemory;
m_DedicatedAllocation.m_pMappedData = pMappedData;
+ m_DedicatedAllocation.m_Prev = VMA_NULL;
+ m_DedicatedAllocation.m_Next = VMA_NULL;
}
ALLOCATION_TYPE GetType() const { return (ALLOCATION_TYPE)m_Type; }
@@ -6319,6 +6537,8 @@
{
VkDeviceMemory m_hMemory;
void* m_pMappedData; // Not null means memory is mapped.
+ VmaAllocation_T* m_Prev;
+ VmaAllocation_T* m_Next;
};
union
@@ -6335,6 +6555,32 @@
#endif
void FreeUserDataString(VmaAllocator hAllocator);
+
+ friend struct VmaDedicatedAllocationListItemTraits;
+};
+
+struct VmaDedicatedAllocationListItemTraits
+{
+ typedef VmaAllocation_T ItemType;
+ static ItemType* GetPrev(const ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(item->GetType() == VmaAllocation_T::ALLOCATION_TYPE_DEDICATED);
+ return item->m_DedicatedAllocation.m_Prev;
+ }
+ static ItemType* GetNext(const ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(item->GetType() == VmaAllocation_T::ALLOCATION_TYPE_DEDICATED);
+ return item->m_DedicatedAllocation.m_Next;
+ }
+ static ItemType*& AccessPrev(ItemType* item)
+ {
+ VMA_HEAVY_ASSERT(item->GetType() == VmaAllocation_T::ALLOCATION_TYPE_DEDICATED);
+ return item->m_DedicatedAllocation.m_Prev;
+ }
+ static ItemType*& AccessNext(ItemType* item){
+ VMA_HEAVY_ASSERT(item->GetType() == VmaAllocation_T::ALLOCATION_TYPE_DEDICATED);
+ return item->m_DedicatedAllocation.m_Next;
+ }
};
/*
@@ -7909,9 +8155,8 @@
// Default pools.
VmaBlockVector* m_pBlockVectors[VK_MAX_MEMORY_TYPES];
- // Each vector is sorted by memory (handle value).
- typedef VmaVector< VmaAllocation, VmaStlAllocator<VmaAllocation> > AllocationVectorType;
- AllocationVectorType* m_pDedicatedAllocations[VK_MAX_MEMORY_TYPES];
+ typedef VmaIntrusiveLinkedList<VmaDedicatedAllocationListItemTraits> DedicatedAllocationLinkedList;
+ DedicatedAllocationLinkedList m_DedicatedAllocations[VK_MAX_MEMORY_TYPES];
VMA_RW_MUTEX m_DedicatedAllocationsMutex[VK_MAX_MEMORY_TYPES];
VmaCurrentBudgetData m_Budget;
@@ -15803,7 +16048,6 @@
memset(&m_MemProps, 0, sizeof(m_MemProps));
memset(&m_pBlockVectors, 0, sizeof(m_pBlockVectors));
- memset(&m_pDedicatedAllocations, 0, sizeof(m_pDedicatedAllocations));
memset(&m_VulkanFunctions, 0, sizeof(m_VulkanFunctions));
if(pCreateInfo->pDeviceMemoryCallbacks != VMA_NULL)
@@ -15862,8 +16106,6 @@
0.5f); // priority (0.5 is the default per Vulkan spec)
// No need to call m_pBlockVectors[memTypeIndex][blockVectorTypeIndex]->CreateMinBlocks here,
// becase minBlockCount is 0.
- m_pDedicatedAllocations[memTypeIndex] = vma_new(this, AllocationVectorType)(VmaStlAllocator<VmaAllocation>(GetAllocationCallbacks()));
-
}
}
@@ -15918,15 +16160,14 @@
VMA_ASSERT(m_Pools.empty());
- for(size_t i = GetMemoryTypeCount(); i--; )
+ for(size_t memTypeIndex = GetMemoryTypeCount(); memTypeIndex--; )
{
- if(m_pDedicatedAllocations[i] != VMA_NULL && !m_pDedicatedAllocations[i]->empty())
+ if(!m_DedicatedAllocations[memTypeIndex].IsEmpty())
{
VMA_ASSERT(0 && "Unfreed dedicated allocations found.");
}
- vma_delete(this, m_pDedicatedAllocations[i]);
- vma_delete(this, m_pBlockVectors[i]);
+ vma_delete(this, m_pBlockVectors[memTypeIndex]);
}
}
@@ -16382,14 +16623,13 @@
if(res == VK_SUCCESS)
{
- // Register them in m_pDedicatedAllocations.
+ // Register them in m_DedicatedAllocations.
{
VmaMutexLockWrite lock(m_DedicatedAllocationsMutex[memTypeIndex], m_UseMutex);
- AllocationVectorType* pDedicatedAllocations = m_pDedicatedAllocations[memTypeIndex];
- VMA_ASSERT(pDedicatedAllocations);
+ DedicatedAllocationLinkedList& dedicatedAllocations = m_DedicatedAllocations[memTypeIndex];
for(allocIndex = 0; allocIndex < allocationCount; ++allocIndex)
{
- VmaVectorInsertSorted<VmaPointerLess>(*pDedicatedAllocations, pAllocations[allocIndex]);
+ dedicatedAllocations.PushBack(pAllocations[allocIndex]);
}
}
@@ -16774,12 +17014,12 @@
{
const uint32_t memHeapIndex = MemoryTypeIndexToHeapIndex(memTypeIndex);
VmaMutexLockRead dedicatedAllocationsLock(m_DedicatedAllocationsMutex[memTypeIndex], m_UseMutex);
- AllocationVectorType* const pDedicatedAllocVector = m_pDedicatedAllocations[memTypeIndex];
- VMA_ASSERT(pDedicatedAllocVector);
- for(size_t allocIndex = 0, allocCount = pDedicatedAllocVector->size(); allocIndex < allocCount; ++allocIndex)
+ DedicatedAllocationLinkedList& dedicatedAllocList = m_DedicatedAllocations[memTypeIndex];
+ for(VmaAllocation alloc = dedicatedAllocList.Front();
+ alloc != VMA_NULL; alloc = dedicatedAllocList.GetNext(alloc))
{
VmaStatInfo allocationStatInfo;
- (*pDedicatedAllocVector)[allocIndex]->DedicatedAllocCalcStatsInfo(allocationStatInfo);
+ alloc->DedicatedAllocCalcStatsInfo(allocationStatInfo);
VmaAddStatInfo(pStats->total, allocationStatInfo);
VmaAddStatInfo(pStats->memoryType[memTypeIndex], allocationStatInfo);
VmaAddStatInfo(pStats->memoryHeap[memHeapIndex], allocationStatInfo);
@@ -17501,10 +17741,8 @@
const uint32_t memTypeIndex = allocation->GetMemoryTypeIndex();
{
VmaMutexLockWrite lock(m_DedicatedAllocationsMutex[memTypeIndex], m_UseMutex);
- AllocationVectorType* const pDedicatedAllocations = m_pDedicatedAllocations[memTypeIndex];
- VMA_ASSERT(pDedicatedAllocations);
- bool success = VmaVectorRemoveSorted<VmaPointerLess>(*pDedicatedAllocations, allocation);
- VMA_ASSERT(success);
+ DedicatedAllocationLinkedList& dedicatedAllocations = m_DedicatedAllocations[memTypeIndex];
+ dedicatedAllocations.Remove(allocation);
}
VkDeviceMemory hMemory = allocation->GetMemory();
@@ -17716,9 +17954,8 @@
for(uint32_t memTypeIndex = 0; memTypeIndex < GetMemoryTypeCount(); ++memTypeIndex)
{
VmaMutexLockRead dedicatedAllocationsLock(m_DedicatedAllocationsMutex[memTypeIndex], m_UseMutex);
- AllocationVectorType* const pDedicatedAllocVector = m_pDedicatedAllocations[memTypeIndex];
- VMA_ASSERT(pDedicatedAllocVector);
- if(pDedicatedAllocVector->empty() == false)
+ DedicatedAllocationLinkedList& dedicatedAllocList = m_DedicatedAllocations[memTypeIndex];
+ if(!dedicatedAllocList.IsEmpty())
{
if(dedicatedAllocationsStarted == false)
{
@@ -17733,11 +17970,11 @@
json.BeginArray();
- for(size_t i = 0; i < pDedicatedAllocVector->size(); ++i)
+ for(VmaAllocation alloc = dedicatedAllocList.Front();
+ alloc != VMA_NULL; alloc = dedicatedAllocList.GetNext(alloc))
{
json.BeginObject(true);
- const VmaAllocation hAlloc = (*pDedicatedAllocVector)[i];
- hAlloc->PrintParameters(json);
+ alloc->PrintParameters(json);
json.EndObject();
}
