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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
