Blog
std::vector & std::list - porównanie
Stanisław Kubiak 15.11.2018
Kontenery STL – pytanie o nie zdaje się być absolutnie podstawowe. A jednak – zbyt często widzieliśmy, że przybliżenie złożoności obliczeniowej std::vector bądź złożoności pamięciowe dla std::list graniczy z cudem. W związku z tym, zaczynam sesję wpisów o kontenerach dostępnych w bibliotece standardowej. Na pierwszy ogień idą dwa podstawowe – wspomniany vector oraz lista.
Zacznijmy jednak od krótkiego przypomnienia, w jaki sposób klasyfikujemy kontenery dostępne w bibliotece standardowej. Na pomoc przybędzie nam oczywiście standard C++ – dzięki niemu wszystko stanie się bardzo jasne: http://eel.is/c++draft/containers.general#tab:containers.lib.summary – przy okazji właśnie udowodniłem, że standard C++ jest bardzo przejrzysty, prosty i klarowny.
Ekhm..
tl;dr bo nie chcę klikać w dziwne linki – kontenery dzielimy na: sekwencyjne, asocjacyjne (posortowane oraz nieposortowane) oraz adaptery. Cykl wpisów zaczynamy od sekwencyjnych. A konkretnie dwóch – std::list oraz std::vector.
std::list
Idea tego kontenera jest bardzo prosta. Tworzymy osobne węzły listy i łączymy je ze sobą wskaźnikami.
Uwaga – istnieje lista pojedynczo wiązana (jednokierunkowa) – std::forward_list. Element poprzedzający wskazuje na element następny. Istnieje również lista podwójnie wiązana(dwukierunkowa) – std::list. Poza wskaźnikiem na element następny, dostępny jest również wskaźnik na element poprzedzający.
Najistotniejszą cechą listy jest fakt, że nie jest przetrzymywana w ciągłym obszarze pamięci. W momencie żądania dodania nowego węzła do listy zostanie zarezerwowany nowa pamięć – najprawdopodobniej w zupełnie innym rejonie. Po udanej alokacji nastąpi jedynie odpowiednie przypisanie wskaźników – to wszystko dzieje się przy stałej złożoności obliczeniowej: O(1). Tyczy się to elementów dodawanych/usuwanych z listy w dowolnym jej węźle. Z racji, że usuwanie/dodawanie elementu nie ma wpływu na pozostałe elementy (jedynie aktualizujemy wskaźniki) – powinniśmy dojść do wniosku, że operacje usuwania/dodawania nie mają wpływu na iteratory – pozostają dalej poprawne.
Co z narzutem pamięciowym? Najpewniej (ponieważ zależy to od implementacji) każdy węzeł listy posiada wskaźnik na element następny, lista dwukierunkowa ponadto wskaźnik na element poprzedzający. Oczywiście, jest jeszcze obiekt przechowywany w węźle listy. Tak więc, narzut dla pojedynczego węzła std::list<int> w moim przypadku wynosi 24 bajty (możecie zweryfikować to u siebie – albo czytając implementację stdlib, albo wywołując operator sizeof na pustym kontenerze) – zakładam, że skupiamy się tylko na domyślnym alokatorze.
Sumarycznie, narzut pamięci wynosić będzie N*(sizeof(T) + 2*rozmiar_wskaźnika) – o rozmiarze wskaźnika możecie poczytać tutaj: https://dorwijnerda.pl/pl/blog/ile-wazy-wskaznik/ N to oczywiście liczba elementów.
std::vector
Pora na drugi kontener.
Cechuje się on odmiennym założeniem – osadzony jest w ciągłych obszarach pamięci. Dzięki temu narzut pamięciowy jest zdecydowanie mniejszy niż w przypadku std::list. Szczegóły już za momencik, najpierw suche fakty.
std::vector utożsamiać można z tablicą o dynamicznym rozmiarze („tablica” o stałym rozmiarze to std::array). Rozmiar zwiększa się w trakcie działania programu na żądanie użytkownika. Związane z tym jest pewne ryzyko – w momencie, gdy przekroczona zostanie liczba deklarowanych obiektów w kontenerze nastąpi relokacja pamięci. Istniejące obiekty zostaną przeniesione w nowe miejsce pamięci. Przy okazji, wszystkie wskaźniki, referencje oraz iteratory wskazujące na “poprzedni” wektor staną się nieaktualne (“zinwalidowane” – na marginesie: należy uważać w takiej sytuacji na UB).To, o ile kontener zostanie powiększony zależy od jego implementacji. Z reguły przyjmuje się, że jest to 150 – 200% poprzedniego rozmiaru.
Operacje dodania/usunięcia elementu na początku/końcu kontenera cechują się zamortyzowaną stałą złożonością obliczeniową: O(1).
Dodawanie, usuwanie elementu w dowolnym miejscu std::vector to już temat trochę bardziej skomplikowany. Wiąże się to z koniecznością przesunięcia wszystkich elementów kontenera przed usuwany element. Stąd pesymistyczna złożoność obliczeniowa wynosi O(n).
Narzut pamięciowy dla std::vector jest minimalny. Poza obszarem pamięci dla elementów kontenera istnieją 3 wskaźniki (aczkolwiek jest to zależne od implementacji stdlib). Jeden wskazujący na zarezerwowany obszar pamięci, drugi na początek kontenera, trzeci na jego koniec.Sumarycznie, narzut pamięciowy wyniesie on N*sizeof(T) + 3*rozmiar_wskaźnika.
Wspomnę jeszcze o jednej konkretnej specjalizacji vectora – std::vector<bool>. Z racji, że zmienna typu bool jest z reguły reprezentowana w postaci liczbowej (http://eel.is/c++draft/basic.fundamental#6, http://eel.is/c++draft/basic.fundamental#7), użytkownik nie operuje na konkretnych bitach. Zamiast tego działa na obiektach typu proxy – semantycznie symulują one zmienną typu bool. Natomiast to, co znajdzie się pod maską zależy od implementacji biblioteki standardowej. Co więcej, nie istnieje wymaganie aby zarezerwowana pamięć była ciągła – http://eel.is/c++draft/vector.bool#3.
Zastosowanie kontenerów
Kiedy wybierać std::list/std::forward_list, a kiedy wybierać std::vector?
Generalna zasada jest taka, że std::vector powinien być podstawowym kontenerem, którego potrzebujesz.
Dostęp do dowolnego elementu jest stały w czasie, posiada minimalny narzut pamięci ponad to co, oferuje zwykły typ tablicowy. Jednocześnie zapewnia dużą wydajność – za chwilę sprawdzimy dlaczego.
Natomiast std::list powinieneś wybrać tylko wtedy, gdy wiesz że będziesz często dodawać bądź usuwać elementy w „środku” kontenera. Jednocześnie, nie będziesz potrzebować odwoływać się do różnych elementów.
Pomiary
Tyle teorii, sprawdźmy jak to wygląda w praktyce.
Na początek przekonajmy się, ile czasu potrzeba na wyszukiwanie konkretnego elementu w raczej niewielkich kontenerach – powiedzmy 10 milionów integerów.
#include <chrono>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <random>
namespace
{
constexpr auto size = 10'000'000;
}
template <typename callback>
void measureRun(std::string what, callback&& c)
{
const auto start = std::chrono::high_resolution_clock::now();
c();
const auto end = std::chrono::high_resolution_clock::now();
const std::chrono::duration<double, std::milli> diff = end - start;
std::cout << what << " took " << diff.count() << "[ms]" << std::endl;
}
int main()
{
std::vector<int> v(size);
std::iota(v.begin(), v.end(), 1);
std::shuffle(v.begin(), v.end(), std::random_device{});
std::list<int> l(v.begin(), v.end());
const auto dummy_find = [val = -1337](auto const& container)
{
for (auto const& e : container)
if (e == val)
break;
};
std::cout << "starting... " << std::endl;
for (std::size_t i = 0u; i < 10; ++i)
measureRun("find for std::vector", [&] {dummy_find(v); });
for (std::size_t i = 0; i < 10; ++i)
measureRun("find for std::list", [&] {dummy_find(l); });
return 0;
}
Nic specjalnego – ot, tworzymy dwa kontenery. Generujemy losowo 10 000 000 liczb, ładujemy je do vectora, karmimy nimi drugi kontener. Wreszcie wykonujemy przegląd zupełny dla w poszukiwaniu szukanego elementu.
Uśrednione pomiary z dziesięciu wykonań na mojej maszynie (i7-7820HQ@2.90 GHz, 32GB ramu, kompilacja z optymalizacją O2) dają następujące wyniki: 23.20 [ms] dla std::vector oraz 134.56 [ms] dla std::list.
Skąd taka duża różnica?
Ano, dlatego że vector rezyduje w ciągłym obszarze pamięci. Skutkuje to tym, że raz załadowana pamięć zostanie efektywnie wykorzystana przez L1 cache (mój CPU posiada go w ilości 256KB), każde kolejne odwołanie do elementu następnego w vectorze odbędzie się prawie natychmiastowo.
Z kolei w std::list, z racji alokowania kolejnych węzłów w różnych obszarach pamięci skazana jest na porażkę. Biorąc pod uwagę wyniki pomiaru należy założyć z praktycznie 100% pewnością, że każde kolejne wyszukanie elementu z listy było równoważne cache miss, a to strata rzędu kilkuset cykli CPU.
Czyli… dla CPU wieczność.
Drobne modyfikacje w pomiarach
Ok, wiemy już, że wszystkiemu winna jest nieciągłość pamięci.
Zmodyfikujmy delikatnie przykład z góry. Wprowadzimy alokator pamięci, który sprawi, że pamięć będzie ciągła również dla listy.
template <typename T>
struct dummyAllocator
{
typedef T value_type;
dummyAllocator() = default;
T* allocate(std::size_t n)
{
T* res = reinterpret_cast<T*>(block.data() + cur_pos);
cur_pos += n;
return res;
}
void deallocate(T*, std::size_t n) noexcept
{
cur_pos -= n;
}
private:
static std::array<T, size> block;
std::size_t cur_pos{ 0 };
};
template<typename T>
std::array<T, size> dummyAllocator<T>::block = std::array<T, size>();
Uwaga! – powyższy „alokator” nie jest w żaden sposób tworem, który powinien działać na produkcji. Nie jest tworem, który powinien przejść jakiekolwiek code review. Jest po prostu POC, tworzony ad hoc. 🙂
int main()
{
std::vector<int> v(size);
std::iota(v.begin(), v.end(), 1);
std::shuffle(v.begin(), v.end(), std::random_device{});
std::vector<int, dummyAllocator<int>> v1(v.begin(), v.end());
const auto dummy_find = [val = 1337](auto const& container)
{
for (auto const& e : container)
if (e == val)
break;
};
std::cout << "starting... " << std::endl;
for (auto i = 0; i < 10; ++i)
{
measureRun("find for std::vector", [&] {dummy_find(v); });
measureRun("find for std::vector with custom allocator", [&] {dummy_find(v1); });
}
v1.clear();
std::list<int> l(v.begin(), v.end());
std::list<int, dummyAllocator<int>> l1(v.begin(), v.end());
for (auto i = 0; i < 10; ++i)
{
measureRun("find for std::list", [&] {dummy_find(l); });
measureRun("find for std::list with custom allocator", [&] {dummy_find(l1); });
}
return 0;
}
Wyniki czasowe prezentują się następująco (ponownie, uśrednione 10 wykonań):
- std::vector: 15.018 [ms]
- std::vector<int, dummyAllocator>: 15.78 [ms]
- std::list: 111.78 [ms]
- std::list<int, dummyAllocator>: 72.43 [ms]
Czyli… vector jest znowu szybszy. I to mimo ciągłego obszaru pamięci – czyżby osoby implementujące stdlib byli aż tak słabymi programistami?
Otóż nie.
Zastosowanie ciągłego obszaru pamięci dla std::list skutkuje zyskiem na poziomie około 35%. Czy to dużo, czy mało? Biorąc pod uwagę, że std::vector jest nadal szybszy (aczkolwiek nie jest to już różnica rzędu wielkości), można odczuć pewien niedosyt. Jednakże biorąc pod uwagę, że węzły listy są ze sobą powiązane wskaźnikami należy uznać to za całkiem niezły wynik (aczkolwiek nadal daleki od ideału). Wskaźniki, o które oparta jest lista, dodają narzut w postaci skoku pod konkretny adres pamięci. A to również jest zabójcze dla pamięci podręcznej. Z racji, że zagadnienia pisania aplikacji, korzystających w pełni z dobrodziejstw pamięci podręcznej wykraczają znacząco poza ten wpis polecam prezentację Scotta Meyersa z Code::Dive 2014: https://www.youtube.com/watch?v=WDIkqP4JbkE
Finisz
Reasumując – zastanawiając się, który z dwójki std::vector oraz std::list użyć, prawie zawsze powinieneś wykorzystać std::vector. Jest szybki, jego narzut pamięciowy jest minimalny, umożliwia szybki dostęp do dowolnego elementu. Może być przyjazny pamięci podręcznej CPU. Aczkolwiek pamiętaj, że posiada on również swoje wady (raczej cechy) – usuwanie, bądź dodawanie elementów w „środku” kontenera jest dość problematyczne. W momencie, gdy wykorzystasz całą dostępną pulę pamięci dla konkretnej instancji std::vector spodziewaj się relokacji pamięci. Która, na pewno, będzie bardzo powolna.
