search

eclipse / elk

Eclipse Layout Kernel - Automatic layout for Java applications.
https://www.eclipse.org/elk/
Other
240 stars 82 forks source link

Maximum call stack size exceeded in $connectedComponentsDFS #755

Open B3rn475 opened 3 years ago

B3rn475 commented 3 years ago

I'm reporting here, even if I'm experiencing the problem with elkjs, as in https://github.com/eclipse/elk/issues/472 it was reported that this is the correct way to do it.

I'm encountering Maximum call stack size exceeded in function $connectedComponentsDFS, while running a layered layout.

The Java counterpart of this function is at https://github.com/eclipse/elk/blob/3630e23fa5abc253233296e2bdf5e18828e5dba7/plugins/org.eclipse.elk.alg.layered/src/org/eclipse/elk/alg/layered/p2layers/NetworkSimplexLayerer.java#L103-L133 and is, unfortunately, recursive.

B3rn475 commented 3 years ago

Extra info: To reproduce it is enough to build a model with 100000 nodes connected in a line n0 => n1 => n2 => .... => n100000.

uruuru commented 3 years ago

Since this keeps re-occurring, it may be a good idea to replace the recursion by an iteration.

Further places:

B3rn475 commented 3 years ago

Thank you very much for these fixes.

Is there an idea of when these changes will get into a release?

uruuru commented 3 years ago

Note that they are not on master yet. Coffman graham is still missing as well.

There's no timeline for the next ELK release, however, I can assemble a dev release based on the current master for elkjs any time.

B3rn475 commented 3 years ago

Just to fully understand.

The dev release you are suggesting would be for cherry picking the changes into elkjs and have a point release there?

uruuru commented 3 years ago

Yes.

B3rn475 commented 3 years ago

That would be awesome

B3rn475 commented 3 years ago

Friendly Ping.

Will you have time to assemble a dev release based on the current master for elkjs?

uruuru commented 3 years ago

@B3rn475, just published elkjs 0.7.3-dev which hopefully contains a fix.

B3rn475 commented 3 years ago

Version 0.7.3-dev solved the problem with $connectedComponentsDFS, but it is triggering it again in $tightTreeDFS.

https://github.com/eclipse/elk/blob/3630e23fa5abc253233296e2bdf5e18828e5dba7/plugins/org.eclipse.elk.alg.common/src/org/eclipse/elk/alg/common/networksimplex/NetworkSimplex.java#L515-L537

Which is also recursive

uruuru commented 3 years ago

:/

Either my simple test didn't cover this or it's part of node placement? I.e. does changing nodePlacement.strategy resolve it?

B3rn475 commented 2 years ago

I tried to change the strategy to any other value, e.g.:

layoutOptions: {
  // ...
  'elk.layered.nodePlacement.strategy': 'LINEAR_SEGMENTS',
}

But nothing changes. (let me know if I'm doing it wrong). I'm working on a model with 20K+ nodes and 25k+ edges.

I guess that, in general, all these recursive functions are there waiting to trigger a Maximum call stack size exceeded error, especially in elkjs, given the fact that there is no guarantee that the walk will not hit an edge case and manage one single node per stack frame.

uruuru commented 2 years ago

I guess that, in general, all these recursive functions are there waiting to trigger a Maximum call stack size exceeded error,

Yes. I tried to remove those that affected your graphs but obviously missed at least one.

perenstrom commented 9 months ago

Hello, any updates on this issue? I encountered it now with about 37k nodes, as well in ElkJS.

soerendomroes commented 9 months ago

Sadly there are no updates.

daydayhappychao commented 1 month ago

bump

daydayhappychao commented 3 weeks ago

Fixed by using the java version of elk. So the reason for the issue is that the elk-js has performance issues. Is it possible to implement elk in the browser using methods other than GWF?

B3rn475 commented 3 weeks ago

@daydayhappychao the main problem is tail recursion. The Java version relies on tail recursion optimizations that do not exist when converted to JavaScript. The main option is to convert all of them into loops.