From 08a9fc04989aa05d4cc8c44430977d23cc729656 Mon Sep 17 00:00:00 2001 From: Gunnar Sletta Date: Tue, 8 Nov 2016 12:47:25 +0100 Subject: 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 --- src/quick/scenegraph/coreapi/qsgbatchrenderer.cpp | 57 +++++------------- src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h | 70 +++++++++++++++++++++-- 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(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; -- cgit v1.2.3