[graph-tool] Surprising run time increase

François francois.kawala at gmail.com
Tue Jun 7 11:27:58 CEST 2016


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 ? 

Bests,
F.



--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Surprising-run-time-increase-tp4026590.html
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.



More information about the graph-tool mailing list