Fix memoryleak introduced in #11670

[nbruin]

In #11670 the following leak was introduced:

        sage: u=id(NumberField(x^2-5,'a').absolute_field('b'))
        sage: import gc
        sage: gc.collect() #random
        10
        sage: [id(v) for v in gc.get_objects() if id(v) == u]

See Nils's explanation in #23807 comment:14 and the surrounding discussion, where this bug was found.

Component: memleak

Keywords: thursdaysbdx

Author: Nils Bruin, Peter Bruin

Branch/Commit: b7e1042

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/23851

[nbruin]

Branch: u/nbruin/fix_memoryleak_introduced_in__11670

[nbruin]

Author: nbruin, pbruin

[nbruin]

Commit: bf22de0

[nbruin]

New commits:

bf22de0

amend caching of "absolute_field" to avoid memory leaks due to "structure" storage.

[pjbruin]

Changed author from nbruin, pbruin to Nils Bruin, Peter Bruin

[pjbruin]

Changed branch from u/nbruin/fix_memoryleak_introduced_in__11670 to u/pbruin/23851-memory_leak

[pjbruin]

Changed commit from bf22de0 to 4568007

[pjbruin]

comment:3

Cleaned up the docstrings of absolute_field() a bit.

[seblabbe]

comment:4

I do not know what is happening with the patchbot. The bug is fixed and I get All tests passed after running make ptestlong on my machine.

[seblabbe]

Changed keywords from none to thursdaysbdx

[seblabbe]

Reviewer: Sébastien Labbé

[vbraun]

comment:5

I'm getting this on various buildbots:

File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1389, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
Failed example:
    u,o = K.S_units([])[0]; u, o
Expected:
    (-1/2*a + 1/2, 6)
Got:
    (1/2*a + 1/2, 6)
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1395, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
Failed example:
    u^2
Expected:
    -1/2*a - 1/2
Got:
    1/2*a - 1/2
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1404, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
Failed example:
    L.S_units([])
Expected:
    [(-1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
Got:
    [(1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1408, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
Failed example:
    L.S_units([K.ideal(1/2*a - 3/2)])
Expected:
    [((-1/6*a - 1/2)*b^2 + (1/3*a - 1)*b + 4/3*a, +Infinity),
     (-1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
Got:
    [((-1/6*a - 1/2)*b^2 + (1/3*a - 1)*b + 4/3*a, +Infinity),
     (1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1413, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
Failed example:
    L.S_units([K.ideal(2)])
Expected:
    [((1/2*a - 1/2)*b^2 + (a + 1)*b + 3, +Infinity),
     ((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a + 1/2, +Infinity),
     ((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a - 1/2, +Infinity),
     (-1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
Got:
    [((1/2*a - 1/2)*b^2 + (a + 1)*b + 3, +Infinity),
     ((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a + 1/2, +Infinity),
     ((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a - 1/2, +Infinity),
     (1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1476, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units
Failed example:
    u = K.units()[0][0]; u
Expected:
    -1/2*a + 1/2
Got:
    1/2*a + 1/2
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1482, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units
Failed example:
    u^2
Expected:
    -1/2*a - 1/2
Got:
    1/2*a - 1/2
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1494, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units
Failed example:
    L.units()
Expected:
    [(-1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
Got:
    [(1/2*a + 1/2, 6),
     ((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),
     (2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]
**********************************************************************
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1503, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units
Failed example:
    L.unit_group().gens_values()
Expected:
    [1/2*a + 1/2, (-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, 2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2]
Got:
    [-1/2*a + 1/2, (-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, 2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2]
**********************************************************************
2 items had failures:
   5 of  18 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units
   4 of  23 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units
    [448 tests, 9 failures, 6.99 s]

[pjbruin]

comment:6

With the following change (which is probably a bad idea) I consistently get the same doctest failures as above:

--- a/src/sage/rings/polynomial/polynomial_quotient_ring.py
+++ b/src/sage/rings/polynomial/polynomial_quotient_ring.py
@@ -1050,7 +1050,6 @@ class PolynomialQuotientRing_generic(CommutativeRing):
         return self(self.polynomial_ring().random_element( \
             degree=self.degree()-1, *args, **kwds))
 
-    @cached_method
     def _S_decomposition(self, S):
         """
         Compute the decomposition of self into a product of number fields.

[sagetrac-git]

Changed commit from 4568007 to 55a59ff

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

55a59ff

Trac 23851: force garbage collection to make S-unit computations deterministic

[pjbruin]

comment:8

The above commit appears to make the computation deterministic again. Let's see if the patchbot agrees.

[seblabbe]

comment:10

Replying to @seblabbe:

I do not know what is happening with the patchbot. The bug is fixed and I get All tests passed after running make ptestlong on my machine.

I confirm that I get the same errors when run alone:

 sage -t src/sage/rings/polynomial/polynomial_quotient_ring.py

I am sorry, I do not know what happened with my run of make ptestlong which said All tests passed. I rechecked the log file of ptestlong.log, and I confirm that I got All tests passed:

Running doctests with ID 2017-09-14-16-16-01-0e639740.
Git branch: 23851
Using --optional=ccache,cmake,cryptominisat,mpir,pandoc_attributes,pandocfilters,python2,rst2ipynb,sage
Doctesting entire Sage library.
Sorting sources by runtime so that slower doctests are run first....
Doctesting 3587 files using 8 threads.
...
sage -t --long --warn-long 58.9 src/sage/rings/polynomial/polynomial_quotient_ring.py
    [448 tests, 3.09 s]
...
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 1623.2 seconds
    cpu time: 10208.6 seconds
    cumulative wall time: 12523.8 seconds

[seblabbe]

comment:11

+        First, we force garbage collection to make the `S`-unit
+        computations below deterministic::

Why? Can you add a sentence in this paragraph saying why the computatino of S-unit depends on the existence of objects that were not yet collected by the garbage collector?

[seblabbe]

comment:12

I confirm that the last commit fixes the sage -t of polynomial_quotient_ring.py when run alone.

[roed314]

comment:19

Do we really want to delete @cached_method on absolute_field?

[seblabbe]

comment:20

Replying to @roed314:

Do we really want to delete @cached_method on absolute_field?

One argument for caching a method is when it takes long time to compute which is not the case here:

sage: %time nf = NumberField(x^2-5,'a')
CPU times: user 1.12 ms, sys: 97 µs, total: 1.21 ms
Wall time: 962 µs
sage: %time nf.absolute_field('b')
CPU times: user 9 µs, sys: 1e+03 ns, total: 10 µs
Wall time: 13.8 µs
Number Field in b with defining polynomial x^2 - 5

Is there another reason why absolute_field should be cached?

[seblabbe]

Changed work issues from fix random doctest failures to none

[roed314]

comment:23

Replying to @seblabbe:

Replying to @roed314:

Do we really want to delete @cached_method on absolute_field?

One argument for caching a method is when it takes long time to compute which is not the case here:

sage: %time nf = NumberField(x^2-5,'a')
CPU times: user 1.12 ms, sys: 97 µs, total: 1.21 ms
Wall time: 962 µs
sage: %time nf.absolute_field('b')
CPU times: user 9 µs, sys: 1e+03 ns, total: 10 µs
Wall time: 13.8 µs
Number Field in b with defining polynomial x^2 - 5

Your timings, on a quadratic field which is already absolute, aren't particularly convincing that this method is always fast. However, running some other tests on higher degree relative extensions shows that they're quite fast as well. I'll withdraw my objection to removing the cached_method.

Is there another reason why absolute_field should be cached?

[vbraun]

comment:24

Merge conflict

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b7e1042

Merge branch 'develop' into ticket/23851-memory_leak

[sagetrac-git]

Changed commit from dd0594d to b7e1042

[jdemeyer]

comment:27

I don't really understand the memory leak. If the original code leaks, isn't that a deeper problem with @cached_method?

[jdemeyer]

comment:29

Does anybody have an idea? If not, please say so. I'm just asking to know whether it's worth my time to investigate it.

[pjbruin]

comment:30

Replying to @jdemeyer:

I don't really understand the memory leak. If the original code leaks, isn't that a deeper problem with @cached_method?

The leak is caused by the combination of @cached_method and UniqueFactory; see Nils's explanation in #23807 comment:14 and the surrounding discussion, where this bug was found.

[jdemeyer]

comment:32

Thanks for the pointer! It all makes sense to me now.

[vbraun]

Changed branch from u/pbruin/23851-memory_leak to b7e1042