Queue.Queue vs. collections.deque


181

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?


RuntimeError: deque mutated during iterationto, co możesz uzyskać, to korzystanie ze wspólnego dequemiędzy kilkoma wątkami i bez blokowania ...
Toine

4
@toine nie ma to jednak nic wspólnego z wątkami. Ten błąd można uzyskać za każdym razem, gdy dodajesz / usuwasz dequepodczas iteracji nawet w tym samym wątku. Jedynym powodem, dla którego nie można uzyskać tego błędu, Queuejest to, że Queuenie obsługuje iteracji.
maks.

Odpowiedzi:


281

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ć.


6
Nie, to wcale nie jest dobry pomysł. Jeśli spojrzysz na źródło Queue.Queue, używa ono dequepod maską. collections.dequejest zbiorem, a Queue.Queuemechanizmem komunikacji. Koszty ogólne Queue.Queuemają sprawić, że będzie wątkowo bezpieczne. Używanie dequedo komunikacji między wątkami doprowadzi tylko do bolesnych wyścigów. Ilekroć dequezdarza się, że jest to bezpieczny wątek, jest to szczęśliwy wypadek, w jaki sposób tłumacz jest implementowany, i nie można na nim polegać. Dlatego właśnie Queue.Queueistnieje.
Keith Gaughan,

2
Pamiętaj tylko, że jeśli komunikujesz się między wątkami, bawisz się ogniem za pomocą deque. deque jest wątkowo bezpieczny przez przypadek ze względu na istnienie GIL. Implementacja bez GIL będzie miała zupełnie inną charakterystykę wydajności, więc dyskontowanie innych implementacji nie jest rozsądne. Poza tym, czy mierzyłeś czas między kolejką a deque do wykorzystania we wszystkich wątkach, a nie naiwny test porównawczy jej użycia w jednym wątku? Jeśli kod jest , że czuły na prędkość kolejki vs deque, Python nie może być językiem szukasz.
Keith Gaughan,

3
@KeithGaughan deque is threadsafe by accident due to the existence of GIL; to prawda, że dequepolega na GIL w celu zapewnienia bezpieczeństwa wątków - ale tak nie jest by accident. Oficjalna dokumentacja Pythona wyraźnie stwierdza, że deque pop*/ append*metody są bezpieczne dla wątków. Tak więc każda poprawna implementacja Pythona musi zapewniać tę samą gwarancję (implementacje bez GIL będą musiały dowiedzieć się, jak to zrobić bez GIL). Możesz bezpiecznie polegać na tych gwarancjach.
maks.

2
@ Niezależnie od mojego poprzedniego komentarza, nie do końca rozumiem, jak byś użył dequedo komunikacji. Jeśli zamkniesz popsię w try/except, skończysz z zajętą ​​pętlą, która pochłonie ogromną ilość procesora, tylko czekając na nowe dane. To wydaje się być bardzo nieefektywnym podejściem w porównaniu z oferowanymi przez blokowanie wywołaniami Queue, które zapewniają, że wątek oczekujący na dane przejdzie w tryb uśpienia i nie zmarnuje czasu procesora.
maks.

3
W takim przypadku możesz chcieć przeczytać kod źródłowy Queue.Queue, ponieważ jest on napisany przy użyciu collections.deque: hg.python.org/cpython/file/2.7/Lib/Queue.py - używa zmiennych warunkowych, aby efektywnie umożliwić dequedostęp do zawijania ponad granicami gwintu bezpiecznie i skutecznie. Wyjaśnienie, w jaki sposób chcesz użyć dequedo komunikacji, znajduje się w źródle.
Keith Gaughan,

44

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:

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

1
Twierdzisz, że „Inne operacje na dequemogą nie być bezpieczne dla wątków”. Skąd to masz?
Matt

@Matt - przeformułowano, aby lepiej przekazać moje znaczenie
Jonathan

3
Ok dzięki. To powstrzymywało mnie od używania deque, ponieważ myślałem, że wiesz coś, czego nie wiedziałem. Chyba po prostu założę, że jest wątek bezpieczny, dopóki nie odkryję inaczej.
Matt

@Matt „Operacje append (), appendleft (), pop (), popleft () i len (d) deque są bezpieczne w wątku w CPython.” źródło: bugs.python.org/issue15329
Filippo Vitale

7

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ę;)


6

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 ...


3

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


2

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.


1
Chcę się upewnić, że do kolejki nie zostaną dodane żadne duplikaty. Czy nie jest to coś, co może obsługiwać kolejka?
miracle2k

1
Prawdopodobnie najlepiej byłoby mieć osobny zestaw i aktualizować go podczas dodawania / usuwania czegoś z kolejki. Będzie to O (log n) zamiast O (n), ale musisz być ostrożny, aby zachować synchronizację zestawu i kolejki (tj. Blokowanie).
brian-brazil

Zestaw Python to tablica skrótów, więc będzie to O (1). Ale tak, nadal będziesz musiał zablokować.
AFoglia,

1

(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


ten rodzaj błędu nie jest szczególny dla wątków i głównego bezpieczeństwa wątków. Zdarza się to np. Przez zrobienie >>> di = {1:None} >>> for x in di: del di[x]
kxr 19.04.17

1
Zasadniczo nigdy nie powinieneś zapętlać czegoś, co może zostać zmodyfikowane przez inny wątek (chociaż w niektórych przypadkach możesz to zrobić, dodając własną ochronę). Podobnie jak w kolejce, masz zamiar wyskoczyć / usunąć element z kolejki przed przetworzeniem i zwykle robisz to z whilepętlą.
fantaboliczny
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.