Welcome to RenEvo Sign in | Join | Help
in
Home Wiisis Blogs Forums Photos Downloads About

Developer

A bad approach to adding RemoveAt to a Queue<T>

Tonight on Stackoverflow a gentlemen asked if it would be possible to add an extension method to the Queue<T> class to remove an item by index. Anyone who has worked with this class knows that there is no Add or Remove methods, but instead a Dequeue and Enqueue pair of methods. Well, the problem with Dequeue is that it only removes an item from the end of the queue, so that's not really going to work for this guy.

"I thought of a quick and dirty solution: Inherit from the Queue class and add your own RemoveAt method."

Hey! Bloody brilliant, right? Wrong. The catch 22 is that there is no way to remove an item from the queue class itself except from the Dequeue method, which simply doesn't cut it. So to get around this I had to enumerate through all the items, add each item to a new queue, skipping the index we want to remove. Well, this is a neat solution, however it creates a new queue everytime you need to remove an item by index.

It doesn't sound so bad, but consider the code:

Custom Queue<T> class

queuea

Test Code in Main()

queueb

 

I knew as soon as I wrote this that it would be a significant performance hit, but I didn't realize just how bad until I looked a bit deeper. Essentially this means that each time RemoveAt is called, the queue is enumerated, and a new queue is created. If we have a queue with 5000 items, and we needed to remove 2500 of them, this would result in 12,502,500 calls to the Count property, and 12,410,000 calls to the Enqueue method. A lot, much? I didn’t get this data out of thin air though, I used Visual Studios performance tools, so let’s take a look at the actual benchmarks:

 

perfs

 

Ouch! Approximately 9 minutes to remove 2500 items from a queue with 5000 items.. That is definitely not performance savvy. So I ran a comparison using a generic list.

 

 

perfs2

 

4.36 milliseconds… What a time difference! So you can see that a small “innocent” “work-around” can be absolutely detrimental to your applications performance. Oops! Luckily I thought ahead of time and told the guy someone else would probably post a better solution, and it was as simple as recommending a generic List<T>. :P

Published Tuesday, February 10, 2009 2:48 AM by Dave Anderson

Comments

 

RenEvo Software and Designs - Community said:

So, I took a bit of a hiatus over the last few weeks. Catching up with friends, family, and the wife.

February 10, 2009 2:24 PM
Anonymous comments are disabled
Powered by Community Server, by Telligent Systems