Queue.Queue vs collections.deque

181

J'ai besoin d'une file d'attente dans laquelle plusieurs threads peuvent mettre des éléments et à partir de laquelle plusieurs threads peuvent lire.

Python a au moins deux classes de files d'attente, Queue.Queue et collections.deque, la première utilisant apparemment la seconde en interne. Les deux prétendent être thread-safe dans la documentation.

Cependant, la documentation de la file d'attente indique également:

collections.deque est une implémentation alternative de files d'attente illimitées avec des opérations atomiques rapides append () et popleft () qui ne nécessitent pas de verrouillage.

Ce que je suppose que je ne comprends pas tout à fait: cela signifie-t-il que deque n'est pas entièrement thread-safe après tout?

Si c'est le cas, je ne comprends peut-être pas entièrement la différence entre les deux classes. Je peux voir que Queue ajoute une fonctionnalité de blocage. D'autre part, il perd certaines fonctionnalités deque comme la prise en charge de l'opérateur interne.

Accéder directement à l'objet deque interne est

x dans la file d'attente (). deque

thread-safe?

Aussi, pourquoi Queue utilise-t-il un mutex pour ses opérations alors que deque est déjà thread-safe?

miracle2k
la source
RuntimeError: deque mutated during iterationest ce que vous pourriez obtenir est d'utiliser un partage dequeentre plusieurs threads et pas de verrouillage ...
toine
4
@toine qui n'a rien à voir avec les threads cependant. Vous pouvez obtenir cette erreur chaque fois que vous ajoutez / supprimez une dequeitération en cours, même dans le même thread. La seule raison pour laquelle vous ne pouvez pas obtenir cette erreur Queueest qu'elle Queuene prend pas en charge l'itération.
max

Réponses:

281

Queue.Queueet collections.dequeservent à des fins différentes. Queue.Queue est destiné à permettre à différents threads de communiquer à l'aide de messages / données en file d'attente, alors qu'il collections.dequeest simplement conçu comme une structure de données. C'est pourquoi Queue.Queuea des méthodes telles que put_nowait(), get_nowait()et join(), alors collections.dequene fonctionne pas. Queue.Queuen'est pas destiné à être utilisé comme une collection, c'est pourquoi il n'a pas les goûts de l' inopérateur.

Cela se résume à ceci: si vous avez plusieurs threads et que vous voulez qu'ils puissent communiquer sans avoir besoin de verrous, vous recherchez Queue.Queue; si vous voulez juste une file d'attente ou une file d'attente double comme structure de données, utilisez collections.deque.

Enfin, accéder et manipuler le deque interne d'un Queue.Queueest jouer avec le feu - vous ne voulez vraiment pas faire cela.

Keith Gaughan
la source
6
Non, ce n'est pas du tout une bonne idée. Si vous regardez la source de Queue.Queue, il utilise dequesous le capot. collections.dequeest une collection, tandis que Queue.Queuec'est un mécanisme de communication. La surcharge Queue.Queueest de le rendre threadsafe. Utiliser dequepour communiquer entre les threads ne mènera qu'à des courses douloureuses. Chaque fois dequequ'il est threadsafe, c'est un heureux accident de la façon dont l'interpréteur est implémenté, et non quelque chose sur lequel on peut se fier. C'est pourquoi Queue.Queueexiste en premier lieu.
Keith Gaughan
2
Gardez simplement à l'esprit que si vous communiquez entre les threads, vous jouez avec le feu en utilisant deque. deque est threadsafe par accident en raison de l'existence du GIL. Une implémentation sans GIL aura des caractéristiques de performances complètement différentes, il n'est donc pas judicieux de ne pas tenir compte des autres implémentations. En outre, avez-vous chronométré Queue vs deque pour une utilisation à travers les threads par opposition à un benchmark naïf de son utilisation dans un seul thread? Si votre code est aussi sensible à la vitesse de Queue vs deque, Python n'est peut-être pas le langage que vous recherchez.
Keith Gaughan
3
@KeithGaughan deque is threadsafe by accident due to the existence of GIL; il est vrai que dequecela s'appuie sur GIL pour garantir la sécurité des threads - mais ce n'est pas le cas by accident. La documentation officielle de python indique clairement que les méthodes deque pop*/ append*sont thread-safe. Ainsi, toute implémentation python valide doit fournir la même garantie (les implémentations sans GIL devront trouver comment faire cela sans GIL). Vous pouvez compter sur ces garanties en toute sécurité.
max
2
@fantabolous malgré mon commentaire précédent, je ne comprends pas très bien comment vous l'utiliseriez dequepour la communication. Si vous vous enroulez popdans un try/except, vous vous retrouverez avec une boucle occupée consommant une énorme quantité de CPU en attendant de nouvelles données. Cela semble être une approche horriblement inefficace par rapport aux appels de blocage proposés par Queue, qui garantissent que le thread en attente de données passera en veille et ne perdra pas de temps CPU.
max
3
Vous voudrez peut-être lire le code source pour cela Queue.Queue, car il est écrit à l'aide de collections.deque: hg.python.org/cpython/file/2.7/Lib/Queue.py - il utilise des variables de condition pour permettre efficacement l'accès à l' dequeenveloppe. au-dessus des limites de filetage de manière sûre et efficace L'explication de la façon dont vous utiliseriez un dequepour la communication est juste là dans la source.
Keith Gaughan
44

Si tout ce que vous recherchez est un moyen sûr pour les threads de transférer des objets entre les threads , les deux fonctionneraient (à la fois pour FIFO et LIFO). Pour FIFO:

Remarque:

  • D'autres opérations sur dequepeuvent ne pas être thread-safe, je ne suis pas sûr.
  • dequene bloque pas pop()ou popleft()donc vous ne pouvez pas baser votre flux de thread consommateur sur le blocage jusqu'à ce qu'un nouvel élément arrive.

Cependant, il semble que deque présente un avantage d'efficacité significatif . Voici quelques résultats de référence en quelques secondes en utilisant CPython 2.7.3 pour insérer et supprimer 100 000 éléments

deque 0.0747888759791
Queue 1.60079066852

Voici le code de référence:

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
la source
1
Vous prétendez que "D'autres opérations sur dequepeuvent ne pas être thread-safe". D'où vient ça?
Matt
@Matt - reformulé pour mieux transmettre ma signification
Jonathan
3
OK merci. Cela m'empêchait d'utiliser deque parce que je pensais que vous saviez quelque chose que je ne savais pas. Je suppose que je suppose que c'est thread-safe jusqu'à ce que je découvre le contraire.
Matt
@Matt "Les opérations append (), appendleft (), pop (), popleft () et len ​​(d) de deque sont thread-safe en CPython." source: bugs.python.org/issue15329
Filippo Vitale
7

Pour plus d'informations, il existe un ticket Python référencé pour deque thread-safety ( https://bugs.python.org/issue15329 ). Titre "clarifier quelles méthodes deque sont thread-safe"

Bottom line ici: https://bugs.python.org/issue15329#msg199368

Les opérations append (), appendleft (), pop (), popleft () et len ​​(d) de deque sont thread-safe dans CPython. Les méthodes d'ajout ont un DECREF à la fin (pour les cas où maxlen a été défini), mais cela se produit après que toutes les mises à jour de structure ont été effectuées et que les invariants ont été restaurés, il est donc normal de traiter ces opérations comme atomiques.

Quoi qu'il en soit, si vous n'êtes pas sûr à 100% et que vous préférez la fiabilité à la performance, mettez simplement un verrou similaire;)

Méchant loup
la source
6

Toutes les méthodes à un seul élément sur dequesont atomiques et thread-safe. Toutes les autres méthodes sont également thread-safe. Des choses comme len(dq), dq[4]donnent des valeurs correctes momentanées. Mais pensez par exemple à dq.extend(mylist)ceci: vous n'obtenez pas la garantie que tous les éléments dans mylistsont classés dans une ligne lorsque d'autres threads ajoutent également des éléments du même côté - mais ce n'est généralement pas une exigence dans la communication inter-thread et pour la tâche en question.

Donc, a dequeest ~ 20x plus rapide que Queue(qui utilise a dequesous le capot) et à moins que vous n'ayez pas besoin de l'API de synchronisation "confortable" (blocage / timeout), de l' maxsizeobéissance stricte ou du "Override these methods (_put, _get, ..) ) pour implémenter le comportement de sous-classification d' autres organisations de files d'attente , ou lorsque vous vous occupez de telles choses vous-même, alors un bare dequeest une bonne et efficace affaire pour la communication inter-thread à grande vitesse.

En fait, l'utilisation intensive d'un mutex supplémentaire et d' ._get()appels de méthode supplémentaires, etc. Queue.pyest due à des contraintes de compatibilité ascendante, à une sur-conception passée et au manque de soin pour fournir une solution efficace à cet important problème de goulot d'étranglement de vitesse dans la communication inter-thread. Une liste était utilisée dans les anciennes versions de Python - mais même list.append () /. Pop (0) était et est atomique et threadsafe ...

kxr
la source
3

En ajoutant notify_all()à chacun d'eux deque append, des popleftrésultats bien pires dequeque l'amélioration de 20x obtenue par le dequecomportement par défaut :

deque + notify_all: 0.469802
Queue:              0.667279

@Jonathan modifie un peu son code et j'obtiens le benchmark en utilisant cPython 3.6.2 et j'ajoute une condition dans la boucle deque pour simuler le comportement de Queue.

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)

Et il semble que les performances soient limitées par cette fonction condition.notify_all()

collections.deque est une implémentation alternative de files d'attente illimitées avec des opérations rapides atomiques append () et popleft () qui ne nécessitent pas de verrouillage. file d'attente de documents

nikan1996
la source
2

dequeest thread-safe. «opérations qui ne nécessitent pas de verrouillage» signifie que vous n'avez pas à faire le verrouillage vous-même, le deques'en charge.

En regardant la Queuesource, le deque interne est appelé self.queueet utilise un mutex pour les accesseurs et les mutations, il Queue().queuen'est donc pas sûr à utiliser pour les threads.

Si vous recherchez un opérateur "in", alors une deque ou une file d'attente n'est peut-être pas la structure de données la plus appropriée pour votre problème.

brian-brésil
la source
1
Eh bien, ce que je veux faire, c'est m'assurer qu'aucun doublon n'est ajouté à la file d'attente. N'est-ce pas quelque chose qu'une file d'attente pourrait potentiellement prendre en charge?
miracle2k
1
Il serait probablement préférable d'avoir un ensemble séparé et de le mettre à jour lorsque vous ajoutez / supprimez quelque chose de la file d'attente. Ce sera O (log n) plutôt que O (n), mais vous devrez faire attention à garder l'ensemble et la file d'attente synchronisés (c'est-à-dire le verrouillage).
brian-brazil
Un ensemble Python est une table de hachage, donc ce serait O (1). Mais oui, vous devrez toujours verrouiller.
AFoglia
1

(il semble que je n'ai pas la réputation de commenter ...) Vous devez faire attention aux méthodes de deque que vous utilisez à partir de différents threads.

deque.get () semble être threadsafe, mais j'ai trouvé que faire

for item in a_deque:
   process(item)

peut échouer si un autre thread ajoute des éléments en même temps. J'ai eu une RuntimeException qui se plaignait de "deque muté pendant l'itération".

Vérifiez collectionsmodule.c pour voir quelles opérations sont affectées par cela

Eliot Blennerhassett
la source
ce type d'erreur n'est pas spécial pour les threads et la sécurité principale des threads. Cela arrive par exemple en faisant juste >>> di = {1:None} >>> for x in di: del di[x]
kxr
1
En gros, vous ne devriez jamais boucler sur quelque chose qui pourrait être modifié par un autre thread (bien que dans certains cas vous puissiez le faire en ajoutant votre propre protection). Comme une file d'attente, vous avez l'intention de faire sortir / retirer un élément de la file d'attente avant de le traiter, et vous le feriez normalement avec une whileboucle.
fantastique