0

Im making an evolutionary algorithm and I have some problems with memory leaks. Basically I have a population consisting of trees. When I perform my crossover operation between two trees I want to swap two sub-trees between the two trees. The problem is that this preocess leaks a lot of memory which results in my program being useless for over 30-40 generations. The most important code is as follows:

The class for nodes: 

[System.Serializable]
public class TreeNode
{
    ArrayList mChildren = new ArrayList();
    TreeNode mParent;

public static TreeNode DeepClone<TreeNode>(TreeNode obj)
{
    using (var ms = new MemoryStream())
    {
        var formatter = new BinaryFormatter();
        formatter.Serialize(ms, obj);
        ms.Position = 0;

        return (TreeNode) formatter.Deserialize(ms);
    }
}

public TreeNode (TreeNode parent)
{
    mParent = parent;
}
}

The class for the trees:

[System.Serializable]
public class Tree
{
    TreeNode mRoot = new TreeNode(null);

    public static Tree DeepClone<Tree>(Tree obj)
    {
        using (var ms = new MemoryStream())
        {
            var formatter = new BinaryFormatter();
            formatter.Serialize(ms, obj);
            ms.Position = 0;

            return (Tree) formatter.Deserialize(ms);
        }
    }
}

I've been looking at How do you do a deep copy of an object in .NET (C# specifically)? for the deep copying, but Im not sure if its implemented correctly.

As for my test program: 

for (int i = 0; i < 50; i++)
{
    trees[i] = new Tree();
    trees[i].generateTree(30);
}

for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 49; j++)
    {
        trees[j].getRandomSubtree(Tree.DeepClone<Tree>(trees[j+1]));
    }
    System.GC.Collect();
}

The getRandomSubtree() function basically selects a random sub-tree from one tree and swaps it with a randomly selected sub-tree from another tree. I also make sure to update the parent reference of the sub-trees. When I run this code my program is leaking a lot of memory. If I stop making deep copys the program stops leaking memory so something is going on that I quite dont understand.

Community
  • 1
  • 1
Jesper Evertsson
  • 613
  • 9
  • 28
  • If you want to swap them, why do a deep copy? Just exchange the references. – Emond Mar 27 '14 at 11:00
  • Sorry, I forgot to mention. After I do my tournament selection I want to keep both the parents as well as create two children of them. The children are created by copying the paretns and then swaping the sub-trees. – Jesper Evertsson Mar 27 '14 at 11:08

1 Answers1

2

I don't think you want to serialize the parent field. Mark it as NonSerialized. Of course, you then need to fix this after deserialization.

Or simply set it to null before serializing:

public static TreeNode DeepClone<TreeNode>(TreeNode obj)
{
    TreeNode oldParent = obj.mParent;
    obj.mParent = null;
    using (var ms = new MemoryStream())
    {
        var formatter = new BinaryFormatter();
        formatter.Serialize(ms, obj);
        obj.mParent = oldParent;

        ms.Position = 0;

        TreeNode result = (TreeNode) formatter.Deserialize(ms);
        result.mParent = oldParent;
        return result;
    }
}
Henrik
  • 23,186
  • 6
  • 42
  • 92
  • How would I fix it after deserialization? I'm pretty new to C# and doesn't really feel comfortable with the serialization concept – Jesper Evertsson Mar 27 '14 at 11:10
  • I implemented this but now the mParent field is null for every root of a cloned sub-tree – Jesper Evertsson Mar 27 '14 at 12:14
  • Did you miss the lines `obj.mParent = oldParent;` and `result.mParent = oldParent;`? Also, for this code you should not mark `mParent` as `NonSerialized`. Sorry, if that was not clear. – Henrik Mar 27 '14 at 12:17
  • Got all the code and in TreeNode I have [System.NonSerialized] TreeNode mParent; And to clearify all the mParent fields are null in the clone, not just the roots – Jesper Evertsson Mar 27 '14 at 12:23
  • I did however have to change the line: public static TreeNode DeepClone(TreeNode obj) to public static TreeNode DeepClone(TreeNode obj) since otherwise I got errors when I tried to add your suggested changes. Don't think that would affect anything though. – Jesper Evertsson Mar 27 '14 at 12:24
  • Yes, sorry. Please remove the `NonSerialized` attribute. Otherwise, you would have to restore all `mParent` fields in the subtree. – Henrik Mar 27 '14 at 12:28
  • Oh, you wrote should NOT mark. My mistake for being blind. So ok, now the cloning works as intended but the program still leaks a lot of memory when I run the test program. So now I tried to replace the part where I swap the sub-trees with a line that just replaces the current Tree with a clone of the Tree and now it doesn't leak any memory. So this probably means that there is a problem somewhere in my swap sub-tree code... – Jesper Evertsson Mar 27 '14 at 12:35
  • Anyway, thanks for your help. I will probably make a new question with the updated problem. – Jesper Evertsson Mar 27 '14 at 15:08