Ask Your Question
0

Memory blowup 2

asked 2012-02-27 17:38:14 +0100

G-Sage gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2012-03-03 03:38:07 +0100

Jason Grout gravatar image

updated 2012-03-03 04:29:55 +0100

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.

edit flag offensive delete link more
0

answered 2012-02-29 09:33:21 +0100

Nathann gravatar image

updated 2012-02-29 09:34:57 +0100

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

edit flag offensive delete link more

Comments

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!

G-Sage gravatar imageG-Sage ( 2012-02-29 09:38:36 +0100 )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.

G-Sage gravatar imageG-Sage ( 2012-02-29 09:48:36 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-02-27 17:38:14 +0100

Seen: 541 times

Last updated: Mar 03 '12