# Memory blowup 2

This code in Sage 4.8 (with CPlex installed if that matters) uses a lot of memory. After around 36 million graphs, it is using around 21 Gigs:

for g in graphs.nauty_geng("11"):
ind_set = g.independent_set()

edit retag close merge delete

Sort by » oldest newest most voted

It looks to me like there may be several memory leaks in devel/sage/sage/graphs/cliquer.pyx. Notice, for example:

cdef graph_t *g
g=graph_new(graph.order())


But then we never deallocate the g memory. It looks like cliquer/graph.h also defines a graph_free function, and it looks awfully suspicious that we never call it anywhere in that file after we've done a graph_new. We'd have to add graph_free to the cliquer.pxd file as well.

Edit: Section B of the cliquer manual says to use graph_free to free the graph given by graph_new.

Edit 2: There are more memory leaks. I think the list that is returned from the cliquer function calls should be freed with free, and inside the cliquer package, I think the cliquer options structs should be freed (i.e., any call to sage_init_clique_opt() should be saved as a variable and then freed at the end of the function).

Edit 3: I've moved these findings to http://trac.sagemath.org/sage_trac/ti... and posted up some preliminary patches and diffs there.

more

I guess this code does not eat a lot of memory unless you call independent_set(algorithm = "MILP"). In which case the problem is the same as this bug report, and the discussion is going on at this address.

Nathann

more

I'm confused. It does use a lot of memory even when you don't do algorithm = "MILP". Look at the code above. There is no algorithm = "MILP". Thanks for your help!

( 2012-02-29 02:38:36 -0500 )edit

@Nathann For my purposes, I need to be able to run through all graphs of some order, say 10 or 11 maybe later 12, and I will be finding the size of the largest independent set for every such graph. For now, that is possible with graphs of order 10. It is not possible with graphs of order 11 because it uses too much memory.

( 2012-02-29 02:48:36 -0500 )edit