Change implementation of shadow nodes to use a double-linked list

Since eea8fa64ab27854b71f46ef143e35b6c9acbba14, we're seeing increased
times in QSGNode::removeChildNode(). The reason for this seems to be
that iteration through the linked list is significantly slower than
iteration through a QList<> due to that each node needs to be loaded
in memory to iterate to the next, compared a more plain sequential
pointer compare with QList<>.

This implementation changes the nodes to use a circular double-linked
list so we can drop the iteration when removing nodes. This brings us
slightly better performance than the original QList based
implementation while still using the same amount of memory as the
single-linked list one.

Change-Id: I0b693730f5b82ad7767e507accafd90551e03fbc
Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>

2 files changed, 81 insertions, 46 deletions

diff --git a/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp b/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
index 49bbbf0ba8..81aa641e03 100644
--- a/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
+++ b/src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp
@@ -90,7 +90,7 @@ DECLARE_DEBUG_VAR(noclip)
 static QElapsedTimer qsg_renderer_timer;
 
 #define QSGNODE_TRAVERSE(NODE) for (QSGNode *child = NODE->firstChild(); child; child = child->nextSibling())
-#define SHADOWNODE_TRAVERSE(NODE) for (Node *child = NODE->firstChild; child; child = child->nextSibling)
+#define SHADOWNODE_TRAVERSE(NODE) for (Node *child = NODE->firstChild(); child; child = child->sibling())
 
 static inline int size_of_type(GLenum type)
 {
@@ -510,7 +510,7 @@ void Updater::updateRootTransforms(Node *node, Node *root, const QMatrix4x4 &com
     while (n != root) {
         if (n->type() == QSGNode::TransformNodeType)
             m = static_cast<QSGTransformNode *>(n->sgNode)->matrix() * m;
-        n = n->parent;
+        n = n->parent();
     }
 
     m = combined * m;
@@ -1013,16 +1013,8 @@ void Renderer::nodeWasAdded(QSGNode *node, Node *shadowParent)
     Node *snode = m_nodeAllocator.allocate();
     snode->sgNode = node;
     m_nodes.insert(node, snode);
-    if (shadowParent) {
-        snode->parent = shadowParent;
-        if (shadowParent->lastChild) {
-            shadowParent->lastChild->nextSibling = snode;
-            shadowParent->lastChild = snode;
-        } else {
-            shadowParent->firstChild = snode;
-            shadowParent->lastChild = snode;
-        }
-    }
+    if (shadowParent)
+        shadowParent->append(snode);
 
     if (node->type() == QSGNode::GeometryNodeType) {
         snode->data = m_elementAllocator.allocate();
@@ -1054,17 +1046,12 @@ void Renderer::nodeWasRemoved(Node *node)
     // here, because we delete 'child' (when recursed, down below), so we'd
     // have a use-after-free.
     {
-        Node *child = node->firstChild;
-        Node *nextChild = 0;
-
+        Node *child = node->firstChild();
         while (child) {
-            // Get the next child now before we proceed
-            nextChild = child->nextSibling;
-
             // Remove (and delete) child
+            node->remove(child);
             nodeWasRemoved(child);
-
-            child = nextChild;
+            child = node->firstChild();
         }
     }
 
@@ -1110,6 +1097,7 @@ void Renderer::nodeWasRemoved(Node *node)
     }
 
     Q_ASSERT(m_nodes.contains(node->sgNode));
+
     m_nodeAllocator.release(m_nodes.take(node->sgNode));
 }
 
@@ -1120,13 +1108,13 @@ void Renderer::turnNodeIntoBatchRoot(Node *node)
     node->isBatchRoot = true;
     node->becameBatchRoot = true;
 
-    Node *p = node->parent;
+    Node *p = node->parent();
     while (p) {
         if (p->type() == QSGNode::ClipNodeType || p->isBatchRoot) {
             registerBatchRoot(node, p);
             break;
         }
-        p = p->parent;
+        p = p->parent();
     }
 
     SHADOWNODE_TRAVERSE(node)
@@ -1255,33 +1243,18 @@ void Renderer::nodeChanged(QSGNode *node, QSGNode::DirtyState state)
                                               | QSGNode::DirtyForceUpdate);
     if (dirtyChain != 0) {
         dirtyChain = QSGNode::DirtyState(dirtyChain << 16);
-        Node *sn = shadowNode->parent;
+        Node *sn = shadowNode->parent();
         while (sn) {
             sn->dirtyState |= dirtyChain;
-            sn = sn->parent;
+            sn = sn->parent();
         }
     }
 
     // Delete happens at the very end because it deletes the shadownode.
     if (state & QSGNode::DirtyNodeRemoved) {
-        Node *parent = shadowNode->parent;
-        if (parent) {
-            Q_ASSERT(parent->firstChild);
-            Q_ASSERT(parent->lastChild);
-            shadowNode->parent = 0;
-            Node *child = parent->firstChild;
-            if (child == shadowNode) {
-                parent->firstChild = shadowNode->nextSibling;
-                if (parent->lastChild == shadowNode)
-                    parent->lastChild = 0;
-            } else {
-                while (child->nextSibling != shadowNode)
-                    child = child->nextSibling;
-                child->nextSibling = shadowNode->nextSibling;
-                if (shadowNode == parent->lastChild)
-                    parent->lastChild = child;
-            }
-        }
+        Node *parent = shadowNode->parent();
+        if (parent)
+            parent->remove(shadowNode);
         nodeWasRemoved(shadowNode);
         Q_ASSERT(m_nodes.value(node) == 0);
     }
diff --git a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
index 01e517e65b..eb5bfca1ee 100644
--- a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
+++ b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
@@ -451,11 +451,73 @@ struct Batch
 struct Node
 {
     QSGNode *sgNode;
-    Node *parent;
     void *data;
-    Node *firstChild;
-    Node *nextSibling;
-    Node *lastChild;
+
+    Node *m_parent;
+    Node *m_child;
+    Node *m_next;
+    Node *m_prev;
+
+    Node *parent() const { return m_parent; }
+
+    void append(Node *child) {
+        Q_ASSERT(child);
+        Q_ASSERT(!hasChild(child));
+        Q_ASSERT(child->m_parent == 0);
+        Q_ASSERT(child->m_next == 0);
+        Q_ASSERT(child->m_prev == 0);
+
+        if (!m_child) {
+            child->m_next = child;
+            child->m_prev = child;
+            m_child = child;
+        } else {
+            m_child->m_prev->m_next = child;
+            child->m_prev = m_child->m_prev;
+            m_child->m_prev = child;
+            child->m_next = m_child;
+        }
+        child->setParent(this);
+    }
+
+    void remove(Node *child) {
+        Q_ASSERT(child);
+        Q_ASSERT(hasChild(child));
+
+        // only child..
+        if (child->m_next == child) {
+            m_child = 0;
+        } else {
+            if (m_child == child)
+                m_child = child->m_next;
+            child->m_next->m_prev = child->m_prev;
+            child->m_prev->m_next = child->m_next;
+        }
+        child->m_next = 0;
+        child->m_prev = 0;
+        child->setParent(0);
+    }
+
+    Node *firstChild() const { return m_child; }
+
+    Node *sibling() const {
+        Q_ASSERT(m_parent);
+        return m_next == m_parent->m_child ? 0 : m_next;
+    }
+
+    void setParent(Node *p) {
+        Q_ASSERT(m_parent == 0 || p == 0);
+        m_parent = p;
+    }
+
+    bool hasChild(Node *child) const {
+        Node *n = m_child;
+        while (n && n != child)
+            n = n->sibling();
+        return n;
+    }
+
+
 
     QSGNode::DirtyState dirtyState;