Pourquoi le traitement d'un tableau trié est-il plus lent qu'un tableau non trié?

J'ai une liste de 500000 Tuple<long,long,string>objets générés aléatoirement sur lesquels j'effectue une simple recherche "entre":

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

Lorsque je génère mon tableau aléatoire et lance ma recherche de 100 valeurs générées de manière aléatoire x, les recherches se terminent en quatre secondes environ. Sachant les grandes merveilles que le tri fait sur la recherche , j'ai cependant décidé de trier mes données - d'abord par Item1, puis par Item2et enfin par Item3- avant d'exécuter mes 100 recherches. Je m'attendais à ce que la version triée fonctionne un peu plus rapidement à cause de la prédiction de branche: ma pensée a été qu'une fois que nous arrivons au point où Item1 == x, toutes les vérifications supplémentaires de t.Item1 <= xprédisent correctement la branche comme "pas de prise", accélérant la partie arrière de la chercher. À ma grande surprise, les recherches ont pris deux fois plus de temps sur un tableau trié !

J'ai essayé de changer l'ordre dans lequel j'ai exécuté mes expériences et j'ai utilisé des graines différentes pour le générateur de nombres aléatoires, mais l'effet a été le même: les recherches dans un tableau non trié ont été exécutées presque deux fois plus vite que les recherches dans le même tableau, mais trié!

Quelqu'un at-il une bonne explication de cet effet étrange? Le code source de mes tests suit; J'utilise .NET 4.0.

private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
    var data = new byte[8];
    r.NextBytes(data);
    return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}
static void Test(bool doSort) {
    var data = new List<Tuple<long,long,string>>(TotalCount);
    var random = new Random(1000000007);
    var sw = new Stopwatch();
    sw.Start();
    for (var i = 0 ; i != TotalCount ; i++) {
        var a = NextLong(random);
        var b = NextLong(random);
        if (a > b) {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var s = string.Format("{0}-{1}", a, b);
        data.Add(Tuple.Create(a, b, s));
    }
    sw.Stop();
    if (doSort) {
        data.Sort(new TupleComparer());
    }
    Console.WriteLine("Populated in {0}", sw.Elapsed);
    sw.Reset();
    var total = 0L;
    sw.Start();
    for (var i = 0 ; i != TotalQueries ; i++) {
        var x = NextLong(random);
        var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
        total += cnt;
    }
    sw.Stop();
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
    Test(false);
    Test(true);
    Test(false);
    Test(true);
}

Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)

Lorsque vous utilisez la liste non triée, tous les tuples sont accessibles dans l' ordre de la mémoire . Ils ont été alloués consécutivement dans la RAM. Les CPU adorent accéder à la mémoire séquentiellement car ils peuvent demander spéculativement la prochaine ligne de cache afin qu'elle soit toujours présente en cas de besoin.

Lorsque vous triez la liste, vous la mettez dans un ordre aléatoire car vos clés de tri sont générées de manière aléatoire. Cela signifie que les accès mémoire aux membres de tuple sont imprévisibles. Le CPU ne peut pas extraire la mémoire et presque tous les accès à un tuple sont un échec de cache.

Ceci est un bel exemple d'un avantage spécifique de la gestion de la mémoire GC : les structures de données qui ont été allouées ensemble et utilisées ensemble fonctionnent très bien. Ils ont une grande localité de référence .

Dans ce cas, la pénalité des échecs de cache l' emporte sur la pénalité de prédiction de branche enregistrée .

Essayez de passer à un struct-tuple. Cela restaurera les performances car aucune référence au pointeur ne doit se produire au moment de l'exécution pour accéder aux membres de tuple.

Chris Sinclair note dans les commentaires que "pour TotalCount environ 10 000 ou moins, la version triée fonctionne plus rapidement ". En effet, une petite liste tient entièrement dans le cache du processeur . Les accès mémoire peuvent être imprévisibles mais la cible est toujours dans le cache. Je pense qu'il y a encore une petite pénalité car même une charge du cache prend quelques cycles. Mais cela ne semble pas être un problème car le CPU peut jongler avec plusieurs charges en suspens , augmentant ainsi le débit. Chaque fois que le CPU attend une attente de mémoire, il accélérera toujours dans le flux d'instructions pour mettre en file d'attente autant d'opérations de mémoire que possible. Cette technique est utilisée pour masquer la latence.

Ce type de comportement montre à quel point il est difficile de prédire les performances sur les processeurs modernes. Le fait que nous ne soyons que 2 fois plus lents lorsque nous passons d'un accès séquentiel à un accès aléatoire à la mémoire me dit combien il se passe sous les couvertures pour masquer la latence de la mémoire. Un accès à la mémoire peut bloquer la CPU pendant 50-200 cycles. Étant donné que le numéro un pourrait s'attendre à ce que le programme devienne> 10x plus lent lors de l'introduction des accès aléatoires à la mémoire.

LINQ ne sait pas si votre liste est triée ou non.

Étant donné que Count avec le paramètre de prédicat est la méthode d'extension pour tous les IEnumerables, je pense qu'il ne sait même pas s'il fonctionne sur la collection avec un accès aléatoire efficace. Ainsi, il vérifie simplement chaque élément et Usr a expliqué pourquoi les performances étaient inférieures.

Pour exploiter les avantages de performance d'un tableau trié (comme la recherche binaire), vous devrez faire un peu plus de codage.