Mauvaise performance du vecteur <bool> dans une cible 64 bits avec VS2012

Question

L'analyse comparative de cette classe:

struct Sieve {
  std::vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= (int)sqrt((double)n); ++i)
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i)
          isPrime[j] = false;
  }
};

Je reçois plus de 3 fois plus de performances (temps CPU) avec 64-bit et 32-bit version (version release) lors de l'appel d'un constructeur pour un grand nombre, par ex.

Sieve s(100000000);

J'ai testé sizeof(bool) et il est 1 pour les deux versions. Quand j'ai substitut vector<bool> avec vector<char> de la performance devient le même pour 64-bits et 32-bits. Pourquoi est-ce?

Voici les temps d'exécution pour S(100000000) (version 32 bits en mode premier, de 64 bits à la seconde)):

vector<bool> 0.97 s 3.12 s vector<char> 0.99 s 0.99 s vector<int> 1.57 s 1.59 s

J'ai aussi fait une folie test avec VS2010 (invité par Wouter Huysentruit de réponse), qui a produit 0.98 s 0.88 s. Si il ya quelque chose de mal avec VS2012 mise en œuvre.

J'ai soumis un rapport d'erreur à Microsoft Connect

MODIFIER

Beaucoup de réponses de commentaires ci-dessous sur les insuffisances de l'aide d' int pour l'indexation. Cela peut être vrai, mais même le Grand Magicien lui-même est à l'aide d'une norme for (int i = 0; i < v.size(); ++i) dans ses livres, donc, un tel modèle ne devrait pas subir une importante perte de performance. En outre, cette question a été soulevée au cours de Natifs de 2013 de la conférence et le président du groupe de C++ gourous ont fait part de leur début de recommandations d'utilisation size_t pour l'indexation et un type de retour d' size() comme une erreur. Ils ont dit: "nous sommes désolés, nous étions jeunes..."

Le titre de cette question pourrait être reformulée pour: Plus de 3 fois les performances de tomber sur ce code lors de la mise à niveau de VS2010 pour VS2012.

MODIFIER

J'ai fait une grossière tentative de se trouver un alignement de la mémoire d'index i et j et découvert que cette version instrumentée:

struct Sieve {
  vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= sqrt((double)n); ++i) {
      if (i == 17) cout << ((int)&i)%16 << endl;
      if (isPrime[i]) 
        for (int j = i*i; j <= n; j += i) {
          if (j == 4) cout << ((int)&j)%16 << endl;
          isPrime[j] = false;
        }
    }
  }
};

l'auto-magiquement court vite maintenant (seulement 10% plus lente que la version 32 bits). Cette VS2010 et les performances du mal à accepter une théorie de l'optimiseur avoir des problèmes inhérents à traiter avec int indices au lieu de size_t.

Answer 1

std::vector<bool> n'est pas directement en faute. La différence de performances est finalement causé par votre utilisation de l'signé de 32 bits int tapez dans vos boucles et plutôt de mauvaise allocation des registres par le compilateur. Considérons, par exemple, votre intime de la boucle:

for (int j = i*i; j <= n; j += i)
    isPrime[j] = false;

Ici, j est un entier signé 32 bits. Lorsqu'il est utilisé en isPrime[j], cependant, elle doit être promue (et de signe étendu) pour un entier de 64 bits, afin d'effectuer l'indice de calcul. Le compilateur ne peut pas simplement traiter j comme une valeur 64 bits, parce que ce serait de modifier le comportement de la boucle (par exemple, si n est négatif). Le compilateur a également ne peut pas effectuer le calcul de l'indice à l'aide de la version 32 bits de quantité j, parce que ce serait de modifier le comportement de cette expression (par exemple, si j est négatif).

Ainsi, le compilateur a besoin de générer du code pour la boucle à l'aide d'un 32-bit j , ensuite, il faut générer du code pour convertir j d'un entier de 64 bits pour l'indice de calcul. Il doit faire la même chose pour la boucle externe avec i. Malheureusement, il semble que le compilateur alloue des registres plutôt mal dans ce cas^(*)--il commence à répandre temporaires de la pile, provoquant l'impact sur les performances que vous voyez.

Si vous modifiez votre programme pour utiliser size_t partout (qui est de 32 bits x86 ou 64 bits x64), vous observerez que la performance est sur le pair avec x86, parce que le code généré doit seulement travailler avec les valeurs de la même taille:

Sieve (size_t n = 1)
{
    isPrime.assign (n+1, true);
    isPrime[0] = isPrime[1] = false;

    for (size_t i = 2; i <= static_cast<size_t>(sqrt((double)n)); ++i)
        if (isPrime[i]) 
            for (size_t j = i*i; j <= n; j += i)
                isPrime[j] = false;
}

Vous devriez faire de toute façon, car le mélange entiers signés et non signés, en particulier lorsque ces types sont de largeurs différentes, est périlleux et peut conduire à des erreurs inattendues.

Notez que l'utilisation de std::vector<char> également "résout" le problème, mais pour une raison différente: l'indice de calcul nécessaire pour accéder à un élément d'un std::vector<char> est beaucoup plus simple que l'accès à un élément d' std::vector<bool>. L'optimiseur est capable de générer un code de meilleure qualité pour le plus simple des calculs.

---

(*) Je ne travaille pas sur la génération de code, et je ne suis pas un expert de l'assemblée ou du faible niveau d'optimisation de la performance, mais en regardant le code généré, et étant donné qu'il est indiqué ici que Visual C++ 2010 génère un code de meilleure qualité, je suppose qu'il y a des possibilités d'amélioration dans le compilateur. Je vais m'assurer que la connexion bug que vous avez ouvert obtient transmis à l'équipe du compilateur afin de prendre un coup d'oeil.

Answer 2

J'ai testé avec vector<bool> dans VS2010: 32 bits besoins 1452ms tout en 64 bits besoins 1264ms pour terminer sur une i3.

Le même test dans VS2012 (sur i7 cette fois) les besoins de 700ms (32 bits) et 2730ms (64-bit), il est donc quelque chose de mal avec le compilateur de VS2012. Peut-être que vous pouvez signaler ce test comme un bug de Microsoft.

Mise à JOUR

Le problème est que le VS2012 compilateur utilise un temporaire de la pile variable pour une partie du code dans l'intérieur de la boucle lors de l'utilisation d'int comme itérateur. L'assemblée pièces énumérées ci-dessous sont de la partie du code à l'intérieur d' <vector>, en += operator de la std::vector<bool>::iterator.

size_t comme itérateur

Lors de l'utilisation d' size_t comme itérateur, une partie du code ressemble à ceci:

or  rax, -1
sub rax, rdx
shr rax, 5
lea rax, QWORD PTR [rax*4+4]
sub r8, rax

Ici, toutes les instructions d'utilisation utiliser les registres du CPU qui sont très rapides.

int comme itérateur

Lors de l'utilisation d' int comme itérateur, même partie ressemble à ceci:

or  rcx, -1
sub rcx, r8
shr rcx, 5
shl rcx, 2
mov rax, -4
sub rax, rcx
mov rdx, QWORD PTR _Tmp$6[rsp]
add rdx, rax

Ici, vous voyez les _Tmp$6 pile variable utilisée, ce qui provoque le ralentissement.

Point de compilateur dans la bonne direction

Le plus drôle, c'est que vous pouvez le compilateur dans la bonne direction en utilisant l' vector<bool>::iterator directement.

struct Sieve {
  std::vector<bool> isPrime;

  Sieve (int n = 1) {
    isPrime.assign(n + 1, true);

    std::vector<bool>::iterator it1 = isPrime.begin();
    std::vector<bool>::iterator end = it1 + n;
    *it1++ = false;
    *it1++ = false;
    for (int i = 2; i <= (int)sqrt((double)n); ++it1, ++i)
        if (*it1)
            for (std::vector<bool>::iterator it2 = isPrime.begin() + i * i; it2 <= end; it2 += i)
                *it2 = false;
  }
};

Answer 3

vector<bool> est un conteneur très spécial qui utilise un bit par élément plutôt que de fournir une sémantique de conteneur normale. Je soupçonne que la logique de manipulation des bits est beaucoup plus coûteuse lors de la compilation de 64 bits (elle utilise toujours des fragments de 32 bits pour contenir les bits ou pour une autre raison). vector<char> se comporte exactement comme un vector normal, il n'y a donc pas de logique particulière.

Vous pouvez également utiliser deque<bool> sans la spécialisation.