From 252d2e5f2a237862cc50f926f66184d499298239 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Wed, 6 Sep 2017 13:17:54 +0200 Subject: Rework resource handling Rework the way the QResourceManager allocates and manages it's resources. Get rid of the huge pre-allocated freelist, and instead merge it with the counter field (that is now always a quintptr large). Give QHandle a direct pointer to it's data in addition to the counter. This makes QHandle 8 or 16 bytes large, but speeds up access to it's data and gives more safety on the counter as that one now always has at least 31 bits. Counter and the linked freelist use the same memory location. To avoid potential conflicts, make sure the counter is always an odd number, so it can't be a valid pointer. Do not use INDEXBITS anymore, the resource manager can now always allocate as many resources as we have RAM available and will grow with the required use (and not allocate fixed memory upfront). This change reduces the memory consumption of the qardboard example from a bit above 40 to 10MB. Change-Id: I514f2d3f957f8635098fb88342e42e3361456340 Reviewed-by: Sean Harmer --- src/core/resources/qhandle_p.h | 89 ++++++----- src/core/resources/qresourcemanager_p.h | 177 +++++++++------------ src/render/backend/renderview.cpp | 2 +- tests/auto/core/handle/tst_handle.cpp | 96 +++-------- .../core/qresourcemanager/tst_qresourcemanager.cpp | 25 ++- .../tst_bench_qresourcesmanager.cpp | 7 +- 6 files changed, 162 insertions(+), 234 deletions(-) diff --git a/src/core/resources/qhandle_p.h b/src/core/resources/qhandle_p.h index c4b53ec21..95483d197 100644 --- a/src/core/resources/qhandle_p.h +++ b/src/core/resources/qhandle_p.h @@ -53,9 +53,7 @@ #include #include -#include - -class tst_Handle; // needed for friend class declaration below +#include QT_BEGIN_NAMESPACE @@ -65,69 +63,72 @@ template class QHandle { public: + struct Data { + union { + quintptr counter; + Data *nextFree; + }; + }; QHandle() - : m_handle(0) + : d(nullptr), + counter(0) {} - - - quint32 index() const { return d.m_index; } - quint32 counter() const { return d.m_counter; } - quint32 handle() const { return m_handle; } - bool isNull() const { return !m_handle; } - - operator quint32() const { return m_handle; } - - static quint32 maxIndex() { return MaxIndex; } - static quint32 maxCounter() { return MaxCounter; } - - QHandle(quint32 i, quint32 count) + QHandle(Data *d) + : d(d), + counter(d->counter) + { + } + QHandle(const QHandle &other) + : d(other.d), + counter(other.counter) + { + } + QHandle &operator=(const QHandle &other) { - d.m_index = i; - d.m_counter = count; - d.m_unused = 0; - Q_ASSERT(i < MaxIndex); - Q_ASSERT(count < MaxCounter); + d = other.d; + counter = other.counter; + return *this; } - enum { - // Sizes to use for bit fields - IndexBits = INDEXBITS, - CounterBits = 32 - INDEXBITS - 2, // We use 2 bits for book-keeping in QHandleManager + inline T *operator->() const; + T *data() const; - // Sizes to compare against for asserting dereferences - MaxIndex = (1 << IndexBits) - 1, - MaxCounter = ((1 << CounterBits) - 1 > SHRT_MAX) ? SHRT_MAX - 1 : (1 << CounterBits) - 1 - }; + quintptr handle() const { return reinterpret_cast(d); } + bool isNull() const { return !d; } + + Data *data_ptr() const { return d; } + bool operator==(const QHandle &other) const { return d == other.d && counter == other.counter; } + bool operator!=(const QHandle &other) const { return !operator==(other); } private: - struct Data { - quint32 m_index : IndexBits; - quint32 m_counter : CounterBits; - quint32 m_unused : 2; - }; - union { - Data d; - quint32 m_handle; - }; + Data *d; + quintptr counter; }; + template QDebug operator<<(QDebug dbg, const QHandle &h) { QDebugStateSaver saver(dbg); QString binNumber = QString::number(h.handle(), 2).rightJustified(32, QChar::fromLatin1('0')); - dbg.nospace() << "index = " << h.index() - << " magic/counter = " << h.counter() - << " m_handle = " << h.handle() + dbg.nospace() << " m_handle = " << h.handle() << " = " << binNumber; return dbg; } +template +uint qHash(const QHandle &h, uint seed) +{ + using QT_PREPEND_NAMESPACE(qHash); + return qHash(h.handle(), seed); +} + } // Qt3DCore +// simpler than fighting the Q_DECLARE_TYPEINFO macro, use QString as a dummy to get movable semantics template -class QTypeInfo > // simpler than fighting the Q_DECLARE_TYPEINFO macro - : public QTypeInfoMerger, quint32> {}; +class QTypeInfo > + : public QTypeInfoMerger, QString> {}; QT_END_NAMESPACE diff --git a/src/core/resources/qresourcemanager_p.h b/src/core/resources/qresourcemanager_p.h index 4cb2a38af..8f0440498 100644 --- a/src/core/resources/qresourcemanager_p.h +++ b/src/core/resources/qresourcemanager_p.h @@ -220,119 +220,114 @@ struct Int2Type }; }; +template +class QHandleData : public QHandle::Data +{ +public: + T data; +}; + +template +inline T *QHandle::operator->() const { return (d && counter == d->counter) ? &static_cast *>(d)->data : nullptr; } +template +inline T *QHandle::data() const { return (d && counter == d->counter) ? &static_cast *>(d)->data : nullptr; } + template class ArrayAllocatingPolicy { public: + typedef QHandleData HandleData; typedef QHandle Handle; ArrayAllocatingPolicy() { - m_freeList.resize(MaxSize); - for (int i = 0; i < MaxSize; i++) - m_freeList[i] = MaxSize - (i + 1); } ~ArrayAllocatingPolicy() { + m_activeHandles.clear(); deallocateBuckets(); } Handle allocateResource() { - Q_ASSERT(!m_freeList.isEmpty()); - int idx = m_freeList.takeLast(); - int bucketIdx = idx / BucketSize; - int localIdx = idx % BucketSize; - Q_ASSERT(bucketIdx <= m_numBuckets); - if (bucketIdx == m_numBuckets) { - m_bucketDataPtrs[bucketIdx] = static_cast(malloc(sizeof(T) * BucketSize)); - m_counters[bucketIdx] = static_cast(malloc(sizeof(short) * BucketSize)); - // ### memset is only needed as long as we also use this for primitive types (see FrameGraphManager) - // ### remove once this is fixed, add a static_assert on T instead - memset((void *)m_bucketDataPtrs[bucketIdx], 0, sizeof(T) * BucketSize); - memset(m_counters[bucketIdx], 0, sizeof(short) * BucketSize); - ++m_numBuckets; - } - - Q_ASSERT(idx <= m_numConstructed); - if (idx == m_numConstructed) { - new (m_bucketDataPtrs[bucketIdx] + localIdx) T; - ++m_numConstructed; - } - Q_STATIC_ASSERT(Handle::MaxCounter < USHRT_MAX); - Q_ASSERT(m_counters[bucketIdx][localIdx] <= 0); - m_counters[bucketIdx][localIdx] *= -1; - ++m_counters[bucketIdx][localIdx]; - if (m_counters[bucketIdx][localIdx] >= Handle::MaxCounter) - m_counters[bucketIdx][localIdx] = 1; - - return Handle(idx, m_counters[bucketIdx][localIdx]); + if (!freeList) + allocateBucket(); + typename Handle::Data *d = freeList; + freeList = freeList->nextFree; + d->counter = allocCounter; + allocCounter += 2; // ensure this will never clash with a pointer in nextFree by keeping the lowest bit set + Handle handle(d); + m_activeHandles.push_back(handle); + return handle; } - void releaseResource(Handle h) + void releaseResource(const Handle &handle) { - int idx = h.index(); - int bucketIdx = idx / BucketSize; - int localIdx = idx % BucketSize; - - Q_ASSERT(h.counter() == static_cast(m_counters[bucketIdx][localIdx])); - T *r = m_bucketDataPtrs[bucketIdx] + localIdx; - - m_freeList.append(idx); - m_counters[bucketIdx][localIdx] *= -1; - performCleanup(r, Int2Type::needsCleanup>()); + m_activeHandles.removeOne(handle); + typename Handle::Data *d = handle.data_ptr(); + d->nextFree = freeList; + freeList = d; + performCleanup(&static_cast *>(d)->data, Int2Type::needsCleanup>()); } - T *data(Handle h/*, bool *ok = 0*/) { - int bucketIdx = h.index() / BucketSize; - int localIdx = h.index() % BucketSize; - - if (h.counter() != static_cast(m_counters[bucketIdx][localIdx])) { - return nullptr; - } - return m_bucketDataPtrs[bucketIdx] + localIdx; + T *data(Handle h) { + return h.operator->(); } void for_each(std::function f) { - for (int idx = 0; idx < m_numConstructed; ++idx) { - int bucketIdx = idx / BucketSize; - int localIdx = idx % BucketSize; - T * t = m_bucketDataPtrs[bucketIdx] + localIdx; - f(t); + Bucket *b = firstBucket; + while (b) { + for (int idx = 0; idx < Bucket::NumEntries; ++idx) { + T *t = &b->data[idx].data; + f(t); + } + b = b->header.next; } } + int count() const { return m_activeHandles.size(); } + QVector activeHandles() const { return m_activeHandles; } + private: Q_DISABLE_COPY(ArrayAllocatingPolicy) - - enum { - MaxSize = (1 << INDEXBITS), - // use at most 1024 items per bucket, or put all items into a single - // bucket if MaxSize is small enough - BucketSize = (1 << (INDEXBITS < 10 ? INDEXBITS : 10)) + struct Bucket { + struct Header { + Bucket *next; + } header; + enum { + Size = 4096, + NumEntries = (Size - sizeof(Header))/sizeof(HandleData) + }; + HandleData data[NumEntries]; }; - void deallocateBuckets() - { - while (m_numConstructed > 0) { - --m_numConstructed; - int bucketIdx = m_numConstructed / BucketSize; - int localIdx = m_numConstructed % BucketSize; - (m_bucketDataPtrs[bucketIdx] + localIdx)->~T(); - } + Bucket *firstBucket = 0; + QVector m_activeHandles; + typename Handle::Data *freeList = 0; + int allocCounter = 1; + + void allocateBucket() { + // no free handle, allocate a new + Bucket *b = new Bucket; - while (m_numBuckets > 0) { - --m_numBuckets; - free(m_bucketDataPtrs[m_numBuckets]); - free(m_counters[m_numBuckets]); + b->header.next = firstBucket; + firstBucket = b; + for (int i = 0; i < Bucket::NumEntries - 1; ++i) { + b->data[i].nextFree = &b->data[i + 1]; } + b->data[Bucket::NumEntries - 1].nextFree = nullptr; + freeList = &b->data[0]; } - T* m_bucketDataPtrs[MaxSize / BucketSize]; - short *m_counters[MaxSize / BucketSize]; - QVector m_freeList; - int m_numBuckets = 0; - int m_numConstructed = 0; + void deallocateBuckets() + { + Bucket *b = firstBucket; + while (b) { + Bucket *n = b->header.next; + delete b; + b = n; + } + } void performCleanup(T *r, Int2Type) { @@ -379,21 +374,18 @@ public: Handle acquire() { typename LockingPolicy::WriteLocker lock(this); - Handle handle = Allocator::allocateResource(); - m_activeHandles.push_back(handle); - return handle; + return Allocator::allocateResource(); } ValueType* data(const Handle &handle) { - typename LockingPolicy::ReadLocker lock(this); - return Allocator::data(handle); + return handle.operator->(); } void release(const Handle &handle) { typename LockingPolicy::WriteLocker lock(this); - releaseLocked(handle); + Allocator::releaseResource(handle); } bool contains(const KeyType &id) const @@ -413,7 +405,6 @@ public: Handle &handleToSet = m_keyToHandleMap[id]; if (handleToSet.isNull()) { handleToSet = Allocator::allocateResource(); - m_activeHandles.push_back(handleToSet); } return handleToSet; } @@ -441,8 +432,7 @@ public: ValueType *getOrCreateResource(const KeyType &id) { const Handle handle = getOrAcquireHandle(id); - typename LockingPolicy::ReadLocker lock(this); - return Allocator::data(handle); + return handle.operator->(); } void releaseResource(const KeyType &id) @@ -450,27 +440,16 @@ public: typename LockingPolicy::WriteLocker lock(this); Handle handle = m_keyToHandleMap.take(id); if (!handle.isNull()) - releaseLocked(handle); + Allocator::releaseResource(handle); } int maximumSize() const { return m_maxSize; } - int count() const Q_DECL_NOEXCEPT { return m_activeHandles.size(); } - - inline QVector activeHandles() const Q_DECL_NOEXCEPT { return m_activeHandles; } - protected: QHash m_keyToHandleMap; - QVector m_activeHandles; const int m_maxSize; private: - void releaseLocked(const Handle &handle) - { - m_activeHandles.removeOne(handle); - Allocator::releaseResource(handle); - } - friend QDebug operator<< <>(QDebug dbg, const QResourceManager &manager); }; diff --git a/src/render/backend/renderview.cpp b/src/render/backend/renderview.cpp index 8c9737689..7adf7c5d2 100644 --- a/src/render/backend/renderview.cpp +++ b/src/render/backend/renderview.cpp @@ -379,7 +379,7 @@ void sortByMaterial(QVector &commands, int begin, const int end while (begin != end) { if (begin + 1 < rangeEnd) { std::stable_sort(commands.begin() + begin + 1, commands.begin() + rangeEnd, [] (RenderCommand *a, RenderCommand *b){ - return a->m_material < b->m_material; + return a->m_material.handle() < b->m_material.handle(); }); } begin = rangeEnd; diff --git a/tests/auto/core/handle/tst_handle.cpp b/tests/auto/core/handle/tst_handle.cpp index 07155844f..4d4ccb645 100644 --- a/tests/auto/core/handle/tst_handle.cpp +++ b/tests/auto/core/handle/tst_handle.cpp @@ -28,12 +28,7 @@ #include #include - -#if Q_BYTE_ORDER == Q_BIG_ENDIAN -#define GET_EXPECTED_HANDLE(qHandle) ((qHandle.index() << (qHandle.CounterBits + 2)) + (qHandle.counter() << 2)) -#else /* Q_LITTLE_ENDIAN */ -#define GET_EXPECTED_HANDLE(qHandle) (qHandle.index() + (qHandle.counter() << qHandle.IndexBits)) -#endif +#include class tst_Handle : public QObject { @@ -49,8 +44,6 @@ private slots: void assignment(); void equality(); void inequality(); - void staticLimits(); - void bigHandle(); }; class SimpleResource @@ -64,107 +57,60 @@ public: }; typedef Qt3DCore::QHandle Handle; -typedef Qt3DCore::QHandle BigHandle; +typedef Qt3DCore::QHandleData HandleData; void tst_Handle::defaultConstruction() { Handle h; QVERIFY(h.isNull() == true); - QVERIFY(h.index() == 0); - QVERIFY(h.counter() == 0); QVERIFY(h.handle() == 0); } void tst_Handle::construction() { - Handle h(0, 1); + HandleData d; + Handle h(&d); QVERIFY(h.isNull() == false); - QVERIFY(h.index() == 0); - QVERIFY(h.counter() == 1); qDebug() << h; - QVERIFY(h.handle() == GET_EXPECTED_HANDLE(h)); - - Handle h2(1, 1); - QVERIFY(h2.isNull() == false); - QVERIFY(h2.index() == 1); - QVERIFY(h2.counter() == 1); - qDebug() << h2; - QVERIFY(h2.handle() == GET_EXPECTED_HANDLE(h2)); + QVERIFY(h.handle() == reinterpret_cast(&d)); } void tst_Handle::copyConstruction() { - Handle h1(0, 1); - Handle h2(h1); + HandleData d; + Handle h(&d); + Handle h2(h); QVERIFY(h2.isNull() == false); - QVERIFY(h2.index() == 0); - QVERIFY(h2.counter() == 1); - QVERIFY(h2.handle() == GET_EXPECTED_HANDLE(h2)); + QVERIFY(h2.handle() == h.handle()); } void tst_Handle::assignment() { - Handle h1(0, 1); - Handle h2 = h1; + HandleData d; + Handle h(&d); + Handle h2; + h2 = h; QVERIFY(h2.isNull() == false); - QVERIFY(h2.index() == 0); - QVERIFY(h2.counter() == 1); - QVERIFY(h2.handle() == GET_EXPECTED_HANDLE(h2)); + QVERIFY(h2.handle() == h.handle()); } void tst_Handle::equality() { - Handle h1(2, 1); - Handle h2(2, 1); + HandleData d; + Handle h1(&d); + Handle h2(&d); QVERIFY(h1.isNull() == false); - QVERIFY(h1.index() == 2); - QVERIFY(h1.counter() == 1); - QVERIFY(h1.handle() == GET_EXPECTED_HANDLE(h1)); QVERIFY(h1 == h2); } void tst_Handle::inequality() { - Handle h1(2, 1); - Handle h2(3, 1); + HandleData d1; + HandleData d2; + Handle h1(&d1); + Handle h2(&d2); QVERIFY(h1.isNull() == false); - QVERIFY(h1.index() == 2); - QVERIFY(h1.counter() == 1); - QVERIFY(h1.handle() == GET_EXPECTED_HANDLE(h1)); QVERIFY(h1 != h2); - - Handle h3(2, 2); - QVERIFY(h1 != h3); -} - -void tst_Handle::staticLimits() -{ - QVERIFY(Handle::maxIndex() == (1 << 16) - 1); - QVERIFY(Handle::maxCounter() == (1 << (32 - 16 - 2)) - 1); -} - -void tst_Handle::bigHandle() -{ - BigHandle h; - QVERIFY(h.isNull() == true); - QVERIFY(h.index() == 0); - QVERIFY(h.counter() == 0); - QVERIFY(h.handle() == 0); - - BigHandle h1(0, 1); - QVERIFY(h1.isNull() == false); - QVERIFY(h1.index() == 0); - QVERIFY(h1.counter() == 1); - QVERIFY(h1.handle() == GET_EXPECTED_HANDLE(h1)); - - BigHandle h2(1, 1); - QVERIFY(h2.isNull() == false); - QVERIFY(h2.index() == 1); - QVERIFY(h2.counter() == 1); - QVERIFY(h2.handle() == GET_EXPECTED_HANDLE(h2)); - - QVERIFY(BigHandle::maxIndex() == (1 << 22) - 1); - QVERIFY(BigHandle::maxCounter() == (1 << (32 - 22 - 2)) - 1); } QTEST_APPLESS_MAIN(tst_Handle) diff --git a/tests/auto/core/qresourcemanager/tst_qresourcemanager.cpp b/tests/auto/core/qresourcemanager/tst_qresourcemanager.cpp index c3238fc8f..b7bd7c28a 100644 --- a/tests/auto/core/qresourcemanager/tst_qresourcemanager.cpp +++ b/tests/auto/core/qresourcemanager/tst_qresourcemanager.cpp @@ -97,8 +97,9 @@ void tst_DynamicArrayPolicy::acquireResources() } for (uint i = 0; i < 5; i++) { - QVERIFY(handles.at(i).index() == i); - QVERIFY(handles.at(i).counter() == 1); + QVERIFY(!handles.at(i).isNull()); + if (i > 0) + QVERIFY(handles.at(i) != handles.at(i-1)); } } @@ -117,8 +118,6 @@ void tst_DynamicArrayPolicy::getResources() } for (uint i = 0; i < 5; i++) { - QVERIFY(handles.at(i).index() == i); - QVERIFY(handles.at(i).counter() == 1); resources << manager.data(handles.at(i)); QVERIFY(resources.at(i) != nullptr); resources.at(i)->m_value = i; @@ -153,8 +152,6 @@ void tst_DynamicArrayPolicy::registerResourcesResize() } for (int i = 0; i < 7; i++) { - QVERIFY(handles.at(i).index() == static_cast(i)); - QVERIFY(handles.at(i).counter() == 1); if (i < 2) QVERIFY(manager.data(handles.at(i))->m_value == i + 2); else @@ -169,14 +166,16 @@ void tst_DynamicArrayPolicy::removeResource() { Qt3DCore::QResourceManager manager; - QList resources; QList handles; for (int i = 0; i < 32; i++) { handles << manager.acquire(); - resources << manager.data(handles.at(i)); } + + tst_ArrayResource *resource = handles.at(2).data(); + QVERIFY(resource != nullptr); + manager.release(handles.at(2)); QVERIFY(manager.data(handles.at(2)) == nullptr); // Triggers QASSERT so commented @@ -255,7 +254,7 @@ protected: void run() { int i = 0; - int max = tHandle::maxIndex(); + int max = 65535; while (i < max) { tst_ArrayResource *r = m_manager->getOrCreateResource(i); i++; @@ -275,7 +274,7 @@ void tst_DynamicArrayPolicy::heavyDutyMultiThreadedAccess() QList threads; int iterations = 8; - int max = tHandle16::maxIndex(); + int max = 65535; for (int i = 0; i < iterations; i++) { tst_Thread *thread = new tst_Thread(); @@ -326,7 +325,7 @@ protected: void run() { int i = 0; - int max = tHandle::maxIndex(); + int max = 65535; while (i < max) { tst_ArrayResource *r = m_manager->getOrCreateResource(i); QVERIFY(r != nullptr); @@ -349,7 +348,7 @@ void tst_DynamicArrayPolicy::heavyDutyMultiThreadedAccessRelease() QList threads; int iterations = 8; - int max = tHandle16::maxIndex(); + int max = 65535; for (int u = 0; u < 2; u++) { @@ -385,8 +384,6 @@ void tst_DynamicArrayPolicy::maximumNumberOfResources() QList resources; QList handles; - QCOMPARE(tHandle16::maxIndex(), (uint)manager.maximumSize()); - for (int i = 0; i < manager.maximumSize(); i++) { handles << manager.acquire(); resources << manager.data(handles.at(i)); diff --git a/tests/benchmarks/core/qresourcesmanager/qresourcesmanager/tst_bench_qresourcesmanager.cpp b/tests/benchmarks/core/qresourcesmanager/qresourcesmanager/tst_bench_qresourcesmanager.cpp index 6ddb058a1..51eb2d6fc 100644 --- a/tests/benchmarks/core/qresourcesmanager/qresourcesmanager/tst_bench_qresourcesmanager.cpp +++ b/tests/benchmarks/core/qresourcesmanager/qresourcesmanager/tst_bench_qresourcesmanager.cpp @@ -159,9 +159,14 @@ void benchmarkReleaseResources() QVector > handles(max); for (int i = 0; i < max; i++) handles[i] = manager.acquire(); + for (int i = 0; i < max; i++) + manager.release(handles.at(i)); + handles.clear(); QBENCHMARK_ONCE { - /*manager.reset()*/; + // the release/clear should have left many unused handled in the resourcemanager, + // so the next acquire will trigger a collection of all freed resources + manager.acquire(); } } -- cgit v1.2.3