Queue.Queue vs. collections.deque

181

Preciso de uma fila na qual vários threads possam colocar coisas e vários threads possam ler.

O Python possui pelo menos duas classes de fila, Queue.Queue e collections.deque, sendo que o primeiro parece usar o último internamente. Ambos afirmam ser seguros para threads na documentação.

No entanto, os documentos da fila também declaram:

collections.deque é uma implementação alternativa de filas ilimitadas com operações atômicas append () e popleft () rápidas que não requerem bloqueio.

Acho que não entendo bem: isso significa que o deque não é totalmente seguro para threads, afinal?

Se for, posso não entender completamente a diferença entre as duas classes. Percebo que a fila adiciona funcionalidade de bloqueio. Por outro lado, perde alguns recursos de deque, como suporte para o operador.

Acessar o objeto deque interno diretamente, é

x em Queue (). deque

discussão segura?

Além disso, por que o Queue emprega um mutex para suas operações quando o deque já é seguro para threads?

miracle2k
fonte
RuntimeError: deque mutated during iterationé o que você poderia estar recebendo está usando uma compartilhada dequeentre vários fio e nenhum bloqueio ...
toine
4
@ toine que não tem nada a ver com tópicos. Você pode obter esse erro sempre que adicionar / excluir por algum dequetempo, mesmo iterando no mesmo thread. O único motivo pelo qual você não pode obter esse erro Queueé que Queueele não suporta iteração.
max

Respostas:

281

Queue.Queuee collections.dequeservir a propósitos diferentes. O Queue.Queue destina-se a permitir que diferentes threads se comuniquem usando mensagens / dados em fila, ao passo que collections.dequeé simplesmente uma estrutura de dados. É por isso que Queue.Queuetem métodos como put_nowait(), get_nowait()e join(), enquanto collections.dequenão. Queue.Queuenão se destina a ser usado como uma coleção, e é por isso que não possui os gostos do inoperador.

Tudo se resume a isso: se você tem vários threads e deseja que eles possam se comunicar sem a necessidade de bloqueios, está procurando Queue.Queue; se você quiser apenas uma fila ou uma fila dupla como uma estrutura de dados, use collections.deque.

Finalmente, acessar e manipular o deque interno de a Queue.Queueestá brincando com fogo - você realmente não quer fazer isso.

Keith Gaughan
fonte
6
Não, isso não é uma boa ideia. Se você olhar para a fonte de Queue.Queue, ele usa dequesob o capô. collections.dequeé uma coleção, enquanto Queue.Queueé um mecanismo de comunicação. A sobrecarga Queue.Queueé torná-lo seguro. Usar dequepara se comunicar entre threads só leva a corridas dolorosas. Sempre dequeque for seguro, é um feliz acidente de como o intérprete é implementado, e não algo em que se possa confiar. É por isso que Queue.Queueexiste em primeiro lugar.
precisa
2
Lembre-se de que, se você está se comunicando através de threads, está brincando com fogo usando deque. o deque é seguro por acidente devido à existência do GIL. Uma implementação sem GIL terá características de desempenho completamente diferentes, portanto, descontar outras implementações não é prudente. Além disso, você cronometrou o Fila versus o deque para uso em threads em oposição a uma referência ingênua de seu uso em um único thread? Se o seu código é que sensível à velocidade da fila vs deque, Python pode não ser o idioma que você está procurando.
Keith Gaughan
3
@KeithGaughan deque is threadsafe by accident due to the existence of GIL; é verdade que dequedepende do GIL para garantir a segurança do thread - mas não é by accident. A documentação oficial do python afirma claramente que deque pop*/ append*métodos são seguros para threads. Portanto, qualquer implementação python válida deve fornecer a mesma garantia (as implementações sem GIL terão que descobrir como fazer isso sem o GIL). Você pode confiar nessas garantias.
max
2
@fantabolous, apesar do meu comentário anterior, não entendo bem como você usaria dequepara a comunicação. Se você envolver popum try/except, você terminará com um loop ocupado consumindo uma quantidade enorme de CPU apenas aguardando novos dados. Isso parece uma abordagem terrivelmente ineficiente em comparação com as chamadas de bloqueio oferecidas por Queue, que garantem que o thread que está aguardando os dados entre em suspensão e não perca tempo com a CPU.
máx
3
Você pode querer ler o código-fonte para Queue.Queueisso, porque está escrito usando collections.deque: hg.python.org/cpython/file/2.7/Lib/Queue.py - ele usa variáveis ​​de condição para permitir dequeque os envoltórios sejam acessados com eficiência sobre os limites da rosca com segurança e eficiência. A explicação de como você usaria um dequepara comunicação está ali na fonte.
precisa
44

Se tudo que você procura é uma maneira segura de encadear a transferência de objetos entre encadeamentos , ambos funcionam (ambos para FIFO e LIFO). Para FIFO:

Nota:

  • Outras operações no dequepodem não ser seguras para threads, não tenho certeza.
  • dequenão bloqueia pop()ou, popleft()portanto, você não pode basear seu fluxo de encadeamento no bloqueio até que um novo item chegue.

No entanto, parece que o deque tem uma vantagem de eficiência significativa . Aqui estão alguns resultados de benchmark em segundos usando o CPython 2.7.3 para inserir e remover 100k itens

deque 0.0747888759791
Queue 1.60079066852

Aqui está o código de referência:

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
fonte
1
Você afirma que "Outras operações ativadas dequepodem não ser seguras para threads". De onde você tira isso?
Matt
@ Matt - reformulada para transmitir melhor o que quero dizer
Jonathan
3
Ok obrigado. Isso estava me impedindo de usar o deque porque pensei que você sabia algo que eu não sabia. Acho que vou assumir que é seguro para threads até descobrir o contrário.
Matt
@Matt "As operações append (), appendleft (), pop (), popleft () e len (d) do deque são seguras para thread no CPython." Fonte: bugs.python.org/issue15329
Filippo Vitale
7

Para obter informações, há um ticket Python referenciado para deque thread-safety ( https://bugs.python.org/issue15329 ). Título "esclarecer quais métodos de deque são seguros para threads"

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

As operações append (), appendleft (), pop (), popleft () e len (d) do deque são seguras para threads no CPython. Os métodos append possuem um DECREF no final (para casos em que maxlen foi definido), mas isso acontece após todas as atualizações de estrutura terem sido feitas e os invariantes terem sido restaurados, portanto, não há problema em tratar essas operações como atômicas.

De qualquer forma, se você não tem 100% de certeza e prefere confiabilidade ao desempenho, basta colocar um Lock;)

Lobo mau
fonte
6

Todos os métodos de elemento único ativados dequesão atômicos e seguros para threads. Todos os outros métodos também são seguros para threads. Coisas como len(dq), dq[4]produzem valores corretos momentâneos. Mas pense, por exemplo dq.extend(mylist): você não tem garantia de que todos os elementos mylistsão arquivados em uma linha quando outros threads também acrescentam elementos do mesmo lado - mas isso geralmente não é um requisito na comunicação entre threads e para a tarefa questionada.

Portanto, a dequeé ~ 20x mais rápido do que Queue(que usa um dequesob o capô) e, a menos que você não precise da API de sincronização "confortável" (bloqueio / tempo limite), a maxsizeobediência estrita ou a "Substituir esses métodos (_put, _get, .. ) para implementar o comportamento de subclasse de outras organizações de filas " , ou quando você cuida dessas coisas sozinho, um negócio simples dequeé bom e eficiente para a comunicação entre threads de alta velocidade.

De fato, o uso intenso de um método extra mutex e extra, ._get()etc., Queue.pyé devido a restrições de compatibilidade com versões anteriores, excesso de design passado e falta de cuidados em fornecer uma solução eficiente para esse importante problema de gargalo de velocidade na comunicação entre threads. Uma lista foi usada em versões mais antigas do Python - mas mesmo list.append () /. Pop (0) era & é atômica e segura para threads ...

kxr
fonte
3

Adicionando notify_all()a cada deque appende popleftresulta em muito piores resultados para dequeque a melhoria 20x alcançado por padrão dequede comportamento :

deque + notify_all: 0.469802
Queue:              0.667279

@ Jonathan modifica um pouco seu código e eu recebo o benchmark usando o cPython 3.6.2 e adiciono a condição no loop deque para simular o comportamento da fila.

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)

E parece que o desempenho limitado por esta função condition.notify_all()

collections.deque é uma implementação alternativa de filas ilimitadas com operações atômicas append () e popleft () rápidas que não requerem bloqueio. docs Fila

nikan1996
fonte
2

dequeé seguro para threads. "operações que não exigem bloqueio" significa que você não precisa fazer o bloqueio sozinho, dequeele cuida disso.

Examinando a Queuefonte, o deque interno é chamado self.queuee usa um mutex para acessadores e mutações, portanto, nãoQueue().queue é seguro para uso em threads.

Se você estiver procurando por um operador "in", uma fila ou fila provavelmente não é a estrutura de dados mais apropriada para o seu problema.

brian-brazil
fonte
1
Bem, o que eu quero fazer é garantir que nenhuma duplicata seja adicionada à fila. Isso não é algo que uma fila possa suportar?
miracle2k
1
Provavelmente seria melhor ter um conjunto separado e atualizá-lo quando você adiciona / remove algo da fila. Será O (log n) em vez de O (n), mas você terá que ter cuidado para manter o conjunto e a fila em sincronia (ou seja, travar).
brian-brazil
Um conjunto Python é uma tabela de hash, portanto seria O (1). Mas sim, você ainda teria que fazer o bloqueio.
AFoglia
1

(parece que não tenho reputação para comentar ...) Você precisa ter cuidado com quais métodos do deque você usa em diferentes threads.

deque.get () parece ser seguro para threads, mas descobri que fazer

for item in a_deque:
   process(item)

pode falhar se outro segmento estiver adicionando itens ao mesmo tempo. Eu recebi um RuntimeException que reclamou "deque foi alterado durante a iteração".

Verifique collectionsmodule.c para ver quais operações são afetadas por este

Eliot Blennerhassett
fonte
esse tipo de erro não é especial para threads e principal segurança de thread. Isso acontece, por exemplo, apenas fazendo >>> di = {1:None} >>> for x in di: del di[x]
KXR
1
Basicamente, você nunca deve fazer um loop sobre algo que possa ser modificado por outro thread (embora em alguns casos você possa fazê-lo adicionando sua própria proteção). Como uma fila, você pretende abrir / retirar um item da fila antes de processá-lo e normalmente faria isso com um whileloop.
fantabolous