Ask Your Question
4

Memory leak with matroid is_connected method

asked 2019-09-12 04:20:58 -0500

fmorlin gravatar image

updated 2019-09-15 07:14:02 -0500

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 False
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2019-09-13 05:49:11 -0500

tmonteil gravatar image

updated 2019-09-15 06:07:47 -0500

I 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, 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.

edit flag offensive delete link more

Comments

Thank 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.

fmorlin gravatar imagefmorlin ( 2019-09-13 09:03:35 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-09-12 04:20:58 -0500

Seen: 91 times

Last updated: Sep 15