Queues - Is Infinity all right?

[Peter Hansen]

Anand Pillai wrote:
> 
> The standard Python Queue module, allows to generate queues that
> have no size limit, by passing the size argument as <= 0.
> 
> q = Queue(0)
> 
> In a multithreaded application, these queues could be useful
> when you have many threads using the queue for data access
> and synchronization.
> 
> Is there a performance hit when one uses an 'infinite' queue
> when compared to a queue of fixed size?
> 
> Of course it should depend upon the O(n) of the Queue data structure,
> how the time of access (get/put) varies with the number of items in
> it.
> 
> I would like to have some light on this. Is it constant, O(n) or
> a higher order?

Checking the source, Queue is implemented as a sophisticated wrapper
around a standard Python list [].  That means adding an item is 
amortized O(1), while removing one is O(n).

That said, I'd consider using a fixed queue only when I was greatly
concerned about whether my consumer thread was going to be able to
keep up with my producer thread(s), and was therefore concerned about
overflowing memory with unconsumed input.

In other words, I'd worry more about the robustness of the app
than about optimizing it before it worked...

-Peter