Immutability Matters
Stacks Miscellany

Before we move on to other kinds of immutable data structures, some miscellany about how we might improve on the ImmutableStack<T> we already have - or perhaps just do things differently. All of these observations were submitted by blog readers - thanks everyone for the feedback.

Renaming Empty

We created a predicate for testing to see if an ImmutableStack<T> contains any elements or not, a property called Empty.

For clarity, we might want to instead call this property IsEmpty, making it clearer to the reader that this is a query that tells us about the stack, not a command that changes it.

Renaming Discard

Our stacks have a command for throwing away the top item of the stack, revealing the item beneath (if any). We called this command Discard().

It turns out that there is considerable precedence for calling this command Pop() even though it differs from the classic definition of a queue because doesn’t return the top item.

I’m not quite sure on which side of this decision I fall - on the one hand, using a different name for the command might improve clarity, given that the semantics of the command are subtly different from the usual Pop(). But, on the other hand, developers expect to have a method called Pop() and some might be thrown if there isn’t one available.

Counting

While we have implemented IEnumerable, we haven’t implemented any explicit Count property, forcing any consumer to iterate through the stack to get the number of elements.

It may be worth adding Count as a property so that obtaining the size of the stack becomes a trivial operation - we can calculate the size of the stack in our constructor as a performance optimization.

The down side is that we’ll be increasing the memory footprint very slightly. This may have no discernable effect.

Reversing

There are some data structures that use stacks as building blocks and these sometimes require a Reverse() method that takes one stack and returns another with all the items in the reverse order.

One way to implement this would be to define it on our base interface IImmutableStack<T>. However, this would require every implementation to rewrite essentially the same algorithm; a better approach might be to create an extension method that can be used with any stack.

Being Lazy

One reader wondered whether the precalculation of the hash code in the constructor for every instance of SimpleImmutableStack was appropriate.

Performing the calculation of GetHashCode() on demand, whenever required, would reduce the size of each instance, possibly saving memory (though, only if the memory allocator isn’t rounding the size up to a boundary size anyway).

Deferring the calculation until later, by using Lazy<T> to calculate the hash code the first time it is needed, would increase memory allocation (for the instance of Lazy<T>).

In either case, using the hashcode becomes more expensive and it would probably be appropriate to remove the optimization we added to our equality testing.

On balance, I’d suggest that calculation in the constructor is appropriate - it’s a single bitwise calculation (fast), requires access to data already referenced (and therefore likely already in the processor’s memory caches), and the optimization for equality testing is beneficial.

Sealing

Should our IImmutableStack<T> implementations be marked as sealed?

Some suggest that sealing a class gives the compiler more opportunity for micro-optimization, but others contend that any benefit is so small as to be meaningless.

There is value, however, in marking the implementations as sealed from a communication perspective. Marking our implementations as sealed is an easy way to inform any maintenance developer about our intentions.

Prior post in this series:
Stack Equality

Next post in this series:
Queues