View Issue Details

IDProjectCategoryView StatusLast Update
0016604ScribusGeneralpublic2021-08-11 05:19
Reporterfsimonis Assigned Tojghali  
PrioritynormalSeverityminorReproducibilityN/A
Status resolvedResolutionfixed 
Product Version1.5.8.svn 
Fixed in Version1.5.8.svn 
Summary0016604: Slow name checks in item creation
DescriptionChecking for an existing name in a document is currently implemented in a very inefficient way.
It checks Elements of the doc by gathering all elements of groups in a QList and then checks each element for a matching name.
This is especially noticeable when directly opening pdfs and importing Text as Vector graphics, which renders each character as a separate polygon. Currently, this is dominated by the name checks in PageItem::PageItem().

This patch changes the name checking of PageItems by directly iterating through items and groups, preventing the gathering of all PageItems.

While the complexity is still a huge problem for larger documents, the constant factor is way better.
The first 20 pages of my test pdf take 60 seconds to load without and 20 with this patch.
TagsNo tags attached.
PatchYes

Activities

fsimonis

2021-08-03 15:20

reporter  

0001-Refactor-itemNameExists.patch (3,090 bytes)   
From 7a857644cde5f42c38380fd71943cdf497eae67c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Fr=C3=A9d=C3=A9ric=20Simonis?= <simonisfrederic@gmail.com>
Date: Tue, 3 Aug 2021 17:15:35 +0200
Subject: [PATCH] Refactor itemNameExists

---
 scribus/pageitem.h         |  8 ++++++++
 scribus/pageitem_group.cpp | 11 +++++++++++
 scribus/pageitem_group.h   |  1 +
 scribus/scribusdoc.cpp     | 23 ++++-------------------
 4 files changed, 24 insertions(+), 19 deletions(-)

diff --git a/scribus/pageitem.h b/scribus/pageitem.h
index eead94200..f4083bc38 100644
--- a/scribus/pageitem.h
+++ b/scribus/pageitem.h
@@ -813,6 +813,14 @@ public: // Start public functions
 	 */
 	void setItemName(const QString& newName);
 
+	/**
+	 * @brief checks if this or child items have the given name.
+	 * @param checkItemName the name to search for
+	 */
+	virtual bool itemNameExists(const QString& checkItemName) const {
+		return m_itemName == checkItemName;
+	}
+
 	/**
 	* @brief Set the masterpage the object is on
 	* @param mpName name of the master page
diff --git a/scribus/pageitem_group.cpp b/scribus/pageitem_group.cpp
index 9e45a9cbf..cd7ee0a84 100644
--- a/scribus/pageitem_group.cpp
+++ b/scribus/pageitem_group.cpp
@@ -109,6 +109,17 @@ void PageItem_Group::layout()
 	}
 }
 
+bool PageItem_Group::itemNameExists(const QString& checkItemName) const {
+	if (itemName() == checkItemName)
+		return true;
+
+	for (const auto& item: groupItemList) {
+		if (item->itemNameExists(checkItemName))
+			return true;
+	}
+	return false;
+}
+
 void PageItem_Group::setLayer(int newLayerID)
 {
 	for (int em = 0; em < groupItemList.count(); ++em)
diff --git a/scribus/pageitem_group.h b/scribus/pageitem_group.h
index 7aedd2830..29b8799c6 100644
--- a/scribus/pageitem_group.h
+++ b/scribus/pageitem_group.h
@@ -45,6 +45,7 @@ public:
 	bool isTextContainer() const override;
 	ItemType realItemType() const override { return PageItem::Group; }
 
+	bool itemNameExists(const QString& checkItemName) const override;
 	void adjustXYPosition();
 	void setLayer(int layerId) override;
 	void setMasterPage(int page, const QString& mpName) override;
diff --git a/scribus/scribusdoc.cpp b/scribus/scribusdoc.cpp
index e77f8ceef..8ede7ce4e 100644
--- a/scribus/scribusdoc.cpp
+++ b/scribus/scribusdoc.cpp
@@ -6431,28 +6431,13 @@ int ScribusDoc::currentPageNumber()
 }
 
 
-bool ScribusDoc::itemNameExists(const QString& checkItemName)
+bool ScribusDoc::itemNameExists(const QString& checkItemName) const
 {
-	bool found = false;
-	QList<PageItem*> allItems;
-	int docItemCount = Items->count();
-	for (int i = 0; i < docItemCount; ++i)
-	{
-		PageItem *currItem = Items->at(i);
-		if (checkItemName == currItem->itemName())
+	for (const auto& item: *Items) {
+		if (item->itemNameExists(checkItemName))
 			return true;
-		if (currItem->isGroup())
-		{
-			allItems = currItem->getAllChildren();
-			for (int ii = 0; ii < allItems.count(); ii++)
-			{
-				if (checkItemName == allItems.at(ii)->itemName())
-					return true;
-			}
-		}
-		allItems.clear();
 	}
-	return found;
+	return false;
 }
 
 
-- 
2.32.0

jghali

2021-08-03 19:15

administrator   ~0049191

Last edited: 2021-08-03 19:16

This implementation uses recursive calls, which could trigger a stack overflow if a group was too "deep". A safer implementation could use PageItemIterator:

bool ScribusDoc::itemNameExists(const QString& checkItemName) const
{
    PageItemIterator it(*Items, PageItemIterator::IterateInGroups);
    for ( ; *it; ++it)
    {
        PageItem *currItem = *it;
        if (currItem->itemName() == checkItemName)
            return true;
    }

    return false;
}

This PageItemIterator based implementation should be slower than your implementation, but safer. So I'd be curious to know how it performs compared to your implementation.

fsimonis

2021-08-04 10:37

reporter   ~0049196

As is, the PageItemIterator version perform the same as the previous version, which is due to PageItem::itemName() returning a copy of the string.

So I added the following to circumvent this.
bool PageItem::hasItemName(const QString& name) const { return m_item_name == name ; }
I did some measurements, but the original implementation has strong variations in the runtime.

Baseline: 50 seconds +- 10 seconds
PageItemIterator + hasItemName: ~30s
Recursive: ~20s
Group Stack + hasItemName: ~20s

The group stack is an alternative impl, which uses a stack for group items.

bool ScribusDoc::itemNameExists(const QString& checkItemName) const
{
  std::vector<PageItem*> groups;
  // Reserve a 64B cacheline for the stack on 64bit systems
  groups.reserve(8);
  // Process root elements of the doc and remember groups
    for (PageItem* item: *Items) {
        if (item->hasItemName(checkItemName))
            return true;
    if (item->isGroup())
      groups.push_back(item);
    }

  // Process groups
  while(!groups.empty()) {
    PageItem* item = groups.back();
    groups.pop_back();
    for (PageItem* item: item->groupItemList) {
      if (item->hasItemName(checkItemName))
        return true;
      if (item->isGroup())
        groups.push_back(item);
      }
  }
  return false;
}

jghali

2021-08-11 00:06

administrator   ~0049205

Thanks. After several tests on Windows and Linux, I went for your stack based implementation as it provides performances close to the recursive implementation while being safer. I was more generous tho as for the initial cacheline (32 items instead of 8).

ale

2021-08-11 05:19

manager   ~0049206

of course, the solution would be that scribus finally stops, to internally use names that are given by the user.
just use an auto incrementing index.

the user could then set a second field with a name that has no meaning for scribus.
if you want, you can still check them for uniqueness (way fewer fields, of course!) or even not care at all about them (just do something sane ,if the user picks twice the same item name)

over the years, so many hours have been spent for solving issues in items, colors, styles and other resources.
it really hurts, when i read tickets like this one.

Issue History

Date Modified Username Field Change
2021-08-03 15:20 fsimonis New Issue
2021-08-03 15:20 fsimonis File Added: 0001-Refactor-itemNameExists.patch
2021-08-03 19:15 jghali Note Added: 0049191
2021-08-03 19:16 jghali Note Edited: 0049191
2021-08-04 10:37 fsimonis Note Added: 0049196
2021-08-11 00:06 jghali Assigned To => jghali
2021-08-11 00:06 jghali Status new => resolved
2021-08-11 00:06 jghali Resolution open => fixed
2021-08-11 00:06 jghali Fixed in Version => 1.5.8.svn
2021-08-11 00:06 jghali Note Added: 0049205
2021-08-11 00:08 jghali Summary Slow name checks in Item creation => Slow name checks in item creation
2021-08-11 05:19 ale Note Added: 0049206