Skip to content

SVG import is exponentially slow with respect to the number of layers #2515

Open
@Keavon

Description

@Keavon

During the import process, we are finding space to push the nodes. As more nodes are added, each additional node has to account for all the existing ones. So this probably is taking roughly O(n^2) because of:

Image

And we can see the call stack depth grow over time (actually, we're seeing the stack depth grow linearly but take increasingly long to do so over time, hence the inverse of the graph of the equation above):

Image

This repeatedly alternates between these two functions:

  • NodeNetworkInterface::vertical_shift_with_push
  • NodeNetworkInterface::shift_node_or_parent

We should probably avoid running any of this logic and just precompute the coordinates of each layer in the resulting layers that get added to the graph. We should also see if this repeated looping between those two functions can be avoided in the general case, even outside of SVG importing.

Reproduction SVG (takes about 10 seconds to open)

Metadata

Metadata

Assignees

Labels

PerformanceSpeed and efficiency improvements

Type

Projects

Status

Short-Term

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions