View Issue Details
ID | Project | Category | View Status | Date Submitted | Last Update |
---|---|---|---|---|---|
0016604 | Scribus | General | public | 2021-08-03 15:20 | 2021-11-09 21:39 |
Reporter | fsimonis | Assigned To | jghali | ||
Priority | normal | Severity | minor | Reproducibility | N/A |
Status | closed | Resolution | fixed | ||
Product Version | 1.5.8.svn | ||||
Fixed in Version | 1.5.8.svn | ||||
Summary | 0016604: Slow name checks in item creation | ||||
Description | Checking 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. | ||||
Tags | No tags attached. | ||||
Patch | Yes | ||||
|
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 |
|
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. |
|
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; } |
|
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). |
|
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. |
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 | |
2021-11-09 21:39 | cbradney | Status | resolved => closed |