diff options
author | Erik Verbruggen <erik.verbruggen@digia.com> | 2016-03-03 15:06:25 +0100 |
---|---|---|
committer | Erik Verbruggen <erik.verbruggen@theqtcompany.com> | 2016-03-08 09:37:40 +0000 |
commit | ec3b4cf7a5de9a4ead73f09c3d7a02421b29f805 (patch) | |
tree | 38f816e8ca1219c81bb5419ef1c7ef60209630a1 | |
parent | 350a74ec69b535df07ad7ca45415090749c75293 (diff) |
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>
-rw-r--r-- | src/particles/qquickparticlesystem.cpp | 18 | ||||
-rw-r--r-- | src/particles/qquickparticlesystem_p.h | 62 | ||||
-rw-r--r-- | src/qml/jsruntime/qv4util_p.h | 10 |
3 files changed, 80 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 diff --git a/src/qml/jsruntime/qv4util_p.h b/src/qml/jsruntime/qv4util_p.h index 132abd211e..59c12c5e46 100644 --- a/src/qml/jsruntime/qv4util_p.h +++ b/src/qml/jsruntime/qv4util_p.h @@ -102,6 +102,9 @@ public: void resize(int newSize) { bits.resize(newSize); } + void resize(int newSize, bool newValue) + { bits.resize(newSize, newValue); } + void assign(int newSize, bool value) { bits.assign(newSize, value); } @@ -159,6 +162,13 @@ public: void resize(int newSize) { bits.resize(newSize); } + void resize(int newSize, bool newValue) + { + int oldSize = bits.size(); + bits.resize(newSize); + bits.fill(newValue, oldSize, bits.size()); + } + void assign(int newSize, bool value) { bits.resize(newSize); |