Optimize ArrayPreallocationPolicy.

The tricks applied are identical to those done previously for
ArrayAllocationPolicy:

We remove the obsolete hash for the index mapping and instead use
pointer differences directly, which is much faster and reduces
the memory consumption.

Some variables are also renamed to better reflect common allocator
nomenclature.

The added benchmark shows a reduction of the instruction count
by a factor of about 10.

Change-Id: Icabc354ab9e1e8ea0b1dc83c71a2f2cfe49d1da0
Reviewed-by: Sean Harmer <sean.harmer@kdab.com>

5 files changed, 74 insertions, 49 deletions

diff --git a/src/core/resources/qresourcesmanager.h b/src/core/resources/qresourcesmanager.h
index 2fe544a79..aeaefbc89 100644
--- a/src/core/resources/qresourcesmanager.h
+++ b/src/core/resources/qresourcesmanager.h
@@ -267,43 +267,43 @@ class ArrayPreallocationPolicy
 {
 public:
     ArrayPreallocationPolicy()
-        : m_resourcesEntries(1 << INDEXBITS)
     {
-        for (int i = 0; i < m_resourcesEntries.size(); i++)
-            m_freeEntryIndices << i;
+        reset();
     }
 
     T* allocateResource()
     {
-        int idx = m_freeEntryIndices.takeFirst();
-        T* newT = m_resourcesEntries.data() + idx;
-        m_resourcesToIndices[newT] = idx;
-        return newT;
+        Q_ASSERT(!m_freeList.isEmpty());
+        int idx = m_freeList.last();
+        m_freeList.pop_back();
+        return m_bucket.data() + idx;
     }
 
     void releaseResource(T *r)
     {
-        if (m_resourcesToIndices.contains(r)) {
-            int idx = m_resourcesToIndices.take(r);
-            performCleanup(r, Int2Type<QResourceInfo<T>::needsCleanup>());
-            m_resourcesEntries[idx] = T();
-            m_freeEntryIndices.append(idx);
-        }
+        Q_ASSERT(m_bucket.data() <= r && r < m_bucket.data() + MaxSize);
+        int idx = r - m_bucket.data();
+        m_freeList.append(idx);
+        performCleanup(r, Int2Type<QResourceInfo<T>::needsCleanup>());
+        *r = T();
     }
 
     void reset()
     {
-        m_resourcesToIndices.clear();
-        m_resourcesEntries.clear();
-        m_resourcesEntries.resize(1 << INDEXBITS);
-        for (int i = 0; i < m_resourcesEntries.size(); i++)
-            m_freeEntryIndices << i;
+        m_bucket.clear();
+        m_bucket.resize(MaxSize);
+        m_freeList.resize(MaxSize);
+        for (int i = 0; i < MaxSize; i++)
+            m_freeList[i] = MaxSize - (i + 1);
     }
 
 private:
-    QVector<T> m_resourcesEntries;
-    QList<int> m_freeEntryIndices;
-    QHash<T*, int> m_resourcesToIndices;
+    enum {
+      MaxSize = 1 << INDEXBITS
+    };
+
+    QVector<T> m_bucket;
+    QVector<int> m_freeList;
 
     void performCleanup(T *r, Int2Type<true>)
     {
diff --git a/tests/benchmarks/core/qresourcesmanager/arraypolicy/arraypolicy.pro b/tests/benchmarks/core/qresourcesmanager/arraypolicy/arraypolicy.pro
new file mode 100644
index 000000000..2195d5e4f
--- /dev/null
+++ b/tests/benchmarks/core/qresourcesmanager/arraypolicy/arraypolicy.pro
@@ -0,0 +1,6 @@
+TARGET = tst_bench_arraypolicy
+
+TEMPLATE = app
+QT += testlib 3dcore
+
+SOURCES += tst_bench_arraypolicy.cpp
diff --git a/tests/benchmarks/core/qresourcesmanager/dynamicarraypolicy/tst_bench_dynamicarraypolicy.cpp b/tests/benchmarks/core/qresourcesmanager/arraypolicy/tst_bench_arraypolicy.cpp
index 9dcba7ccf..19580be11 100644
--- a/tests/benchmarks/core/qresourcesmanager/dynamicarraypolicy/tst_bench_dynamicarraypolicy.cpp
+++ b/tests/benchmarks/core/qresourcesmanager/arraypolicy/tst_bench_arraypolicy.cpp
@@ -43,14 +43,19 @@
 #include <QMatrix4x4>
 #include <Qt3DCore/QResourcesManager>
 
-class tst_DynamicArrayPolicy : public QObject
+class tst_ArrayPolicy : public QObject
 {
     Q_OBJECT
 private Q_SLOTS:
-    void benchmarkAllocateSmallResources();
-    void benchmarkReleaseSmallResources();
-    void benchmarkAllocateBigResources();
-    void benchmarkReleaseBigResources();
+    void benchmarkDynamicAllocateSmallResources();
+    void benchmarkDynamicReleaseSmallResources();
+    void benchmarkDynamicAllocateBigResources();
+    void benchmarkDynamicReleaseBigResources();
+
+    void benchmarkPreallocatedAllocateSmallResources();
+    void benchmarkPreallocatedReleaseSmallResources();
+    void benchmarkPreallocatedAllocateBigResources();
+    void benchmarkPreallocatedReleaseBigResources();
 };
 
 struct SmallType
@@ -63,10 +68,10 @@ struct BigType
     QMatrix4x4 a;
 };
 
-template<typename T>
+template<typename C, typename T>
 void benchmarkAllocateResources()
 {
-    Qt3D::ArrayAllocatingPolicy<T, 16> allocator;
+    C allocator;
 
     const int max = (1 << 16) - 1;
     QBENCHMARK_ONCE {
@@ -77,44 +82,64 @@ void benchmarkAllocateResources()
     }
 }
 
-template<typename T>
+template<typename C, typename T>
 void benchmarkReleaseResources()
 {
-    Qt3D::ArrayAllocatingPolicy<int, 16> allocator;
+    C allocator;
 
     const int max = (1 << 16) - 1;
-    QVector<int*> resources(max);
+    QVector<T*> resources(max);
     for (int i = 0; i < max; i++) {
         resources[i] = allocator.allocateResource();
     }
 
     QBENCHMARK_ONCE {
-        foreach (int* ptr, resources) {
+        foreach (T* ptr, resources) {
             allocator.releaseResource(ptr);
         }
     }
 }
 
-void tst_DynamicArrayPolicy::benchmarkAllocateSmallResources()
+void tst_ArrayPolicy::benchmarkDynamicAllocateSmallResources()
+{
+    benchmarkAllocateResources<Qt3D::ArrayAllocatingPolicy<SmallType, 16>, SmallType>();
+}
+
+void tst_ArrayPolicy::benchmarkDynamicReleaseSmallResources()
+{
+    benchmarkReleaseResources<Qt3D::ArrayAllocatingPolicy<SmallType, 16>, SmallType>();
+}
+
+void tst_ArrayPolicy::benchmarkDynamicAllocateBigResources()
+{
+    benchmarkAllocateResources<Qt3D::ArrayAllocatingPolicy<BigType, 16>, BigType>();
+}
+
+void tst_ArrayPolicy::benchmarkDynamicReleaseBigResources()
+{
+    benchmarkReleaseResources<Qt3D::ArrayAllocatingPolicy<BigType, 16>, BigType>();
+}
+
+void tst_ArrayPolicy::benchmarkPreallocatedAllocateSmallResources()
 {
-    benchmarkAllocateResources<SmallType>();
+    benchmarkAllocateResources<Qt3D::ArrayPreallocationPolicy<SmallType, 16>, SmallType>();
 }
 
-void tst_DynamicArrayPolicy::benchmarkReleaseSmallResources()
+void tst_ArrayPolicy::benchmarkPreallocatedReleaseSmallResources()
 {
-    benchmarkReleaseResources<SmallType>();
+    benchmarkReleaseResources<Qt3D::ArrayPreallocationPolicy<SmallType, 16>, SmallType>();
 }
 
-void tst_DynamicArrayPolicy::benchmarkAllocateBigResources()
+void tst_ArrayPolicy::benchmarkPreallocatedAllocateBigResources()
 {
-    benchmarkAllocateResources<BigType>();
+    benchmarkAllocateResources<Qt3D::ArrayPreallocationPolicy<BigType, 16>, BigType>();
 }
 
-void tst_DynamicArrayPolicy::benchmarkReleaseBigResources()
+void tst_ArrayPolicy::benchmarkPreallocatedReleaseBigResources()
 {
-    benchmarkReleaseResources<BigType>();
+    benchmarkReleaseResources<Qt3D::ArrayPreallocationPolicy<BigType, 16>, BigType>();
 }
 
-QTEST_APPLESS_MAIN(tst_DynamicArrayPolicy)
+QTEST_APPLESS_MAIN(tst_ArrayPolicy)
 
-#include "tst_bench_dynamicarraypolicy.moc"
+#include "tst_bench_arraypolicy.moc"
diff --git a/tests/benchmarks/core/qresourcesmanager/dynamicarraypolicy/dynamicarraypolicy.pro b/tests/benchmarks/core/qresourcesmanager/dynamicarraypolicy/dynamicarraypolicy.pro
deleted file mode 100644
index d4b32b55c..000000000
--- a/tests/benchmarks/core/qresourcesmanager/dynamicarraypolicy/dynamicarraypolicy.pro
+++ /dev/null
@@ -1,6 +0,0 @@
-TARGET = tst_bench_dynamicarraypolicy
-
-TEMPLATE = app
-QT += testlib 3dcore
-
-SOURCES += tst_bench_dynamicarraypolicy.cpp
diff --git a/tests/benchmarks/core/qresourcesmanager/qresourcesmanager.pro b/tests/benchmarks/core/qresourcesmanager/qresourcesmanager.pro
index 37b73b61a..9de015e73 100644
--- a/tests/benchmarks/core/qresourcesmanager/qresourcesmanager.pro
+++ b/tests/benchmarks/core/qresourcesmanager/qresourcesmanager.pro
@@ -1,5 +1,5 @@
 TEMPLATE = subdirs
 
 SUBDIRS += \
-        dynamicarraypolicy \
+        arraypolicy \
         qresourcesmanager