Queue.Queue vs. collections.deque

181

Necesito una cola en la que múltiples hilos puedan poner cosas, y múltiples hilos pueden leer.

Python tiene al menos dos clases de cola, Queue.Queue y collections.deque, y la primera aparentemente usa la segunda internamente. Ambos afirman ser seguros para subprocesos en la documentación.

Sin embargo, los documentos de la cola también indican:

collections.deque es una implementación alternativa de colas ilimitadas con operaciones rápidas atómica append () y popleft () que no requieren bloqueo.

Lo que supongo que no entiendo del todo: ¿significa esto que deque no es completamente seguro para subprocesos después de todo?

Si es así, es posible que no entienda completamente la diferencia entre las dos clases. Puedo ver que Queue agrega funcionalidad de bloqueo. Por otro lado, pierde algunas características antiguas como el soporte para el operador interno.

Acceder al objeto de deque interno directamente, es

x en Queue (). deque

¿a salvo de amenazas?

Además, ¿por qué Queue emplea un mutex para sus operaciones cuando deque ya es seguro para subprocesos?

miracle2k
fuente
RuntimeError: deque mutated during iterationes lo que podría estar obteniendo es usar un dequehilo compartido entre varios hilos y sin bloqueo ...
Toine
44
@toine que no tiene nada que ver con hilos sin embargo. Puede obtener este error cada vez que agregue / elimine un dequetiempo mientras itera incluso en el mismo hilo. La única razón por la que no puede obtener este error Queuees que Queueno admite la iteración.
max

Respuestas:

281

Queue.Queuey collections.dequesirven para diferentes propósitos. Queue.Queue está destinado a permitir que diferentes hilos se comuniquen usando mensajes / datos en cola, mientras collections.dequeque simplemente está pensado como una estructura de datos. Es por eso que Queue.Queuetiene como métodos put_nowait(), get_nowait()y join(), mientras que collections.dequeno lo hace. Queue.Queueno está destinado a ser utilizado como una colección, por lo que carece de los gustos del inoperador.

Se reduce a esto: si tiene múltiples hilos y desea que puedan comunicarse sin la necesidad de bloqueos, está buscando Queue.Queue; si solo desea una cola o una cola de doble extremo como estructura de datos, use collections.deque.

Finalmente, acceder y manipular la deque interna de un Queue.Queuejuego es jugar con fuego, realmente no quieres estar haciendo eso.

Keith Gaughan
fuente
66
No, esa no es una buena idea en absoluto. Si nos fijamos en la fuente de Queue.Queue, se utiliza dequedebajo del capó. collections.dequees una colección, mientras que Queue.Queuees un mecanismo de comunicación. La sobrecarga Queue.Queuees hacerla segura. Usar dequepara comunicarse entre hilos solo conducirá a carreras dolorosas. Siempre dequeque sea seguro para subprocesos, es un feliz accidente de cómo se implementa el intérprete, y no es algo en lo que se pueda confiar. Por eso Queue.Queueexiste en primer lugar.
Keith Gaughan
2
Solo tenga en cuenta que si se está comunicando a través de hilos, está jugando con fuego usando deque. Deque es a prueba de hilos por accidente debido a la existencia de la GIL. Una implementación sin GIL tendrá características de rendimiento completamente diferentes, por lo que no es aconsejable descontar otras implementaciones. Además, ¿ha cronometrado Queue vs deque para usar en todos los hilos en lugar de un punto de referencia ingenuo de su uso en un solo hilo? Si su código es tan sensible a la velocidad de Queue vs deque, Python podría no ser el idioma que está buscando.
Keith Gaughan
3
@KeithGaughan deque is threadsafe by accident due to the existence of GIL; Es cierto que dequedepende de GIL para garantizar la seguridad de los hilos, pero no lo es by accident. La documentación oficial de Python establece claramente que deque pop*/ append*métodos son seguros para subprocesos. Por lo tanto, cualquier implementación válida de Python debe proporcionar la misma garantía (las implementaciones sin GIL tendrán que descubrir cómo hacerlo sin GIL). Puede confiar con seguridad en esas garantías.
max
2
@fantabolous a pesar de mi comentario anterior, no entiendo cómo lo usarías dequepara la comunicación. Si se ajusta popa una try/except, terminará con un bucle ocupado que consume una enorme cantidad de CPU solo esperando nuevos datos. Esto parece un enfoque terriblemente ineficiente en comparación con las llamadas de bloqueo que ofrece Queue, que aseguran que el hilo que espera los datos se suspenda y no pierda el tiempo de la CPU.
max
3
Es posible que desee leer el código fuente para Queue.Queueentonces, porque está escrito usando collections.deque: hg.python.org/cpython/file/2.7/Lib/Queue.py : utiliza variables de condición para permitir dequeque se acceda de manera eficiente sobre los límites del hilo de forma segura y eficiente. La explicación de cómo usaría un dequepara la comunicación está ahí en la fuente.
Keith Gaughan
44

Si todo lo que está buscando es una forma segura de subprocesos para transferir objetos entre subprocesos , entonces ambos funcionarían (tanto para FIFO como para LIFO). Para FIFO:

Nota:

  • Es posible que otras operaciones dequeno sean seguras para subprocesos, no estoy seguro.
  • dequeno se bloquea pop()o popleft()no puede basar su flujo de hilo de consumidor en el bloqueo hasta que llegue un nuevo artículo.

Sin embargo, parece que deque tiene una ventaja de eficiencia significativa . Estos son algunos resultados de referencia en segundos utilizando CPython 2.7.3 para insertar y eliminar elementos de 100k

deque 0.0747888759791
Queue 1.60079066852

Aquí está el código de referencia:

import time
import Queue
import collections

q = collections.deque()
t0 = time.clock()
for i in xrange(100000):
    q.append(1)
for i in xrange(100000):
    q.popleft()
print 'deque', time.clock() - t0

q = Queue.Queue(200000)
t0 = time.clock()
for i in xrange(100000):
    q.put(1)
for i in xrange(100000):
    q.get()
print 'Queue', time.clock() - t0
Jonathan
fuente
1
Afirma que "Otras operaciones dequepueden no ser seguras para subprocesos". ¿De dónde sacas eso?
Matt
@Matt - reformulado para transmitir mejor mi significado
Jonathan
3
OK gracias. Eso me impedía usar Deque porque pensé que sabías algo que yo no. Supongo que asumiré que es seguro para subprocesos hasta que descubra lo contrario.
Matt
@Matt "Las operaciones append (), appendleft (), pop (), popleft () y len (d) de la deque son seguras para subprocesos en CPython". fuente: bugs.python.org/issue15329
Filippo Vitale
7

Para obtener información, hay un ticket de Python al que se hace referencia para deque thread-safety ( https://bugs.python.org/issue15329 ). Título "aclarar qué métodos de extracción son seguros para subprocesos"

En pocas palabras aquí: https://bugs.python.org/issue15329#msg199368

Las operaciones append (), appendleft (), pop (), popleft () y len (d) de la deque son seguras para subprocesos en CPython. Los métodos de agregar tienen un DECREF al final (para los casos en que se ha configurado maxlen), pero esto sucede después de que se hayan realizado todas las actualizaciones de la estructura y se hayan restaurado los invariantes, por lo que está bien tratar estas operaciones como atómicas.

De todos modos, si no está 100% seguro y prefiere la confiabilidad sobre el rendimiento, simplemente coloque un bloqueo similar;)

Lobo malo
fuente
6

Todos los métodos de un solo elemento dequeson atómicos y seguros para subprocesos. Todos los demás métodos también son seguros para subprocesos. Cosas como len(dq), dq[4]producen valores correctos momentáneos. Pero piense, por ejemplo dq.extend(mylist): no se garantiza que todos los elementos mylistse archiven en una fila cuando otros hilos también agregan elementos en el mismo lado, pero eso generalmente no es un requisito en la comunicación entre hilos y para la tarea cuestionada.

Por lo tanto, a dequees ~ 20 veces más rápido que Queue(que usa un dequeoculto) y, a menos que no necesite la API de sincronización "cómoda" (bloqueo / tiempo de espera), la estricta maxsizeobediencia o la "Anulación de estos métodos (_put, _get, .. ) para implementar el comportamiento de subclasificación de otras organizaciones de colas , o cuando usted se ocupa de esas cosas usted mismo, entonces un simple dequees un trato bueno y eficiente para la comunicación entre subprocesos de alta velocidad.

De hecho, el uso intensivo de un mutex adicional y un método adicional, ._get()etc., Queue.pyse debe a restricciones de compatibilidad con versiones anteriores, sobre diseño pasado y falta de cuidado para proporcionar una solución eficiente para este importante problema de cuello de botella de velocidad en la comunicación entre subprocesos. Se utilizó una lista en versiones anteriores de Python, pero incluso list.append () /. Pop (0) era y es atómica y segura para subprocesos ...

kxr
fuente
3

Sumar notify_all()a cada uno deque appendy popleftda como resultado resultados mucho peores dequeque la mejora 20x lograda por el dequecomportamiento predeterminado :

deque + notify_all: 0.469802
Queue:              0.667279

@Jonathan modifica un poco su código y obtengo el punto de referencia usando cPython 3.6.2 y agrego la condición en el bucle deque para simular el comportamiento de Queue do.

import time
from queue import Queue
import threading
import collections

mutex = threading.Lock()
condition = threading.Condition(mutex)
q = collections.deque()
t0 = time.clock()
for i in range(100000):
    with condition:
        q.append(1)
        condition.notify_all()
for _ in range(100000):
    with condition:
        q.popleft()
        condition.notify_all()
print('deque', time.clock() - t0)

q = Queue(200000)
t0 = time.clock()
for _ in range(100000):
    q.put(1)
for _ in range(100000):
    q.get()
print('Queue', time.clock() - t0)

Y parece que el rendimiento está limitado por esta función condition.notify_all()

collections.deque es una implementación alternativa de colas ilimitadas con operaciones atómicas rápidas de append () y popleft () que no requieren bloqueo. docs Queue

nikan1996
fuente
2

dequees seguro para subprocesos. "operaciones que no requieren bloqueo" significa que no tiene que hacer el bloqueo usted mismo, dequese encarga de ello.

Echando un vistazo a la Queuefuente, se llama a la deque interna self.queuey utiliza un mutex para accesores y mutaciones, por Queue().queuelo que no es seguro para usar en subprocesos.

Si está buscando un operador "in", una deque o cola posiblemente no sea la estructura de datos más adecuada para su problema.

brian-brasil
fuente
1
Bueno, lo que quiero hacer es asegurarme de que no se agreguen duplicados a la cola. ¿No es esto algo que una cola podría soportar?
miracle2k
1
Probablemente sea mejor tener un conjunto separado y actualizarlo cuando agregue / elimine algo de la cola. Eso será O (log n) en lugar de O (n), pero deberá tener cuidado de mantener el conjunto y la cola sincronizados (es decir, el bloqueo).
brian-brazil
Un conjunto de Python es una tabla hash, por lo que sería O (1). Pero sí, aún tendría que hacer el bloqueo.
AFoglia
1

(parece que no tengo reputación para comentar ...) Debes tener cuidado con los métodos de deque que utilizas de diferentes hilos.

deque.get () parece ser seguro para subprocesos, pero he encontrado que hacer

for item in a_deque:
   process(item)

puede fallar si otro hilo está agregando elementos al mismo tiempo. Obtuve una RuntimeException que se quejaba de "mutar deque durante la iteración".

Consulte collectionsmodule.c para ver qué operaciones se ven afectadas por esto

Eliot Blennerhassett
fuente
Este tipo de error no es especial para hilos y seguridad principal de hilos. Sucede, por ejemplo, simplemente haciendo >>> di = {1:None} >>> for x in di: del di[x]
kxr
1
Básicamente, nunca debe recorrer algo que podría ser modificado por otro hilo (aunque en algunos casos podría hacerlo agregando su propia protección). Al igual que una cola, tiene la intención de sacar / sacar un elemento de la cola antes de procesarlo, y normalmente lo haría con un whilebucle.
fantástico