From 1bf8826edaecb5485ede616b17e6498754507d93 Mon Sep 17 00:00:00 2001 From: Olli Parviainen Date: Tue, 25 Dec 2018 22:25:32 +0200 Subject: [PATCH] Speed up de-selection by switching to more efficient intrusive list structure De-selection were slow for large path sets because disposal of SPCanvasItems needed to perform linear search through SPCanvasGroup::items linked list for every disposed item separately, meaning O(N^2) operation complexity. For large path sets this became excessively slow. To speed up the disposal operation, changed SPCanvasGroup::items from std::list to boost::intrusive::list that allows getting a linked list position iterator directly from SPCanvasItem pointer in constant time. This reduces the disposal operation complexity from O(N^2) to O(N). Testing with a large path set consisting of >100k items, de-selection became tens of times faster. Signed-off-by: Olli Parviainen --- src/display/sp-canvas-item.h | 10 +++++ src/display/sp-canvas.cpp | 83 +++++++++++++++++++----------------- 2 files changed, 55 insertions(+), 38 deletions(-) diff --git a/src/display/sp-canvas-item.h b/src/display/sp-canvas-item.h index 65bd1cc05c..fc64173252 100644 --- a/src/display/sp-canvas-item.h +++ b/src/display/sp-canvas-item.h @@ -21,6 +21,7 @@ */ #include <2geom/rect.h> +#include #include #include "ui/control-types.h" @@ -49,6 +50,9 @@ typedef struct _GdkCursor GdkCursor; struct SPCanvasItem { GInitiallyUnowned parent_instance; + // boost linked list member hook + boost::intrusive::list_member_hook<> member_hook_; + SPCanvas *canvas; SPCanvasItem *parent; @@ -78,6 +82,12 @@ struct SPCanvasItem { GType sp_canvas_item_get_type(); +//Define type for linked list storing SPCanvasItems +typedef boost::intrusive::list< + SPCanvasItem, + boost::intrusive::member_hook, &SPCanvasItem::member_hook_> > + SPCanvasItemList; + /** * The vtable of an SPCanvasItem. */ diff --git a/src/display/sp-canvas.cpp b/src/display/sp-canvas.cpp index bd4f664495..bd4b142fc8 100644 --- a/src/display/sp-canvas.cpp +++ b/src/display/sp-canvas.cpp @@ -136,8 +136,7 @@ struct SPCanvasGroup { SPCanvasItem item; - std::list items; - + SPCanvasItemList items; }; /** @@ -272,6 +271,9 @@ void sp_canvas_item_construct(SPCanvasItem *item, SPCanvasGroup *parent, gchar c g_return_if_fail(SP_IS_CANVAS_GROUP(parent)); g_return_if_fail(SP_IS_CANVAS_ITEM(item)); + // manually invoke list_member_hook constructor + new (&(item->member_hook_)) boost::intrusive::list_member_hook<>(); + item->parent = SP_CANVAS_ITEM(parent); item->canvas = item->parent->canvas; @@ -495,14 +497,15 @@ void sp_canvas_item_raise(SPCanvasItem *item, int positions) } SPCanvasGroup *parent = SP_CANVAS_GROUP (item->parent); - std::list::iterator l = std::find(parent->items.begin(),parent->items.end(), item); - g_assert (l != parent->items.end()); + auto from = parent->items.iterator_to(*item); + auto to = from; - for (int i=0; i<=positions && l != parent->items.end(); ++i) - ++l; + for (int i = 0; i <= positions && to != parent->items.end(); ++i) { + ++to; + } - parent->items.remove(item); - parent->items.insert(l, item); + parent->items.erase(from); + parent->items.insert(to, *item); redraw_if_visible (item); item->canvas->_need_repick = TRUE; @@ -515,8 +518,8 @@ void sp_canvas_item_raise_to_top(SPCanvasItem *item) if (!item->parent) return; SPCanvasGroup *parent = SP_CANVAS_GROUP (item->parent); - parent->items.remove(item); - parent->items.push_back(item); + parent->items.erase(parent->items.iterator_to(*item)); + parent->items.push_back(*item); redraw_if_visible (item); item->canvas->_need_repick = TRUE; } @@ -540,18 +543,20 @@ void sp_canvas_item_lower(SPCanvasItem *item, int positions) SPCanvasGroup *parent = SP_CANVAS_GROUP(item->parent); - if (!parent || positions == 0 || item == parent->items.front() ) { + if (!parent || positions == 0 || item == &parent->items.front()) { return; } - std::list::iterator l = std::find(parent->items.begin(), parent->items.end(), item); - g_assert (l != parent->items.end()); + auto from = parent->items.iterator_to(*item); + auto to = from; + g_assert(from != parent->items.end()); - for (int i=0; iitems.begin(); ++i) - --l; + for (int i = 0; i < positions && to != parent->items.begin(); ++i) { + --to; + } - parent->items.remove(item); - parent->items.insert(l, item); + parent->items.erase(from); + parent->items.insert(to, *item); redraw_if_visible (item); item->canvas->_need_repick = TRUE; @@ -564,8 +569,8 @@ void sp_canvas_item_lower_to_bottom(SPCanvasItem *item) if (!item->parent) return; SPCanvasGroup *parent = SP_CANVAS_GROUP (item->parent); - parent->items.remove(item); - parent->items.push_front(item); + parent->items.erase(parent->items.iterator_to(*item)); + parent->items.push_front(*item); redraw_if_visible (item); item->canvas->_need_repick = TRUE; } @@ -768,8 +773,8 @@ gint sp_canvas_item_order (SPCanvasItem * item) { SPCanvasGroup * p = SP_CANVAS_GROUP(item->parent); size_t index = 0; - for (std::list::const_iterator it = p->items.begin(); it != p->items.end(); ++it, ++index) { - if ((*it) == item) { + for (auto it = p->items.begin(); it != p->items.end(); ++it, ++index) { + if (item == &(*it)) { return index; } } @@ -793,7 +798,7 @@ static void sp_canvas_group_class_init(SPCanvasGroupClass *klass) static void sp_canvas_group_init(SPCanvasGroup * group) { - new (&group->items) std::list; + new (&group->items) SPCanvasItemList; } void SPCanvasGroup::destroy(SPCanvasItem *object) @@ -803,12 +808,14 @@ void SPCanvasGroup::destroy(SPCanvasItem *object) SPCanvasGroup *group = SP_CANVAS_GROUP(object); - for (std::list::iterator it = group->items.begin(); it != group->items.end(); ++it) { - sp_canvas_item_destroy(*it); + for (auto it = group->items.begin(); it != group->items.end();) { + SPCanvasItem *item = &(*it); + it++; + sp_canvas_item_destroy(item); } group->items.clear(); - group->items.~list(); // invoke manually + group->items.~SPCanvasItemList(); // invoke manually if (SP_CANVAS_ITEM_CLASS(sp_canvas_group_parent_class)->destroy) { (* SP_CANVAS_ITEM_CLASS(sp_canvas_group_parent_class)->destroy)(object); @@ -817,11 +824,11 @@ void SPCanvasGroup::destroy(SPCanvasItem *object) void SPCanvasGroup::update(SPCanvasItem *item, Geom::Affine const &affine, unsigned int flags) { - SPCanvasGroup const *group = SP_CANVAS_GROUP(item); + SPCanvasGroup *group = SP_CANVAS_GROUP(item); Geom::OptRect bounds; - for (std::list::const_iterator it = group->items.begin(); it != group->items.end(); ++it) { - SPCanvasItem *i = *it; + for (auto it = group->items.begin(); it != group->items.end(); ++it) { + SPCanvasItem *i = &(*it); sp_canvas_item_invoke_update (i, affine, flags); @@ -844,7 +851,7 @@ void SPCanvasGroup::update(SPCanvasItem *item, Geom::Affine const &affine, unsig double SPCanvasGroup::point(SPCanvasItem *item, Geom::Point p, SPCanvasItem **actual_item) { - SPCanvasGroup const *group = SP_CANVAS_GROUP(item); + SPCanvasGroup *group = SP_CANVAS_GROUP(item); double const x = p[Geom::X]; double const y = p[Geom::Y]; int x1 = (int)(x - item->canvas->_close_enough); @@ -856,8 +863,8 @@ double SPCanvasGroup::point(SPCanvasItem *item, Geom::Point p, SPCanvasItem **ac *actual_item = nullptr; double dist = 0.0; - for (std::list::const_iterator it = group->items.begin(); it != group->items.end(); ++it) { - SPCanvasItem *child = *it; + for (auto it = group->items.begin(); it != group->items.end(); ++it) { + SPCanvasItem *child = &(*it); if ((child->x1 <= x2) && (child->y1 <= y2) && (child->x2 >= x1) && (child->y2 >= y1)) { SPCanvasItem *point_item = nullptr; // cater for incomplete item implementations @@ -888,10 +895,10 @@ double SPCanvasGroup::point(SPCanvasItem *item, Geom::Point p, SPCanvasItem **ac void SPCanvasGroup::render(SPCanvasItem *item, SPCanvasBuf *buf) { - SPCanvasGroup const *group = SP_CANVAS_GROUP(item); + SPCanvasGroup *group = SP_CANVAS_GROUP(item); - for (std::list::const_iterator it = group->items.begin(); it != group->items.end(); ++it) { - SPCanvasItem *child = *it; + for (auto it = group->items.begin(); it != group->items.end(); ++it) { + SPCanvasItem *child = &(*it); if (child->visible) { if ((child->x1 < buf->rect.right()) && (child->y1 < buf->rect.bottom()) && @@ -909,8 +916,8 @@ void SPCanvasGroup::viewboxChanged(SPCanvasItem *item, Geom::IntRect const &new_ { SPCanvasGroup *group = SP_CANVAS_GROUP(item); - for (std::list::const_iterator it = group->items.begin(); it != group->items.end(); ++it) { - SPCanvasItem *child = *it; + for (auto it = group->items.begin(); it != group->items.end(); ++it) { + SPCanvasItem *child = &(*it); if (child->visible) { if (SP_CANVAS_ITEM_GET_CLASS(child)->viewbox_changed) { SP_CANVAS_ITEM_GET_CLASS(child)->viewbox_changed(child, new_area); @@ -924,7 +931,7 @@ void SPCanvasGroup::add(SPCanvasItem *item) g_object_ref(item); g_object_ref_sink(item); - items.push_back(item); + items.push_back(*item); sp_canvas_item_request_update(item); } @@ -933,7 +940,7 @@ void SPCanvasGroup::remove(SPCanvasItem *item) { g_return_if_fail(item != nullptr); - auto position = std::find(items.begin(), items.end(), item); + auto position = items.iterator_to(*item); if (position != items.end()) { items.erase(position); } -- GitLab