Immutability Matters
Complex Queues

As discussed last time, the solution to our performance problem is to ensure our _inbound stack doesn’t get too large before we reverse it. This means we need to reverse it early; we can’t leave reversal until it’s needed to replace _outbound.

Once we’ve reversed the stack, we need somewhere to keep it around until the existing _outbound stack empties and needs replacing. If a lot of items are enqueued at once, we might have several intermediate stacks to keep around until needed. We need to ensure they are kept in order so that their items are fed out in the right order.

If only we had a data structure that allowed us to maintain an ordered sequence of immutable stacks, taking stacks off the head and adding stacks to the tail when needed.

Hang on, we do: IImmutableQueue<IImmutableStack>.

That’s right, our trick is to create a recursive type definition.

An incomplete definition of ComplexImmutableQueue<T> looks like this:

internal class ComplexImmutableQueue<T> : IImmutableQueue<T>
        where T : IEquatable<T>
{
    // Stack for incoming items added to the queue
    private readonly IImmutableStack<T> _inbound;

    // Stack for outgoing items ready to remove from the queue
    private readonly IImmutableStack<T> _outbound;

    // Nested buffer queue for intermediate stacks
    private readonly IImmutableQueue<IImmutableStack<T>> _buffer;

    // A complex queue is never empty
    public bool IsEmpty => false;

    // The item at the head of this queue
    public T Head { get; }

    public ComplexImmutableQueue(
        T head,
        IImmutableStack<T> inbound,
        IImmutableQueue<IImmutableStack<T>> buffer,
        IImmutableStack<T> outbound)
    {
        Head = head;
        _inbound = inbound;
        _buffer = buffer;
        _outbound = outbound;
    }
}

This is pretty much the same as our existing SimpleImmutableQueue<T> but with the addition of _buffer for keeping track of any intermediate buffers that we’ve already reversed.

We’re not going to get rid of SimpleImmutableQueue<T>, there’s no need. If our queue never gets big enough to require the intermediate buffering, we don’t need to pay the memory cost of the buffer. Instead, we’ll modify SimpleImmutableQueue<T> so that when we .Enqueue() an item that takes the _inbound queue past a threshold, we’ll promote to use a ComplexImmutableQueue<T> implementation.

Let’s walk through how this works as we add a million items. Assuming we limit the size of our _inbound stack to sixteen items, this is what our queue will look like after we’ve queued the first eighteen items:

When we go to .Enqueue() the next item, we can’t add it to the _inbound stack because the stack would exceed our threshold if it got any larger. Instead, we create a new stack for _inbound, reverse the previous one, and put it into our _buffer for later use.

As we add the remaining items to reach a million, each intermediate stack of sixteen items ends up enqueued in our buffer, and we end up with something like this:

Our first two items are held as the Head of the queue and in the _outbound stack. The last fourteen items in the _inbound stack; and all the remaining items are held in our intermediate buffer.

Here’s the code to implement this:

// Maximum size for nested buffer stacks
internal static int BufferLimit = 16;

// Implementation for ComplexImmutableQueue<T>
public IImmutableQueue<T> Enqueue(T value)
{
    if (_inbound.Count < BufferLimit)
    {
        return new SimpleImmutableQueue<T>(
            Head, _inbound.Push(value), _outbound);
    }

    var buffer = ImmutableQueue<IImmutableStack<T>>.Empty
        .Enqueue(_inbound.Reverse());
    return new ComplexImmutableQueue<T>(
        Head, ImmutableStack<T>.Empty.Push(value), buffer, _outbound);
}

The implementation for ComplexImmutableQueue<T>.Enqueue() is very similar; the only significant difference is that we don’t start with an empty intermediate _buffer, but instead use the buffer we’ve already started. The actual implementation is left as an exercise for the reader.

As discussed earlier, we need to implement IEnumerable<T> for each of our queue implementations. Fortunately, we can build upon the way we’ve previously enabled enumeration of immutable stacks:

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

    foreach (var item in _outbound)
    {
        yield return item;
    }

    foreach (var stack in _buffer)
    {
        foreach (var item in stack)
        {
            yield return item;
        }
    }

    foreach (var item in _inbound.Reverse())
    {
        yield return item;
    }
}

Updated 6 Feb: Fixed some errors in the code so the behaviour matches the discussion.