Pourquoi le traitement d’un tableau sortingé est-il plus lent qu’un tableau non sortingé?

J’ai une liste de 500 000 objects Tuple générés aléatoirement sur lesquels je réalise une recherche simple “entre”:

 var data = new List<Tuple>(500000); ... var cnt = data.Count(t => t.Item1 = x); 

Lorsque je génère mon tableau aléatoire et lance ma recherche de 100 valeurs de x générées aléatoirement, les recherches se terminent en quatre secondes environ. Connaissant les merveilles que le sorting fait à la recherche , j’ai décidé de sortinger mes données – d’abord par Item1 , ensuite par Item2 , et finalement par Item3 – avant d’exécuter mes 100 recherches. Je m’attendais à ce que la version sortingée s’exécute un peu plus rapidement en raison de la prédiction de twig: je pensais qu’une fois que nous t.Item1 <= x au point où Item1 == x , toutes les vérifications ultérieures de t.Item1 <= x correctement la twig prendre “, accélérant la partie queue de la recherche. À ma grande surprise, les recherches ont pris deux fois plus de temps sur un tableau sortingé !

J’ai essayé de changer l’ordre dans lequel je faisais mes expériences et d’utiliser différentes sources pour le générateur de nombres aléatoires, mais l’effet a été le même: les recherches dans un tableau non sortingé étaient presque deux fois plus rapides que dans le même tableau. sortingés!

Est-ce que quelqu’un a 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> { public int Compare(Tuple x, Tuple y) { var res = x.Item1.CompareTo(y.Item1); if (res != 0) return res; res = x.Item2.CompareTo(y.Item2); return (res != 0) ? res : Ssortingng.CompareOrdinal(x.Item3, y.Item3); } } static void Test(bool doSort) { var data = new List<Tuple>(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 = ssortingng.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); 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 sortingée, vous accédez à tous les tuples en mémoire . Ils ont été alloués consécutivement dans la RAM. Les processeurs aiment accéder séquentiellement à la mémoire car ils peuvent demander de manière spéculative la ligne de cache suivante afin qu’elle soit toujours présente au besoin.

Lorsque vous sortingez la liste, vous la placez dans un ordre aléatoire car vos clés de sorting sont générées aléatoirement. Cela signifie que les access mémoire aux membres du tuple sont imprévisibles. Le processeur ne peut pas pré-télécharger la mémoire et presque chaque access à un tuple est un échec de cache.

Ceci est un bon 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 sont utilisées ensemble fonctionnent très bien. Ils ont une grande localité de référence .

La pénalité due à des erreurs de cache dépasse la pénalité de prévision de twig enregistrée dans ce cas.

Essayez de passer à un struct -tuple. Cela restaurera les performances car aucune référence de pointeur ne doit être effectuée lors de l’exécution pour accéder aux membres du tuple.

Chris Sinclair note dans les commentaires que “pour TotalCount autour de 10 000 ou moins, la version sortingée est plus rapide “. En effet, une petite liste s’inscrit entièrement dans le cache du processeur . Les access mémoire peuvent être imprévisibles mais la cible est toujours en cache. Je crois qu’il y a encore une petite pénalité car même une charge du cache prend des cycles. Mais cela ne semble pas être un problème car le processeur peut jongler avec plusieurs charges en suspens , augmentant ainsi le débit. Chaque fois que le processeur attend une mémoire, il accélère encore dans le stream d’instructions pour mettre en queue 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 deux fois plus lents lorsque nous passons de l’access séquentiel à l’access à la mémoire aléatoire me dit combien il se passe sous les couvertures pour masquer la latence de la mémoire. Un access mémoire peut bloquer le processeur pendant 50 à 200 cycles. Étant donné que le numéro un, on pourrait s’attendre à ce que le programme devienne> 10 fois plus lent lors de l’introduction d’access à la mémoire aléatoire.

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

Puisque Count avec le paramètre de prédicat est une méthode d’extension pour tous les IEnumerables, je pense qu’il ne sait même pas s’il s’exécute sur la collection avec un access aléatoire efficace. Donc, il vérifie simplement chaque élément et Usr explique pourquoi les performances ont diminué.

Pour exploiter les avantages des performances du tableau sortingé (comme la recherche binary), vous devrez effectuer un peu plus de codage.