Opened 9 years ago

Last modified 8 years ago

#11521 closed defect

Memleak when resolving the action of Integers on an Elliptic Curve — at Version 53

Reported by: jpflori Owned by: robertwb
Priority: major Milestone: sage-5.5
Component: coercion Keywords: sd35
Cc: jpflori, nthiery Merged in:
Authors: Simon King Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11900 #715 Stopgaps:

Description (last modified by SimonKing)

The following piece of code leaks memory.

sage: K = GF(1<<55,'t')
sage: a = K.random_element()
sage: while 1:
....:     E = EllipticCurve(j=a); P = E.random_point(); 2*P;

The problem seems to occur while resolving the action of ZZ on E.

It does not happen if:

  • one does not change the curve in the loop
  • does P+P instead of a multiplication

Apply

trac11521_triple_homset.patch

Change History (54)

comment:1 Changed 9 years ago by jpflori

After looking at #10548, I might have a better idea of the culprit:

sage: import gc
sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field
sage: K = GF(1<<60,'t')
sage: j = K.random_element()
sage: for i in xrange(100):
....:     E = EllipticCurve(j=j); P = E.random_point(); 2*P;
....:     
sage: gc.collect()
440
sage: len([x for x in gc.get_objects() if  isinstance(x,EllipticCurve_finite_field)])
100

comment:2 Changed 9 years ago by jpflori

  • Component changed from memleak to coercion
  • Owner changed from rlm to robertwb

So this could be just #715 .

comment:3 Changed 9 years ago by jpflori

This is definitely #715.

Resetting the coercion cache and calling gc.collect() deletes the cached elements.

I guess weak refs should be used in the different TripleDict? objects of !CoercionModel_cache_maps.

So this should be closed as duplicate/won't fix.

comment:4 Changed 9 years ago by jpflori

  • Status changed from new to needs_review

comment:5 Changed 9 years ago by zimmerma

Jean-Pierre, why did you change the status to "needs review"? There is no patch to review.

Also, how to you reset the coercion cache? I would be interested if you have a workaround for the memory leak in:

for p in prime_range(10^8):
   k = GF(p)

Paul

comment:6 follow-up: Changed 9 years ago by jpflori

As far as I'm concerned, this is nothing but a concrete example of the vague #715. So I guess I put it to "needs review" so that it could be closed as "duplicate/won't fix". Not sure it was the right way to do it.

I seem to remember that I had some workarounds to delete some parts of the cache (so that I could perform my computations), but not all of them. In fact there are several dictionnaries hidden in different places. It was quite a while ago, but I'll have another look at it at some point. Anyway, using weak references for all these dictionnaries seems to be a quite non trivial task. Moreover it should also not slow things down too much to be viable...

comment:7 Changed 9 years ago by zimmerma

for the computations I need to perform, which need to create about 200000 prime fields, this memory leak makes it impossible to perform it with Sage, which eats all the available memory.

I would be satisfied if I had a magic command to type to explicitly free the memory used by every k=GF(p).

Paul

comment:8 follow-up: Changed 9 years ago by jpflori

I'm having a look at your problem right now. Here are some hints to study the problem, mostly stolen from #10548.

I put it here for the record, and so that i can go faster next time.

First, if I only create the finite fields and do nothing with them, I do not seem to get a memleak. Some fields are not garbage collected immediately, but calling gc.collect() does the trick.

sage: import gc
sage: for p in prime_range(10**5):
....:    k = GF(p)
....:
sage: del p, k
sage: gc.collect()
1265
sage: from sage.rings.finite_rings.finite_field_prime_modn import FiniteField_prime_modn as FF
sage: L = [x for x in gc.get_objects() if isinstance(x, FF)]
sage: len(L)
1
sage: L
[Finite Field of size 2]

Of course I guess you actually do something with your finite fields.

So here is a small example causing the fields to stay cached.

sage: import gc
sage: for p in prime_range(10**5):
....:    k = GF(p)
....:
sage: del p, k
sage: gc.collect()
0

The zero here is bad and indeed

sage: from sage.rings.finite_rings.finite_field_prime_modn import FiniteField_prime_modn as FF
sage: L = [x for x in gc.get_objects() if isinstance(x, FF)]
sage: len(L)
9592 

If you want to know where it comes from you can use the objgraph python module (on my debian I just installed the python-objgraph package, updated sys.path in Sage to include '/usr/lib/python2.6/dist-packages')

sage: sys.path.append('/usr/lib/python2.6/dist-packages')
sage: import inspect, objgraph
sage: objgraph.show_backrefs(L[-1],filename='/home/jp/br.png',extra_ignore=[id(L)])

And look at the png or use

sage: brc = objgraph.find_backref_chain(L[-1],inspect.ismodule,max_depth=15,extra_ignore=[id(L)])
sage: map(type,brc)
[<type 'module'>, <type 'dict'>, <type 'dict'>,...
sage: brc[0]
<module 'sage.categories.homset'...

So the culprit is "_cache" in sage.categories.homset which has a direct reference to the finite fields in its keys.

The clean solution woul be to used weakref in the keys (let's say something as WeakKeyDirectory? in python).

However, resetting cache should be a (potentially partial) workaround (and could kill your Sage?).

sage: sage.categories.homset.cache = {}
sage: gc.collect()
376595

It also seems to be enough if I do "a = k.random_element(); a = a+a" in the for loop, but not if I add "a = 47*a+3".

I'm currently investigating that last case.

comment:9 Changed 9 years ago by jpflori

For info, using "k(47)*a+k(3)" is solved,  so the problem left really comes from coercion and action of integers.

sage: cm = sage.structure. get_coercion_model()
sage: cm.reset_cache()

does not help.

comment:10 Changed 9 years ago by jpflori

First, the second example above is missing the line "k(1);" in the for loop, otherwise it does nothing more than the first example.

Second, I guess the remaining references to the finite fields are in the different lists and dictionnaries of the integer ring named _coerce_from_list, _convert_from_list etc.

You can not directly access them from Python level, but there a function _introspect_coerce() (defined in parent.pyx) which returns them.

comment:11 Changed 9 years ago by jpflori

In fact, everything is in _*_hash.

And to conclude, I'd say that right now you can not directly delete entries in this dictionaries from the Python level.

So for minimum changes, you should eitheir avoid coercion, or make the dictionaries "cdef public" in parent.pxd to be able to explicitely delete every created entries (be aware that it could be written in different places for example in ZZ but also in QQ and CC and I don't know where...).

And I could also have missed other dictionaries used by Sage.

comment:12 Changed 9 years ago by zimmerma

Jean-Pierre, I cannot reproduce that:

sage: sys.path.append('/usr/lib/python2.6/dist-packages')
sage: import inspect, objgraph
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)

/users/caramel/zimmerma/Adm/Strass/SED/2011/<ipython console> in <module>()

ImportError: No module named objgraph

Paul

comment:13 Changed 9 years ago by jpflori

Did you "apt-get install python-objgraph" on your system?

If yes, is it a version for python 2.6 ?

comment:14 Changed 9 years ago by jpflori

The path I gave above might also be different on your system...

As the package manager.

comment:15 follow-up: Changed 9 years ago by jpflori

Any progress on your side?

If you found any other dicitonaries leading to cahing problems, it would be great to mention them here for the record.

Hence the day someone will finally decide to tackle ticket #715, it will speed up the search of the culprit.

comment:16 in reply to: ↑ 15 Changed 9 years ago by zimmerma

Replying to jpflori:

Any progress on your side?

no time so far. I will look at this during the SageFlint? days in December, unless someone else has some time before.

Paul

comment:17 in reply to: ↑ 6 Changed 9 years ago by johanbosman

Replying to jpflori:

As far as I'm concerned, this is nothing but a concrete example of the vague #715. So I guess I put it to "needs review" so that it could be closed as "duplicate/won't fix". Not sure it was the right way to do it.

If you think it should be closed, then I think you should set the milestone to duplicate/wontfix. Otherwise, it is probably better to change the status back to 'new'.

comment:18 Changed 9 years ago by zimmerma

with Sage 4.7.2 I get the following:

sage: for p in prime_range(10^5):
....:     K = GF(p)
....:     a = K(0)
....:     
sage: import gc
sage: gc.collect()
0
sage: from sage.rings.finite_rings.finite_field_prime_modn import \
....: FiniteField_prime_modn as FF
sage: L = [x for x in gc.get_objects() if isinstance(x, FF)]
sage: len(L), L[0], L[len(L)-1]
(9592, Finite Field of size 2, Finite Field of size 99767)

thus whenever we use the finite field we get a memleak. (If I remove the a=K(0) line, I get only two elements in L, for p=2 and p=99991.)

Paul

comment:19 Changed 9 years ago by zimmerma

I confirm (cf comment 8) that if I comment out the line

    _cache[(X, Y, category)] = weakref.ref(H)

in categories/homset.py, then the memory leak from comment 18 disappears.

Paul

comment:20 Changed 9 years ago by SimonKing

I think we have a different problem here.

The finite fields themselves should be cached. The cache (see GF._cache) uses weak references, which should be fine.

Also, there are special methods zero_element and one_element which should do caching, because zero and one are frequently used and should not be created over and over again.

However, it seems that all elements of a finite field are cached - and that's bad!

sage: K = GF(5)
sage: K(2) is K(2)
True
sage: K.<a> = GF(17^2)
sage: K(5) is K(5)
True

I see absolutely no reason why all 17^2 elements should be cached.

Fortunately, we have no caching for larger finite fields:

sage: K.<a> = GF(17^10)
sage: K(5) is K(5)
False

comment:21 Changed 9 years ago by SimonKing

  • Status changed from needs_review to needs_work

In the following example, there is no memory leak that would be caused by the sage.categories.homset cache:

sage: len(sage.categories.homset._cache.keys())
100
sage: for p in prime_range(10^5):
....:     K = GF(p)
....:     
sage: len(sage.categories.homset._cache.keys())
100

However, when you do a conversion K(...) then a convert map is created, and apparently is cached:

sage: for p in prime_range(10^5):
....:     K = GF(p)
....:     a = K(0)
....:
sage: len(sage.categories.homset._cache.keys())
9692

The homset cache does use weak references. Hence, it is surprising that the unused stuff can not be garbage collected. Apparently there is some direct reference involved at some point.

I am very stronglyagainst removing the cache of sage.categories.homset. Namely, elliptic curve code uses finite fields and maps involving finite fields a lot, and killing the cache is likely to cause a massive regression.

However, since we actually have coercion maps (not just any odd map), I expect that the direct reference comes from the coercion model. I suggest to look into the coercion code and use weak references there.

By the way, I don't know why the status is "needs review". I think it clearly is "needs work".

comment:22 in reply to: ↑ 8 Changed 9 years ago by SimonKing

Replying to jpflori:

So the culprit is "_cache" in sage.categories.homset which has a direct reference to the finite fields in its keys.

Oops, that could indeed be the problem! Namely, the homset cache uses weak references to its values, but uses direct references to its keys! Perhaps using weak references as keys would work?

comment:23 Changed 9 years ago by zimmerma

it seems the complete caching of field elements only occurs for p < 500:

sage: K=GF(499)
sage: K(5) is K(5)
True
sage: K=GF(503)
sage: K(5) is K(5)
False

A workaround to this memory leak is to free the cache from time to time (thanks Simon):

sage: sage.categories.homset._cache.clear()

Paul

comment:24 Changed 9 years ago by SimonKing

On the other hand, it could be that using weak keys in the homset cache will not work: The keys are triples: domain, codomain and category.

What we want is: If either the domain or the codomain or the category have no strong reference, then the homset can be garbage collected.

Hence: Why don't we use a dictionary of dictionaries of dictionaries?

What I mean is:

  • The keys of sage.categories.homset._cache should be weak references to the domain
  • The values of sage.categories.homset._cache should be dictionaries whose keys are weak references to the codomain.
  • The keys of these dictionaries should be weak references to the category, and the value a weak reference to the homset.

Hence, if there is no strong reference to either domain or codomain or category, then the homset can be deallocated.

comment:25 Changed 9 years ago by SimonKing

The idea sketched in the previous comment seems to work!!!

With it, after running

sage: for p in prime_range(10^5):
....:     K = GF(p)
....:     a = K(0)
....:     print get_memory_usage()

ends with printing 825.45703125

Without it, it ends with printing 902.8125

I don't know if we should ban caching of field elements?

How could fixing that memory leak be demonstrated by a doc test?

Anyway, I will post a preliminary patch in a few minutes (so that you can see if it fixes at least part of the problem for you), while I am running sage -tp 2 devel/sage.

comment:26 Changed 9 years ago by SimonKing

Patch's up!

comment:27 Changed 9 years ago by SimonKing

Hm. There seems to be a problem.

sage -t  devel/sage/doc/en/constructions/linear_codes.rst
The doctested process was killed by signal 11

What is signal 11?

comment:28 Changed 9 years ago by zimmerma

signal 11 is Segmentation Fault

Paul

comment:29 Changed 9 years ago by SimonKing

Indeed it is a segfault. And it is triggered by

sage: w = vector([1,1,-4])

comment:30 Changed 9 years ago by SimonKing

Monique van Beek just pointed me to the fact that the error occurs even earlier:

sage: is_Ring(None)
<BOOOOOM>

comment:31 Changed 9 years ago by SimonKing

Moreover,

sage: None in Rings()
<BOOOOOOM>

comment:32 Changed 9 years ago by SimonKing

That said: I am not working on top of vanilla sage, but I use some patches. In particular, I use #11900, which introduces so called Category_singleton, which has a specialised and very fast containment test.

I would not like to change #11900, but prefer to change my patch from here so that it works on top of #11900.

comment:33 Changed 9 years ago by SimonKing

It turns out that indeed the bug is in #11900. So, I have to fix it there.

comment:34 follow-up: Changed 9 years ago by SimonKing

Cc to Nicolas, since it concerns categories:

Do we want that Hom(1,1) is still supported?

I think it does not make sense at all to talk about the homomorphisms of the number 1 to the number 1. The problem (for my patch as it is posted here) is the fact that one can't create a weak reference to the number 1.

comment:35 Changed 9 years ago by SimonKing

  • Cc nthiery added

Sorry, I forgot to update the Cc field.

Nicolas, please read my previous comment.

comment:36 Changed 9 years ago by SimonKing

With my patch, applied on top of #11900, I get

        sage -t  devel/sage-main/sage/structure/parent.pyx # 2 doctests failed
        sage -t  devel/sage-main/sage/structure/category_object.pyx # 2 doctests failed
        sage -t  devel/sage-main/sage/rings/polynomial/polynomial_singular_interface.py # 1 doctests failed
        sage -t  devel/sage-main/sage/rings/polynomial/multi_polynomial_ring.py # 36 doctests failed
        sage -t  devel/sage-main/sage/structure/parent_base.pyx # 2 doctests failed

At least some of the errors are like

    sage: n = 5; Hom(n,7)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_3[4]>", line 1, in <module>
        n = Integer(5); Hom(n,Integer(7))###line 108:
    sage: n = 5; Hom(n,7)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.integer.Integer' object

and I really don't see why this should be considered a bug.

comment:37 Changed 9 years ago by SimonKing

  • Status changed from needs_work to needs_info

At least one of the errors in polynomial rings is due to a wrong order of initialising things: There is some information missing, and by consequence a weak reference can't be created.

I fixed this problem in the new patch version.

I put it as "needs info", because of my question on whether or not we want to consider an integer as object in a category.

comment:38 Changed 9 years ago by SimonKing

I was told by Mike Hansen why weak references to integers and rationals do not work.

I see three options:

#. Drop the support for Hom(1,1) (which I'd prefer) #. Add a cdef'd attribute __weakref__ to sage.structure.element.Element, which would create an overhead for garbage collection for elements, and also a memory overhead. #. Use two category.homset caches in parallel: One (the default) that uses weak references, and another one that uses "normal" references if weak references fail.

comment:39 Changed 9 years ago by SimonKing

FWIW:

With the latest patch, the tests in polynomial_singular_interface and in multi_polynomial_ring pass.

There remain the following problems:

sage -t  "devel/sage-main/sage/structure/parent.pyx"        
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/parent.pyx", line 1410:
    sage: n = 5; Hom(n,7)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_33[4]>", line 1, in <module>
        n = Integer(5); Hom(n,Integer(7))###line 1410:
    sage: n = 5; Hom(n,7)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.integer.Integer' object
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/parent.pyx", line 1412:
    sage: z=(2/3); Hom(z,8/1)                                                                            
Exception raised:                                                                                        
    Traceback (most recent call last):                                                                   
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test        
        self.run_one_example(test, example, filename, compileflags)                                      
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example      
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_33[5]>", line 1, in <module>
        z=(Integer(2)/Integer(3)); Hom(z,Integer(8)/Integer(1))###line 1412:
    sage: z=(2/3); Hom(z,8/1)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.rational.Rational' object
**********************************************************************
1 items had failures:
   2 of   8 in __main__.example_33
***Test Failed*** 2 failures.
For whitespace errors, see the file /home/simon/.sage//tmp/parent_2986.py
         [11.6 s]

and

sage -t  "devel/sage-main/sage/structure/category_object.pyx"
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/category_object.pyx", line 590:
    sage: n = 5; Hom(n,7)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_17[4]>", line 1, in <module>
        n = Integer(5); Hom(n,Integer(7))###line 590:
    sage: n = 5; Hom(n,7)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.integer.Integer' object
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/category_object.pyx", line 592:
    sage: z=(2/3); Hom(z,8/1)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_17[5]>", line 1, in <module>
        z=(Integer(2)/Integer(3)); Hom(z,Integer(8)/Integer(1))###line 592:
    sage: z=(2/3); Hom(z,8/1)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.rational.Rational' object
**********************************************************************
1 items had failures:
   2 of   8 in __main__.example_17
***Test Failed*** 2 failures.
For whitespace errors, see the file /home/simon/.sage//tmp/category_object_3050.py
         [2.7 s]

and

sage -t  "devel/sage-main/sage/structure/parent_base.pyx"   
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/parent_base.pyx", line 108:
    sage: n = 5; Hom(n,7)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_3[4]>", line 1, in <module>
        n = Integer(5); Hom(n,Integer(7))###line 108:
    sage: n = 5; Hom(n,7)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.integer.Integer' object
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/structure/parent_base.pyx", line 110:
    sage: z=(2/3); Hom(z,8/1)
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_3[5]>", line 1, in <module>
        z=(Integer(2)/Integer(3)); Hom(z,Integer(8)/Integer(1))###line 110:
    sage: z=(2/3); Hom(z,8/1)
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python/site-packages/sage/categories/homset.py", line 159, in Hom
        cache2 = _cache[X]
      File "/home/simon/SAGE/sage-4.8.alpha3/local/lib/python2.6/weakref.py", line 243, in __getitem__
        return self.data[ref(key)]
    TypeError: cannot create weak reference to 'sage.rings.rational.Rational' object
**********************************************************************
1 items had failures:
   2 of   8 in __main__.example_3
***Test Failed*** 2 failures.
For whitespace errors, see the file /home/simon/.sage//tmp/parent_base_3078.py
         [2.6 s]

So, essentially this is just a single test that comes in two versions and is repeated three times - and I would actually say that not raising an error was a bug.

It seems that Hom(1/2,2/3) and similar nonsense is not used in Sage. Hence, I think these tests should be removed. I'll ask sage-devel.

comment:40 Changed 9 years ago by SimonKing

Without the patch:

sage: def test():
....:     for p in prime_range(10^5):
....:         K = GF(p)
....:         a = K(0)
....:         
sage: m0 = get_memory_usage()
sage: %time test()
CPU times: user 7.75 s, sys: 0.08 s, total: 7.83 s
Wall time: 7.84 s
sage: get_memory_usage() - m0
80.234375

With the patch:

sage: def test():
....:     for p in prime_range(10^5):
....:         K = GF(p)
....:         a = K(0)
....:         
sage: m0 = get_memory_usage()
sage: %time test()
CPU times: user 7.59 s, sys: 0.01 s, total: 7.60 s
Wall time: 7.61 s
sage: get_memory_usage() - m0
8.53515625

So, the memory does mildly increase, but it seems that most of the leak is fixed.

I think that a test of the kind

sage: get_memory_usage() - -m0 < 10
True

might be used as a doc test.

comment:41 in reply to: ↑ 34 Changed 9 years ago by nthiery

Replying to SimonKing:

Cc to Nicolas, since it concerns categories:

Do we want that Hom(1,1) is still supported?

I think it does not make sense at all to talk about the homomorphisms of the number 1 to the number 1. The problem (for my patch as it is posted here) is the fact that one can't create a weak reference to the number 1.

I don't see much point either. We had a similar discussion a while ago about whether elements should be objects in a category, and as far as I remember, the answer was no by default (Element does not inherit from CategoryObject?). So +1 on my side to kill this dubious feature. You might want to double check on sage-algebra just to make sure.

comment:42 follow-up: Changed 9 years ago by zimmerma

Simon, you can also use the test suggested by Jean-Pierre Flori (see comment 18 for an example).

Paul

comment:43 in reply to: ↑ 42 Changed 9 years ago by SimonKing

Hi Paul,

Replying to zimmerma:

Simon, you can also use the test suggested by Jean-Pierre Flori (see comment 18 for an example).

Yes, that looks good. With my patch, the test would be like

sage: for p in prime_range(10^5):
....:     K = GF(p)
....:     a = K(0)
....:     
sage: import gc
sage: gc.collect()
1881                                                                                                     
sage: from sage.rings.finite_rings.finite_field_prime_modn import FiniteField_prime_modn as FF           
sage: L = [x for x in gc.get_objects() if isinstance(x, FF)]
sage: len(L), L[0], L[len(L)-1]
(2, Finite Field of size 2, Finite Field of size 99991)

The people at sage-devel somehow seem to agree that objects of a category should be instances of CategoryObject (which elements aren't!), and that we should thus drop the Hom(2/3,8/1) test.

In addition to that, I suggest to provide a better error message, something like

sage: Hom(2/3, 8/1)
Traceback (most recent call last):
...
TypeError: Objects of categories must be instances of <type 'sage.structure.category_object.CategoryObject'>, but 2/3 isn't.

Cheers,

Simon

comment:44 Changed 9 years ago by SimonKing

  • Keywords sd35 added

One bad detail: I'd like to add the test to the documentation of sage.categories.homset. However, if I insert it in the appropriate place, there will be a conflict with both #9138 and #11900.

I could try to insert the test in a less logical place, in order to avoid to have a dependency.

comment:45 Changed 9 years ago by SimonKing

  • Dependencies set to #11900
  • Status changed from needs_info to needs_review

I am very much afraid that I have not been able to make my patch independent of #11900. This is not just because of the documentation, but also because of some details in the choice of the homset's category.

Anyway, it needs review (and so does the most recent version of #11900, by the way)!

comment:46 Changed 9 years ago by SimonKing

  • Status changed from needs_review to needs_work

I did try the new doctests in sage/categories/homset.py. However, with other patches applied, the number returned by gc.collect() changes.

So, for stability, I suggest to simplify the test, so that only the number of finite fields remaining in the cache is tested.

comment:47 Changed 9 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from needs_work to needs_review

I updated the patch.

Difference to the previous patch: The number of objects collect by gc is marked as random (indeed, it will change with #11115 applied). What we are really interested in is the number of finite fields that remains in the cache after garbage collection. This number is two and is not random. Thus, that test is preserved.

comment:48 Changed 9 years ago by SimonKing

  • Status changed from needs_review to needs_work

I think I need help with debugging.

When I have sage-4.8.alpha3 with #9138, #11900, #715 and #11115, then all doctests pass.

When I also have #11521, then the test sage/rings/number_field/number_field_rel.py segfaults. When I run the tests in verbose mode, then all tests seem to pass, but in the very end it says

4 items had no tests:
    __main__
    __main__.change_warning_output
    __main__.check_with_tolerance
    __main__.warning_function
69 items passed all tests:
...
660 tests in 73 items.
660 passed and 0 failed.
Test passed.
The doctested process was killed by signal 11
         [15.0 s]

So, could it be that not one of the tests was killed, but the test process itself?

What is even more confusing: When I run the tests with the option -randorder, then most of the time the tests pass without a problem.

Can you give me any pointer on how those things could possibly be debugged?

comment:49 Changed 9 years ago by fbissey

It sometimes happen that the sage session itself crash on exit. This is probably one of these. Last time I got one it was related to singular I think. It is quite difficult to corner these with gdb. The best you can hope is start a sage session with gdb and then try the last doctest sequence and quit sage, it may lead to the crash in which case you may have some luck with gdb. But this is one of these case where gdb itself may be interfering. I don't think I have time to look into this right now but I'll put it into my "To do" list in case it isn't solved when i have time to spare.

Changed 9 years ago by SimonKing

Use weak references for the keys of the homset cache. If weak references are not supported, then raise an error, pointing out that category objects should be CategoryObjects.

comment:50 Changed 9 years ago by SimonKing

  • Work issues set to Understand why a weak key dictionary is not enough

I have attached a new patch version. It fixes the segfault I mentioned. However, it also does not fix the memory leak.

The difference between the two versions is: The new patch still uses weak references to the key of the cache, but a strong reference to the value (i.e., the homset).

The homset has a reference to domain and codomain, which constitute the cache key. Thus, I expected that it does not make any difference whether one has a strong or a weak reference to the homset. But I stand corrected. That needs to be investigated more deeply.

comment:51 follow-up: Changed 9 years ago by jpflori

Dear Simon,

Thanks a lot for taking care of all of this !

I'm just back from vacation and will have a look at all your patches in the following days.

I must point out that even if the memory leak was small, it did still mater because I used a LOT of them and after several hours of computations it ate all the available memory the piece of code in the ticket description is just a minimal example, in my actual code I used different curves and similar simple computations on them)...

And to make things clear, I must say I put that ticket as need review in order to get it closed as wont fix/duplicate because I thought it could be seen as a concrete example of ticket 715 and all the work could be done there.

Of course youre the one currently doing all the wok, so do as you want :)

Cheers,

JP

comment:52 in reply to: ↑ 51 Changed 9 years ago by SimonKing

Hi Jean-Pierre,

Replying to jpflori:

I must point out that even if the memory leak was small,

It isn't small.

And to make things clear, I must say I put that ticket as need review in order to get it closed as wont fix/duplicate because I thought it could be seen as a concrete example of ticket 715 and all the work could be done there.

I am not sure whether it would be good to do everything on one ticket, as the topics are related, but clearly disting: #715 is about weak "TripleDict" for coercion, #12215 is about a weak version of cached_function, and the ticket here is about the cache of homsets.

On the other hand: I am about to post a new patch here, with #715 as a dependency. It will use the new version of TripleDict from #715. So, one could argue that there is a common tool for both tickets, and they belong together.

Anyway. The new patch will fix the leak, but it will not suffer from the segfaults.

Cheers,

Simon

comment:53 Changed 9 years ago by SimonKing

  • Dependencies changed from #11900 to #11900 #715
  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Work issues Understand why a weak key dictionary is not enough deleted

I have attached another patch under a new name, using a new approach: The weak TripleDict, that I introduce at #715, is an appropriate tool for the cache of homsets. The key is the triple (domain, codomain, category), and the value is a weak reference to the corresponding homset.

There is a new test (the same as in the other patch), showing that the leak is fixed. And all tests in sage/schemes, sage/rings, sage/categories and sage/structure pass.

Hence: Needs review!

Apply trac11521_triple_homset.patch

Note: See TracTickets for help on using tickets.