shortest_path much slower in 1.0.1 than 0.7.1 for multiple destination routing

[byrney]

Firstly apologies, I'm new to R and my first task was to upgrade the libraries used by a routing algorithm. After the upgrade, performance was terrible. I narrowed it down to the change from igraph 7.0.1 to igraph 1.0.1.

I cannot provide the actual code or data but I have an example which I believe exhibits the same behaviour here:

https://gist.github.com/byrney/dcff47249d377014adf7951f2768c883#file-shortestpathbenchmark-r

when executed with igraph 0.7.1 this scales fairly well as the number of to-nodes is increased

for(i in c(1, 10, 25, 50, 100)){ print(system.time(x <- do_work(300, i, 50)))}
 user  system elapsed 
 0.03    0.02    0.08 
 0.03    0.02    0.05 
 0.04    0.00    0.06 
 0.03    0.00    0.05 
 0.05    0.02    0.06 

but in 1.0.1 it drops off very quickly as the number of destinations is increased

for(i in c(1,10,25,50, 100)){ print(system.time(x <- do_work(300, i, 50)))}
 user  system elapsed 
 0.09    0.02    0.24 
 0.66    0.14    1.34 
 1.36    0.59    2.85 
 3.27    1.02    6.28 
 5.94    1.98    8.70 

I tried varying a few parameters but nothing I did made much difference. We have to calculate 1000's of destinations for each starting point so the difference between 0.7.1 and 1.0.1 is significant in the real application and calling shortest_path for each destination is also very slow.

Code and results (including package descriptions) in this gist: https://gist.github.com/byrney/dcff47249d377014adf7951f2768c883

Thanks,

Rob

[gaborcsardi]

Please profile your code, to see what is slow. The profvis package is pretty good for this.

[byrney]

Thanks for the suggestion @gaborcsardi. I profiled the EXAMPLE code (referenced above). Since it just calls get.shortest.path in a loop ~100% of the time is spent in that function.

Drilling down for igraph 1, I can see that simple_es_index is the main time consumer and something called E below that.

Attached is a screenshot of the profile output for rigraph 1.

The trace for 0.7 has less details, ending in a Call, which I assume is where it transitions to native code.

The full output for both 0.7 and 1.0 are attached.

This doesn't tell me much more than I knew before -- the example with 1.0 becomes slow much sooner than 0.7 as the number of destinations increases. Perhaps you have some insights?

Archive.zip

[gaborcsardi]

In igraph 1.0.1 functions return vertex/edge sequence objects, and creating these does have a significant overhead. You can turn this behavior off:

igraph_options(return.vs.es = FALSE)