Allowing iteration without generating any garbage

Question

I have the following code in an object pool that implements the IEnumerable interface.

public IEnumerable<T> ActiveNodes
{
    get
    {
        for (int i = 0; i < _pool.Count; i++)
        {
            if (_pool[i].AvailableInPool)
            {
                yield return _pool[i];
            }
        }
    }
}

As far as I know (according to this question), this will generate garbage as the IEnumerable object will need to be collected. None of the elements in _pool will ever be collected, as the purpose of the pool is to keep references to all of them to prevent garbage creation.

Can anyone suggest a way to allow iteration over _pool so that no garbage is generated?

When iterating over pool, all of the items in pool that have AvailableInPool == true should be iterated over. Order doesn't matter.

Answer 1

Iterating items will in any 'normal' design usually result in the creation of a new enumerable object. Creating and disposing objects is very fast, so only in very special scenarios (where low latency is the top most priority) garbage collections could (I say 'could') be a problem.

A design without garbage is possible by returning structures that don't implement IEnumerable. The C# compiler can still iterate such objects, because the foreach statement uses duck typing. .NET's List<T>, for instance, takes this approach.

When using foreach over both an array and List<T>, no garbage will be generated. When using foreach on an array, C# will transform the operation to a for statement, while List<T> already implements a struct enumerator, causing the foreach to produce no garbage.

Here is a struct enumerable and struct enumerator. When you return the enumerable, the C# compiler can foreach over it:

public struct StructEnumerable<T>
{
    private readonly List<T> pool;

    public StructEnumerable(List<T> pool)
    {
        this.pool = pool;
    }

    public StructEnumerator<T> GetEnumerator()
    {
        return new StructEnumerator<T>(this.pool);
    }
}

Here is the StructEnumerator:

public struct StructEnumerator<T>
{
    private readonly List<T> pool;
    private int index;

    public StructEnumerator(List<T> pool)
    {
        this.pool = pool;
        this.index = 0;
    }

    public T Current
    {
        get
        {
            if (this.pool == null || this.index == 0)
                throw new InvalidOperationException();

            return this.pool[this.index - 1];
        }
    }

    public bool MoveNext()
    {
        this.index++;
        return this.pool != null && this.pool.Count >= this.index;
    }

    public void Reset()
    {
        this.index = 0;
    }
}

You can simply return the StructEnumerable<T> as follows:

public StructEnumerable<T> Items
{
    get { return new StructEnumerable<T>(this.pool); }
}

And C# can iterate over this with a normal foreach:

foreach (var item in pool.Items)
{
    Console.WriteLine(item);
}

Note that you can't LINQ over the item using System.Linq.Enumerable You need the IEnumerable<T> interface for that, and that involves creating enumerators and, therefore, garbage collection. You could, of course, build your own LINQ extension methods, but that will unlikely help, because that will often still result in new objects being created (when closures are being generated for used delegates).