deselecting a long path extremely slow (many minutes)

Bug #1745763 reported by Marcel Waldvogel
12
This bug affects 2 people
Affects Status Importance Assigned to Milestone
Inkscape
Confirmed
Medium
Unassigned

Bug Description

Deselecting a path with more than 10,000 nodes takes minutes (without any visual feedback). Selecting the path takes a fraction of a second or very few seconds (with visual feedback). This even when drawing the entire svg only takes a fraction of a second.

inkscape 0.92.2-1build1 on Ubuntu 17.10 (artful)

How to reproduce:

- Download the SVG from https://commons.wikimedia.org/wiki/File:Europe_blank_laea_location_map_(variant).svg
- Open the file. Rendering is sub-second.
- Unlock layer "_coastline"
- Click inside the image and then double-click to select the path (24k nodes). This takes about 2 seconds on my machine, painted top-down, so there is visual feedback. Also, two seconds for 24k nodes is perfectly acceptable.
- Click outside the image to deselect the path. This takes over 4 minutes (!) on my machine. During this, there is no visual feedback and Gnome even "helpfully" asks whether to kill the process (which I did the first few times, until I became patient enough)

Further operations will take about the same time again. So deselecting long paths should be avoided at all costs.

Further information:

Selecting Russia in layer "_countries" (15k nodes) is sub-second; deselecting it takes just over 1 minute. So it seems that an n^3 algorithm is used for the deselection redraw, as 1:4 ~ (15k:24k)^3. This also correlates with the fact that deselection of paths with 1k or 2k nodes is immediate.

My first assumption was that a redraw is triggered for each of the marker squares, which would explain n^2 runtime.

Remedy:
Possible solutions might include:
- Find an algorithm with lower complexity.
- When deselecting paths with more than 1k (or 10k) nodes, redraw the entire bounding box of the path instead of only the node markers.
- When deselecting long paths, split the path into smaller paths (whether this works depends on the actual redraw procedure used)
- Measure the time it took for the first draw (or last full redraw) of the SVG. When deselecting takes longer than this time, do a full redraw instead.

This might be related to bug #1624072.

Revision history for this message
Marcel Waldvogel (marcel.waldvogel) wrote :

I understand this is a rare case. But when you have to work with these files, working gets all but impossible. For a user, it is baffling that selection should take around a second while deselection could take multiple minutes without any hint whether Inkscape will ever return from that 100% CPU consumption.

summary: - deselecting a long path extremely slow
+ deselecting a long path extremely slow (many minutes)
Revision history for this message
Alvin Penner (apenner) wrote :

thank you for taking the time to issue a report.

problem not reproduced on Windows 10, Inkscape 0.92.2 (5c3e80d, 2017-08-06)
- the path contains 24653 nodes. selecting and deselecting is instantaneous when using the F1 tool.
- significantly slower when using the F2 node tool (perhaps 5 seconds or so) but I assume that is not what you were doing.

Revision history for this message
Patrick Storz (ede123) wrote :

Confirmed on Windows 10 (both master and 0.92.x)

The issue happens when using the node tool (F2) which is activated in the step "double-click to select the path" of the original report.

On my system it does not take minutes but a little less than 30 s to deselect, which is much too long nonetheless. (@Alvin: If it takes only 5 s for you I assume you can be happy to have very fast hardware ;-). I assume selecting is also much faster for you than deselcting?)

Changed in inkscape:
status: New → Confirmed
importance: Undecided → Medium
tags: added: node-editing performance
Revision history for this message
Alvin Penner (apenner) wrote :

yes, I somewhat misjudged the time. With the node tool, the selection takes one or two seconds and the deselection takes about 13 seconds or so.

Revision history for this message
Hachmann (marenhachmann) wrote :

I can confirm, this is an issue I encounter frequently.

Revision history for this message
Patrick Storz (ede123) wrote :

This might actually be a duplicate of bug #1652100.

(Just spotted it when you added it to the release notes Maren)

Revision history for this message
Patrick Storz (ede123) wrote :

Now fixed (see original report for details).

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers