Opened 7 years ago

Closed 7 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 jdemeyer)

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)

trac_12616.patch (7.0 KB) - added by ncohen 7 years ago.
trac_12616_reviewer.patch (1.3 KB) - added by SimonKing 7 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by jason

Why do you import weakref?

comment:3 Changed 7 years ago by ncohen

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 7 years ago by SimonKing

  • 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 7 years ago by ncohen

  • 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 7 years ago by ncohen

comment:6 Changed 7 years ago by SimonKing

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: Changed 7 years ago by ncohen

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 7 years ago by SimonKing

  • 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: Changed 7 years ago by ncohen

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 7 years ago by SimonKing

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: Changed 7 years ago by SimonKing

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: Changed 7 years ago by ncohen

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 7 years ago by SimonKing

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: Changed 7 years ago by SimonKing

  • 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 7 years ago by ncohen

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 7 years ago by SimonKing

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 7 years ago by SimonKing

comment:17 Changed 7 years ago by SimonKing

  • 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 7 years ago by ncohen

  • 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 7 years ago by jdemeyer

  • Description modified (diff)

comment:20 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.