Particles: replace a QSet<int> with a bit vector for group data.

The reusableIndexes represented a "free-list". Now the allocation
behavior in QQuickParticleGroupData::setSize was to grow by (large)
chunks. That means that as soon setSize was called, a (big) number of
hash entries was created, which are drained over time. This memory would
stay around (and probably unused) as long as the group was alive.

By using a bit vector, the amount of memory is much more compressed,
and finding an entry takes less time. The FreeList "caches" the next
free entry, because allocation and de-allocation behavior is that they
occur bunches: allocate a number of particles, use them, allocate the
same number.

Test case: samegame, 1 player, click 1 set of 3 stones, quit.
QQuickParticleSystem::emittersChanged(), before patch:
 - 21 instr. inclusive, 15M in QQuickParticleGroupData::setSize
 - 23,000 calls to QHashData::allocateNode
after:
 - 13M instr. inclusive, 7M in QQuickParticleGroupData::setSize
 - 0 calls to QHashData::allocateNode

Change-Id: If35ea5ed9b29129f210638f6f59275a24eb6afdc
Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>

2 files changed, 70 insertions, 10 deletions

diff --git a/src/particles/qquickparticlesystem.cpp b/src/particles/qquickparticlesystem.cpp
index e9bd073133..f4c9121007 100644
--- a/src/particles/qquickparticlesystem.cpp
+++ b/src/particles/qquickparticlesystem.cpp
@@ -339,11 +339,11 @@ void QQuickParticleGroupData::setSize(int newSize)
         return;
     Q_ASSERT(newSize > m_size);//XXX allow shrinking
     data.resize(newSize);
+    freeList.resize(newSize);
     for (int i=m_size; i<newSize; i++) {
         data[i] = new QQuickParticleData;
         data[i]->groupId = index;
         data[i]->index = i;
-        reusableIndexes << i;
     }
     int delta = newSize - m_size;
     m_size = newSize;
@@ -362,16 +362,15 @@ void QQuickParticleGroupData::kill(QQuickParticleData* d)
     d->lifeSpan = 0;//Kill off
     foreach (QQuickParticlePainter* p, painters)
         p->reload(d);
-    reusableIndexes << d->index;
+    freeList.free(d->index);
 }
 
 QQuickParticleData* QQuickParticleGroupData::newDatum(bool respectsLimits)
 {
     //recycle();//Extra recycler round to be sure?
 
-    while (!reusableIndexes.empty()) {
-        int idx = *(reusableIndexes.begin());
-        reusableIndexes.remove(idx);
+    while (freeList.hasUnusedEntries()) {
+        int idx = freeList.alloc();
         if (data[idx]->stillAlive(m_system)) {// ### This means resurrection of 'dead' particles. Is that allowed?
             prepareRecycler(data[idx]);
             continue;
@@ -383,8 +382,9 @@ QQuickParticleData* QQuickParticleGroupData::newDatum(bool respectsLimits)
 
     int oldSize = m_size;
     setSize(oldSize + 10);//###+1,10%,+10? Choose something non-arbitrarily
-    reusableIndexes.remove(oldSize);
-    return data[oldSize];
+    int idx = freeList.alloc();
+    Q_ASSERT(idx == oldSize);
+    return data[idx];
 }
 
 bool QQuickParticleGroupData::recycle()
@@ -392,7 +392,7 @@ bool QQuickParticleGroupData::recycle()
     while (dataHeap.top() <= m_system->timeInt) {
         foreach (QQuickParticleData* datum, dataHeap.pop()) {
             if (!datum->stillAlive(m_system)) {
-                reusableIndexes << datum->index;
+                freeList.free(datum->index);
             } else {
                 prepareRecycler(datum); //ttl has been altered mid-way, put it back
             }
@@ -400,7 +400,7 @@ bool QQuickParticleGroupData::recycle()
     }
 
     //TODO: If the data is clear, gc (consider shrinking stack size)?
-    return reusableIndexes.count() == m_size;
+    return freeList.count() == 0;
 }
 
 void QQuickParticleGroupData::prepareRecycler(QQuickParticleData* d)
diff --git a/src/particles/qquickparticlesystem_p.h b/src/particles/qquickparticlesystem_p.h
index fcdd027a54..182fc6aed6 100644
--- a/src/particles/qquickparticlesystem_p.h
+++ b/src/particles/qquickparticlesystem_p.h
@@ -61,6 +61,7 @@
 #include <QAbstractAnimation>
 #include <QtQml/qqml.h>
 #include <private/qv8engine_p.h> //For QQmlV4Handle
+#include <private/qv4util_p.h>
 #include "qtquickparticlesglobal_p.h"
 
 QT_BEGIN_NAMESPACE
@@ -134,6 +135,65 @@ private:
 };
 
 class Q_QUICKPARTICLES_PRIVATE_EXPORT QQuickParticleGroupData {
+    class FreeList
+    {
+    public:
+        FreeList()
+            : firstUnused(UINT_MAX)
+            , allocated(0)
+        {}
+
+        void resize(int newSize)
+        {
+            Q_ASSERT(newSize >= 0);
+            int oldSize = isUnused.size();
+            isUnused.resize(newSize, true);
+            if (newSize > oldSize) {
+                if (firstUnused == UINT_MAX) {
+                    firstUnused = oldSize;
+                } else {
+                    firstUnused = std::min(firstUnused, unsigned(oldSize));
+                }
+            } else if (firstUnused >= unsigned(newSize)) {
+                firstUnused = UINT_MAX;
+            }
+        }
+
+        void free(int index)
+        {
+            isUnused.setBit(index);
+            firstUnused = std::min(firstUnused, unsigned(index));
+            --allocated;
+        }
+
+        int count() const
+        { return allocated; }
+
+        bool hasUnusedEntries() const
+        { return firstUnused != UINT_MAX; }
+
+        int alloc()
+        {
+            if (hasUnusedEntries()) {
+                int nextFree = firstUnused;
+                isUnused.clearBit(firstUnused);
+                firstUnused = isUnused.findNext(firstUnused, true, false);
+                if (firstUnused >= unsigned(isUnused.size())) {
+                    firstUnused = UINT_MAX;
+                }
+                ++allocated;
+                return nextFree;
+            } else {
+                return -1;
+            }
+        }
+
+    private:
+        QV4::BitVector isUnused;
+        unsigned firstUnused;
+        int allocated;
+    };
+
 public: // types
     typedef int ID;
     enum { InvalidID = -1, DefaultGroupID = 0 };
@@ -154,7 +214,7 @@ public:
 
     //TODO: Refactor particle data list out into a separate class
     QVector<QQuickParticleData*> data;
-    QSet<int> reusableIndexes;
+    FreeList freeList;
     QQuickParticleDataHeap dataHeap;
     bool recycle(); //Force recycling round, returns true if all indexes are now reusable