Vector vs. List

Na tegorocznej konferencji GovingNative 2012 Bjarne Stroustrup, przedstawił kilka ciekawostek dotyczących nowości w C++:

• http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf

Jednym z punków była wyższość wektora na listą. Lista góruje nad wektorem, w takich operacjach jak wstawianie oraz usuwanie elementów, jednak proces wyszukania odpowiedniego elementu w kontenerze okazuje się być naprawdę wąskim gardłem. Wektor z kolei lepiej radzi sobie z wyszukiwaniem, gorzej natomiast z usuwaniem i wstawianiem. Dzięki współczesnym procesorem korzystającym z mechanizmu dedukcji skoku, wektor okazuje się zyskiwać ogromną przewagę. Mimo iż wykonuje znacznie więcej operacji w pamięci to będą one odbywały się w cache procesora, gdzie są naprawdę szybkie.

Opis testu.
Wygeneruj N losowych liczb i wstaw je tak by zachowana została posortowana kolejność np. 5 1 4 2:

• 5
• 1 5
• 1 4 5
• 1 2 4 5

Usuń elementy z losowej pozycji np. dla 1 2 0 0, będzie to:

• 1 2 4 5
• 1 4 5
• 1 4
• 4

Na początek kilka funkcji pomocniczych. Pierwsza łączy nasz generator z rozkładem jednorodnym

TRnd get_rnd(const int max)
{
    const int seed = 858446;
    TBaseGeneratorType generator(seed);
    boost::uniform_int<> uni_dist(0, max);
    TRnd rnd(generator, uni_dist);
    return rnd;
}

Pierwsza część testu - generyczna funkcja do wstawiania, zachowując posortowaną kolejność.

template <typename T>
void insert_sort(T& con, const int size, TRnd& rnd)
{
    for (int i = 0; i < size; ++i) {
        const int value = rnd();
        typename T::iterator it = std::find_if(con.begin(), con.end(),
                                               value < _1);
        con.insert(it, value);
    }
}

Druga część testu - usuwanie wartości z losowej pozycji.

template <typename T>
void erase_by_rand_pos(T& con, TRnd& rnd)
{
    while (not con.empty()) {
        const int pos = rnd() % con.size();
        typename T::iterator it = con.begin();
        std::advance(it, pos);
        con.erase(it);
    }
}

Ciało testu:

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

#include <boost/lambda/lambda.hpp>
#include <boost/lexical_cast.hpp>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

#include <boost/date_time/posix_time/posix_time.hpp>

using namespace std;
using namespace boost::lambda;
using namespace boost::posix_time;

typedef boost::mt19937 TBaseGeneratorType;
typedef boost::variate_generator<TBaseGeneratorType, 
                                boost::uniform_int<> > TRnd;

int main(int argc, char **argv)
{
    if (argc < 2) {
        cout << "Missing size argument" << endl;
        return -1;
    }

    TRnd rnd = get_rnd(std::numeric_limits<int>::max());
    const int size = boost::lexical_cast<int>(argv[1]);

    const ptime time_start = microsec_clock::local_time();
    cout << "Start at: " << time_start << ", size = "<< size << endl;

//    vector<int> container;
    list<int> container;
    insert_sort(container, size, rnd);

    const ptime time_insert = microsec_clock::local_time();
    cout << "Inserted sort:       " << time_insert - time_start << endl;

    erase_by_rand_pos(container, rnd);

    const ptime time_remove = microsec_clock::local_time();
    cout << "Erase at random pos: " << time_remove - time_insert << endl;
    cout << "Whole process:       " << time_remove - time_start << endl;

    return 0;
}

Wyniki. Wszystkie testy były kompilowane za pomocą g++ (4.6.3) z flagą -O2. Bjarne musiał korzystać z bardziej wyrafinowanego algorytmu niż mój, bo w jego wersji cały proces dla 200000 elementów zajął ok. 500 sekund, w moim przypadku było to już 1116 sekund (sic!), dlatego też nie testowałem powyżej tej wartości. Nie testowałem też "preallocated list" bo nie jestem pewien co to dokładnie jest.

I jeszcze jeden wykres, przedstawiający jak czasowo wyglądały poszczególne operacje, czyli wstawianie z wyszukiwaniem i usuwanie z wyszukiwaniem. Porównując dane, widać, że w przypadku listy, najwolniejszą operacją jest usuwanie z wyszukiwaniem, w przypadku wektora wstawianie z wyszukiwaniem. Usuwanie i wstawianie na wektorze powinny być jego słabym punktem, ale okazują się, że w połączeniu z wyszukiwaniem, są znacznie szybsze od tego co oferuje lista.