Performance: Whidbey generic Queue didn't get hit with the same performance stick as the generic Stack
I think I've narrowed down the new Whidbey generic Stack class to using a linked array Performance: Linked Arrays's now and later. I figured, hey, they must have used the same features in the Queue right? Not quite, in fact the generic queue can actually be slower in some cases. You really have to understand how the old collections worked and how the new ones work. When testing the old collections you had two seprate code-paths that are important. First you have to test the collections with boxing, and that means using a value-type, such as int. Then you test them without boxing using a reference type. Just passing in an object will do for this second test. Generics should have the same performance no matter what we use, so we can just test a single code-path there (or both for completeness).
That gives us three tests, but we'll add three stack tests as well to show how the performance bars are completely different for the two collections.
Testing 100 values for 1000000 iterations
Generic Queue Usage: 00:00:11.6868048
Generic Stack Usage: 00:00:05.0773008
Queue Usage (int): 00:00:11.9672080
Queue Usage (Object): 00:00:10.6953792
Stack Usage (int): 00:00:08.5322688
Stack Usage (Object): 00:00:06.0286688
That is pretty amazing stuff. The Stack is definitely showing clear signs of being improved in terms of performance. I've already shown that in earlier articles, but the percentages between the various tests are important because you'd expect the Queue to share some of that attention to performance. Testing 100 values (enqueue and dequeue) the generic queue has slightly better performance than the boxed integer Queue... What? Hell, it should get quite a bit faster right? Even worse, the old Queue when using reference types is actually faster than the generic version. Something changed. Not sure what, but it is possible to use LinkedArray structures again to make the Queue almost as fast as the Stack. I say almost, because there are some extra features in the Queue, extra checks as you were, that take more time to resolve. As an example, you can see a multi-segment queue implementation of the Enqueue method. Each item in the linked list of arrays is of size growthSize, and we use this to allocate more arrays as needed rather than growing this value and creating increasingly larger arrays as we advance.
public void Enqueue( T value ) {
if ( tail == growthSize ) {
if ( tailList.Next == null ) {
tailList.Next = new LinkedArray<T>( growthSize, null );
}
tailList = tailList.Next;
tail = 0;
}
tailList.Data[tail++] = value;
}
Thats just the start of a performant collection, but you can start to see where the operations required are just about the same as those required for the stack, really bringing this collection into the same league in terms of performance. MS must have some data that people use stacks more than queues?