statistics: keep track of dirty items in double-linked list

So far the items to be recalculated in the drawing thread
had a "dirty" flag and were kept in one array par z-level.

Once the series are implemented in terms of QSGNodes, there
may lots of these items. To make this more efficient when
only one or two of these items change (e.g. highlighting due
to mouseover), keep the dirty items in a linked list.

Of course, this makes the draw first version of the chart
less efficient.

There are more fancy ways of implementing the double-linked
list, but the few ns gained in the render thread are hardly
worth it.

Signed-off-by: Berthold Stoeger <bstoeger@mail.tuwien.ac.at>

4 files changed, 49 insertions, 36 deletions

diff --git a/stats/chartitem.cpp b/stats/chartitem.cpp
index 6fef5e44f..aeb395d41 100644
--- a/stats/chartitem.cpp
+++ b/stats/chartitem.cpp
@@ -14,13 +14,15 @@ static int round_up(double f)
 }
 
 ChartItem::ChartItem(StatsView &v, ChartZValue z) :
-	dirty(false), zValue(z), view(v)
+	dirty(false), dirtyPrev(nullptr), dirtyNext(nullptr),
+	zValue(z), view(v)
 {
 }
 
 ChartItem::~ChartItem()
 {
-	view.unregisterChartItem(this);
+	if (dirty)
+		view.unregisterDirtyChartItem(*this);
 }
 
 QSizeF ChartItem::sceneSize() const
@@ -41,19 +43,17 @@ ChartPixmapItem::~ChartPixmapItem()
 void ChartPixmapItem::setTextureDirty()
 {
 	textureDirty = true;
-	dirty = true;
+	view.registerDirtyChartItem(*this);
 }
 
 void ChartPixmapItem::setPositionDirty()
 {
 	positionDirty = true;
-	dirty = true;
+	view.registerDirtyChartItem(*this);
 }
 
 void ChartPixmapItem::render()
 {
-	if (!dirty)
-		return;
 	if (!node) {
 		node.reset(view.w()->createImageNode());
 		view.addQSGNode(node.get(), zValue);
@@ -71,7 +71,6 @@ void ChartPixmapItem::render()
 		node->setRect(rect);
 		positionDirty = false;
 	}
-	dirty = false;
 }
 
 void ChartPixmapItem::resize(QSizeF size)
@@ -161,5 +160,5 @@ void ChartLineItem::setLine(QPointF fromIn, QPointF toIn)
 	from = fromIn;
 	to = toIn;
 	positionDirty = true;
-	dirty = true;
+	view.registerDirtyChartItem(*this);
 }
diff --git a/stats/chartitem.h b/stats/chartitem.h
index 5dab8d1ea..f13cb3bc4 100644
--- a/stats/chartitem.h
+++ b/stats/chartitem.h
@@ -19,9 +19,10 @@ class ChartItem {
 public:
 	ChartItem(StatsView &v, ChartZValue z);
 	virtual ~ChartItem();
-	virtual void render() = 0;	// Only call on render thread!
+	virtual void render() = 0;		// Only call on render thread!
 	QRectF getRect() const;
-	bool dirty;			// If true, call render() when rebuilding the scene
+	bool dirty;				// If true, call render() when rebuilding the scene
+	ChartItem *dirtyPrev, *dirtyNext;	// Double linked list of dirty items
 	const ChartZValue zValue;
 protected:
 	QSizeF sceneSize() const;
diff --git a/stats/statsview.cpp b/stats/statsview.cpp
index e893c3ebb..40d23eed3 100644
--- a/stats/statsview.cpp
+++ b/stats/statsview.cpp
@@ -36,9 +36,10 @@ StatsView::StatsView(QQuickItem *parent) : QQuickItem(parent),
 	xAxis(nullptr),
 	yAxis(nullptr),
 	draggedItem(nullptr),
-	rootNode(nullptr)
+	rootNode(nullptr),
+	firstDirtyChartItem(nullptr),
+	lastDirtyChartItem(nullptr)
 {
-	chartItems.reset(new std::vector<ChartItem *>[(size_t)ChartZValue::Count]);
 	setFlag(ItemHasContents, true);
 
 	connect(&diveListNotifier, &DiveListNotifier::numShownChanged, this, &StatsView::replotIfVisible);
@@ -124,11 +125,11 @@ QSGNode *StatsView::updatePaintNode(QSGNode *oldNode, QQuickItem::UpdatePaintNod
 		plotAreaChanged(plotRect.size());
 	}
 
-	for (int i = 0; i < (int)ChartZValue::Count; ++i) {
-		for (ChartItem *item: chartItems[i]) {
-			if (item->dirty)
-				item->render();
-		}
+	for (ChartItem *item = std::exchange(firstDirtyChartItem, nullptr); item;
+	     item = std::exchange(item->dirtyNext, nullptr)) {
+		item->render();
+		item->dirty = false;
+		item->dirtyPrev = nullptr;
 	}
 
 	img->fill(Qt::transparent);
@@ -145,22 +146,34 @@ void StatsView::addQSGNode(QSGNode *node, ChartZValue z)
 	rootNode->zNodes[idx]->appendChildNode(node);
 }
 
-// Currently this does an inefficient linear search in the chart-item vector.
-// However, we entertain one vector of items per Z-value and currently
-// only the infobox is explicitly deleted, which has a unique Z-value.
-void StatsView::unregisterChartItem(const ChartItem *item)
+void StatsView::unregisterDirtyChartItem(ChartItem &item)
 {
-	int idx = std::clamp((int)item->zValue, 0, (int)ChartZValue::Count - 1);
-	std::vector<ChartItem *> &v = chartItems[idx];
-	auto it = std::find(v.begin(), v.end(), item);
-	if (it != v.end())
-		v.erase(it);
+	if (!item.dirty)
+		return;
+	if (item.dirtyNext)
+		item.dirtyNext->dirtyPrev = item.dirtyPrev;
+	else
+		lastDirtyChartItem = item.dirtyPrev;
+	if (item.dirtyPrev)
+		item.dirtyPrev->dirtyNext = item.dirtyNext;
+	else
+		firstDirtyChartItem = item.dirtyNext;
+	item.dirtyPrev = item.dirtyNext = nullptr;
+	item.dirty = false;
 }
 
-void StatsView::registerChartItem(ChartItem *item)
+void StatsView::registerDirtyChartItem(ChartItem &item)
 {
-	int idx = std::clamp((int)item->zValue, 0, (int)ChartZValue::Count - 1);
-	chartItems[idx].push_back(item);
+	if (item.dirty)
+		return;
+	if (!firstDirtyChartItem) {
+		firstDirtyChartItem = &item;
+	} else {
+		item.dirtyPrev = lastDirtyChartItem;
+		lastDirtyChartItem->dirtyNext = &item;
+	}
+	lastDirtyChartItem = &item;
+	item.dirty = true;
 }
 
 QQuickWindow *StatsView::w() const
@@ -326,9 +339,10 @@ void StatsView::reset()
 	highlightedSeries = nullptr;
 	xAxis = yAxis = nullptr;
 	draggedItem = nullptr;
-	if (rootNode) {
-		for (int i = 0; i < (int)ChartZValue::Count; ++i)
-			chartItems[i].clear(); // non-owning pointers
+	for (ChartItem *item = std::exchange(firstDirtyChartItem, nullptr); item;
+	     item = std::exchange(item->dirtyNext, nullptr)) {
+		item->dirty = false;
+		item->dirtyPrev = nullptr;
 	}
 	legend.reset();
 	series.clear();
diff --git a/stats/statsview.h b/stats/statsview.h
index c8e850d9b..f472e1e16 100644
--- a/stats/statsview.h
+++ b/stats/statsview.h
@@ -54,8 +54,8 @@ public:
 	QQuickWindow *w() const;		// Make window available to items
 	QSizeF size() const;
 	void addQSGNode(QSGNode *node, ChartZValue z);	// Must only be called in render thread!
-	void registerChartItem(ChartItem *item);
-	void unregisterChartItem(const ChartItem *item);
+	void registerDirtyChartItem(ChartItem &item);
+	void unregisterDirtyChartItem(ChartItem &item);
 	template <typename T, class... Args>
 	std::unique_ptr<T> createChartItem(Args&&... args);
 
@@ -142,7 +142,6 @@ private:
 
 	StatsState state;
 	QFont titleFont;
-	std::unique_ptr<std::vector<ChartItem *>[]> chartItems;
 	std::vector<std::unique_ptr<StatsAxis>> axes;
 	std::unique_ptr<StatsGrid> grid;
 	std::vector<std::unique_ptr<StatsSeries>> series;
@@ -162,6 +161,7 @@ private:
 	void mouseReleaseEvent(QMouseEvent *event) override;
 	void mouseMoveEvent(QMouseEvent *event) override;
 	RootNode *rootNode;
+	ChartItem *firstDirtyChartItem, *lastDirtyChartItem;
 };
 
 // This implementation detail must be known to users of the class.
@@ -170,7 +170,6 @@ template <typename T, class... Args>
 std::unique_ptr<T> StatsView::createChartItem(Args&&... args)
 {
 	std::unique_ptr<T> res(new T(*this, std::forward<Args>(args)...));
-	registerChartItem(res.get());
 	return res;
 }