Pourquoi suis-je en train d'observer que l'héritage multiple est plus rapide que celui de single?

Question

J'ai les deux fichiers suivants :-

single.cpp :-

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long a=0;

class A {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; } 
};

class B : public A {                                                                              
  public:                                                                                                                                                                        
    virtual int f() __attribute__ ((noinline)) { return a; }                                      
    void g() __attribute__ ((noinline)) { return; }                                               
};                                                                                                

int main() {                                                                                      
  cin>>a;                                                                                         
  A* obj;                                                                                         
  if (a>3)                                                                                        
    obj = new B();
  else
    obj = new A();                                                                                

  unsigned long result=0;                                                                         

  for (int i=0; i<65535; i++) {                                                                   
    for (int j=0; j<65535; j++) {                                                                 
      result+=obj->f();                                                                           
    }                                                                                             
  }                                                                                               

  cout<<result<<"\n";                                                                             
}

Et

multiple.cpp :-

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long a=0;

class A {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; }
};

class dummy {
  public:
    virtual void g() __attribute__ ((noinline)) { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() __attribute__ ((noinline)) { return a; }
    virtual void g() __attribute__ ((noinline)) { return; }
};


int main() {
  cin>>a;
  A* obj;
  if (a>3)
    obj = new B();
  else
    obj = new A();

  unsigned long result=0;

  for (int i=0; i<65535; i++) {
    for (int j=0; j<65535; j++) {
      result+=obj->f();
    }
  }

  cout<<result<<"\n";
}

Je suis en utilisant gcc version 3.4.6 avec des drapeaux-O2

Et c'est les timings résultats que j'obtiens :-

multiples :-

real    0m8.635s
user    0m8.608s
sys 0m0.003s

unique :-

real    0m10.072s
user    0m10.045s
sys 0m0.001s

D'autre part, si dans multiple.cpp j'ai inverser l'ordre de dérivation de classe ainsi :-

class B : public dummy, public A {

Puis-je obtenir le minutage suivant (qui est légèrement plus lente que celle de l'héritage simple, comme on peut le deviner grâce à 'thunk' " ajustement de la ce pointeur que le code aurait besoin de le faire) :-

real    0m11.516s
user    0m11.479s
sys 0m0.002s

Aucune idée de pourquoi cela peut-il se passer? Il ne semble pas y avoir de différence dans l'assembly généré pour tous les trois cas, aussi loin que la boucle est concerné. Est-il un autre endroit que je dois regarder?

Aussi, j'ai lié le processus à un cœur de processeur et je suis en cours d'exécution sur une priorité en temps réel avec SCHED_RR.

EDIT:- il a été remarqué par Mysticial et reproduit par moi. Faire un

cout << "vtable: " << *(void**)obj << endl;

juste avant la boucle single.cpp conduit à la seule aussi à être aussi rapide que plusieurs de pointage à 8,4 s tout comme le public A, public factice.

Answer 1

Remarque, cette réponse est très spéculatif.

Contrairement à certains de mes autres réponses à des questions du type "Pourquoi X plus lent que Y", j'ai été incapable de fournir des preuves solides pour la sauvegarde de cette réponse.

---

Après bricoler avec ce pendant environ une heure maintenant, je pense que c'est due à l'adresse de l'alignement de trois choses:

• L'adresse de l' obj
• L'adresse de la Table de Méthode Virtuelle de A
• L'adresse de la fonction f()

(owagh réponse laisse également entrevoir la possibilité d'enseignement de l'alignement.)

La raison pour laquelle l'héritage multiple est plus lent que le seul héritage n'est pas parce que c'est "comme par magie" vite, mais parce que l'héritage simple affaire est en cours d'exécution, soit d'un compilateur ou d'un matériel "hoquet".

---

Si vous videz l'assemblée pour la seule et l'héritage multiple des cas, ils sont identiques (inscrire les noms et tout et tout) à l'intérieur de la boucle imbriquée.

Voici le code que j'ai compilé:

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
unsigned long a=0;


#ifdef SINGLE
class A {
  public:
    virtual int f() { return a; } 
};

class B : public A {
  public:
    virtual int f() { return a; }                                      
    void g() { return; }                                               
};       
#endif

#ifdef MULTIPLE
class A {
  public:
    virtual int f() { return a; }
};

class dummy {
  public:
    virtual void g() { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() { return a; }
    virtual void g() { return; }
};
#endif

int main() {
    cin >> a;
    A* obj;
    if (a > 3)
        obj = new B();
    else
        obj = new A();

    unsigned long result = 0;


    clock_t time0 = clock();

    for (int i=0; i<65535; i++) {
        for (int j=0; j<65535; j++) {
            result += obj->f();
        }
    }      

    clock_t time1 = clock();   
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;    

    cout << result << "\n";
    system("pause");  //  This is useless in Linux, but I left it here for a reason.
}

L'assemblée pour la boucle imbriquée est identique dans les deux uniques et multiples en cas d'héritage:

.L5:
    call    clock
    movl    $65535, %r13d
    movq    %rax, %r14
    xorl    %r12d, %r12d
    .p2align 4,,10
    .p2align 3
.L6:
    movl    $65535, %ebx
    .p2align 4,,10
    .p2align 3
.L7:
    movq    0(%rbp), %rax
    movq    %rbp, %rdi
    call    *(%rax)
    cltq
    addq    %rax, %r12
    subl    $1, %ebx
    jne .L7
    subl    $1, %r13d
    jne .L6
    call    clock

Pourtant, la différence de performances, je vois:

• Unique: 9,4 secondes
• Multiples: 8.06 secondes

Xeon X5482, Ubuntu, GCC 4.6.1 x64.

Cela m'amène à la conclusion que la différence doit dépendre des données.

Si vous regardez cette assemblée, vous remarquerez que les seules instructions qui pourrait avoir de latence variable sont les charges:

    ; %rbp = vtable

movq    0(%rbp), %rax   ; Dereference function pointer from vtable
movq    %rbp, %rdi
call    *(%rax)         ; Call function pointer - f()

suivie par un peu plus de l'accès à la mémoire à l'intérieur de l'appel de l' f().

---

C'est juste que dans le seul et unique exemple d'héritage, les décalages de ladite valeurs ne sont pas favorables pour le processeur. Je n'ai aucune idée pourquoi. Mais j'ai eu à soupçonner quelque chose, ce serait de cache-banque des conflits d'une manière similaire pour la région 2 dans le diagramme de cette question.

En réorganisant le code et l'ajout de mannequin fonctions, je peux changer ces décalages qui, dans beaucoup de cas permettra d'éliminer cette de ralentir et de faire de l'héritage simple, rapide, comme le cas de l'héritage multiple.

---

Par exemple, en supprimant l' system("pause") inverse la fois:

#ifdef SINGLE
class A {
  public:
    virtual int f() { return a; } 
};

class B : public A {
  public:
    virtual int f() { return a; }                                      
    void g() { return; }                                               
};       
#endif

#ifdef MULTIPLE
class A {
  public:
    virtual int f() { return a; }
};

class dummy {
  public:
    virtual void g() { return; }
};

class B : public A, public dummy {
  public:
    virtual int f() { return a; }
    virtual void g() { return; }
};
#endif

int main() {
    cin >> a;
    A* obj;
    if (a > 3)
        obj = new B();
    else
        obj = new A();

    unsigned long result = 0;


    clock_t time0 = clock();

    for (int i=0; i<65535; i++) {
        for (int j=0; j<65535; j++) {
            result += obj->f();
        }
    }      

    clock_t time1 = clock();   
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;    

    cout << result << "\n";
//    system("pause");
}

• Unique: 8.06 secondes
• Multiples: 9,4 secondes

Answer 2

Je crois que j'ai au moins quelques de plomb sur lesquelles cela pourrait se produire. L'assemblée des boucles est exactement identiques, mais les fichiers ne sont pas!

Pour la boucle avec le cout au premier (c)

cout << "vtable: " << *(void**)obj << endl;

for (int i=0; i<65535; i++) {
  for (int j=0; j<65535; j++) {
    result+=obj->f();
  }
}

Je reçois le texte suivant dans le fichier d'objet :-

40092d:       bb fe ff 00 00          mov    $0xfffe,%ebx                                       
400932:       48 8b 45 00             mov    0x0(%rbp),%rax                                     
400936:       48 89 ef                mov    %rbp,%rdi                                          
400939:       ff 10                   callq  *(%rax)                                            
40093b:       48 98                   cltq                                                      
40093d:       49 01 c4                add    %rax,%r12                                          
400940:       ff cb                   dec    %ebx                                               
400942:       79 ee                   jns    400932 <main+0x42>                                 
400944:       41 ff c5                inc    %r13d                                              
400947:       41 81 fd fe ff 00 00    cmp    $0xfffe,%r13d                                      
40094e:       7e dd                   jle    40092d <main+0x3d>                                 

Toutefois, sans le cout, les boucles deviennent :- (.rpc en premier)

for (int i=0; i<65535; i++) {
  for (int j=0; j<65535; j++) {
    result+=obj->f();
  }
}

Maintenant, .obj :-

400a54:       bb fe ff 00 00          mov    $0xfffe,%ebx
400a59:       66                      data16                                                    
400a5a:       66                      data16 
400a5b:       66                      data16                                                    
400a5c:       90                      nop                                                       
400a5d:       66                      data16                                                    
400a5e:       66                      data16                                                    
400a5f:       90                      nop                                                       
400a60:       48 8b 45 00             mov    0x0(%rbp),%rax                                     
400a64:       48 89 ef                mov    %rbp,%rdi                                          
400a67:       ff 10                   callq  *(%rax)
400a69:       48 98                   cltq   
400a6b:       49 01 c4                add    %rax,%r12                                          
400a6e:       ff cb                   dec    %ebx                                               
400a70:       79 ee                   jns    400a60 <main+0x70>                                 
400a72:       41 ff c5                inc    %r13d                                              
400a75:       41 81 fd fe ff 00 00    cmp    $0xfffe,%r13d
400a7c:       7e d6                   jle    400a54 <main+0x64>                          

Donc, je dois dire que ce n'est pas vraiment à cause de faux aliasing comme Mysticial points, mais simplement en raison de ces Opr, que le compilateur/linker est électroluminescentes.

L'assemblée, dans les deux cas :-

.L30:
        movl    $65534, %ebx
        .p2align 4,,7                   
.L29:
        movq    (%rbp), %rax            
        movq    %rbp, %rdi
        call    *(%rax)
        cltq    
        addq    %rax, %r12                                                                        
        decl    %ebx
        jns     .L29
        incl    %r13d 
        cmpl    $65534, %r13d
        jle     .L30

Maintenant, .p2align 4,,7 insérer des données/Opr, jusqu'à ce que l'instruction de compteur pour la prochaine instruction a les quatre derniers bits de 0 pour un maximum de 7 Opr. Maintenant l'adresse de l'instruction juste après p2align dans le cas sans cout et avant de rembourrage serait

0x400a59 = 0b101001011001

Et comme il faut <=7 Opr, pour aligner la prochaine instruction, il sera en fait le faire dans le fichier de l'objet.

D'autre part, pour le cas avec le cout, l'instruction juste après .p2align terres jusqu'à

0x400932 = 0b100100110010

et il faudrait > 7 Opr au pad à un divisibles par 16 frontière. Par conséquent, il ne le fait pas.

Donc, le temps supplémentaire est tout simplement en raison de l'Opr, que le compilateur plaquettes avec le code (pour mieux le cache de l'alignement) lors de la compilation avec l'option-O2 drapeau et pas vraiment à cause de faux aliasing.

Je pense que cela résout le problème. Je suis à l'aide de http://sourceware.org/binutils/docs/as/P2align.html comme ma référence pour ce .p2align la réalité.

Answer 3

Cette réponse est encore plus spéculatives.

Après bricoler avec ce pendant 5 minutes et la lecture Mysticials réponse, la conclusion est que c'est un problème matériel: Le code généré dans la chaleur de la boucle est fondamentalement la même, de sorte qu'il n'est pas un problème avec le compilateur, qui quitte le matériel que le seul suspect.

Quelques pensées éparses:

• Direction de la prévision
• L'alignement ou partielle de l'aliasing de la branche (=fonction) cible adresses
• Le cache L1 chaude après la lecture de la même adresse tout le temps
• Les rayons cosmiques

Answer 4

Avec votre code actuel, le compilateur est libre de devirtualiser les appels à obj->f() , puisque obj ne peut avoir aucun type dynamique autre que class B .

Je suggère

 if (a>3) {
    B* objb = new B();
    objb->a = 5;
    obj = objb;
}
else
    obj = new A();
 

Answer 5

Mon hypothèse est que class B : public dummy, public A a un alignement défavorable en ce qui concerne A . Pad dummy à 16 octets et voyez s'il y a une différence.