[go: up one dir, main page]

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. An intrusive list has the linked list next/prev hooks directly within the stored SPCanvasItem object structure itself, hence knowing pointer to such object enables directly manipulating it's placement in the list. This reduces the item disposal operation complexity from O(N^2) to O(N).

Testing with a large path set consisting of >100k items, de-selection became (at least) tens of times faster.

Signed-off-by: Olli Parviainen oparviai@iki.fi

Edited by Olli Parviainen

Merge request reports

Loading