Memory leaks on matrix creation?

[Jori Mäntysalo]

I was asked to make a code that iterates over all matrices of given type
and size. And once again I see a memory leak. Here's an example code

n = 7
m = Integer(n*(n-1)/2)
for i in IntegerRange(2^m):
d = i.digits(base=2, padto=m)
l = [[1]+[0]*(n-1)]
for j in range(n-1):
l.append( d[(j+1)*j/2:(j+1)*(j+2)/2]+ [1] + [0]*(n-j-2) )
M = Matrix(l)
eig = sorted((M*M.transpose()).eigenvalues())[0]
if eig <= 0:
print "Foobar"

These kind of codes, where I make millions of small objects, compute
something and discard the object, seems to eat memory. Not much, but so
much that otherwise reasonable computable thing - say, something to run
for two days - will be impossible to do directly.

Is there anything I can do for these? (Other than running the code
part-by-part.)

This was ran on newest beta version.

--
Jori Mäntysalo

[Ralf Stephan]

On Monday, July 13, 2015 at 9:44:01 AM UTC+2, Jori Mäntysalo wrote:

Is there anything I can do for these? (Other than running the code
part-by-part.)

As quick hint I would use valgrind for the search.

http://wiki.sagemath.org/ValgrindingSage

[Volker Braun]

For every matrix dimension there is a parent (MatrixSpace). You are most likely seeing those. Use @fork / @parallel.

On Monday, July 13, 2015 at 9:44:01 AM UTC+2, Jori Mäntysalo wrote:

[Nils Bruin]

On Monday, July 13, 2015 at 10:39:17 AM UTC+2, Ralf Stephan wrote:

As quick hint I would use valgrind for the search.

http://wiki.sagemath.org/ValgrindingSage

Does valgrind understand python memory layout? most leaks in sage are due to lingering references and hence are detectable by python. If I run:

import gc
from collections import Counter
gc.collect()
pre={id(c) for c in gc.get_objects()}

n = 5

m = Integer(n*(n-1)/2)
for i in IntegerRange(2^m):
     d = i.digits(base=2, padto=m)
     l = [[1]+[0]*(n-1)]
     for j in range(n-1):
         l.append( d[(j+1)*j/2:(j+1)*(j+2)/2]+ [1] + [0]*(n-j-2) )
     M = Matrix(l)
     eig = sorted((M*M.transpose()).eigenvalues())[0]
     if eig <= 0:
         print "Foobar"

gc.collect()
post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
sorted(post.iteritems(),key=lambda t: t[1])

I find:

...
[(<type 'set'>, 1),
 (<type 'generator'>, 1),
 (<type 'builtin_function_or_method'>, 1),
 (<class '_ast.Attribute'>, 1),
 (<class 'sage.rings.qqbar.AlgebraicPolynomialTracker'>, 1),
 (<class 'sage.rings.qqbar.ANRoot'>, 1),
 (<type 'enumerate'>, 1),
 (<class '_ast.Interactive'>, 1),
 (<class '_ast.comprehension'>, 1),
 (<type 'function'>, 1),
 (<type 'instancemethod'>, 1),
 (<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_field'>,
  1),
 (<type 'listiterator'>, 1),
 (<class '_ast.Assign'>, 1),
 (<type 'sage.rings.complex_interval.ComplexIntervalFieldElement'>, 1),
 (<class '_ast.Compare'>, 1),
 (<class '_ast.GeneratorExp'>, 1),
 (<class '_ast.Module'>, 1),
 (<type 'weakref'>, 3),
 (<class '_ast.Call'>, 4),
 (<type 'frame'>, 6),
 (<type 'sage.rings.rational.Rational'>, 6),
 (<type 'sage.rings.real_mpfi.RealIntervalFieldElement'>, 6),
 (<class 'sage.rings.qqbar.ANRational'>, 6),
 (<class 'sage.rings.qqbar.AlgebraicNumber'>, 7),
 (<class '_ast.Name'>, 9),
 (<type 'tuple'>, 11),
 (<type 'list'>, 29),
 (<type 'dict'>, 32),
 (<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 6273)]
...

so I'd think there's a leak in constructing univar_pd. My guess would be a cached routine that shouldn't be cached.

[Jori Mäntysalo]

On Mon, 13 Jul 2015, Volker Braun wrote:

> For every matrix dimension there is a parent (MatrixSpace). You are most
> likely seeing those.

But they have the same size. 7 x 7 on my example code.

--
Jori Mäntysalo

[Nils Bruin]

On Monday, July 13, 2015 at 10:51:09 AM UTC+2, Nils Bruin wrote:

so I'd think there's a leak in constructing univar_pd. My guess would be a cached routine that shouldn't be cached.

A little bisection shows that the leak is caused by calling "eigenvalues".

However

L=[c for c in gc.get_objects() if type(c) is sage.rings.polynomial.polynomial_compiled.univar_pd]
objgraph.show_backrefs(L[1000],filename="test.png")

seems to show that the only reference that's findable by python's gc is the one from L! So the leak in this case might be due to a refcounting error (or a reference to a python object held by something outside the scope of the python memory manager). Or I've overlooked some subtle issue.

[Simon King]

Hi Volker and Jori,

On 2015-07-13, Volker Braun <vbrau...@gmail.com> wrote:
> For every matrix dimension there is a parent (MatrixSpace). You are most=20

> likely seeing those. Use @fork / @parallel.

MatrixSpace is supposed to use a weak cache. Hence, if you drop all
matrices of a given dimension and base ring, then the corresponding
matrix space is supposed to be deallocated. If it isn't, then it's a
bug.

Best regards,
Simon

[Jori Mäntysalo]

On Mon, 13 Jul 2015, Nils Bruin wrote:

> A little bisection shows that the leak is caused by calling "eigenvalues".

Can you make a ticket with minimal example demonstrating bug?

--
Jori Mäntysalo

[Volker Braun]

True, but in practice its easy to have a matrix result hang off an @cached_method.

[Sébastien Labbé]

Can you make a ticket with minimal example demonstrating bug?

Here it is:

http://trac.sagemath.org/ticket/18897

Sébastien

[Simon King]

Sébastien Labbé <slabqc <at> gmail.com> writes:
> Here it is:http://trac.sagemath.org/ticket/18897 Sébastien

The leak was in deallocation of sage.misc.binary_tree.BinaryTree. My fix
needs review.

Cheers,
Simon