Unwanted allocations when enumerating tree

I am using Jetbrains rider with a C# project and using the Dynamic Program Analysis feature when debugging and I have piece of code which is showing issues with high memory allocation when enumerating a Tree Structure.

The tree needs to be thread safe as it can be written to by another thread while enumerated.

Here is the offending code that seems to be over allocating and, the JetBrains tool seems to think that the issue is due to a Closure Object but I am not convinced, it is on the small object heap

public IEnumerator<TreeNode<T>> GetEnumerator()
{
    yield return this;

    if (this.children == null)
    {
        yield break;
    }

    // Copy the children in case the collection gets modified while reading
    var childrenCopy = new List<TreeNode<T>>(this.children);

    foreach (var child in childrenCopy)
    {
        foreach (var subChild in child)
        {
            yield return subChild;
        }
    }
}

— Update

I understand that the child copy will allocate, but once it’s out of scope I would expect it to be released and not stuck on the small object heap

Any ideas on what is going would be appreciated.

Thanks

>Solution :

The majority of allocations will be from the list copy. And this will not ensure thread safety as the list can be changed while you are doing the copy.

To fix this I would suggest using an immutable collection, like ImmutableList<T> for the children list. Adding a new node will create a new collection, i.e. Children = Children.Add(newNode). This will increase allocations when adding items, but you will not need any defensive copies when iterating.

You will also do an allocation for each object in the tree, since the iterator block itself will require an allocation. If you want to fix this you can switch to an iterative instead of recursive approach. I.e. create a stack (or queue) that you loop over, popping an item and pushing all of its childs.