Queue.Queue vs. collections.deque

Potrzebuję kolejki, w której wiele wątków może umieszczać różne rzeczy, z których wiele wątków może czytać.

Python ma co najmniej dwie klasy kolejek, Queue.Queue i collections.deque, przy czym ta pierwsza najwyraźniej wykorzystuje tę drugą wewnętrznie. Oba twierdzą, że są bezpieczne w wątku w dokumentacji.

Jednak dokumenty kolejki również stwierdzają:

collections.deque to alternatywna implementacja niezwiązanych kolejek z szybkimi atomowymi operacjami append () i popleft (), które nie wymagają blokowania.

Co chyba nie do końca rozumiem: czy to znaczy, że deque nie jest w pełni bezpieczny dla wątków?

Jeśli tak, może nie do końca rozumiem różnicę między dwiema klasami. Widzę, że Kolejka dodaje funkcje blokowania. Z drugiej strony traci niektóre funkcje deque, takie jak wsparcie dla operatora.

Bezpośredni dostęp do wewnętrznego obiektu deque jest

x w Queue (). deque

bezpieczny dla wątków?

Ponadto, dlaczego Queue używa muteksu do swoich operacji, skoro deque jest już bezpieczny dla wątków?

Queue.Queuei collections.dequesłużą różnym celom. Queue.Queue jest przeznaczony do umożliwienia komunikacji między różnymi wątkami za pomocą wiadomości / danych w kolejce, podczas gdy collections.dequejest po prostu przeznaczony jako struktura danych. Dlatego Queue.Queuema metod, takich jak put_nowait(), get_nowait()i join(), natomiast collections.dequenie. Queue.Queuenie jest przeznaczony do wykorzystania jako kolekcja, dlatego brakuje mu tego inoperatora.

Sprowadza się to do tego: jeśli masz wiele wątków i chcesz, aby mogły komunikować się bez potrzeby blokowania, szukasz Queue.Queue; jeśli chcesz po prostu kolejki lub kolejki podwójnie zakończonej jako struktury danych, użyj collections.deque.

Wreszcie, dostęp do wewnętrznego deque i manipulowanie nim Queue.Queueto zabawa z ogniem - naprawdę nie chcesz tego robić.

Jeśli wszystko, czego szukasz, to bezpieczny dla wątków sposób przenoszenia obiektów między wątkami , oba działałyby (zarówno dla FIFO, jak i LIFO). W przypadku FIFO:

• Queue.put()i Queue.get()są bezpieczne dla wątków
• deque.append()i deque.popleft()są bezpieczne dla wątków

Uwaga:

• Inne operacje na deque mogą nie być bezpieczne dla wątków, nie jestem pewien.
• dequenie blokuje się na pop()lubpopleft() nie można więc oprzeć przepływ wątek konsumentów na blokowanie aż nowa pozycja przybywa.

Wydaje się jednak, że deque ma znaczną przewagę wydajności . Oto kilka wyników testu porównawczego w sekundach przy użyciu CPython 2.7.3 do wstawiania i usuwania 100 000 elementów

deque 0.0747888759791
Queue 1.60079066852

Oto kod testu porównawczego:

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

Aby uzyskać informacje, istnieje bilet w języku Python, do którego odwołuje się deque thread-safety ( https://bugs.python.org/issue15329 ). Tytuł „wyjaśnij, które metody deque są bezpieczne dla wątków”

Podsumowując: https://bugs.python.org/issue15329#msg199368

Operacje append (), appendleft (), pop (), popleft () i len (d) deque są bezpieczne w wątku w CPython. Metody dołączania mają na końcu DECREF (w przypadkach, w których ustawiono maksymalny poziom), ale dzieje się tak po dokonaniu wszystkich aktualizacji struktury i przywróceniu niezmienników, więc można traktować te operacje jako atomowe.

W każdym razie, jeśli nie jesteś w 100% pewien i wolisz niezawodność od wydajności, po prostu wstaw blokadę;)

Wszystkie metody jednoelementowe dequesą atomowe i bezpieczne dla wątków. Wszystkie pozostałe metody są również wątkowo bezpieczne. Rzeczy takie len(dq), jak dq[4]chwilowe poprawne wartości. Ale pomyśl np. O dq.extend(mylist): nie otrzymujesz gwarancji, że wszystkie elementy wmylist są zapisywane w rzędzie, gdy inne wątki również dołączają elementy po tej samej stronie - ale zwykle nie jest to wymagane w komunikacji między wątkami i dla kwestionowanego zadania.

Tak więc a dequejest ~ 20 razy szybszy niż Queue(który używa dequemaskowania) i chyba, że ​​nie potrzebujesz „wygodnego” API synchronizacji (blokowanie / maxsizeprzekroczenie limitu czasu), ścisłego przestrzegania lub „Zastąp te metody (_put, _get, .. ), aby wdrożyć zachowanie podklasowania innych organizacji kolejek lub gdy sam zajmiesz się takimi sprawami, dequeto dobry i skuteczny sposób na szybką komunikację między wątkami.

W rzeczywistości duże użycie dodatkowej metody mutex i dodatkowej metody ._get()itp. Queue.pyJest spowodowane ograniczeniami kompatybilności wstecznej, przeprojektowaniem w przeszłości i brakiem dbałości o zapewnienie skutecznego rozwiązania tego ważnego problemu wąskiego gardła w komunikacji między wątkami. Lista była używana w starszych wersjach Pythona - ale nawet list.append () /. Pop (0) był i jest atomowy i bezpieczny dla wątków ...

Dodanie notify_all()do każdegodeque append i popleftwyników w znacznie gorszych wyników dequeniż poprawa 20x osiągnąć domyślnego dequezachowania :

deque + notify_all: 0.469802
Queue:              0.667279

@Jathanathan zmodyfikuje trochę swój kod, a ja otrzymuję test porównawczy za pomocą cPython 3.6.2 i dodam warunek w pętli deque, aby zasymulować zachowanie kolejki.

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)

I wydaje się, że wydajność ograniczona przez tę funkcję condition.notify_all()

collections.deque to alternatywna implementacja niezwiązanych kolejek z szybkimi atomowymi operacjami append () i popleft (), które nie wymagają blokowania. kolejka dokumentów

dequejest bezpieczny dla wątków. „Operacje, które nie wymagają blokowania” oznaczają, że nie musisz sam blokować, dequezajmuje się tym.

Patrząc na Queueźródło, wywoływana jest wewnętrzna deque self.queuei używa muteksu dla akcesoriów i mutacji, więc tak nieQueue().queue jest bezpieczny w wątkach.

Jeśli szukasz operatora „w”, deque lub kolejka prawdopodobnie nie są najbardziej odpowiednią strukturą danych dla twojego problemu.

(wygląda na to, że nie mam reputacji do komentowania ...) Musisz uważać, jakich metod deque używasz z różnych wątków.

deque.get () wydaje się być wątkowo bezpieczny, ale znalazłem, że to działa

for item in a_deque:
   process(item)

może się nie powieść, jeśli inny wątek dodaje elementy w tym samym czasie. Dostałem wyjątek RuntimeException, który narzekał „deque zmutowany podczas iteracji”.

Sprawdź kolekcjemodule.c, aby zobaczyć, na które operacje ma to wpływ