Fastest way to iterate over a stack in c#

Question

I feel that using GetEnumerator() and casting IEnumerator.Current is expensive. Any better suggestions?

I'm open to using a different data structure if it offers similiar capabilities with better performance.

After thought:
Would a generic stack be a better idea so that the cast isn't necessary?

Answer 1

Yes, using a generic stack will spare the cast.

Answer 2

If you need the functionality of a Stack (as apposed to a List, or some other colleciton type), then yes, use a generic stack. This will speed things up a bit as the compiler will skip the casting at runtime (because it's garunteed at compile time).

Stack<MyClass> stacky = new Stack<MyClass>();

foreach (MyClass item in stacky)
{
    // this is as fast as you're going to get.
}

Answer 3

enumerating over a generic IEnumerable<T> or IEnumerator<T> doesn't doesn't create a cast if the iterating variable is of type T, so yes using the generic is going to be faster in most cases, but generics have some very subtle issues, especially when used with value types.

Rico Mariani (Microsoft performance architect) has some posts detailing the differences and the underpinnings

• Six Questions about Generics and Performance
• Performance Quiz #7 -- Generics Improvements and Costs
• Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Answer 4

Have you done any benchmarks, or are they just gut feelings?

If you think that the majority of the processing time is spent looping through stacks you should benchmark it and make sure that that is the case. If it is, you have a few options.

1. Redesign the code so that the looping isn't necessary
2. Find a faster looping construct. (I would recommend generics even though it wouldn't matter that much. Again, do benchmarks).

EDIT:

Examples of looping that might not be necessary are when you try to do lookups in a list or match two lists or similar. If the looping takes a long time, see if it make sense to put the lists into binary trees or hash maps. There could be an initial cost of creating them, but if the code is redesigned you might get that back by having O(1) lookups later on.

Answer 5

An alternative to creating an enumerator is to use the ToArray method, and then iterate over the array. The stack iterator causes some slight overhead for checking whether the stack has been modified, whereas iteration over the array would be fast. However, there is of course the overhead of creating the array in the first place. As mats says, you should benchmark the alternatives.

Answer 6

Stack<T> (with foreach) would indeed save the cast, but actually boxing isn't all that bad in the grand scheme of things. If you have performance issues, I doubt this is the area where you can add much value. Use a profiler, and focus on real problems - otherwise this is premature.

Note that if you only want to read the data once (i.e. you are happy to consume the stack), then this may be quicker (avoids the overhead of an enumerator); YMMV.

    Stack<T> stack = null;
    while (stack.Count > 0)
    {
        T value = stack.Pop();
        // process value
    }