Którego kontenera STL powinienem użyć do FIFO?

Który pojemnik STL najlepiej pasowałby do moich potrzeb? Zasadniczo mam pojemnik o szerokości 10 elementów, w którym ciągle wprowadzam push_backnowe elementy, podczas pop_frontgdy najstarszy element (około milion razy).

Obecnie używam std::dequedo tego zadania, ale zastanawiałem się, czy a std::listbyłoby bardziej wydajne, ponieważ nie musiałbym zmieniać swojej alokacji (a może mylę std::dequea std::vector?). A może jest jeszcze bardziej wydajny pojemnik na moje potrzeby?

PS Nie potrzebuję dostępu swobodnego

Ponieważ istnieje mnóstwo odpowiedzi, możesz być zdezorientowany, ale podsumowując:

Użyj std::queue. Powód jest prosty: jest to struktura FIFO. Chcesz FIFO, używasz std::queue.

Sprawia, że ​​twój zamiar staje się jasny dla innych, a nawet dla ciebie. A std::listalbo std::dequenie. Lista może wstawiać i usuwać w dowolnym miejscu, co nie jest tym, co ma robić struktura FIFO, a dequemoże dodawać i usuwać z dowolnego końca, czego również nie może zrobić struktura FIFO.

Dlatego powinieneś użyć queue.

Teraz zapytałeś o wydajność. Po pierwsze, zawsze pamiętaj o tej ważnej zasadzie: najpierw dobry kod, na końcu wydajność.

Powód jest prosty: ludzie, którzy dążą do wydajności przed czystością i elegancją, prawie zawsze kończą pracę na końcu. Ich kod staje się bzdurą, ponieważ porzucili wszystko, co dobre, aby naprawdę nic z tego nie wyciągnąć.

Pisząc najpierw dobry, czytelny kod, większość problemów z wydajnością rozwiąże się sama. A jeśli później stwierdzisz, że brakuje wydajności, możesz teraz łatwo dodać profiler do ładnego, czystego kodu i dowiedzieć się, gdzie jest problem.

To wszystko powiedział, std::queueto tylko adapter. Zapewnia bezpieczny interfejs, ale używa innego kontenera w środku. Możesz wybrać ten podstawowy kontener, a to zapewnia dużą elastyczność.

Więc jakiego podstawowego kontenera należy użyć? Wiemy, że std::listi std::dequeobaj zapewniają niezbędne funkcje ( push_back(), pop_front(), i front()), więc jak możemy zdecydować?

Po pierwsze, zrozum, że przydzielanie (i zwalnianie) pamięci nie jest na ogół szybkim zadaniem, ponieważ wymaga wyjścia do systemu operacyjnego i poproszenia go o zrobienie czegoś. A listmusi przydzielać pamięć za każdym razem, gdy coś jest dodawane i zwalniać ją, gdy zniknie.

Z dequedrugiej strony A przydziela porcje. Będzie przydzielać rzadziej niż plik list. Potraktuj to jako listę, ale każdy fragment pamięci może zawierać wiele węzłów. (Oczywiście sugerowałbym, aby naprawdę nauczyć się, jak to działa ).

Tak więc samo z tym dequepowinno działać lepiej, ponieważ nie radzi sobie tak często z pamięcią. W połączeniu z faktem, że obsługujesz dane o stałym rozmiarze, prawdopodobnie nie będzie trzeba ich przydzielać po pierwszym przejściu przez dane, podczas gdy lista będzie stale alokować i zwalniać.

Drugą rzeczą do zrozumienia jest wydajność pamięci podręcznej . Wychodzenie do pamięci RAM jest powolne, więc gdy procesor naprawdę tego potrzebuje, wykorzystuje ten czas najlepiej, zabierając z powrotem fragment pamięci do pamięci podręcznej. Ponieważ a dequealokuje w fragmentach pamięci, jest prawdopodobne, że dostęp do elementu w tym kontenerze spowoduje, że procesor CPU przywróci również resztę kontenera. Teraz dalszy dostęp do pliku dequebędzie szybki, ponieważ dane są w pamięci podręcznej.

W przeciwieństwie do listy, na której dane są przydzielane pojedynczo. Oznacza to, że dane mogą być rozproszone po całym miejscu w pamięci, a wydajność pamięci podręcznej będzie niska.

Biorąc to pod uwagę, a dequepowinno być lepszym wyborem. Dlatego jest to domyślny kontener podczas korzystania z pliku queue. To powiedziawszy, nadal jest to tylko (bardzo) wyedukowane przypuszczenie: będziesz musiał sprofilować ten kod, używając dequew jednym teście, a listw drugim, aby naprawdę wiedzieć na pewno.

Ale pamiętaj: spraw, aby kod działał z czystym interfejsem, a następnie martw się o wydajność.

Jan obawia się, że zawinięcie listlub dequespowoduje spadek wydajności. Po raz kolejny ani on, ani ja nie możemy powiedzieć na pewno bez profilowania go sami, ale są szanse, że kompilator będzie wbudowywał wywołania, które queuewykonuje. To znaczy, kiedy powiesz queue.push(), tak naprawdę powie queue.container.push_back(), całkowicie pomijając wywołanie funkcji.

Po raz kolejny jest to tylko zgadywanie, ale użycie a queuenie obniży wydajności w porównaniu z używaniem podstawowego kontenera surowego. Jak powiedziałem wcześniej, używaj queue, ponieważ jest czysty, łatwy w użyciu i bezpieczny, a jeśli to naprawdę staje się profilem problemu i testem.

Sprawdź std::queue. Otacza podstawowy typ kontenera, a kontener domyślny to std::deque.

Tam, gdzie wydajność naprawdę ma znaczenie, sprawdź bibliotekę buforów cyklicznych Boost .

Ciągle push_backnowe elementy przy pop_frontnajstarszym elemencie (około miliona razy).

Milion to naprawdę niewielka liczba w informatyce. Jak sugerowali inni, użyj std::queuejako pierwszego rozwiązania. W mało prawdopodobnym przypadku, gdy będzie to zbyt wolne, zidentyfikuj wąskie gardło za pomocą profilera (nie zgaduj!) I zaimplementuj ponownie, używając innego kontenera z tym samym interfejsem.

Dlaczego nie std::queue? Wszystko, co ma, to push_backi pop_front.

Kolejka jest prawdopodobnie prostszy interfejs niż deque ale dla takiego małego liście, różnica w wydajności jest prawdopodobnie znikomy.

To samo dotyczy listy . Wszystko zależy od tego, jakiego API chcesz.

Użyj a std::queue, ale pamiętaj o kompromisach wydajności dwóch Containerklas standardowych .

Domyślnie std::queuejest to adapter na wierzchu std::deque. Zwykle daje to dobrą wydajność, gdy masz małą liczbę kolejek zawierających dużą liczbę wpisów, co jest prawdopodobnie częstym przypadkiem.

Jednak nie bądź ślepy na implementację std :: deque . Konkretnie:

„… deki zwykle mają duży minimalny koszt pamięci; deque przechowujący tylko jeden element musi przydzielić swoją pełną wewnętrzną tablicę (np. 8 razy większy rozmiar obiektu w 64-bitowej bibliotece libstdc ++; 16 razy większy niż rozmiar obiektu lub 4096 bajtów, w zależności od tego, która z tych wartości jest większa , w 64-bitowym libc ++). ”

Aby to zlikwidować, zakładając, że pozycja kolejki jest czymś, co chciałbyś umieścić w kolejce, tj. Ma stosunkowo mały rozmiar, to jeśli masz 4 kolejki, z których każda zawiera 30 000 wpisów, std::dequeimplementacja będzie opcją z wyboru. I odwrotnie, jeśli masz 30000 kolejek, z których każda zawiera 4 wpisy, wtedy jest więcej niż prawdopodobne, że std::listimplementacja będzie optymalna, ponieważ nigdy nie zamortyzujesz std::dequekosztów ogólnych w tym scenariuszu.

Przeczytasz wiele opinii o tym, dlaczego pamięć podręczna jest królem, jak Stroustrup nienawidzi połączonych list itp., I wszystko to jest prawdą, pod pewnymi warunkami. Po prostu nie akceptuj tego na ślepą wiarę, ponieważ w naszym drugim scenariuszu jest mało prawdopodobne, że domyślna std::dequeimplementacja będzie działać. Oceń swoje użycie i zmierz.

Ta sprawa jest na tyle prosta, że ​​możesz po prostu napisać własną. Oto coś, co działa dobrze w sytuacjach z mikrokontrolerem, w których użycie STL zajmuje zbyt dużo miejsca. Jest to dobry sposób na przekazywanie danych i sygnału z obsługi przerwań do głównej pętli.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};