Speed on different platforms

Hi folks,

I'm using GraphViz as a library on

Windows (32bit your provided 2.38 zip, 64bit self 2.34),
Mac (brew 2.38),
Linux (Ubuntu 2.36).

Currently I'm timing the same situation: A small graph, about 60 nodes, positions are fixed and only spline edge layout is done with neato.
Mac and Linux are about equal, but Windows 32bit is much slower (factor 5). Windows 64bit is about a factor 3 slower.

Would you expect such behaviour, i.e. is it known and/or is there a reason for this?
Any hints if or how I could improve the speed on Windows?

Is the speed in the spline layout related to the presence of a GraphViz dependency library? (i.e. a very fast solver library for something...)

Not related, is there a 64bit Windows Version of GraphViz?

Thank you.

Regards Mike

The code is identical for all

The code is identical for all systems. I would have guessed that it is simply a matter of compiler and compile-time options (we still use VS 2008 and probably don't use various compile-time flags to optimize the code), except presumably you have optimized your 64-bit build. In any case, I do see a factor of 3 on my mac between non-optimized and optimized versions, so using -O2 or something makes a difference. If you can suggest the Windows analogue of -O2, I can try putting it in and see what happens.

Also, no, there is currently no 64-bit Windows version. Our resources are spread pretty thin.

Thank you for your reply. I

Thank you for your reply.

I compiled my 64bit Windows version with mingw, so there is also -O2 used. My compiled 32bit version on Windows was actually a little slower then your provided one, so optimization doesn't seem to be the problem. The difference between 64bit and 32bit Windows is roughly 2, so maybe there are some optimizations using 64bit?

I've investigated a little further. As said I have nodes with fixed positions and want to route the edges, so neato resp. nop2 is needed.

Guessing: From the resulting layouts I guess, that the routes of the edges do not depend on one another, so one could parallelize the routing. Therefore a function like "route(const &Graph, Edge)" would be perfect. Could you point me to a place similar to that in the code? (I guess there is a loop routing all the edges somewhere?)

Furthermore I checked routing all edges compared to half of them compared to only one. (using gvRender and setting pos="" for resp. edges): There was no difference in time routing all or just half of them; just one was much faster as expected.

Currently a hint for a function "route(const &Graph, Edge)" would be very nice.

Regards Mike

 

I assume by routing, you are

I assume by routing, you are using splines=true or polyline, because otherwise, spline routing should be immediate. For spline routing in neato, there are four phases: aggregate the multiedges; construct the visibility graph of the vertices of the node shapes; attach the shortest path in the visibility graph to each edge; route each edge. (If there actually are multiedges, special-purpose code is called to handle this.) Constructing the visibility graph is cubic and can be the real bottleneck. Once that is done, finding the shortest path and constructing the edge can be parallelized, as you suggest.

Attaching the shortest path is done in lib/neatogen/neatosplines.c, line 602. The "route" function you are looking for occurs in lib/neatogen/neatosplines.c, line 652:

                    if (edgetype == ET_SPLINE)
                        makeSpline(g, e0, obs, npoly, TRUE);
                    else
                        makePolyline(g, e0);

There is an outer loop over i < cnt, but assuming the GTS library is present, cnt will always be 0. So, if splines=true, makeSpline() is called; otherwise, makePolyline() is called.

Note that one could conceivably use makeMultiSpline for everything, to avoid the visibility graph construction.I also have the outline for another routing algorithm that should be even faster, and doesn't require the nodes not to overlap, but it is not clear if I will ever get time to implement it.

 

Thank you for the

Thank you for the hint.

Well, I was hoping that the "makeSpline" would only alter the edge and not the graph, so it would be straight forward to parallelize it, but it also alters the graph (update of the bounding box) which calls for some synchronization and with this for a deeper understanding of what is really going on.

Regards Mike

Thank you very much. I will

Thank you very much. I will check your reference.

You're right, I meant spline edges.

Meanwhile, speaking of time, does 100ms(MAC) to 600ms(Windows) (each time fast Intel i7 quadcore) sound reasonable for the attached graph, or would you expect much faster spline edge routing, when the positions are given?

http://www.graphviz.org/sites/default/files/u7642/graph.png

Regards Mike

Any chance you could post or

Any chance you could post or point to the DOT file?

I don't have a good feel for what times one might expect on current hardware. I would also have to check to see if we only use rectangles, or if you are paying for the curved shapes.

Sorry, I had to change the

Sorry, I had to change the labels, but the width and height are more important anyway. http://www.graphviz.org/sites/default/files/u7642/graph.dot_.jpg You have to rename it to dot.

Thank you for your help.

Regards Mike

Recent comments