deselecting a long path extremely slow (many minutes)

Bug #1745763 reported by Marcel Waldvogel on 2018-01-27
12
This bug affects 2 people
Affects Status Importance Assigned to Milestone
Inkscape
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.

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)
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.

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
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.

Hachmann (marenhachmann) wrote :

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

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)

Patrick Storz (ede123) wrote :

Now fixed (see original report for details).

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

Other bug subscribers