[graph-tool] Surprising run time increase

[Tiago de Paula Peixoto]

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 at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20160607/331d0892/attachment.asc>