Va ranger ta chambre : ou comment une liste est parfois plus rapide qu’un dictionary

“Va ranger ta chambre ! ”, l’hymne universel de tous les parents. Enfant, beaucoup d’entre nous ont pu remettre en cause le bien-fondé de ce genre d’injonction. Des années plus tard, quand Microsoft nous dit dans sa documentation que la recherche dans un dictionary se fait en temps constant (quasi O(1)), on serait tenté de l’accepter sans avoir recours à notre esprit critique. À tort peut-être ?

Pour s’en convaincre, il suffit de faire une petite expérience : insérons 32 éléments dans un dictionary et allons en chercher 8. Faisons la même chose dans une simple liste. Vous pensez que le dictionary est le plus rapide ? Eh bien non ? La liste prend 8.25 ticks en moyenne quand le dictionary en prend 9.64. Et ce n’est pas un tour de magie. Voilà comment j’ai fait.*

Pour la liste

var list = new List();

 foreach (var record in records)
    list.Add(record);

 string bar;
 for (int j = 0; j < records.Count; j += peakinc) 
    bar = list.Find(r => r.Key == records[j].Key).Data;

Pour le dictionary

var dico = new Dictionary<string, string>();

foreach (var record in records)
    dico.Add(record.Key, record.Data);

 string bar;
 for (int j = 0; j < records.Count; j += peakInc)
     bar = dico[records[j].Key];

Record étant la classe suivante

class Record
{
    public readonly string Key;
    public readonly string Data;

    public Record()
    {
        Key = Guid.NewGuid().ToString();
        Data = "Foo";
    }

    public override int GetHashCode()
    {
        return Key.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null) 
            return false;
        
        var other = obj as Record;
        
        if (other == null) 
            return false;
        
        return Key == other.Key;
    }
}

*Vous pouvez trouver l’intégralité du code sur mon github

Aucune astuce ici.

Un mensonge par omission

Mais alors la documentation Microsoft nous mentirait-elle? Oui mais par omission. En réalité, pour trouver rapidement ce que l’on cherche, il faut surtout prendre le temps de bien le ranger dès le départ. Et c’est ce qui arrive ici. Pour la liste, l’insertion est très rapide étant donné qu’il y a un tableau derrière. Vous pouvez le vérifier sur le site de Microsoft ici. Il y a néanmoins le problème de l’agrandissement du tableau à gérer. Et la recherche est plutôt lente, car il faut parcourir toutes les entrées pour trouver celle recherchée. Sur une liste de 32 entrées et 8 recherches, la liste prend un tiers de son temps à insérer et deux tiers pour la recherche. Mon exemple est donc plutôt favorable à la liste.

Dans le dictionary, il faut allouer un tableau de trois cases lors de l’insertion si c’est le premier élément. Ensuite, il faut se préparer à de nombreuses opérations. D’abord on demande le HashCode du Record (ici celui du GUID). On fait un “&” avec 0x7FFFFFFF pour s’assurer d’avoir un chiffre positif. Ensuite, on calcule le modulo du résultat par le nombre de cases du tableau (buckets). Puis on parcourt la liste du bucket pour s’assurer qu’il n’y a pas déjà un élément ayant la même clé. S’il n’y en a pas, on se prépare à l’insertion en vérifiant la capacité du tableau. S’il est trop petit, on calcule le double de la taille actuelle. Vous suivez encore ? Passée cette étape, il faut calculer le nombre premier directement supérieur, qui sera la nouvelle taille de ce tableau. Et enfin on insère la nouvelle entrée.

Tenir compte de l’allocation mémoire

Une autre chose qu’il faut bien prendre en compte dans le dictionnary est l’allocation mémoire. Sur un nombre de 32 entrées avec 8 recherches, si on pré-alloue le dictionary à 32 emplacements à la construction on gagne 25% de temps. Pour la recherche, l’algorithme ressemble au début de l’insertion. On calcule successivement le HashCode et le modulo pour pouvoir parcourir la liste à cet emplacement. En somme c’est bien l’insertion qui prend du temps. Jugez plutôt. Avec mon exemple de 32 entrées et 8 recherches, le dictionary passe 83% de son temps à insérer. Ici aussi le code du dictionnaire est sur le site de Microsoft.

Vous comprenez pourquoi la liste peut être plus rapide selon les cas d’utilisation. Voici quelques chiffres de l’expérience précédente faite sur différents nombres d’entrées. La mesure est le nombre de ticks moyen pris par le CPU sur au moins 100.000 itérations consécutives.

Vous trouverez les sources et les résultats de tests intermédiaires (entre 16 et 1024) dans un tableur sur mon github.

Arbitrer entre la liste et le dictionnary

Pour conclure, le temps de calcul du HashCode et les collisions (nombre de fois où il est identique pour des entrées différentes) sont déterminants. La surcharge de la méthode Equals également. Les deux sont intimement liés et doivent être cohérents entre eux. Pour indexer des entrées, le choix d’une liste doit être envisagé. Il s’impose d’autant plus si la liste est créée de manière dynamique (à chaque request par exemple) et qu’elle compte un nombre d’entrées inférieur à plus ou moins une vingtaine (tableaux de 16 et 32).

En revanche, si la liste est “statique” (créée une fois pour toutes) ou qu’elle comporte un nombre d’entrées important, le dictionary demeure la meilleure solution. C’est également le cas si vous allez souvent y chercher des éléments. Pensez également à pré-initialiser vos conteneurs si vous le pouvez. Si vous connaissez le nombre exact d’entrées, utilisez un tableau. Attention toutefois au dilemme CPU vs Memory. Si vous pré-initialisez à une valeur haute, vous aurez certes moins à allouer plus tard, mais vous risquez de gaspiller bien plus de mémoire. Vous l’aurez compris, si savoir lire une documentation est nécessaire, notre valeur ajoutée et de voir ce qui n’y figure pas !