Opened 6 years ago

Closed 6 years ago

#18897 closed defect (fixed)

Memory leak in sage.misc.binary_tree.BinareeTree

Reported by: slabbe Owned by:
Priority: critical Milestone: sage-6.8
Component: memleak Keywords:
Cc: SimonKing, jmantysalo Merged in:
Authors: Simon King Reviewers: Sébastien Labbé, Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 80ce876 (Commits, GitHub, GitLab) Commit: 80ce8765811c7ac18b921467e113630169b6aaaf
Dependencies: Stopgaps:

Status badges

Description (last modified by slabbe)

This method, inspired from the code of Nils Bruin posted in the sage-devel post Memory leaks on matrix creation?, shows some leak in the eigenvalues method for integer matrices of order larger or equal to 4. Examples are below.

def test(L, dim):
    import gc
    from collections import Counter
    gc.collect()
    pre={id(c) for c in gc.get_objects()}
    for _ in range(100):
        matrix(dim, L).eigenvalues()
    gc.collect()
    post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
    return [(k,v) for (k,v) in post.iteritems() if v>10]

An example with no leak::

    sage: L = [1,0,0,1,0,0,1,1,0,0,0,1,2,0,0,1,0,0,2,0,0,0,0,0,1]
    sage: test(L, 5)
    []

Five forgotten polynomials::

    sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
    sage: test(L, 5)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]

Twelve forgotten polynomials::

    sage: L = [0,1,2,0,0,2,1,2,1,1,1,0,1,1,2,1,1,1,2,0,0,2,0,2,0]
    sage: test(L, 5)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1200)]

A 4 by 4 matrix with five forgotten polynomials::

    sage: L = [0, 2, 0, 2, 2, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]
    sage: test(L, 4)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]

Random ones::

    sage: test([randint(0,100) for _ in range(9)], 3)
    []
    sage: test([randint(0,100) for _ in range(16)], 4)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]
    sage: test([randint(0,2) for _ in range(25)], 5)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]
    sage: test([randint(0,2) for _ in range(25)], 5)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1200)]
    sage: test([randint(0,2) for _ in range(25)], 5)
    []
    sage: test([randint(0,100) for _ in range(36)], 6)
    [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1400)]

Change History (37)

comment:1 Changed 6 years ago by slabbe

  • Description modified (diff)

comment:2 Changed 6 years ago by slabbe

  • Summary changed from Memory leak in eigenvalues method to Memory leak in polynomial_compiled.univar_pd

comment:3 Changed 6 years ago by SimonKing

  • Cc SimonKing added

comment:4 Changed 6 years ago by slabbe

It seems to come from the factor method applied on the charpoly after changing the ring to AlgebraicField.

def test(L, dim):
    import gc
    from collections import Counter
    gc.collect()
    pre={id(c) for c in gc.get_objects()}
    for _ in range(100):
        matrix(dim, L).charpoly().change_ring(QQbar).factor()
    gc.collect()
    post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
    return [(k,v) for (k,v) in post.iteritems() if v>10]

We get:

sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
sage: test(L, 5)
[(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1000)]
Last edited 6 years ago by slabbe (previous) (diff)

comment:5 Changed 6 years ago by slabbe

Ok, so it seems to come from calling roots on an element of the Univariate Polynomial Ring in x over Algebraic Field :

def test():
    import gc
    from collections import Counter
    gc.collect()
    pre={id(c) for c in gc.get_objects()}
    R.<x> = QQbar['x']
    p = x^5 - 8*x^4 + 21*x^3 - 22*x^2 + 9*x - 1
    for _ in range(100):
        #p.factor()                              # which then calls:
        #QQbar._factor_univariate_polynomial(p)  # which then calls:
        p.roots()
    gc.collect()
    post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
    return [(k,v) for (k,v) in post.iteritems() if v>10]

We get:

sage: test()
[(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1000)]

comment:6 Changed 6 years ago by slabbe

Those univar_pd are created in the class CompiledPolynomialFunction which provides an easy way to create the problem:

def test():
    from sage.rings.polynomial.polynomial_compiled import CompiledPolynomialFunction
    import gc
    from collections import Counter
    gc.collect()
    pre={id(c) for c in gc.get_objects()}
    L = [-1, 9, -22, 21, -8, 1]
    for _ in range(100):
        CompiledPolynomialFunction(L)
    gc.collect()
    post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
    return [(k,v) for (k,v) in post.iteritems() if v>10]

and we get:

sage: test()
[(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 100)]

comment:7 Changed 6 years ago by slabbe

Ok, so this goes now beyond my knowledge. Somebody else will need to check why the univar_pd are not garbage collected.

https://github.com/sagemath/sage/blob/master/src/sage/rings/polynomial/polynomial_compiled.pyx#L402

comment:8 Changed 6 years ago by SimonKing

During initialisation of a compiled polynomial, _parse_structure() is called, which creates a sage.misc.binary_tree.BinaryTree. Into this binary tree, a univar_pd is inserted.

When finishing initialisation of a compiled polynomial, the binary tree gets deallocated. However, the univar_pd does not get deallocated. I don't know why it isn't, but rather clearly that's where the leak is occurring.

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

Got it!

It seems that a binary tree is NEVER completely deallocated. When calling binary_tree_dealloc(node), then the left and right descendants of node are deallocated, but not node itself.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by SimonKing

Replying to SimonKing:

It seems that a binary tree is NEVER completely deallocated. When calling binary_tree_dealloc(node), then the left and right descendants of node are deallocated, but not node itself.

To be precise: The pointer to node is freed, but one should call free_binary_tree_node(node) instead.

comment:11 Changed 6 years ago by SimonKing

  • Branch set to u/SimonKing/memory_leak_compiled_polynomial

comment:12 Changed 6 years ago by SimonKing

  • Authors set to Simon King
  • Commit set to 79923d35f59362331a5aa006f8dbc6c329acd440
  • Status changed from new to needs_review

I used your test to show that the memory leak is fixed. Note, however, that the fix is in the deallocation of binary trees and has nothing to do with compiled polynomials.


New commits:

79923d3Fix a memory leak in the deallocation of binary trees

comment:13 Changed 6 years ago by jmantysalo

  • Cc jmantysalo added

comment:14 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by dimpase

Replying to SimonKing:

Replying to SimonKing:

It seems that a binary tree is NEVER completely deallocated. When calling binary_tree_dealloc(node), then the left and right descendants of node are deallocated, but not node itself.

To be precise: The pointer to node is freed, but one should call free_binary_tree_node(node) instead.

the following looks more logical to me (diff over your patch):

diff --git a/src/sage/misc/binary_tree.pyx b/src/sage/misc/binary_tree.pyx
index 984ef57..c637d91 100644
--- a/src/sage/misc/binary_tree.pyx
+++ b/src/sage/misc/binary_tree.pyx
@@ -25,13 +25,11 @@ cdef void free_binary_tree_node(binary_tree_node *self):
     sage_free(self)
 
 cdef void binary_tree_dealloc(binary_tree_node *self):
-    # deallocate the descendants of self, but NOT self
     if self.left != NULL:
         binary_tree_dealloc(self.left)
-        free_binary_tree_node(self.left)
     if self.right != NULL:
         binary_tree_dealloc(self.right)
-        free_binary_tree_node(self.right)
+    free_binary_tree_node(self)
 
 
 cdef void binary_tree_insert(binary_tree_node *self, int key, object value):
@@ -210,7 +208,6 @@ cdef class BinaryTree:
         """
         if self.head != NULL:
             binary_tree_dealloc(self.head)
-            free_binary_tree_node(self.head)
 
     def insert(BinaryTree self, object key, object value = None):
         """

comment:15 Changed 6 years ago by slabbe

  • Branch changed from u/SimonKing/memory_leak_compiled_polynomial to public/18897
  • Commit changed from 79923d35f59362331a5aa006f8dbc6c329acd440 to 720de3bf96d4e72965581bbf5ad372e94fe61237

The fix proposed by Simon fixes all the way to create the bug I saw yesterday. To me it is a positive review. I added a reference to the ticket in the doctest and posted that on public/18897.

(the comment of dimpase just appeared as I was writing this comment)


New commits:

720de3bTrac #18897: added a ref to trac # in doctest

comment:16 Changed 6 years ago by dimpase

I am now running tests with the change I proposed (which I like as it makes code shorter and more readable), just to be 100% sure.

comment:17 Changed 6 years ago by slabbe

  • Summary changed from Memory leak in polynomial_compiled.univar_pd to Memory leak in sage.misc.binary_tree.pyx

comment:18 in reply to: ↑ 14 ; follow-ups: Changed 6 years ago by SimonKing

  • Summary changed from Memory leak in sage.misc.binary_tree.pyx to Memory leak in polynomial_compiled.univar_pd

Replying to dimpase:

the following looks more logical to me (diff over your patch):

I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in binary_tree_dealloc:

cdef void binary_tree_dealloc(binary_tree_node *self):
    if self == NULL:
        return
    binary_tree_dealloc(self.left)
    binary_tree_dealloc(self.right)
    free_binary_tree_node(self)

comment:19 in reply to: ↑ 18 Changed 6 years ago by SimonKing

Replying to SimonKing:

Replying to dimpase:

the following looks more logical to me (diff over your patch):

I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in binary_tree_dealloc:

PS: And then of course BinaryTree.__dealloc__ simply becomes

    def __dealloc__(self):
        binary_tree_dealloc(self.head)

comment:20 Changed 6 years ago by SimonKing

PS: I am doing this change now. Also, I am changing __init__ into __cinit__.

Rationale: The current __init__ just sets the pointer self.head = NULL. But initialising c-data (pointers etc.) is the job of __cinit__: It should initialise the c-data to such extend that __dealloc__ can not crash. With the current code, there may be circumstances under which the __init__ is not called, so that __dealloc__ will fail with a segmentation fault.

comment:21 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by dimpase

Replying to SimonKing:

Replying to dimpase:

the following looks more logical to me (diff over your patch):

I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in binary_tree_dealloc:

cdef void binary_tree_dealloc(binary_tree_node *self):
    if self == NULL:
        return
    binary_tree_dealloc(self.left)
    binary_tree_dealloc(self.right)
    free_binary_tree_node(self)

or even

cdef void binary_tree_dealloc(binary_tree_node *self):
    if self != NULL:
        binary_tree_dealloc(self.left)
        binary_tree_dealloc(self.right)
        free_binary_tree_node(self)

comment:22 Changed 6 years ago by git

  • Commit changed from 720de3bf96d4e72965581bbf5ad372e94fe61237 to 6d340771137df00b0da8a24485a95383f111d533

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

6d34077Simplify code for deallocation of binary trees

comment:23 Changed 6 years ago by SimonKing

Something completely different: Shouldn't BinaryTree be moved to sage.data_structures?


New commits:

6d34077Simplify code for deallocation of binary trees

New commits:

6d34077Simplify code for deallocation of binary trees

comment:24 in reply to: ↑ 21 Changed 6 years ago by SimonKing

Replying to dimpase:

or even

cdef void binary_tree_dealloc(binary_tree_node *self):
    if self != NULL:
        binary_tree_dealloc(self.left)
        binary_tree_dealloc(self.right)
        free_binary_tree_node(self)

Right. Before I change that: Should the module be moved to data_structures? After all, it is a general data structure that does not rely on sage-specific structures (i.e., not on parents and elements).

comment:25 Changed 6 years ago by SimonKing

PPS: Why is the implementation of binary trees in sage.combinat.binary_tree totally orthogonal to the one in sage.misc.binary_tree?

I'll ask on sage.combinat, and I suppose moving to sage.data_structure and unification of the two implementations should be on a separate ticket. So, I'll do the additional simplification now, and everything else is for later.

comment:26 Changed 6 years ago by git

  • Commit changed from 6d340771137df00b0da8a24485a95383f111d533 to 80ce8765811c7ac18b921467e113630169b6aaaf

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

80ce876Further simplification

comment:27 follow-up: Changed 6 years ago by dimpase

  • Priority changed from major to critical
  • Status changed from needs_review to needs_info

I just tried the example in the ticket description, both on unpatched and patched, and got the following disturbing output:

$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.8.beta8, Release Date: 2015-07-10               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: def test(L, dim):                                      
        import gc
        from collections import Counter
        gc.collect()
        pre={id(c) for c in gc.get_objects()}
        for _ in range(100):
                matrix(dim, L).eigenvalues()
        gc.collect()
        post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
        return [(k,v) for (k,v) in post.iteritems() if v>10]
....:     
sage: L = [1,0,0,1,0,0,1,1,0,0,0,1,2,0,0,1,0,0,2,0,0,0,0,0,1]
sage: test(L, 5)
[(<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 11),
 (<type 'instance'>, 106),
 (<type 'function'>, 1680),
 (<type 'dict'>, 271),
 (<type 'type'>, 78),
 (<type 'method_descriptor'>, 195),
 (<type 'wrapper_descriptor'>, 403),
 (<type 'property'>, 37),
 (<type 'classobj'>, 13),
 (<type 'module'>, 83),
 (<type 'list'>, 262),
 (<type 'sage.misc.constant_function.ConstantFunction'>, 21),
 (<type 'tuple'>, 264),
 (<type 'getset_descriptor'>, 199),
 (<class 'weakref.KeyedRef'>, 64),
 (<class 'numpy.testing.nosetester.NoseTester'>, 19),
 (<type 'staticmethod'>, 50),
 (<type 'member_descriptor'>, 12),
 (<type 'builtin_function_or_method'>, 177),
 (<type 'weakref'>, 152),
 (<type 'instancemethod'>, 22),
 (<type 'cell'>, 40)]
sage: 

if I re-run stuff, it works as it should; on the patched system:

sage: test(L, 5) # as before the fix:
[]
sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
sage: test(L, 5) # did not work before the fix:
[]
sage: 

on the unpatched system:

sage: test(L, 5)
[]
sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
sage: test(L, 5)
[(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]
sage: 

In short: something happens on the 1st call... Perhaps it is harmless, I don't know.

comment:28 Changed 6 years ago by dimpase

perhaps matrix leaks in other places, too; on the patched system:

$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.8.beta8, Release Date: 2015-07-10               │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: matrix(5,[1]*25);                                  
sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
sage: def test(L, dim):                                      
        import gc
        from collections import Counter
        gc.collect()
        pre={id(c) for c in gc.get_objects()}
        for _ in range(100):
                matrix(dim, L).eigenvalues()
        gc.collect()
        post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
        return [(k,v) for (k,v) in post.iteritems() if v>10]
....:     
sage: test(L, 5)
[(<type 'function'>, 13),
 (<type 'dict'>, 18),
 (<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 11),
 (<type 'list'>, 34),
 (<type 'sage.misc.constant_function.ConstantFunction'>, 21),
 (<type 'tuple'>, 88),
 (<type 'cell'>, 24),
 (<class 'weakref.KeyedRef'>, 64),
 (<type 'staticmethod'>, 12),
 (<type 'weakref'>, 27)]
sage: test(L, 5)
[]
sage: 

comment:29 in reply to: ↑ 27 Changed 6 years ago by SimonKing

  • Status changed from needs_info to needs_review

Replying to dimpase:

In short: something happens on the 1st call... Perhaps it is harmless, I don't know.

Well, if something is only there in the first run, then it is not accumulating, and thus by definition it is not a leak, and thus not critical.

comment:30 Changed 6 years ago by SimonKing

On the other hand: What happens if you are also iterating over different base rings?

comment:31 Changed 6 years ago by SimonKing

sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1]
sage: def test(L, dim):
....:     import gc
....:     from collections import Counter
....:     gc.collect()
....:     pre={id(c) for c in gc.get_objects()}
....:     m = matrix(dim, L)
....:     for p in range(2,102):
....:         m.change_ring(GF(nth_prime(p))).eigenvalues()
....:     gc.collect()
....:     post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
....:     return [(k,v) for (k,v) in post.iteritems() if v>10]
....: 
sage: test(L, 5)
[(<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category'>,
  100),
 (<type 'sage.libs.ntl.ntl_ZZ_pX.ntl_ZZ_pX'>, 76),
 (<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>,
  2494),
 (<class 'sage.rings.finite_rings.homset.FiniteFieldHomset_with_category'>,
  76),
 (<type 'sage.categories.morphism.IdentityMorphism'>, 153),
 (<class 'sage.rings.homset.RingHomset_quo_ring_with_category'>, 100),
 (<type 'weakref'>, 3700),
 (<type 'sage.categories.map.FormalCompositeMap'>, 200),
 (<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>,
  16),
 (<class 'sage.modules.free_module.FreeModule_ambient_field_with_category'>,
  60),
 (<type 'sage.libs.ntl.ntl_ZZ_pEContext.ntl_ZZ_pEContext_class'>, 75),
 (<type 'sage.categories.morphism.CallMorphism'>, 197),
 (<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p_with_category'>,
  176),
 (<type 'list'>, 8080),
 (<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>,
  523),
 (<type 'sage.rings.finite_rings.integer_mod.NativeIntStruct'>, 100),
 (<type 'sage.rings.finite_rings.integer_mod.Int_to_IntegerMod'>, 200),
 (<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>, 382),
 (<type 'sage.misc.constant_function.ConstantFunction'>, 3050),
 (<class 'sage.rings.ideal.Ideal_pid'>, 100),
 (<type 'sage.rings.finite_rings.hom_prime_finite_field.FiniteFieldHomomorphism_prime'>,
  76),
 (<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>,
  100),
 (<class 'sage.structure.sequence.Sequence_generic'>, 75),
 (<type 'dict'>, 2034),
 (<type 'sage.misc.cachefunc.CachedMethodCaller'>, 123),
 (<class 'sage.rings.finite_rings.conway_polynomials.PseudoConwayLattice'>,
  100),
 (<type 'staticmethod'>, 132),
 (<type 'cell'>, 204),
 (<type 'sage.structure.element.NamedBinopMethod'>, 13),
 (<type 'sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod'>, 176),
 (<type 'sage.rings.finite_rings.element_givaro.Cache_givaro'>, 16),
 (<type 'sage.rings.polynomial.polynomial_element.PolynomialBaseringInjection'>,
  200),
 (<type 'classobj'>, 13),
 (<type 'function'>, 1817),
 (<type 'property'>, 37),
 (<class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'>,
  60),
 (<class 'sage.rings.homset.RingHomset_generic_with_category'>, 100),
 (<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 72),
 (<type 'frozenset'>, 33),
 (<type 'sage.structure.coerce_dict.MonoDictEraser'>, 2087),
 (<type 'sage.structure.coerce_dict.TripleDict'>, 1043),
 (<type 'instancemethod'>, 609),
 (<type 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt'>,
  180),
 (<class 'sage.structure.dynamic_class.DynamicClasscallMetaclass'>, 21),
 (<type 'wrapper_descriptor'>, 513),
 (<type 'instance'>, 106),
 (<type 'sage.libs.ntl.ntl_ZZ_pContext.ntl_ZZ_pContext_class'>, 76),
 (<type 'getset_descriptor'>, 202),
 (<class 'sage.rings.finite_rings.homset.FiniteFieldHomset_with_category'>,
  76),
 (<type 'sage.structure.coerce_dict.MonoDict'>, 2087),
 (<type 'sage.structure.coerce_maps.DefaultConvertMap_unique'>, 1090),
 (<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, 21566),
 (<class 'weakref.KeyedRef'>, 10447),
 (<type 'builtin_function_or_method'>, 428),
 (<type 'member_descriptor'>, 12),
 (<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category.element_class'>,
  76),
 (<type 'sage.rings.morphism.RingHomomorphism_cover'>, 76),
 (<class 'sage.categories.homset.Homset_with_category'>, 176),
 (<type 'method_descriptor'>, 360),
 (<type 'module'>, 94),
 (<type 'tuple'>, 2688),
 (<type 'sage.libs.pari.gen.gen'>, 60),
 (<type 'sage.structure.coerce_dict.TripleDictEraser'>, 1043),
 (<class 'numpy.testing.nosetester.NoseTester'>, 19),
 (<type 'type'>, 82),
 (<type 'sage.rings.morphism.RingMap_lift'>, 76)]
sage: test(L, 5)
[]

So, that looks like a different kind of leak: Some objects are not deallocated when they aren't used (output of the first test(L, 5)), but at least they are still available for future use (output of the second test(L, 5)).

The patch from this ticket has fixes one leak, and I'd say that the other leak should be addressed on a different ticket.

comment:32 Changed 6 years ago by SimonKing

...
 (<class 'sage.rings.homset.RingHomset_quo_ring_with_category'>, 100),
...
 (<class 'sage.rings.homset.RingHomset_generic_with_category'>, 100),
...

I guess that's the culprit.

comment:33 Changed 6 years ago by dimpase

I opened #18905 to work on the latest leaks. Otherwise, it's good to go.

comment:34 Changed 6 years ago by slabbe

Replying to dimpase:

In short: something happens on the 1st call... Perhaps it is harmless, I don't know.

Yes, I noticed the same thing yesterday. There is stuff that is there the first execution, but never after. I did not look deeper into that...

comment:35 Changed 6 years ago by dimpase

  • Reviewers set to Sébastien Labbé, Dima Pasechnik
  • Status changed from needs_review to positive_review

comment:36 Changed 6 years ago by slabbe

  • Summary changed from Memory leak in polynomial_compiled.univar_pd to Memory leak in sage.misc.binary_tree.BinareeTree

comment:37 Changed 6 years ago by vbraun

  • Branch changed from public/18897 to 80ce8765811c7ac18b921467e113630169b6aaaf
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.