We previously enabled enumeration of our immutable stacks - we should do the same for our immutable queues. Unfortunately, it’s a bit more complicated this time around. (For those looking to the solution to the puzzle posed at the end of my earlier post, you’ll need to wait until next time - but read to the end of this post for a clue.)
To begin, we’ll modify our base interface to extend
We could take the same approach as we did earlier, creating a custom implementation of
IEnumerator<T> and hooking it up to our queue. The implementation would look like this:
This approach gives us a simple way to enumerate across the content of any implementation of
IImmutableQueue<T>. I have the unit tests to prove that it works (more on those in a later post).
But there’s a real problem with this approach, one that didn’t affect us when we implemented enumeration for immutable stacks.
.Discard() the top item from an
IImmutableStack<T>, our implementations always return an existing instance. There is no heap allocation going on. However, when we
.Dequeue() the head item from an
IImmutableQueue<T>, our current implementation returns a new instance representing the smaller queue. This means that every step of enumeration we do with this implementation is going to generate debris on our object heap, forcing the garbage collector to do more work, cleaning up after us more often. This may also promote other objects into higher generations of the heap, slowing their collection when they are eventually discarded.
Fortunately, there’s a much better way - for each kind of
IImmutableQueue<T> to implement it’s own enumerator, in the same way as our stack
Enumeration of an
EmptyImmutableQueue<T> is trivial:
Enumeration of a
SimpleImmutableQueue<T> is a little more complex, but not overly so. We need to return:
Headof the queue; then
- Each of the items in
- Each of the items in
_inboundin reverse order.
This has a much lower object creation rate, leaving much less debris on our object heap and requiring garbage collection to happen much less frequently.
Is it perfect?
No, it’s not - it has a nasty flaw waiting to bite. Something that might not be discovered with test workloads, but only when production gets busy. In fact, this is the very same issue that I mentioned in my earlier post, talking about why the implementation of
SimpleImmutableQueue<T> was unsuitable for production use. Have you solved that puzzle yet?