Friday, October 24, 2014

Vitesse d'insertion: Vector vs List

J’ai récemment vu un débat sur la vitesse d’insertion dans une liste par rapport à un vector. Il semblait que grâce au préfetcheur, comme un vector occupe une zone contiguë de mémoire l’insertion pouvait être plus rapide que dans une liste.

Ceci est surprenant, car l’insertion dans un vector nécessite de recopier tous les éléments suivant la position d’insertion. On a donc une complexité en moyenne linéaire. Alors qu’une insertion dans une liste ne demande que de mettre à jour un nombre constant de pointeurs et a donc une complexité constante.

Voyons en pratique ce qu’il en est.

Effectuons un benchmark simple: on va remplir un conteneur (une liste ou un vector) d’entiers pris dans un ordre aléatoire, mais en les insérant de manière triée, afin de simuler une série d’insertions à des positions aléatoires. Bien entendu si l’on ne se préoccupe que d’insérer de manière triée des entiers, de nombreuses optimisations sont possibles. Par exemple, on peut trouver la position d’insertion par dichotomie, on peut aussi tout insérer puis trier à la fin, ou simplement utiliser un set, mais le but ici est de simuler des insertions à des positions aléatoires dans un conteneur.

Voici le code utilisé:


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

using namespace std;
using namespace std::chrono;

class bench{
    high_resolution_clock::time_point start;
public:
    bench():start(high_resolution_clock::now()){};
    ~bench(){
        auto end = high_resolution_clock::now();
        cout << duration_cast<duration<double,milli>>(end-start).count();
    }
};

template<typename T>
void insert_all(const vector<int>& t, T& collection){
    for(int n:t){
        auto it = find_if(begin(collection), end(collection), [n](int x){return x>n;});
        collection.insert(it, n);
    }
}

const vector<int> values{1000,2000,4000,8000,16000};

int main(){
    cout << "SIZE,Vector Time(ms),List Time(ms)\n";
    for(int N:values)
        for(int again=0;again<3;++again){
        vector<int> t(N);
        for(int i=0;i<N;++i)
            t[i] = i;
        random_shuffle(begin(t), end(t));
        cout << N << ',';
        vector<int> t_vector;
        {bench b;insert_all(t, t_vector);}
        cout << ',';
        list<int> t_list;
        {bench b;insert_all(t, t_list);}
        cout << '\n';
    }
}

Et les résultats obtenus sur ma machine (j’ai pris la moyenne de plusieurs essais).

SIZE Vector Time(ms) List Time(ms)
1k 0.164817 0.49307
2k 0.697207 4.74188
4k 3.80992 26.7169
8k 7.23118 106.516
16k 39.1317 746.279
32k 138.673 6167.51
64k 570.2 16853.9
128k 2403.38 152090

J’ai aussi testé sur une machine ayant une architecture différente (ARMv6l c’est à dire sur un raspberryPi) les résultats sont du même ordre de grandeur: le vector est largement plus rapide.

Est-ce que cela montre que les insertions sur un vector sont plus rapides que sur une liste ? Non, cela montre uniquement que construire un conteneur par insertions en position aléatoire est plus rapide sur un vector que sur une liste, mais cela ne nous dit rien sur la vitesse d’insertion.

En profilant le code, on voit qu’une portion significative du temps est passée dans la fonction find_if. En fait, on doit parcourir linéairement le conteneur pour trouver la position d’insertion puis effectuer l’insertion. Que le conteneur soit un vector ou une liste la complexité d’une insertion est donc linéaire.

Il est tout de même intéressant de noter que parcourir des éléments stockés sur une zone mémoire contiguë est significativement plus rapide. Comme il est possible en C++ d’avoir du contrôle sur le layout de la mémoire c’est un point qui peut être utile.

Cependant en pratique, je ne connais pas beaucoup d’exemples sur lesquels l’utilisation d’une liste est supérieure à celle d’un vector. En effet si la liste est plus rapide pour l’insertion ou la suppression en position arbitraire d’un élément. Dès qu’il faut parcourir le conteneur pour trouver cette position d’insertion, le vector redevient plus rapide. Un cas possible est celui de l’implémentation d’un cache LRU. En stockant dans la table de hachage l’itérateur vers la position de l’élément dans la liste on peut effectuer toutes les opérations en temps constant.

No comments:

Post a Comment