Memory leak when using shortest_paths

[matt-wirtz]

Hello,

there is a memory leak when using shortest_paths algorithm.

library(igraph)
iterations <- 1000
g <-  make_tree(n = 5000, children = 3, mode = "out")

for (i in 1:length(V(g))) { V(g)[i]$name <- ifelse(i %% 10 == 0, "home", "away")}
for (i in 1:length(E(g))) { E(g)[i]$weight <- as.integer(runif(1, 1, 10)) }

print(sum(gc()[,4]))
for (i in 1:iterations) { 
  if (i %% 100 == 0) print(sum(gc()[,4]))
  sp <- shortest_paths(g, from = 3, to = V(g)[name == "home"], 
                   mode="out", output="vpath", weights = E(g)$weight) 
  }

The memory used by the R session is displayed after every 100 calls to shortest_paths. It increases more or less steadily. When using smaller graphs it takes more iterations to make the increase obvious. I tested it on ArchLinux and Windows using igraph 1.1.2.

I came across this issue in a lager simulation and there I ended up with an R session using 3GB while all objects within the R session just needed 5MB. After drilling down I found out that the calls to shortest_paths caused the memory leaks.

[szhorvat]

Output in the dev version (1.3):

[1] 312.2
[1] 312.2
[1] 328.3
[1] 328.3
[1] 328.4
[1] 347.7
[1] 347.7
[1] 347.7
[1] 422.1
[1] 422.1

There are also a very large number of warnings. I wonder if it has to do with these.

[ntamas]

Interestingly enough, the leak is not there if I set igraph_options(return.vs.es=FALSE) - which means that the leak is not in the shortest path routine where I initially suspected it to be, but in create_vs().

[ntamas]

An even simpler way to trigger the issue (no graphs involved):

library(igraph)

iterations <- 500000

print(sum(gc()[,4]))
env <- new.env()
for (i in 1:iterations) {
  if (i %% 50000 == 0) {
    print(sum(gc()[,4]))
  }
  igraph:::make_weak_ref(env, NULL)
}

print("Calling GC after loop")
sum(gc()[,4])

print("Removing env from workspace")
rm(env)

print("Calling GC after removal")
sum(gc()[,4])

print("Exiting after last GC")

I'm just starting to understand weakrefs in R; it looks like igraph:::make_weak_ref(env, ...) (which is an R wrapper for the low-level R_MakeWeakRef function) returns an object that somehow remains alive even if I don't store it anywhere, and its memory is reclaimed only when env goes out of scope (or after calling rm(env)). The consequence is that calling V(g) many times in a loop allocates lots of these objects, and these are reclaimed only when g is destroyed. That's why we see an increasing memory consumption in the example above. I don't know whether this is by design or not; I need to investigate this more.

[ntamas]

Note to self: each igraph object contains a hidden environment that is used to record mutable meta-information about the graph without changing its identity. igraph vertex sequence objects (i.e. ones created with V(g)) contain a weak reference that points back to the environment object hidden in its parent graph. In turn, this environment object contains a key named me, which points back to the graph itself. This is how the vertex sequence object can get hold of the graph it refers to (it follows the weakref, and fetches the me key from the environment it points to). The idea is that when the underlying graph is removed from the workspace, its environment loses its last strong reference, which in turn invalidates the weak reference in the vertex sequence so the vertex sequence becomes "orphaned" automatically.

This seems to be the only place where weakrefs are used in the code, and this is the cause of the increase in memory usage. When V(g) is invoked, a new weakref is created, and this weakref is somehow not collected by the garbage collector when V(g) is discarded. The memory held by the weakref is released only when the key of the weakref is invalidated by the GC, even if no one needs the weakref any more.

Replacing the weakref with a strong reference resolves the leak, but this is only a workaround, not a solution for the underlying problem.

---

Update: the weakref behaviour seems to be documented.

A WeakRef object with a reachable key will not be garbage collected even if the WeakRef object is not itself reachable.

[ntamas]

Retargeting this to a later milestone as it's unlikely that we can sort this out before the release of 1.3.0 -- it would require us to find a replacement for the current weakref trickery, and this does not seem trivial.

[cdueben]

Is there any way for the user to fix this? My 1 TB RAM machine ran out of memory after a few loop iterations.

[szhorvat]

A potential workaround is mentioned in #288 (comment)

[cdueben]

Thanks. Though, after playing around with that suggestion for a few days, I have to report that it does not work (anymore). Maybe it used to work with previous versions of R, igraph, or its dependencies, but now the problem also occurs with igraph_options(return.vs.es = FALSE). Do you have any other recommendation?

[szhorvat]

Can you show a complete minimal example that reproduces the issue? Maybe what you observe is not even the same problem. Run the example in a clean session and include the output of sessionInfo().