[PATCH vkd3d 2/6] vkd3d: Use a binary search for matching a descriptor to an allocation.

[Conor McCarthy]

The performance improvement will be useful for Vulkan-backed heaps,
where descriptor heaps must be found more often.

Signed-off-by: Conor McCarthy <cmccarthy at codeweavers.com>
---
 libs/vkd3d/device.c | 60 +++++++++++++++++++++++++++++++--------------
 1 file changed, 42 insertions(+), 18 deletions(-)

diff --git a/libs/vkd3d/device.c b/libs/vkd3d/device.c
index 09bdb7a5..537bc7b2 100644
--- a/libs/vkd3d/device.c
+++ b/libs/vkd3d/device.c
@@ -2184,6 +2184,7 @@ bool vkd3d_gpu_descriptor_allocator_register_range(struct vkd3d_gpu_descriptor_a
         const struct d3d12_desc *base, size_t count)
 {
     struct vkd3d_gpu_descriptor_allocation *allocation;
+    size_t i;
     int rc;
 
     if ((rc = pthread_mutex_lock(&allocator->mutex)))
@@ -2199,7 +2200,13 @@ bool vkd3d_gpu_descriptor_allocator_register_range(struct vkd3d_gpu_descriptor_a
         return false;
     }
 
-    allocation = &allocator->allocations[allocator->allocation_count++];
+    for (i = 0; i < allocator->allocation_count; ++i)
+        if (base < allocator->allocations[i].base)
+            break;
+
+    allocation = &allocator->allocations[i];
+    memmove(allocation + 1, allocation, (allocator->allocation_count++ - i) * sizeof(*allocation));
+
     allocation->base = base;
     allocation->count = count;
 
@@ -2226,8 +2233,8 @@ bool vkd3d_gpu_descriptor_allocator_unregister_range(
         if (allocator->allocations[i].base != base)
             continue;
 
-        if (i != --allocator->allocation_count)
-            allocator->allocations[i] = allocator->allocations[allocator->allocation_count];
+        memmove(&allocator->allocations[i], &allocator->allocations[i + 1],
+                (--allocator->allocation_count - i) * sizeof(allocator->allocations[0]));
 
         found = true;
         break;
@@ -2238,12 +2245,40 @@ bool vkd3d_gpu_descriptor_allocator_unregister_range(
     return found;
 }
 
+/* We could use bsearch() or recursion here, but it probably helps to omit
+ * all the extra function calls. */
+static struct vkd3d_gpu_descriptor_allocation *vkd3d_gpu_descriptor_allocator_binary_search(
+        const struct vkd3d_gpu_descriptor_allocator *allocator, const struct d3d12_desc *desc)
+{
+    struct vkd3d_gpu_descriptor_allocation *allocations = allocator->allocations;
+    const struct d3d12_desc *base;
+    size_t centre, count;
+
+    for (count = allocator->allocation_count; count > 1; )
+    {
+        centre = count >> 1;
+        base = allocations[centre].base;
+        if (base <= desc)
+        {
+            allocations += centre;
+            count -= centre;
+        }
+        else
+        {
+            count = centre;
+        }
+    }
+
+    return (desc >= allocations->base && desc < allocations->base + allocations->count) ? allocations : NULL;
+}
+
+
 /* Return the available size from the specified descriptor to the heap end. */
 size_t vkd3d_gpu_descriptor_allocator_range_size_from_descriptor(
         struct vkd3d_gpu_descriptor_allocator *allocator, const struct d3d12_desc *desc)
 {
     struct vkd3d_gpu_descriptor_allocation *allocation;
-    size_t remaining, offset, i;
+    size_t remaining;
     int rc;
 
     if ((rc = pthread_mutex_lock(&allocator->mutex)))
@@ -2252,20 +2287,9 @@ size_t vkd3d_gpu_descriptor_allocator_range_size_from_descriptor(
         return 0;
     }
 
-    for (i = 0, remaining = 0; i < allocator->allocation_count; ++i)
-    {
-        allocation = &allocator->allocations[i];
-
-        if (desc < allocation->base)
-            continue;
-
-        offset = desc - allocation->base;
-        if (offset >= allocation->count)
-            continue;
-
-        remaining = allocation->count - offset;
-        break;
-    }
+    remaining = 0;
+    if ((allocation = vkd3d_gpu_descriptor_allocator_binary_search(allocator, desc)))
+        remaining = allocation->count - (desc - allocation->base);
 
     pthread_mutex_unlock(&allocator->mutex);
 
-- 
2.33.0