ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 13 Sep 2019 09:03:35 -0500Memory leak with matroid is_connected methodhttp://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/Hello.
I've been using Graphic Matroids to deal with some enumeration problems, where I filter a list of graphs based on their flats. Even without really undestanding what happens at low level, I could verify that the computation is faster when I build the equivalent representation of each graphic matroid using the Incidence matrix of the graph over GF(2).
One big issue that I am facing is that some memory leak is ocurring. As the size of my list of graphs grows, the ram memory got consumed until a point that my computer breaks down and restarts. My way out has been to use a bash script to keep calling the main program until I reach the end of an external text file (the input).
To force the `gc.collect()` seems to not be an option, because the program becomes really slow.
EDIT 1:
The memory leak seems to be related with the `is_connected` method. Here is a piece of my code showing two different situations:
With the use of `is_connected`:
sage: G = [g for g in graphs.nauty_geng("12 16:16 -Ct")]
sage: len(G)
11771
sage: print(get_memory_usage())
....:
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: if M.is_connected():
....: pass
....: print(get_memory_usage())
....:
3396.38671875
3418.06640625
and without:
sage: print(get_memory_usage())
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: for r in range(M.corank()):
....: for F in M.coflats(r):
....: pass
....:
....: print(get_memory_usage())
....:
3490.53515625
3490.53515625
EDIT 2:
Ok, I solved my problem by just explicitly declaring the function `is_connected` in the body of my code, instead of using the method present in the abstract matroid class. I'm not sure about why it really worked, I tried this approach because I thought it had something to do with the lists that are created by the `components` method, however I stopped investigating when I notice the memory leak vanished just by using the function. To be honest, I changed the script to not return any output (there was an option to input a certificate flag and return the components).
I'm letting the code below for the case someone faces a similar problem or has any better solution or clue about why it happened:
cpdef components(self):
B = self.basis()
components = [frozenset([e]) for e in self.groundset()]
for e in self.groundset() - B:
C = self.circuit(B | set([e]))
components2 = []
for comp in components:
if len(C & comp) != 0:
C = C | comp
else:
components2.append(comp)
components2.append(C)
components = components2
return components
cpdef is_connected(self):
comp = components(self)
if len(comp) == 1:
return True
else:
return FalseThu, 12 Sep 2019 04:20:58 -0500http://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/Answer by tmonteil for <p>Hello.</p>
<p>I've been using Graphic Matroids to deal with some enumeration problems, where I filter a list of graphs based on their flats. Even without really undestanding what happens at low level, I could verify that the computation is faster when I build the equivalent representation of each graphic matroid using the Incidence matrix of the graph over GF(2). </p>
<p>One big issue that I am facing is that some memory leak is ocurring. As the size of my list of graphs grows, the ram memory got consumed until a point that my computer breaks down and restarts. My way out has been to use a bash script to keep calling the main program until I reach the end of an external text file (the input). </p>
<p>To force the <code>gc.collect()</code> seems to not be an option, because the program becomes really slow.</p>
<p>EDIT 1:</p>
<p>The memory leak seems to be related with the <code>is_connected</code> method. Here is a piece of my code showing two different situations:</p>
<p>With the use of <code>is_connected</code>:</p>
<pre><code>sage: G = [g for g in graphs.nauty_geng("12 16:16 -Ct")]
sage: len(G)
11771
sage: print(get_memory_usage())
....:
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: if M.is_connected():
....: pass
....: print(get_memory_usage())
....:
3396.38671875
3418.06640625
</code></pre>
<p>and without:</p>
<pre><code>sage: print(get_memory_usage())
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: for r in range(M.corank()):
....: for F in M.coflats(r):
....: pass
....:
....: print(get_memory_usage())
....:
3490.53515625
3490.53515625
</code></pre>
<p>EDIT 2:</p>
<p>Ok, I solved my problem by just explicitly declaring the function <code>is_connected</code> in the body of my code, instead of using the method present in the abstract matroid class. I'm not sure about why it really worked, I tried this approach because I thought it had something to do with the lists that are created by the <code>components</code> method, however I stopped investigating when I notice the memory leak vanished just by using the function. To be honest, I changed the script to not return any output (there was an option to input a certificate flag and return the components).</p>
<p>I'm letting the code below for the case someone faces a similar problem or has any better solution or clue about why it happened:</p>
<pre><code>cpdef components(self):
B = self.basis()
components = [frozenset([e]) for e in self.groundset()]
for e in self.groundset() - B:
C = self.circuit(B | set([e]))
components2 = []
for comp in components:
if len(C & comp) != 0:
C = C | comp
else:
components2.append(comp)
components2.append(C)
components = components2
return components
cpdef is_connected(self):
comp = components(self)
if len(comp) == 1:
return True
else:
return False
</code></pre>
http://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/?answer=47880#post-id-47880I can not reproduce you problem, you should provide more details, see:
sage: I = random_matrix(ZZ,10,10)
sage: M = Matroid(matrix = I, ring = GF(2))
sage: for _ in range(10):
....: for i in range(0, M.corank() + 1):
....: for F in M.coflats(i):
....: pass
....: get_memory_usage()
....:
8393.46875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
**EDIT** There is indeed a memory leak in the `components` method of `BasisExchangeMatroid`, a call to `sig_free` was missing. This is now [trac ticket 28498](https://trac.sagemath.org/ticket/28498), thanks for reporting.
So, you can wait for a next release that the fix is incorporated into Sage, or if you built Sage from Source, you can just add the missing line and recompile.Fri, 13 Sep 2019 05:49:11 -0500http://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/?answer=47880#post-id-47880Comment by fmorlin for <p>I can not reproduce you problem, you should provide more details, see:</p>
<pre><code>sage: I = random_matrix(ZZ,10,10)
sage: M = Matroid(matrix = I, ring = GF(2))
sage: for _ in range(10):
....: for i in range(0, M.corank() + 1):
....: for F in M.coflats(i):
....: pass
....: get_memory_usage()
....:
8393.46875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
8393.71875
</code></pre>
<p><strong>EDIT</strong> There is indeed a memory leak in the <code>components</code> method of <code>BasisExchangeMatroid</code>, a call to <code>sig_free</code> was missing. This is now <a href="https://trac.sagemath.org/ticket/28498">trac ticket 28498</a>, thanks for reporting.</p>
<p>So, you can wait for a next release that the fix is incorporated into Sage, or if you built Sage from Source, you can just add the missing line and recompile.</p>
http://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/?comment=47883#post-id-47883Thank you for your answer! I verified and in fact there was no memory leak occurring in the first code snippet I posted. The issue appears to be related with the `is_connected()` method.Fri, 13 Sep 2019 09:03:35 -0500http://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/?comment=47883#post-id-47883