Sage: Ticket #14549: Memory leak in algebraic_immunity of BooleanFunction class
https://trac.sagemath.org/ticket/14549
<p>
On my Mac OS X 10.8.3 the code
</p>
<pre class="wiki">from sage.crypto.boolean_function import BooleanFunction
s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)]
s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)]
</pre><p>
takes around 5GB of RAM on each "s=..." part. You can repeat the procedure for new 5GB.
</p>
<p>
Without algebraic_immunity function, the problem disappears.
</p>
<p>
The actual leak happens in <a class="missing wiki">BooleanPolynomialRing?</a>, see the below discussion. For this instance, the leak can be somewhat prevented, by using the constructor factory for <a class="missing wiki">BooleanPolynomialRing?</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14549
Trac 1.1.6jdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/14549#comment:1
https://trac.sagemath.org/ticket/14549#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/14549#comment:2
https://trac.sagemath.org/ticket/14549#comment:2
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/14549#comment:3
https://trac.sagemath.org/ticket/14549#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/14549#comment:4
https://trac.sagemath.org/ticket/14549#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketasanteTue, 16 May 2017 16:17:43 GMT
https://trac.sagemath.org/ticket/14549#comment:5
https://trac.sagemath.org/ticket/14549#comment:5
<p>
I took a look at this issue, it is still present in sage-8.0. But it seems as this is not a problem in the algebraic_immunity function, but, inherited from the call to annihilator, a problem with pbori's <a class="missing wiki">BooleanPolynomialRing?</a> objects. The memory leak can be reproduced by
</p>
<pre class="wiki">from sage.rings.polynomial.pbori import BooleanPolynomialRing
s=[BooleanPolynomialRing(8, 'x') for _ in xrange(100)]
</pre><p>
and repeating the last line.
</p>
<p>
I skimmed over the <a class="missing wiki">PolyBoRi?</a> wrapper code, but I have no idea about cython and how this wrapping works in sage, so I'm a bit lost here :) Maybe someone else has a idea, what to do here.
</p>
<p>
Should this ticket be somehow changed? Closed as the problem is somewhere else, or how to proceed?
</p>
TicketnbruinTue, 16 May 2017 19:02:58 GMT
https://trac.sagemath.org/ticket/14549#comment:6
https://trac.sagemath.org/ticket/14549#comment:6
<p>
The leak actually already exists on python level:
</p>
<pre class="wiki">
import gc
from collections import Counter
gc.collect()
pre={id(c) for c in gc.get_objects()}
from sage.rings.polynomial.pbori import BooleanPolynomialRing
for i in range(100):
P=BooleanPolynomialRing(8, 'x')
del P
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])
</pre><p>
shows that the sage python-level polynomial rings remain in memory.
Looking at the backreferences graph:
</p>
<pre class="wiki">objgraph.show_backrefs((a for a in gc.get_objects() if type(a) is sage.rings.polynomial.pbori.BooleanPolynomialRing).next(),filename="g.png",max_depth=6)
</pre><p>
You can see there is a circular reference between
<code>sage.rings.polynomial.pbori.BooleanMonomialMonoid</code> and
<code>sage.rings.polynomial.pbori.BooleanPolynomialRing</code>. Furthermore, the polynomial ring is a construction parameter for the monoid. This puts a strong reference to the polynomial ring in the <code>CachedRepresentation</code> cache, so the cycle is kept alive.
</p>
<p>
The simple solution is to not make <code>BooleanMonomialMonoid</code> to be <a class="missing wiki">UniqueRepresentation?</a>. It probably doesn't need to be. If that's not an option, then <code>BooleanPolynomialRing</code> isn't allowed to store any references to the <code>BooleanMonomialMonoid</code> (after all, it can look it up in the <code>CachedRepresentation</code> cache ...)
</p>
<p>
This is a classic memory leak that keeps happening over and over.
</p>
<p>
(it could still be that pbori leaks underneath as well, but the construction above can already explain exploding memory use)
</p>
TicketasanteTue, 16 May 2017 19:37:08 GMT
https://trac.sagemath.org/ticket/14549#comment:7
https://trac.sagemath.org/ticket/14549#comment:7
<p>
I tried to simple remove the inheritance of <a class="missing wiki">UniqueRepresentation?</a>:
</p>
<pre class="wiki">diff --git a/src/sage/rings/polynomial/pbori.pyx b/src/sage/rings/polynomial/pbori.pyx
index 812f3b9..b6b761a 100644
--- a/src/sage/rings/polynomial/pbori.pyx
+++ b/src/sage/rings/polynomial/pbori.pyx
@@ -1835,7 +1835,7 @@ def get_var_mapping(ring, other):
return var_mapping
-class BooleanMonomialMonoid(UniqueRepresentation,Monoid_class):
+class BooleanMonomialMonoid(Monoid_class):
"""
Construct a boolean monomial monoid given a boolean polynomial
ring.
</pre><p>
but this does not seem to solve the problem for me (ie. it still leaks).
</p>
<p>
Interestingly, there seems to be no leak, when not importing <a class="missing wiki">BooleanPolynomialRing?</a> from pbori before. I guess it then calls the constructor from <code>sage/rings/polynomial/polynomial_ring_constructor.py</code>
</p>
<p>
Calling this constructor in annihilator also seems to solve the memory leak in the boolean_functions module.
</p>
TicketnbruinTue, 16 May 2017 20:55:59 GMT
https://trac.sagemath.org/ticket/14549#comment:8
https://trac.sagemath.org/ticket/14549#comment:8
<p>
That sounds like a reasonable hack for the immediate problem. It looks like <code>pbori.BooleanPolynomialRing</code> isn't <a class="missing wiki">UniqueRepresentation?</a> by itself, so calling the factory function is definitely the way to go.
</p>
<p>
Your tests suggest there needs to be more work if we actually want to solve the underlying leak (there are more polynomial rings that leak: anything that has to do with libsingular has eternal life too). With using the appropriate factory function, you will see that
</p>
<pre class="wiki">for i in range(10000):
R=BooleanPolynomialRing(8,"x%s"%i)
</pre><p>
still leaks.
</p>
TicketasanteTue, 16 May 2017 21:03:37 GMTowner, milestone changed; branch set
https://trac.sagemath.org/ticket/14549#comment:9
https://trac.sagemath.org/ticket/14549#comment:9
<ul>
<li><strong>owner</strong>
changed from <em>mvngu</em> to <em>asante</em>
</li>
<li><strong>branch</strong>
set to <em>u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-8.0</em>
</li>
</ul>
TicketgitTue, 16 May 2017 21:05:12 GMTcommit set
https://trac.sagemath.org/ticket/14549#comment:10
https://trac.sagemath.org/ticket/14549#comment:10
<ul>
<li><strong>commit</strong>
set to <em>b350237676f95b1cc666dd0347982b7c588beaa7</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=b350237676f95b1cc666dd0347982b7c588beaa7"><span class="icon"></span>b350237</a></td><td><code>hack: solving the immediate memory leak here</code>
</td></tr></table>
TicketasanteTue, 16 May 2017 21:09:39 GMTstatus changed
https://trac.sagemath.org/ticket/14549#comment:11
https://trac.sagemath.org/ticket/14549#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketasanteTue, 16 May 2017 21:11:33 GMTkeywords, description changed; author set
https://trac.sagemath.org/ticket/14549#comment:12
https://trac.sagemath.org/ticket/14549#comment:12
<ul>
<li><strong>keywords</strong>
<em>memory</em> <em>leak</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14549?action=diff&version=12">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Friedrich Wiemer</em>
</li>
</ul>
TicketnbruinWed, 17 May 2017 13:23:17 GMT
https://trac.sagemath.org/ticket/14549#comment:13
https://trac.sagemath.org/ticket/14549#comment:13
<p>
There is some related discussion on <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/21892" title="defect: Memory leak in BooleanPolynomialRing (needs_work)">#21892</a>. Apparently <code>UniqueRepresentation</code> is there because of a pickling problem and possibly we can do away with <a class="missing wiki">BooleanPolynomialRing?</a>.
</p>
<p>
One solution is to close this ticket by merging the branch here and leave <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/21892" title="defect: Memory leak in BooleanPolynomialRing (needs_work)">#21892</a> open for resolving the underlying problem.
</p>
TicketmalbFri, 28 Jul 2017 16:13:09 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/14549#comment:14
https://trac.sagemath.org/ticket/14549#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Martin Albrecht</em>
</li>
</ul>
<p>
Looks good to me.
</p>
TicketvbraunMon, 31 Jul 2017 20:18:05 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/14549#comment:15
https://trac.sagemath.org/ticket/14549#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class</em> to <em>b350237676f95b1cc666dd0347982b7c588beaa7</em>
</li>
</ul>
Ticket