Hi François, On 07.06.2016 11:27, François wrote:

Hello,

For experimental purpose I benchmarked the *topology.shortest_distance* run time. I stumbled upon something I fail to explain. In this benchmark I compare two graphs :

(*) The first graph is undirected and has about 11M edges and 8M vertices; (*) The second graph is a copy of the first one with directed edges. In this graph, for each edge from the first graph the backward edge is added. Hence, the second graph has about 22M edge and 8M vertices.

I use https://gist.github.com/Fkawala/f7a3366a0d702163d7499ce29efec78e <https://gist.github.com/Fkawala/f7a3366a0d702163d7499ce29efec78e> to measure the run time of a shortest path to all vertices within a given distance.

With the first graph the run time is :

ncalls tottime percall cumtime percall filename:lineno(function) 1 0.035 0.035 0.060 0.060 graph_tool/topology/__init__.py:1272(shortest_distance) 1 0.000 0.000 0.019 0.019 graph_tool/decorators.pyc:1(copy_property) 2/1 0.000 0.000 0.019 0.019 graph_tool/decorators.py:126(wrapper) 1 0.013 0.013 0.019 0.019 graph_tool/__init__.py:2247(copy_property) 10 0.000 0.000 0.011 0.001 graph_tool/__init__.py:146(_prop) 8 0.000 0.000 0.011 0.001 graph_tool/__init__.py:476(_get_any) 8 0.011 0.001 0.011 0.001 graph_tool/__init__.py:893(reserve) 1 0.000 0.000 0.001 0.001 graph_tool/__init__.py:2559(set_edge_filter) 1 0.000 0.000 0.001 0.001 graph_tool/__init__.py:680(__set_array) 1 0.000 0.000 0.000 0.000 graph_tool/__init__.py:643(get_array) 4 0.000 0.000 0.000 0.000 graph_tool/__init__.py:667(_get_data) [truncated]

With the second graph the run is :

ncalls tottime percall cumtime percall filename:lineno(function) 1 2.347 2.347 2.372 2.372 graph_tool/topology/__init__.py:1272(shortest_distance) 1 0.000 0.000 0.019 0.019 graph_tool/decorators.pyc:1(copy_property) 2/1 0.000 0.000 0.019 0.019 graph_tool/decorators.py:126(wrapper) 1 0.012 0.012 0.018 0.018 graph_tool/__init__.py:2247(copy_property) 9 0.000 0.000 0.011 0.001 graph_tool/__init__.py:146(_prop) 5 0.000 0.000 0.011 0.002 graph_tool/__init__.py:476(_get_any) 5 0.011 0.002 0.011 0.002 graph_tool/__init__.py:893(reserve) 1 0.001 0.001 0.001 0.001 graph_tool/__init__.py:975(_check_prop_scalar) [truncated]

How could we explain this difference? I there a something to do to reduce the run time observed with the second graph ?

This is indeed quite unexpected. Could you please provide a test graph together with the script you sent, so I can investigate? I think one would need to to a profiling at the C++ level (using perf) to see what is going on. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>