get.adjlist very very slow, and potential fix

[cfhammill]

For large graphs get.adjlist is very slow, for a graph with 125000 vertices, and 735000 edges

system.time(adj1 <- igraph::get.adjlist(graph, "out"))
   user  system elapsed 
665.323   1.508 667.865 

The C-code to extract the neighbours isn't the culprit

system.time(.Call("R_igraph_get_adjlist", graph, 1, package = "igraph"))
   user  system elapsed 
  0.011   0.000   0.012 

The slowness can be traced to:

res <- lapply(res, function(x) V(graph)[x + 1])

I suspect the proper vertex list indexing is overkill here and causing an extreme slowdown. Since the return-type from c-code should be guaranteed to be a list of integer vectors, and the doc promises to return a list of integer vectors could we get away with:

vvec <- unclass(V(graph))
res <- lapply(res, function(x) vvec[x + 1])

Or potentially even:

res <- lapply(res, `+`, 1)

Benchmarks:

system.time(na1 <- new_adj_list1(graph, mode = "out"))
   user  system elapsed 
  0.187   0.000   0.188

system.time(na2 <- new_adj_list2(graph, mode = "out"))
   user  system elapsed 
  0.069   0.000   0.069

all.equal(na1, na2)
[1] TRUE

all.equal(lapply(adj1, function(x) as.numeric(unclass(x)))
        , na1)
[1] TRUE

[gaborcsardi]

Thanks! Would you like to submit a pull request?

[cfhammill]

Sure thing. Do you prefer the first or second version, the second has a precedent in ego

rigraph/R/structural.properties.R

Line 1702 in 665d71e

res <- lapply(res, function(x) x+1)

[gaborcsardi]

Second is good. But we should probably add a class. G On 25 May 2017 07:12, "Chris Hammill" <notifications@github.com> wrote: Sure thing. Do you prefer the first or second version, the second has a precedent in ego https://github.com/igraph/rigr aph/blob/665d71ebd40cdfe9b996a4f50c35d65b791e4102/R/ structural.properties.R#L1702 — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#194 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAoTQF4WXYdStIKcApCNCw8Wh-jwtyV5ks5r9Yw5gaJpZM4Nc1In> .

[cfhammill]

Hmm, looking at the ego example, it seems like this problem was found before. The c code returns a 0-indexed integer vector list, increments by one, and then checks igraph_opt("return.vs.es"), if it's true, the integer vectors are cast as vertex lists with create_vs .

Setting that option to TRUE, ego on one of my example graphs takes 450s, set to FALSE it takes 61ms. For now I think I will use that same solution in as_adj_list, but I wonder how to make that option obvious so that people who run into this will know how to correct it. I could add it to the docs, but if others are like me, they might not see it there. Could it be added as an argument, defaulting to the option?

[ntamas]

I think this is now basically fixed as we use the new unsafe_create_vs() function in as_adj_list, which now constructs V(graph) only once instead of once for every row of the adjacency list.