Sage: Ticket #12616: The LP are not deallocated because of cyclic references !
https://trac.sagemath.org/ticket/12616
<p>
Helloooooooooo !!!!
</p>
<p>
Because of a cyclic reference (the LP pointed toward the LP variables, and the LP variables toward the LP), the LP objects were not immediately deallocated at the end of functions using them. That produced memory problems that have been reported there :
</p>
<p>
<a class="ext-link" href="http://ask.sagemath.org/question/1170/memory-blowup-with-milp"><span class="icon"></span>http://ask.sagemath.org/question/1170/memory-blowup-with-milp</a>
<a class="ext-link" href="http://ask.sagemath.org/question/1191/memory-blowup-2"><span class="icon"></span>http://ask.sagemath.org/question/1191/memory-blowup-2</a>
<a class="ext-link" href="http://groups.google.com/forum/#!topic/sage-devel/4jJbIC5TqVs/discussion"><span class="icon"></span>http://groups.google.com/forum/#!topic/sage-devel/4jJbIC5TqVs/discussion</a>
</p>
<p>
Thanks to the wonderful people one can find among Sage developpers who always have a perfect answer ready for you, here is a patch to fix it. It's actually quite straightforward (one of the two references was not even necessary, nor even used) when you know where it comes from, but without the good hint you can search for a long time <code>:-D</code>
</p>
<p>
Nathann
</p>
<p>
APPLY:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12616/trac_12616.patch" title="Attachment 'trac_12616.patch' in Ticket #12616">trac_12616.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12616/trac_12616.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12616/trac_12616_reviewer.patch" title="Attachment 'trac_12616_reviewer.patch' in Ticket #12616">trac_12616_reviewer.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12616/trac_12616_reviewer.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12616
Trac 1.1.6ncohenFri, 02 Mar 2012 10:01:07 GMTstatus, description changed
https://trac.sagemath.org/ticket/12616#comment:1
https://trac.sagemath.org/ticket/12616#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12616?action=diff&version=1">diff</a>)
</li>
</ul>
TicketjasonFri, 02 Mar 2012 10:02:27 GMT
https://trac.sagemath.org/ticket/12616#comment:2
https://trac.sagemath.org/ticket/12616#comment:2
<p>
Why do you import weakref?
</p>
TicketncohenFri, 02 Mar 2012 10:04:15 GMT
https://trac.sagemath.org/ticket/12616#comment:3
https://trac.sagemath.org/ticket/12616#comment:3
<p>
Because I did some tests with it before, and because I'm an idiot who does not read his patches again before sending them for review. Patch updated, sorry about that <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketSimonKingWed, 07 Mar 2012 14:45:18 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/12616#comment:4
https://trac.sagemath.org/ticket/12616#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Add doctest</em>
</li>
</ul>
<p>
Hi Nathann,
</p>
<p>
it seems to me that your solution is the cleanest (if a reference is not needed, then avoid it).
</p>
<p>
A general remark: Python's garbage collector is able to deal with cyclic references. There is only one exception I know of: If one or more of the objects involved in the cycle has a <code>__del__</code> method, then Python is not sure where in the cycle the collection should start.
</p>
<p>
So, if a reference cycle can not be avoided (e.g., a polynomial ring R=ZZ['x','y'] points to its generators R.0, R.1, but the generators are elements and thus point to their parent R), then one could also solve the problem by not introducing <code>__del__</code> methods.
</p>
<p>
<code>__dealloc__</code> (in Cython) is fine, though; but it would only be called <em>after</em> all Python attributes of the object are gone.
</p>
<p>
Concerning your patch: Any bug fix ought to be doc tested.
</p>
<p>
So, could you add a test that demonstrates that the leak is fixed? This could be along the following lines:
</p>
<pre class="wiki">sage: C = the.class.of.the.object.that.was.leaking
sage: import gc
sage: _ = gc.collect() # avoid side effects of other doc tests
sage: len([x for x in gc.get_objects() if isinstance(x,C)])
0
sage: <some code that would create leaking C instances without your patch>
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,C)])
0
</pre><p>
Of course, it should then also be checked that the last line does not return 0 without your patch.
</p>
TicketncohenWed, 07 Mar 2012 16:09:58 GMTstatus changed
https://trac.sagemath.org/ticket/12616#comment:5
https://trac.sagemath.org/ticket/12616#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Helloooooooo !!!
</p>
<p>
Thank you for this doctest ! Here is an updated patch which contains it. On an unpatched Sage it produces
</p>
<pre class="wiki">**********************************************************************
File "/home/ncohen/.Sage/devel/sage-0/sage/numerical/mip.pyx", line 221:
sage: len([x for x in gc.get_objects() if isinstance(x,C)])
Expected:
0
Got:
1
**********************************************************************
1 items had failures:
1 of 12 in __main__.example_2
</pre><p>
And once the patch is applied :
</p>
<pre class="wiki">sage -t "devel/sage-0/sage/numerical/mip.pyx"
[1.6 s]
----------------------------------------------------------------------
All tests passed!
</pre><p>
Nathann
</p>
TicketncohenWed, 07 Mar 2012 16:10:40 GMTattachment set
https://trac.sagemath.org/ticket/12616
https://trac.sagemath.org/ticket/12616
<ul>
<li><strong>attachment</strong>
set to <em>trac_12616.patch</em>
</li>
</ul>
TicketSimonKingWed, 07 Mar 2012 16:47:52 GMT
https://trac.sagemath.org/ticket/12616#comment:6
https://trac.sagemath.org/ticket/12616#comment:6
<p>
Hi Nathann,
</p>
<p>
is it really safe to do
</p>
<pre class="wiki">sage: just_create_variables()
sage: len([x for x in gc.get_objects() if isinstance(x,C)])
</pre><p>
without a garbage collection between the two lines?
</p>
<p>
Of course, the variables created inside <code>just_create_variables</code> are deleted when it is done. However, there is no guarantee that a deleted object is immediately garbage collected. In general, garbage collection can happen between any two Python calls -- sooner or later.
</p>
<p>
Hence, it could be that the doc test example runs into a racing condition, and it could happen that the test randomly fails when Python decides that it is not in the mood for an immediate garbage collection. I suggest to insert
</p>
<pre class="wiki">sage: _ = gc.collect()
</pre><p>
between the two lines, just to be on the safe side.
</p>
TicketncohenWed, 07 Mar 2012 16:52:52 GMT
https://trac.sagemath.org/ticket/12616#comment:7
https://trac.sagemath.org/ticket/12616#comment:7
<p>
Hellooooooo !!!!
</p>
<p>
Well, the first reason is that with this line added between the two, the answer is 0 whether the patch is applied or not. Using gc.collect() was actually Volker's first answer to the sage-devel thread which totally solved the problem : the instances of <a class="missing wiki">MixedIntegerLinearProgram?</a> are indeed deallocated by the garbage collector when it is *called*, which is not done systematically when the function ends. Robert Bradshaw and William then said that if there was no cyclic dependency the work would be done without the garbage collector's help at the end of the function, which is actually the case.
</p>
<p>
Hence, in this situation, the doctest fails when the patch is not applied, and according to their answers (and experience until now) has no reason to fail when the patch is applied. What do you advise ?
</p>
<p>
Nathann
</p>
TicketSimonKingWed, 07 Mar 2012 18:50:46 GMTwork_issues deleted
https://trac.sagemath.org/ticket/12616#comment:8
https://trac.sagemath.org/ticket/12616#comment:8
<ul>
<li><strong>work_issues</strong>
<em>Add doctest</em> deleted
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12616#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Well, the first reason is that with this line added between the two, the answer is 0 whether the patch is applied or not.
</p>
</blockquote>
<p>
Then there is either no memory leak, or the leaking object is not <code>MixedIntegerLinearProgram</code>.
</p>
<blockquote class="citation">
<p>
Using gc.collect() was actually Volker's first answer to the sage-devel thread which totally solved the problem : the instances of <a class="missing wiki">MixedIntegerLinearProgram?</a> are indeed deallocated by the garbage collector when it is *called*, which is not done systematically when the function ends.
</p>
</blockquote>
<p>
That's just the usual behaviour of garbage collection.
</p>
<blockquote class="citation">
<p>
Robert Bradshaw and William then said that if there was no cyclic dependency the work would be done without the garbage collector's help at the end of the function, which is actually the case.
</p>
<p>
Hence, in this situation, the doctest fails when the patch is not applied, and according to their answers (and experience until now) has no reason to fail when the patch is applied. What do you advise ?
</p>
</blockquote>
<p>
Hm. Difficult.
</p>
<p>
When you say "memory leak", I expect something like
</p>
<pre class="wiki">sage: for p in prime_range(10^5):
....: K = GF(p)
....: a = K(0)
....:
</pre><p>
Here, the line <code>a = K(0)</code> creates a coercion from <code>ZZ</code> to <code>K</code>, and without <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11521" title="defect: Use weak references to cache homsets (closed: fixed)">#11521</a> coercion maps <em>together with domain and codomain</em> are cached and will thus stay in memory forever, soon eating up your computer's brain.
</p>
<p>
But when you say that the garbage collector can successfully collect the <code>MixedIntegerLinearProgram</code> when explicitly do the collection, then it should be the case that sooner or later it will be collected automatically.
</p>
<p>
In fact, it is the case:
</p>
<pre class="wiki">sage: def just_create_variables():
....: for n in range(1000):
....: p = MixedIntegerLinearProgram()
....: b = p.new_variable()
....: p.add_constraint(b[3]+b[6] <= n)
....: p.solve()
....: print n,get_memory_usage()
....:
sage: just_create_variables()
0 842.51171875
1 842.671875
2 842.671875
3 842.671875
4 842.671875
5 842.8359375
6 842.8359375
...
993 846.75
994 846.75
995 846.75
996 846.75
997 846.75
998 846.75
999 846.75
</pre><p>
OK, the memory consumption mildly increases, but the instances of the mixed integer linear program are collectable:
</p>
<pre class="wiki">sage: len([x for x in gc.get_objects() if isinstance(x,MixedIntegerLinearProgram)])
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
/home/SimonKing/<ipython console> in <module>()
NameError: name 'gc' is not defined
sage: import gc # Oops...
sage: len([x for x in gc.get_objects() if isinstance(x,MixedIntegerLinearProgram)])
8 # only 8, even though 1000 were created!!
sage: gc.collect()
100
sage: len([x for x in gc.get_objects() if isinstance(x,MixedIntegerLinearProgram)])
0
</pre><p>
That is with vanilla sage-4.8 on sage.math. So, I'd say there was no leak!
</p>
TicketncohenWed, 07 Mar 2012 18:55:23 GMT
https://trac.sagemath.org/ticket/12616#comment:9
https://trac.sagemath.org/ticket/12616#comment:9
<p>
Well... Waiting for the garbage collector to do its job seemed to be the cause of the memory blowups reported (though it looks like they have been updated since and that this patch does not fix it <code>:-ppp</code>). Well, this patch still is useful though, what do you advise we should do with it then ? It's still waiting for a review <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketSimonKingWed, 07 Mar 2012 21:51:36 GMT
https://trac.sagemath.org/ticket/12616#comment:10
https://trac.sagemath.org/ticket/12616#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12616#comment:9" title="Comment 9">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Well... Waiting for the garbage collector to do its job seemed to be the cause of the memory blowups reported
</p>
</blockquote>
<p>
Amazing...
</p>
<blockquote class="citation">
<blockquote>
<p>
Well, this patch still is useful though, ...
</p>
</blockquote>
</blockquote>
<p>
Agreed. Avoiding a redundant reference is a good thing - but I can not be sure whether it is really not needed and will not be needed in future. And difficult to test...
</p>
TicketSimonKingThu, 08 Mar 2012 08:36:55 GMT
https://trac.sagemath.org/ticket/12616#comment:11
https://trac.sagemath.org/ticket/12616#comment:11
<p>
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
</p>
<p>
If this ticket fixes at least one of them, then it can be turned into a doc test (by the same blahblah with <code>gc.get_objects()</code> as before).
</p>
<p>
For instance, does your patch fix the following memory leak (sorry, can't test it myself right now)?
</p>
<pre class="wiki">g = graphs.PetersenGraph()
for count in [1..100000]:
if count % 5000 == 0:
print count
print get_memory_usage()
gc.collect()
print get_memory_usage()
test = g.independent_set()
</pre><p>
Here, you are just calling <code>g.independent_set()</code> repeatedly - but apparently some objects won't be garbage collected. That would really be a memory leak.
</p>
TicketncohenThu, 08 Mar 2012 17:05:57 GMT
https://trac.sagemath.org/ticket/12616#comment:12
https://trac.sagemath.org/ticket/12616#comment:12
<p>
Hellooooooo !!
</p>
<blockquote class="citation">
<p>
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
</p>
</blockquote>
<p>
Well, the objective of this ticket was to fix this memory leak as *when I created the ticket* I believed the memory leak came from non-deallocated <a class="missing wiki">MixedIntegerLinearProgram?</a> objects.
</p>
<p>
The memory leak that is given in the report actually has two causes :
</p>
<ul><li>the problem this very patch adresses
</li><li>a memory leak in the interface with Cliquer that is being fixed in <a class="closed ticket" href="https://trac.sagemath.org/ticket/12622" title="defect: cliquer memory leaks (closed: duplicate)">#12622</a>. By the way, I wrote to Jason about that and it looks like the patch will actually be a total rewriting of Cliquer's interface with Sage.
</li></ul><p>
Nathann
</p>
TicketSimonKingFri, 09 Mar 2012 09:27:33 GMT
https://trac.sagemath.org/ticket/12616#comment:13
https://trac.sagemath.org/ticket/12616#comment:13
<p>
Hi Nathann,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12616#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
</p>
</blockquote>
</blockquote>
<p>
I think I stand corrected in what I said about Python's garbage collector.
</p>
<p>
If I am not mistaken, the garbage collector is involved <em>only</em> if there are reference cycles. Hence, if an object deleted and is not contained in a reference cycle, it will be immediately removed, even if garbage collection is switched off:
</p>
<pre class="wiki">sage: class C:
....: def __del__(self):
....: print "deleting the object"
....:
sage: class D:
....: pass
....:
sage: c = C()
sage: import gc
sage: gc.disable()
sage: del c
deleting the object
</pre><p>
Hence, since your patch destroys one reference cycle, it makes sure that a deleted mixed integer linear program will be immediately removed.
</p>
<p>
Here is an example in which garbage collection comes in. The slight problem is that if one has a <code>__del__</code> method in the cycle, then the garbage collector does not know what to do. Hence, in my example, I am creating a cycle of instances of D, with a pointer to an instance of C, such that one sees when things are deleted:
</p>
<pre class="wiki">sage: d1 = D()
sage: d2 = D()
sage: d1.d = d2
sage: d2.d = d1
sage: c = C()
sage: d1.c = c
sage: del d1
sage: del c
sage: del d2
</pre><p>
Nothing happens! The <code>__del__</code> method of c is not called!! Hence, with garbage collection disabled, the reference cycle <code>d1 <--> d2</code> can not be removed.
</p>
<p>
Let's do the collection manually:
</p>
<pre class="wiki">sage: gc.collect()
deleting the object
681
</pre><p>
Aha! The reference cycle, and thus the last reference to c, has gone.
</p>
<p>
The last example shows that we must not have <code>__del__</code> in the reference cycle:
</p>
<pre class="wiki">sage: d = D()
sage: c = C()
sage: d.c = c
sage: c.d = d
sage: del c
sage: del d
sage: gc.collect()
4
sage: len([x for x in gc.get_objects() if isinstance(x,C)])
1
</pre><p>
So, c is not deleted and will not be deleted! That would be a memory leak.
</p>
<p>
What does that mean for your patch?
</p>
<ul><li>I still believe it is a good idea to avoid reference cycles, when possible. However, I don't think that your patch fixes an actual leak.
</li><li>By now, I think that your example <em>does</em> demonstrate the fix, and that it works stably.
</li></ul><p>
So, let me run doctests, and if they pass, I give it a positive review.
</p>
TicketSimonKingFri, 09 Mar 2012 10:01:41 GMTdependencies set
https://trac.sagemath.org/ticket/12616#comment:14
https://trac.sagemath.org/ticket/12616#comment:14
<ul>
<li><strong>dependencies</strong>
set to <em>#11606</em>
</li>
</ul>
<p>
Sorry, but the patch does not apply to sage-5.0.prealpha0, and that's the latest version that I have on my laptop. The three mismatches happen in sage/numerical/mip.pyx.
</p>
<p>
Actually, that was the first thing I thought when I read your patch: It not only changes code but also changes a lot of white space - which makes it very likely that mismatches happen, and they did happen.
</p>
<p>
For example, your patch tries to replace a line formed by 8 white spaces with an empty line (namely in line 214 of mip.pyx). These 8 white spaces are not present in sage-5.0.prealpha0.
</p>
<p>
However, the patch does apply to sage-5.0.beta6, and I found that the white space has been introduced in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11606" title="enhancement: simplify constraints in linear programs (closed: fixed)">#11606</a>.
</p>
<p>
So, I am adding it as a dependency.
</p>
TicketncohenFri, 09 Mar 2012 10:14:17 GMT
https://trac.sagemath.org/ticket/12616#comment:15
https://trac.sagemath.org/ticket/12616#comment:15
<p>
Helloooooooo !!!
</p>
<blockquote class="citation">
<p>
Sorry, but the patch does not apply to sage-5.0.prealpha0, and that's the latest version that I have on my laptop. The three mismatches happen in sage/numerical/mip.pyx.
</p>
</blockquote>
<p>
Yep, sorry about that ! I am using Sage 5.0-beta6
</p>
<blockquote class="citation">
<p>
So, I am adding it as a dependency.
</p>
</blockquote>
<p>
Right ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketSimonKingFri, 09 Mar 2012 12:15:04 GMT
https://trac.sagemath.org/ticket/12616#comment:16
https://trac.sagemath.org/ticket/12616#comment:16
<p>
Darn. I was in the hope that the patch bot would be able to resolve the dependencies. But apparently <a class="closed ticket" href="https://trac.sagemath.org/ticket/11606" title="enhancement: simplify constraints in linear programs (closed: fixed)">#11606</a> has a dependency (relative to 4.8) as well!
</p>
TicketSimonKingFri, 09 Mar 2012 12:19:33 GMTattachment set
https://trac.sagemath.org/ticket/12616
https://trac.sagemath.org/ticket/12616
<ul>
<li><strong>attachment</strong>
set to <em>trac_12616_reviewer.patch</em>
</li>
</ul>
TicketSimonKingFri, 09 Mar 2012 12:23:09 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/12616#comment:17
https://trac.sagemath.org/ticket/12616#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
I added a reviewer patch that (I think) makes the additional doc test a bit clearer. Namely, state that the patch is not about "collect or not collect", but about "collect without relying on the cyclic garbage collector". Moreover, I explicitly disable cyclic garbage collection for the test. Otherwise, it could theoretically happen that <em>sometimes</em> the test would pass even without Nathann's patch (namely when garbage collection just happens to happen too early).
</p>
<p>
If you agree with my reviewer patch, it is a positive review.
</p>
TicketncohenFri, 09 Mar 2012 12:30:43 GMTdescription changed
https://trac.sagemath.org/ticket/12616#comment:18
https://trac.sagemath.org/ticket/12616#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12616?action=diff&version=18">diff</a>)
</li>
</ul>
<p>
Wow !! Very nice trick ! I had no idea you could do that... Python is really scary <code>:-D</code>
</p>
<p>
I just applied this patch and tested it without any problem, so I guess it is good to go. Thank you very much for your help ! I'm relieved to know this doctest would warn me if I make the same mistake again <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerSat, 10 Mar 2012 09:37:39 GMTdescription changed
https://trac.sagemath.org/ticket/12616#comment:19
https://trac.sagemath.org/ticket/12616#comment:19
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12616?action=diff&version=19">diff</a>)
</li>
</ul>
TicketjdemeyerTue, 13 Mar 2012 08:24:52 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/12616#comment:20
https://trac.sagemath.org/ticket/12616#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta8</em>
</li>
</ul>
Ticket