Opened 9 years ago
Closed 9 years ago
#12616 closed defect (fixed)
The LP are not deallocated because of cyclic references !
Reported by: | ncohen | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | linear programming | Keywords: | |
Cc: | jason, john_perry | Merged in: | sage-5.0.beta8 |
Authors: | Nathann Cohen | Reviewers: | Simon King |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11606 | Stopgaps: |
Description (last modified by )
Helloooooooooo !!!!
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 :
http://ask.sagemath.org/question/1170/memory-blowup-with-milp http://ask.sagemath.org/question/1191/memory-blowup-2 http://groups.google.com/forum/#!topic/sage-devel/4jJbIC5TqVs/discussion
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 :-D
Nathann
APPLY:
Attachments (2)
Change History (22)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
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 ^^;
Nathann
comment:4 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Add doctest
Hi Nathann,
it seems to me that your solution is the cleanest (if a reference is not needed, then avoid it).
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 __del__
method, then Python is not sure where in the cycle the collection should start.
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 __del__
methods.
__dealloc__
(in Cython) is fine, though; but it would only be called after all Python attributes of the object are gone.
Concerning your patch: Any bug fix ought to be doc tested.
So, could you add a test that demonstrates that the leak is fixed? This could be along the following lines:
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
Of course, it should then also be checked that the last line does not return 0 without your patch.
comment:5 Changed 9 years ago by
- Status changed from needs_work to needs_review
Helloooooooo !!!
Thank you for this doctest ! Here is an updated patch which contains it. On an unpatched Sage it produces
********************************************************************** 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
And once the patch is applied :
sage -t "devel/sage-0/sage/numerical/mip.pyx" [1.6 s] ---------------------------------------------------------------------- All tests passed!
Nathann
Changed 9 years ago by
comment:6 Changed 9 years ago by
Hi Nathann,
is it really safe to do
sage: just_create_variables() sage: len([x for x in gc.get_objects() if isinstance(x,C)])
without a garbage collection between the two lines?
Of course, the variables created inside just_create_variables
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.
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
sage: _ = gc.collect()
between the two lines, just to be on the safe side.
comment:7 follow-up: ↓ 8 Changed 9 years ago by
Hellooooooo !!!!
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 MixedIntegerLinearProgram? 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.
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 ?
Nathann
comment:8 in reply to: ↑ 7 Changed 9 years ago by
- Work issues Add doctest deleted
Replying to ncohen:
Well, the first reason is that with this line added between the two, the answer is 0 whether the patch is applied or not.
Then there is either no memory leak, or the leaking object is not MixedIntegerLinearProgram
.
Using gc.collect() was actually Volker's first answer to the sage-devel thread which totally solved the problem : the instances of MixedIntegerLinearProgram? are indeed deallocated by the garbage collector when it is *called*, which is not done systematically when the function ends.
That's just the usual behaviour of garbage collection.
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.
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 ?
Hm. Difficult.
When you say "memory leak", I expect something like
sage: for p in prime_range(10^5): ....: K = GF(p) ....: a = K(0) ....:
Here, the line a = K(0)
creates a coercion from ZZ
to K
, and without #715 and #11521 coercion maps together with domain and codomain are cached and will thus stay in memory forever, soon eating up your computer's brain.
But when you say that the garbage collector can successfully collect the MixedIntegerLinearProgram
when explicitly do the collection, then it should be the case that sooner or later it will be collected automatically.
In fact, it is the case:
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
OK, the memory consumption mildly increases, but the instances of the mixed integer linear program are collectable:
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
That is with vanilla sage-4.8 on sage.math. So, I'd say there was no leak!
comment:9 follow-up: ↓ 10 Changed 9 years ago by
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 :-ppp
). Well, this patch still is useful though, what do you advise we should do with it then ? It's still waiting for a review :-)
Nathann
comment:10 in reply to: ↑ 9 Changed 9 years ago by
Replying to ncohen:
Well... Waiting for the garbage collector to do its job seemed to be the cause of the memory blowups reported
Amazing...
Well, this patch still is useful though, ...
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...
comment:11 follow-up: ↓ 12 Changed 9 years ago by
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
If this ticket fixes at least one of them, then it can be turned into a doc test (by the same blahblah with gc.get_objects()
as before).
For instance, does your patch fix the following memory leak (sorry, can't test it myself right now)?
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()
Here, you are just calling g.independent_set()
repeatedly - but apparently some objects won't be garbage collected. That would really be a memory leak.
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 9 years ago by
Hellooooooo !!
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
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 MixedIntegerLinearProgram? objects.
The memory leak that is given in the report actually has two causes :
- the problem this very patch adresses
- a memory leak in the interface with Cliquer that is being fixed in #12622. 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.
Nathann
comment:13 in reply to: ↑ 12 Changed 9 years ago by
Hi Nathann,
Replying to ncohen:
In the ticket description, you mention a few reports on memory leaks. Is the objective of this ticket to fix all of them?
I think I stand corrected in what I said about Python's garbage collector.
If I am not mistaken, the garbage collector is involved only 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:
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
Hence, since your patch destroys one reference cycle, it makes sure that a deleted mixed integer linear program will be immediately removed.
Here is an example in which garbage collection comes in. The slight problem is that if one has a __del__
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:
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
Nothing happens! The __del__
method of c is not called!! Hence, with garbage collection disabled, the reference cycle d1 <--> d2
can not be removed.
Let's do the collection manually:
sage: gc.collect() deleting the object 681
Aha! The reference cycle, and thus the last reference to c, has gone.
The last example shows that we must not have __del__
in the reference cycle:
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
So, c is not deleted and will not be deleted! That would be a memory leak.
What does that mean for your patch?
- 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.
- By now, I think that your example does demonstrate the fix, and that it works stably.
So, let me run doctests, and if they pass, I give it a positive review.
comment:14 follow-up: ↓ 15 Changed 9 years ago by
- Dependencies set to #11606
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.
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.
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.
However, the patch does apply to sage-5.0.beta6, and I found that the white space has been introduced in #11606.
So, I am adding it as a dependency.
comment:15 in reply to: ↑ 14 Changed 9 years ago by
Helloooooooo !!!
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.
Yep, sorry about that ! I am using Sage 5.0-beta6
So, I am adding it as a dependency.
Right ! :-)
Nathann
comment:16 Changed 9 years ago by
Darn. I was in the hope that the patch bot would be able to resolve the dependencies. But apparently #11606 has a dependency (relative to 4.8) as well!
Changed 9 years ago by
comment:17 Changed 9 years ago by
- Reviewers set to Simon King
- Status changed from needs_review to positive_review
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 sometimes the test would pass even without Nathann's patch (namely when garbage collection just happens to happen too early).
If you agree with my reviewer patch, it is a positive review.
comment:18 Changed 9 years ago by
- Description modified (diff)
Wow !! Very nice trick ! I had no idea you could do that... Python is really scary :-D
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 :-)
Nathann
comment:19 Changed 9 years ago by
- Description modified (diff)
comment:20 Changed 9 years ago by
- Merged in set to sage-5.0.beta8
- Resolution set to fixed
- Status changed from positive_review to closed
Why do you import weakref?