C++0x - std::set vs std::unordered_set

Il aura tout de même fallu attendre C++0x (ou devrais-je commencer à dire C++2011?) pour voir enfin apparaître les tables de hachage dans la bibliothèque standard. Diverses extensions, ansi que Boost, proposaient leurs implémentations, mais ça fait toujours plaisir de voir les choses se standardiser.

Je dois cependant avouer que les tables de hachage m'ont souvent laissé un peu perplexe: leurs performances dépendent énormément du bon choix pour la fonction de hachage, ce qui rend fort difficile les prédictions. Je préfère généralement un bon arbre binaire, qui va certes nécessiter une allocation à chaque insertion et une recherche logarithmique, mais que j'ai l'impression de mieux comprendre.

Voyons donc un petit benchmark afin de se faire une idée. D'un côté, le bon vieux std::set, de l'autre, le std::unordered_set. L'on insère 1000 entiers, on mesure le temps, et l'on recommence.




Comme l'on pouvait s'y attendre, l'on voit que l'insertion dans un std::set augmente de manière logarithmique. L'on voit également que l'insertion dans un std::unordered_set augmente de manière linéaire, sauf au moment des rehash: une fois que la table est trop pleine, le conteneur réalloue une nouvelle table plus grande, et y hache de nouveau chaque élément.

Alors oui, le std::unordered_est est plus rapide que le std::set, sur un ensemble qui tendrait plutôt à défavoriser ce dernier: ayant utilisé des entiers consécutifs, le hachage est très efficace (c'est l'entier lui même), et il n'y a pas de collisions.

Cependant, si le std::unordered_set est plus efficace sur le long terme, ses performances instantanées peuvent tout d'un coup devenir absolument horribles si l'on doit re-hacher. Un programme qui nécessite de bonnes performances à chaque insertion, et pas seulement dans l'ensemble, devra l'éviter.

Une approche intéressante pour profiter des performances des tables de hachage sans payer un rehash couteux de temps en temps est d'amortir ce hachage: lorsque la table devient trop grande, l'on alloue une nouvelle table dans laquelle on met le nouvel élément. Chaque nouvelle insertion embarque avec elle quelques éléments de la vieille table, et chaque recherche vérifie les deux tables. Ainsi, au fur et à mesure, les éléments de la petite table sont déplacés dans la grande, et l'on peut se débarrasser de la petite, et recommencer le processus une fois que la grande devient à son tour trop pleine.

Voici le code du benchmark. Étrangement, la table de hachage a de meilleures performances à froid, et le std::set à chaud, ce qui est la raison pour laquelle je commence à insérer dans un set sans mesurer. Et je ne m'explique absolument pas le blip aux 3/4 de l'insertion dans le std::set, qui se reproduit à chaque exécution

#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <unordered_set>

int main()
{
  int interval = 1000;
  int points = 1000000;
  
  std::vector<std::chrono::microseconds> setTimes;
  std::vector<std::chrono::microseconds> hashTimes;
  
  setTimes.reserve(points / interval);
  hashTimes.reserve(points / interval);
  
  {
    std::unordered_set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
      if(i % interval == 0)
      {
        hashTimes.push_back(std::chrono::system_clock::now() - base);
      }
    }
  }

  {
    std::set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
    }
  }
  {
    std::set<int> container;
    auto base = std::chrono::system_clock::now();
    for(int i = 0; i < points; ++i)
    {
      container.insert(i);
      if(i % interval == 0)
      {
        setTimes.push_back(std::chrono::system_clock::now() - base);
      }
    }
  }
  
  auto it = setTimes.begin();
  auto end = setTimes.end();
  auto it2 = hashTimes.begin();
  for(; it != end; ++it, ++it2)
  {
    std::cout << it->count() << "\t" <<  it2->count() << "\n";
  }
  std::cout.flush();
}