File.File d'attente vs collections.deque

Si tout ce que vous cherchez est un moyen thread-safe de transférer des objets entre les threads, alors les deux fonctionneraient (à la fois pour FIFO et LIFO). Pour FIFO:

• Queue.put() et Queue.get() sont thread-safe
• deque.append() et deque.popleft() sont thread-safe

Remarque:

• D'autres opérations sur deque pourraient ne pas être thread safe, Je ne suis pas sûr.
• deque ne bloque pas sur pop() ou popleft() de sorte que vous ne pouvez pas baser votre flux de thread consommateur sur blocage jusqu'à ce qu'un nouvel élément arrive.

Cependant, il semble que deque a un avantage d'efficacité significatif . Voici quelques résultats de benchmark en quelques secondes en utilisant CPython 2.7.3 pour insérer et supprimer des éléments 100k

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

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"

Ligne de Fond ici: https://bugs.python.org/issue15329#msg199368

Append(), appendleft(), pop(), popleft () et Len (d) les opérations sont thread-safe dans Disponible. Les méthodes append ont un DECREF à la fin (pour les cas où maxlen a été défini), mais ceci arriver après toutes les mises à jour de la structure ont été faites et le les invariants ont été restaurés, il est donc correct de traiter ces opérations comme atomique.

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

deque est Fil-sûr. "opérations qui ne nécessitent pas de verrouillage" signifie que vous n'avez pas à faire le verrouillage vous-même, le deque s'en occupe.

Les Queue source, l'interne deque est appelé self.queue et utilise un mutex pour les accesseurs et les mutations, de sorte que Queue().queue est pas thread-safe à utiliser.

Si vous recherchez un opérateur "in", 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.

deque 0.469802
Queue 0.667279

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

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 illimitées avec des opérations atomic append() et popleft () rapides qui ne nécessitent pas de verrouillage. file d'attente des documents

(Il semble que je n'ai pas de réputation à commenter...) Vous devez faire attention aux méthodes de la 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 exception RuntimeException qui se plaignait de "deque muté pendant l'itération".

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

Toutes les méthodes à un élément sur deque sont atomiques et sans thread. Toutes les autres méthodes sont thread-safe aussi. Des choses comme len(dq), dq[4] rendement des valeurs correctes momentanées. Mais pensez par exemple à dq.extend(mylist): vous n'obtenez pas une garantie que tous les éléments de 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.

Pour un deque est ~20x plus vite 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), le strict maxsize obeyance ou le " remplace ces méthodes (_put, _get,..) pour implémenter d'autres organisations de file d'attente" comportement de sous-classe, ou lorsque vous prenez soin de telles choses vous-même, alors un deque nu est un bon accord et efficace pour la communication inter-thread à grande vitesse.

En fait, l'utilisation intensive d'un mutex supplémentaire et d'une méthode supplémentaire ._get() etc. les appels de méthode dans Queue.py sont dus aux contraintes de rétrocompatibilité, à la sur-conception passée et au manque de soin pour fournir une solution efficace à ce problème important de goulot d'étranglement de vitesse dans la communication inter-thread. Une liste a été utilisée dans les anciennes versions de Python-mais même list.annexer()/.pop(0) était & est atomique et threadsafe ...