Use an allocator for QSGBatchRenderer::Node and Element instances.

Cuts down quite a bit on the time spent on the render thread during
the sync phase.

Change-Id: Ide8c4348141c84ed8abd9a869607a022652c2828
Reviewed-by: Robin Burchell <robin.burchell@viroteck.net>

2 files changed, 140 insertions, 22 deletions

diff --git a/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp b/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
index ef125e07a9..ca5b038efa 100644
--- a/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
+++ b/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
@@ -832,8 +832,8 @@ Renderer::~Renderer()
         for (int i=0; i<m_batchPool.size(); ++i) qsg_wipeBatch(m_batchPool.at(i), this);
     }
 
-    // The shadowtree
-    qDeleteAll(m_nodes.values());
+    foreach (Node *n, m_nodes.values())
+        m_nodeAllocator.release(n);
 
     // Remaining elements...
     for (int i=0; i<m_elementsToDelete.size(); ++i) {
@@ -841,7 +841,7 @@ Renderer::~Renderer()
         if (e->isRenderNode)
             delete static_cast<RenderNodeElement *>(e);
         else
-            delete e;
+            m_elementAllocator.release(e);
     }
 }
 
@@ -980,7 +980,8 @@ void Renderer::nodeWasAdded(QSGNode *node, Node *shadowParent)
     if (node->isSubtreeBlocked())
         return;
 
-    Node *snode = new Node(node);
+    Node *snode = m_nodeAllocator.allocate();
+    snode->sgNode = node;
     m_nodes.insert(node, snode);
     if (shadowParent) {
         snode->parent = shadowParent;
@@ -988,7 +989,8 @@ void Renderer::nodeWasAdded(QSGNode *node, Node *shadowParent)
     }
 
     if (node->type() == QSGNode::GeometryNodeType) {
-        snode->data = new Element(static_cast<QSGGeometryNode *>(node));
+        snode->data = m_elementAllocator.allocate();
+        snode->element()->setNode(static_cast<QSGGeometryNode *>(node));
 
     } else if (node->type() == QSGNode::ClipNodeType) {
         snode->data = new ClipBatchRootInfo;
@@ -1051,7 +1053,7 @@ void Renderer::nodeWasRemoved(Node *node)
     }
 
     Q_ASSERT(m_nodes.contains(node->sgNode));
-    delete m_nodes.take(node->sgNode);
+    m_nodeAllocator.release(m_nodes.take(node->sgNode));
 }
 
 void Renderer::turnNodeIntoBatchRoot(Node *node)
@@ -1234,8 +1236,8 @@ void Renderer::buildRenderLists(QSGNode *node)
     if (node->isSubtreeBlocked())
         return;
 
-    Q_ASSERT(m_nodes.contains(node));
     Node *shadowNode = m_nodes.value(node);
+    Q_ASSERT(shadowNode);
 
     if (node->type() == QSGNode::GeometryNodeType) {
         QSGGeometryNode *gn = static_cast<QSGGeometryNode *>(node);
@@ -1256,7 +1258,7 @@ void Renderer::buildRenderLists(QSGNode *node)
 
     } else if (node->type() == QSGNode::ClipNodeType || shadowNode->isBatchRoot) {
         Q_ASSERT(m_nodes.contains(node));
-        BatchRootInfo *info = batchRootInfo(m_nodes.value(node));
+        BatchRootInfo *info = batchRootInfo(shadowNode);
         if (node == m_partialRebuildRoot) {
             m_nextRenderOrder = info->firstOrder;
             QSGNODE_TRAVERSE(node)
@@ -2460,7 +2462,7 @@ void Renderer::deleteRemovedElements()
         if (e->isRenderNode)
             delete static_cast<RenderNodeElement *>(e);
         else
-            delete e;
+            m_elementAllocator.release(e);
     }
     m_elementsToDelete.reset();
 }
diff --git a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
index 5447d9ea52..29604cf820 100644
--- a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
+++ b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
@@ -31,8 +31,8 @@
 **
 ****************************************************************************/
 
-#ifndef ULTRARENDERER_H
-#define ULTRARENDERER_H
+#ifndef QSGBATCHRENDERER_P_H
+#define QSGBATCHRENDERER_P_H
 
 #include <private/qsgrenderer_p.h>
 #include <private/qsgnodeupdater_p.h>
@@ -40,6 +40,8 @@
 
 #include <private/qsgrendernode_p.h>
 
+#include <QtCore/QBitArray>
+
 QT_BEGIN_NAMESPACE
 
 class QOpenGLVertexArrayObject;
@@ -59,6 +61,115 @@ class Updater;
 class Renderer;
 class ShaderManager;
 
+template <typename Type, int PageSize> class AllocatorPage
+{
+public:
+    // The memory used by this allocator
+    char data[sizeof(Type) * PageSize];
+
+    // 'blocks' contains a list of free indices which can be allocated.
+    // The first available index is found in PageSize - available.
+    int blocks[PageSize];
+
+    // 'available' is the number of available instances this page has left to allocate.
+    int available;
+
+    // This is not strictly needed, but useful for sanity checking and anyway
+    // pretty small..
+    QBitArray allocated;
+
+    AllocatorPage()
+        : available(PageSize)
+        , allocated(PageSize)
+    {
+        for (int i=0; i<PageSize; ++i) blocks[i] = i;
+    }
+
+    Type *at(uint index) const
+    {
+        return (Type *) &data[index * sizeof(Type)];
+    }
+};
+
+template <typename Type, int PageSize> class Allocator
+{
+public:
+    Allocator()
+    {
+        pages.push_back(new AllocatorPage<Type, PageSize>());
+    }
+
+    ~Allocator()
+    {
+        qDeleteAll(pages);
+    }
+
+    Type *allocate()
+    {
+        AllocatorPage<Type, PageSize> *p = 0;
+        for (int i=0; i<pages.size(); ++i) {
+            if (pages.at(i)->available > 0) {
+                p = pages.at(i);
+                break;
+            }
+        }
+        if (!p) {
+            p = new AllocatorPage<Type, PageSize>();
+            pages.push_back(p);
+        }
+        uint pos = p->blocks[PageSize - p->available];
+        void *mem = p->at(pos);
+        p->available--;
+        p->allocated.setBit(pos);
+        Type *t = new (mem) Type();
+        return t;
+    }
+
+    void releaseExplicit(uint pageIndex, uint index)
+    {
+        AllocatorPage<Type, PageSize> *page = pages.at(pageIndex);
+        if (!page->allocated.testBit(index))
+            qFatal("Double delete in allocator: page=%d, index=%d", pageIndex , index);
+
+        // Call the destructor
+        page->at(index)->~Type();
+
+        page->allocated[index] = false;
+        page->available++;
+        page->blocks[PageSize - page->available] = index;
+
+        // Remove the pages if they are empty and they are the last ones. We need to keep the
+        // order of pages since we have references to their index, so we can only remove
+        // from the end.
+        while (page->available == PageSize && pages.size() > 1 && pages.back() == page) {
+            pages.pop_back();
+            delete page;
+            page = pages.back();
+        }
+    }
+
+    void release(Type *t)
+    {
+        int pageIndex = -1;
+        for (int i=0; i<pages.size(); ++i) {
+            AllocatorPage<Type, PageSize> *p = pages.at(i);
+            if ((Type *) (&p->data[0]) <= t && (Type *) (&p->data[PageSize * sizeof(Type)]) > t) {
+                pageIndex = i;
+                break;
+            }
+        }
+        Q_ASSERT(pageIndex >= 0);
+
+        AllocatorPage<Type, PageSize> *page = pages.at(pageIndex);
+        int index = (quint64(t) - quint64(&page->data[0])) / sizeof(Type);
+
+        releaseExplicit(pageIndex, index);
+    }
+
+    QVector<AllocatorPage<Type, PageSize> *> pages;
+};
+
+
 inline bool hasMaterialWithBlending(QSGGeometryNode *n)
 {
     return (n->opaqueMaterial() ? n->opaqueMaterial()->flags() & QSGMaterial::Blending
@@ -149,8 +260,8 @@ struct Buffer {
 
 struct Element {
 
-    Element(QSGGeometryNode *n)
-        : node(n)
+    Element()
+        : node(0)
         , batch(0)
         , nextInBatch(0)
         , root(0)
@@ -161,10 +272,15 @@ struct Element {
         , removed(false)
         , orphaned(false)
         , isRenderNode(false)
-        , isMaterialBlended(n ? hasMaterialWithBlending(n) : false)
+        , isMaterialBlended(false)
     {
     }
 
+    void setNode(QSGGeometryNode *n) {
+        node = n;
+        isMaterialBlended = hasMaterialWithBlending(n);
+    }
+
     inline void ensureBoundsValid() {
         if (!boundsComputed)
             computeBounds();
@@ -192,8 +308,7 @@ struct Element {
 struct RenderNodeElement : public Element {
 
     RenderNodeElement(QSGRenderNode *rn)
-        : Element(0)
-        , renderNode(rn)
+        : renderNode(rn)
     {
         isRenderNode = true;
     }
@@ -289,15 +404,14 @@ struct Batch
 
 struct Node
 {
-    Node(QSGNode *node, Node *sparent = 0)
-        : sgNode(node)
-        , parent(sparent)
+    Node()
+        : sgNode(0)
+        , parent(0)
         , data(0)
         , dirtyState(0)
         , isOpaque(false)
         , isBatchRoot(false)
     {
-
     }
 
     QSGNode *sgNode;
@@ -435,7 +549,6 @@ private:
 
     friend class Updater;
 
-
     void map(Buffer *buffer, int size);
     void unmap(Buffer *buffer, bool isIndexBuf = false);
 
@@ -532,6 +645,9 @@ private:
 
     QHash<Node *, uint> m_visualizeChanceSet;
     VisualizeMode m_visualizeMode;
+
+    Allocator<Node, 256> m_nodeAllocator;
+    Allocator<Element, 64> m_elementAllocator;
 };
 
 Batch *Renderer::newBatch()
@@ -556,4 +672,4 @@ Batch *Renderer::newBatch()
 
 QT_END_NAMESPACE
 
-#endif // ULTRARENDERER_H
+#endif // QSGBATCHRENDERER_P_H