Particles: reduce memory allocations by flattening a set

When an affector acts on a particle, it will add it to a set
of "seen" particles. This means an allocation, per particle,
per frame.

In Qt 6 the problem is less dramatic due to the new QHash
implementation, which uses "wider" buckets, but in Qt 5 this is
hundreds of memory allocations (and deallocations) per frame.

Just reimplement a minimal flat-set API for this use case,
and replace the QSet usages with it. On a testcase with
200 active particles, this reduces memory allocations from
~20'000 per second to 0 when the scene is "stable".

Change-Id: I4be1e12a23b8dffca91955148532db243e383a4c
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Shawn Rutledge <shawn.rutledge@qt.io>
(cherry picked from commit 27c0034d6bb0df50d4479e42fc82fcd74b03d810)

5 files changed, 151 insertions, 3 deletions

diff --git a/src/particles/particles.pri b/src/particles/particles.pri
index 576d826903..adb43b5e45 100644
--- a/src/particles/particles.pri
+++ b/src/particles/particles.pri
@@ -13,6 +13,7 @@ HEADERS += \
     $$PWD/qquickparticleaffector_p.h \
     $$PWD/qquickparticleemitter_p.h \
     $$PWD/qquickparticleextruder_p.h \
+    $$PWD/qquickparticleflatset_p.h \
     $$PWD/qquickparticlepainter_p.h \
     $$PWD/qquickparticlesmodule_p.h \
     $$PWD/qquickparticlesystem_p.h \
diff --git a/src/particles/qquickparticleaffector_p.h b/src/particles/qquickparticleaffector_p.h
index fd4887333e..a91fc4e574 100644
--- a/src/particles/qquickparticleaffector_p.h
+++ b/src/particles/qquickparticleaffector_p.h
@@ -55,6 +55,7 @@
 #include "qquickparticlesystem_p.h"
 #include "qquickparticleextruder_p.h"
 #include "qtquickparticlesglobal_p.h"
+#include "qquickparticleflatset_p.h"
 
 QT_BEGIN_NAMESPACE
 
@@ -194,7 +195,7 @@ protected:
     static const qreal simulationCutoff;
 
     QPointF m_offset;
-    QSet<QPair<int, int> > m_onceOffed;
+    QtQuickParticlesPrivate::QFlatSet<QPair<int, int>> m_onceOffed;
 private:
     QSet<int> m_groupIds;
     bool m_updateIntSet;
diff --git a/src/particles/qquickparticleflatset_p.h b/src/particles/qquickparticleflatset_p.h
new file mode 100644
index 0000000000..77946c8b87
--- /dev/null
+++ b/src/particles/qquickparticleflatset_p.h
@@ -0,0 +1,145 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtQuick module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QQUICKPARTICLEFLATSET_P_H
+#define QQUICKPARTICLEFLATSET_P_H
+
+#include <QtGlobal>
+
+#include <vector>
+#include <algorithm>
+#include <iterator>
+
+QT_BEGIN_NAMESPACE
+
+// Minimal API, just for the consumption of Qt Quick Particles.
+// For extra safety, it's in a private namespace
+
+namespace QtQuickParticlesPrivate {
+
+template <typename T>
+class QFlatSet
+{
+public:
+    using iterator = typename std::vector<T>::iterator;
+    using const_iterator = typename std::vector<T>::const_iterator;
+    using value_type = typename std::vector<T>::value_type;
+    using size_type = int;
+
+    iterator find(const T &t)
+    {
+        return std::find(begin(), end(), t);
+    }
+
+    const_iterator find(const T &t) const
+    {
+        return std::find(begin(), end(), t);
+    }
+
+    bool contains(const T &t) const
+    {
+        return find(t) != end();
+    }
+
+    void clear()
+    {
+        m_data.clear();
+    }
+
+    void reserve(int capacity)
+    {
+        m_data.reserve(capacity);
+    }
+
+    iterator insert(const T &t)
+    {
+        auto i = find(t);
+        if (i != end())
+            return i;
+        T copy = t;
+        m_data.push_back(std::move(copy));
+        return std::prev(m_data.end());
+    }
+
+    iterator insert(T &&t)
+    {
+        auto i = find(t);
+        if (i != end())
+            return i;
+        m_data.push_back(std::move(t));
+        return std::prev(m_data.end());
+    }
+
+    size_type remove(const T &t)
+    {
+        auto i = std::find(m_data.begin(), m_data.end(), t);
+        if (i != m_data.end()) {
+            m_data.erase(i);
+            return 1;
+        }
+        return 0;
+    }
+
+    iterator operator<<(const T &t)
+    {
+        return insert(t);
+    }
+
+    iterator operator<<(T &&t)
+    {
+        return insert(std::move(t));
+    }
+
+    iterator begin() { return m_data.begin(); }
+    const_iterator begin() const { return m_data.begin(); }
+    const_iterator cbegin() const { return m_data.cbegin(); }
+
+    iterator end() { return m_data.end(); }
+    const_iterator end() const { return m_data.end(); }
+    const_iterator cend() const { return m_data.cend(); }
+
+private:
+    std::vector<T> m_data;
+};
+
+} // namespace QtQuickParticlesPrivate
+
+QT_END_NAMESPACE
+
+#endif // QQUICKPARTICLEFLATSET_P_H
diff --git a/src/particles/qquickparticlesystem.cpp b/src/particles/qquickparticlesystem.cpp
index 158aede727..57812ba797 100644
--- a/src/particles/qquickparticlesystem.cpp
+++ b/src/particles/qquickparticlesystem.cpp
@@ -1077,7 +1077,7 @@ void QQuickParticleSystem::updateCurrentTime( int currentTime )
         emitter->emitWindow(timeInt);
     foreach (QQuickParticleAffector* a, m_affectors)
         a->affectSystem(dt);
-    foreach (QQuickParticleData* d, needsReset)
+    for (QQuickParticleData* d : needsReset)
         foreach (QQuickParticlePainter* p, groupData[d->groupId]->painters)
             p->reload(d);
 
diff --git a/src/particles/qquickparticlesystem_p.h b/src/particles/qquickparticlesystem_p.h
index 7c0a1ffd7d..ea890d20f4 100644
--- a/src/particles/qquickparticlesystem_p.h
+++ b/src/particles/qquickparticlesystem_p.h
@@ -63,6 +63,7 @@
 #include <private/qv4global_p.h>
 #include <private/qv4staticvalue_p.h>
 #include "qtquickparticlesglobal_p.h"
+#include "qquickparticleflatset_p.h"
 
 QT_BEGIN_NAMESPACE
 
@@ -409,7 +410,7 @@ public:
     int systemSync(QQuickParticlePainter* p);
 
     //Data members here for ease of related class and auto-test usage. Not "public" API. TODO: d_ptrize
-    QSet<QQuickParticleData*> needsReset;
+    QtQuickParticlesPrivate::QFlatSet<QQuickParticleData*> needsReset;
     QVector<QQuickParticleData*> bySysIdx; //Another reference to the data (data owned by group), but by sysIdx
     QQuickStochasticEngine* stateEngine;