queue versus list

[duncan smith]

On 19/03/2020 20:40, MRAB wrote:
> On 2020-03-19 20:08, duncan smith wrote:
>> Hello,
>>        I have generator code along the following lines,
>>
>>
>> Q = queue.Queue()
>> Q.put(x)
>> while not Q.empty():
>>      x = Q.get()
>>      if <some condition that depends on x>:
>>          yield x
>>      else:
>>        Q.put(<some value that depends on x>)
>>
>>
>> If I change it to,
>>
>>
>> Q = []
>> Q.append(x)
>> for x in Q:
>>      if <some condition that depends on x>:
>>          yield x
>>      else:
>>        Q.append(<some value that depends on x>)
>>
>>
>> then it runs approximately 3 times more quickly. I seem to remember
>> (from somewhere) that the language specification doesn't guarantee that
>> the latter will continue to work, but that it's unlikely that future
>> implementations will break it. Apart from that, is there any good reason
>> why I shouldn't use the list? Is there another approach that might avoid
>> the overhead of using a queue? Results from profiling the two
>> implementations below in case it makes anything clearer. TIA.
>>
> [snip]

Thanks MRAB and Paul,

> A number of points:
> 
> 1. I'm not sure it's a good idea to mutate a list while iterating over it.
> 

AFAICR that's the bit that depends on the implementation of lists. As
long as iteration involves incrementing an index and indexing into the
list it will work.

> 2. The example with the list retains all of the results, whereas the one
> with the queue consumes them.
> 
> 3. Queues are thread-safe because they're used for communication between
> threads, but lists aren't thread-safe; that might be something to do
> with the difference.
> 
> 4. If it doesn't need to be thread-safe, why not try deques instead?

Bingo. Performance is indistinguishable from that of the list. Thread
safety is unimportant (for my purposes), but the docs at
https://docs.python.org/2/library/collections.html#collections.deque
state "Deques support thread-safe, memory efficient appends and pops
from either side of the deque with approximately the same O(1)
performance in either direction". Looking at the output from the
profiler for my implementation with the queue it looks like a deque is
being used but there's various other stuff happening relating to thread
safety. Is the lesson from this that if all you're doing is appending
and popping, then use a deque (rather than a queue) even if you want
thread safety? (It makes quite a difference in performance for my use
case.) Cheers.

Duncan