Queue.Queue vs. collections.deque

Question

J'ai besoin d'une file d'attente dans laquelle plusieurs threads peuvent mettre des choses, et dans laquelle plusieurs threads peuvent lire.

Python possède au moins deux classes de files d'attente, Queue.Queue y collections.deque Le premier semble utiliser le second en interne. Les deux prétendent être thread-safe dans la documentation.

Cependant, la documentation sur les files d'attente indique également :

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

Ce que je ne comprends pas très bien : Est-ce que cela signifie que deque n'est pas totalement thread-safe après tout ?

Si c'est le cas, je ne comprends peut-être pas bien la différence entre les deux classes. Je peux voir que Queue ajoute une fonctionnalité de blocage. D'un autre côté, elle perd certaines fonctionnalités deque comme le support de l'in-operator.

Accéder directement à l'objet interne deque, c'est

x dans Queue().deque

thread-safe ?

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

Answer 1

Queue.Queue y collections.deque servent des objectifs différents. Queue.Queue est destiné à permettre à différents threads de communiquer en utilisant des messages/données mis en file d'attente, alors que collections.deque est simplement conçu comme une structure de données. C'est pourquoi Queue.Queue a des méthodes comme put_nowait() , get_nowait() y join() alors que collections.deque ne le fait pas. Queue.Queue n'est pas destiné à être utilisé comme une collection, c'est pourquoi il n'est pas doté des éléments tels que l'onglet in opérateur.

En résumé, si vous avez plusieurs fils d'exécution et que vous voulez qu'ils puissent communiquer sans avoir besoin de verrous, il vous faut Queue.Queue ; si vous voulez simplement une file d'attente ou une file d'attente à double extrémité comme structure de données, utilisez collections.deque .

Enfin, l'accès et la manipulation de la deque interne d'une Queue.Queue c'est jouer avec le feu - vous ne voulez vraiment pas faire ça.

Answer 2

Si tout ce que vous cherchez est un moyen sûr de transférer des objets entre les threads alors les deux fonctionneraient (aussi bien pour le FIFO que pour le LIFO). Pour le FIFO :

• Queue.put() y Queue.get() sont à l'abri des fils
• deque.append() y deque.popleft() sont à l'abri des fils

Note :

• Autres opérations sur deque n'est peut-être pas sûr, je ne suis pas sûr.
• deque ne bloque pas sur pop() o popleft() donc vous ne pouvez pas baser votre flux de consommation sur le blocage jusqu'à ce qu'un nouvel élément arrive.

Cependant, il semble que deque a un avantage significatif en termes d'efficacité . Voici quelques résultats de référence en secondes en utilisant CPython 2.7.3 pour insérer et supprimer 100k é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

Answer 3

Pour information, il existe un ticket Python référencé pour la thread-safety deque ( https://bugs.python.org/issue15329 ). Titre "clarifier les méthodes deque qui sont thread-safe".

La ligne de fond ici : https://bugs.python.org/issue15329#msg199368

Les opérations append(), appendleft(), pop(), popleft() et len(d) du deque sont thread-safe en CPython. Les méthodes append ont un DECREF à la fin (pour les cas où maxlen a été défini), mais cela se mais cela se produit après que toutes les mises à jour de la structure aient été effectuées et que les invariants aient été restaurés. et que les invariants ont été restaurés, il est donc correct de traiter ces opérations comme 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 like Lock ;)

Answer 4

Toutes les méthodes à élément unique sur deque sont atomiques et sans risque pour les fils. Toutes les autres méthodes sont également thread-safe. Des choses comme len(dq) , dq[4] donnent des valeurs momentanément correctes. Mais pensez, par exemple, à dq.extend(mylist) : vous n'obtenez pas la garantie que tous les éléments dans mylist sont classés dans une rangée 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 interrogée.

Donc un deque est ~20x plus rapide que Queue (qui utilise un deque sous le capot) et, à moins que vous n'ayez pas besoin de l'API de synchronisation "confortable" (blocage / timeout), l'API de synchronisation stricte est la meilleure solution. maxsize l'obéissance ou la "Remplacez ces méthodes (_put, _get, ..) pour mettre en œuvre d'autres organisations de file d'attente". comportement de sous-classification, ou lorsque vous vous occupez vous-même de ces choses, alors une simple deque est une solution efficace pour la communication inter-filière à grande vitesse.

En fait, l'utilisation intensive d'un mutex supplémentaire et d'une méthode supplémentaire ._get() etc. dans les appels de méthode de Queue.py est due à des contraintes de rétrocompatibilité, à une conception excessive et à un manque de soin pour fournir une solution efficace à cet important problème de goulot d'étranglement dans la communication inter-filière. Une liste était utilisée dans les anciennes versions de Python - mais même list.append()/.pop(0) était et est atomique et threadsafe ...

Answer 5

Ajout de notify_all() à chaque deque append y popleft donne des résultats bien pires pour deque que l'amélioration de 20x réalisée par défaut deque comportement :

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 en ajoutant une condition dans la boucle deque pour simuler le comportement 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)

Et il semble que la performance limitée par cette fonction condition.notify_all()

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