Pourquoi la modification simultanée des tableaux est-elle si lente?

Question

J'ai écrit un programme pour illustrer les effets de cache de la contention dans les programmes multithread. Ma première coupe a été de créer un tableau de long et de montrer comment la modification des éléments adjacents causes de conflit. Voici le programme.

const long maxCount = 500000000;
const int numThreads = 4;
const int Multiplier = 1;
static void DoIt()
{
    long[] c = new long[Multiplier * numThreads];
    var threads = new Thread[numThreads];

    // Create the threads
    for (int i = 0; i < numThreads; ++i)
    {
        threads[i] = new Thread((s) =>
            {
                int x = (int)s;
                while (c[x] > 0)
                {
                    --c[x];
                }
            });
    }

    // start threads
    var sw = Stopwatch.StartNew();
    for (int i = 0; i < numThreads; ++i)
    {
        int z = Multiplier * i;
        c[z] = maxCount;
        threads[i].Start(z);
    }
    // Wait for 500 ms and then access the counters.
    // This just proves that the threads are actually updating the counters.
    Thread.Sleep(500);
    for (int i = 0; i < numThreads; ++i)
    {
        Console.WriteLine(c[Multiplier * i]);
    }

    // Wait for threads to stop
    for (int i = 0; i < numThreads; ++i)
    {
        threads[i].Join();
    }
    sw.Stop();
    Console.WriteLine();
    Console.WriteLine("Elapsed time = {0:N0} ms", sw.ElapsedMilliseconds);
}

Je suis en cours d'exécution Visual Studio 2010, d'un programme compilé en mode Release, .NET 4.0 cible "any CPU", et exécuté dans le runtime 64 bits sans le débogueur (Ctrl+F5).

Ce programme s'exécute en environ 1 700 ms sur mon système, avec un seul thread. Avec deux threads, il faut plus de 25 secondes. Comprendre que la différence était la cache de contention, j'ai mis en Multipler = 8 et a couru de nouveau. Le résultat est de 12 secondes, de sorte que la contention a été au moins une partie du problème.

L'augmentation de Multiplier - delà de 8 n'est pas d'améliorer les performances.

Pour comparaison, un programme semblable qui n'est pas utiliser un tableau ne prend qu'environ 2 200 ms avec deux threads lorsque les variables sont adjacentes. Quand j'ai séparer les variables, les deux thread version s'exécute dans le même laps de temps que le single-threaded version.

Si le problème a été la matrice de l'indexation des frais généraux, vous attendez qu'il s'affiche dans le thread unique version. Il me semble que il y a une sorte d'exclusion mutuelle passe lors de la modification de la matrice, mais je ne sais pas ce que c'est.

En regardant l'généré IL n'est pas très éclairant. Ni la visualisation du démontage. Le démontage ne montrent quelques appels à (je pense) la bibliothèque d'exécution, mais je n'étais pas en mesure de le coiffer.

Je ne suis pas compétent avec windbg ou d'autres outils de débogage ces jours-ci. Ça fait longtemps depuis que j'ai eu besoin d'eux. Donc je suis perplexe.

Ma seule hypothèse est que le moteur d'exécution de code est "sale" drapeau sur chaque écriture. Il semble que quelque chose comme cela serait nécessaire pour favoriser la levée d'une exception si le tableau est modifié alors qu'il est énuméré. Mais j'admets que je n'ai pas de preuve directe de cette hypothèse.

Quelqu'un peut-il me dire quelle est la cause de ce gros ralentissement?

Answer 1

Vous avez un faux partage. J'ai écrit un article à ce sujet ici