¿Por qué observo que la herencia múltiple es más rápida que la única?

13 minutos de lectura

avatar de usuario
owagh

Tengo los siguientes dos archivos: –

único.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";                                                                             
}

Y

múltiples.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";
}

Estoy usando gcc versión 3.4.6 con banderas -O2

Y estos son los resultados de tiempos que obtengo: –

múltiples :-

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

único :-

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

Por otro lado, si en multiple.cpp invierto el orden de derivación de clases así:

class B : public dummy, public A {

Luego obtengo los siguientes tiempos (que es un poco más lento que el de la herencia única, como cabría esperar gracias a los ajustes ‘thunk’ en este puntero que el código tendría que hacer): –

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

¿Alguna idea de por qué puede estar pasando esto? No parece haber ninguna diferencia en el ensamblaje generado para los tres casos en lo que respecta al bucle. ¿Hay algún otro lugar que deba mirar?

Además, he vinculado el proceso a un núcleo de CPU específico y lo ejecuto con prioridad en tiempo real con SCHED_RR.

EDITAR: – Esto fue notado por Mysticial y reproducido por mí. haciendo un

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

justo antes de que el bucle en single.cpp lleve a que single también sea tan rápido como el registro múltiple a 8.4 s, al igual que public A, public dummy.

  • +1 para una pregunta interesante y bien formulada.

    – Lucian Grigore

    3 mayo 2012 a las 20:50

  • No esperaría que la velocidad de la aritmética de enteros dependiera de los valores (el punto flotante ciertamente lo hace), pero establezca obj->a a un valor constante sólo para asegurarse.

    – Ben Voigt

    3 mayo 2012 a las 20:50

  • Configurándolo en 5. Tomando eso como entrada, pero sí, es 5 para todos los casos de ejecución. Pero como tú mismo señalas, no debería importar.

    – owagh

    3 mayo 2012 a las 20:52


  • ¿Cuándo creas una instancia del objeto A? Solo veo una nueva instancia de B, no A.

    – andré

    3 mayo 2012 a las 20:54

  • @owagh: no estoy hablando del valor del global, que se lee desde la consola. estoy hablando de obj->aque nunca se asigna y por lo tanto es indeterminado.

    – Ben Voigt

    3 mayo 2012 a las 20:55

avatar de usuario
místico

Tenga en cuenta que esta respuesta es altamente especulativa.

A diferencia de algunas de mis otras respuestas a preguntas del tipo “¿Por qué X es más lento que Y?”, No he podido proporcionar evidencia sólida para respaldar esta respuesta.


Después de jugar con esto durante aproximadamente una hora, creo que se debe a la alineación de direcciones de tres cosas:

(La respuesta de Owagh también sugiere la posibilidad de alineación de instrucciones).

La razón por la que la herencia múltiple es más lenta que la herencia única no es porque sea “mágicamente” rápida, sino porque el caso de la herencia única se está ejecutando en un compilador o en un “hipo” de hardware.


Si descarga el ensamblaje para los casos de herencia simple y múltiple, son idénticos (nombres de registro y todo) dentro del ciclo anidado.

Aquí está el código que 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.
}

El ensamblaje para el bucle anidado es idénticos en casos de herencia única y múltiple:

.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

Sin embargo, la diferencia de rendimiento que veo es:

  • Único: 9,4 segundos
  • Múltiple: 8.06 segundos

Xeon X5482, Ubuntu, CCG 4.6.1 x64.

Esto me lleva a la conclusión de que la diferencia debe depender de los datos.

Si observa ese ensamblaje, notará que las únicas instrucciones que podrían tener una latencia variable son las cargas:

    ; %rbp = vtable

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

seguido de algunos accesos más a la memoria dentro de la llamada f().


Sucede que en el ejemplo de herencia única, las compensaciones de los valores antes mencionados no son favorables para el procesador. No tengo ni idea de porqué. Pero tenía que sospechar algo, serían conflictos de caché y banco de manera similar a la región 2 en el diagrama de esta pregunta.

Al reorganizar el código y agregar funciones ficticias, puedo cambiar estas compensaciones, lo que en muchos casos eliminará esta ralentización y hará que la herencia única sea tan rápida como el caso de herencia múltiple.


Por ejemplo, quitando el system("pause") invierte los tiempos:

#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");
}
  • Único: 8,06 segundos
  • Múltiple: 9,4 segundos

  • No creo que los conflictos del banco de caché sean los culpables, la caché de instrucciones es fundamentalmente diferente a los datos L1 (predecodificación, límites de instrucciones, etc.) aún más especulativo

    -Gunther Piez

    4 de mayo de 2012 a las 0:12


  • Sí, obviamente fue solo una suposición descabellada. Es difícil probar algo porque cualquier modificación al código cambiará todas las compensaciones.

    – Místico

    4 de mayo de 2012 a las 0:14

  • Supongo que si pudiera pausar la ejecución e inspeccionar el código en ejecución en la memoria (algo así como un entrenador de juegos) eso podría ayudarlo.

    – owagh

    4 de mayo de 2012 a las 0:40

  • Sí, me imagino que un emulador de ciclo preciso funcionará. No estoy seguro de si existen para las máquinas Intel actuales fuera de Intel.

    – Místico

    4 de mayo de 2012 a las 0:42

  • Bueno, esta parece ser la respuesta más sensata junto con la explicación en su pregunta anterior. Voy a votar esto, pero espero una respuesta más definitiva.

    – owagh

    7 mayo 2012 a las 13:31

Creo que tengo al menos alguna pista más sobre por qué esto puede estar sucediendo. El ensamblaje de los bucles es exactamente idéntico, ¡pero los archivos de objetos no lo son!

Para el bucle con el cout al principio (es decir)

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

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

Obtengo lo siguiente en el archivo de objeto: –

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>                                 

Sin embargo, sin el cout, los bucles se convierten en :- (.cpp primero)

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

Ahora, .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>                          

Entonces, debo decir que no se debe realmente a un alias falso como señala Mysticial, sino simplemente a estos NOP que emite el compilador/enlazador.

El montaje en ambos casos es: –

.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

Ahora, .p2align 4,,7 insertará datos/NOP hasta que el contador de instrucciones para la siguiente instrucción tenga los últimos cuatro bits 0 para un máximo de 7 NOP. Ahora la dirección de la instrucción justo después de p2align en el caso sin cout y antes del relleno sería

0x400a59 = 0b101001011001

Y dado que se necesitan

Por otro lado, para el caso de cout, la instrucción justo después de .p2align aterriza en

0x400932 = 0b100100110010

y se necesitarían> 7 NOP para rellenarlo hasta un límite divisible por 16. Por lo tanto, no hace eso.

Por lo tanto, el tiempo adicional necesario se debe simplemente a los NOP con los que el compilador rellena el código (para una mejor alineación de la memoria caché) al compilar con el indicador -O2 y no se debe realmente a un alias falso.

Creo que esto resuelve el problema. estoy usando http://sourceware.org/binutils/docs/as/P2align.html
como mi referencia para lo que realmente hace .p2align.

  • +1 me gusta esto. También consideré la posibilidad de alinear las instrucciones. Pero nunca pude probarlo.

    – Místico

    7 mayo 2012 a las 15:39

Esta respuesta es aún más especulativa.

Después de jugar con esto durante 5 minutos y leer la respuesta de Mysticial, la conclusión es que se trata de un problema de hardware: el código generado en el bucle activo es básicamente el mismo, por lo que no es un problema con el compilador, eso deja el hardware como el único sospechoso.

Algunos pensamientos aleatorios:

  • Predicción de rama
  • Alineación o creación de alias parcial de direcciones de destino de rama (= función)
  • La memoria caché L1 se calienta después de leer la misma dirección todo el tiempo
  • Rayos cósmicos

  • ¿Puede dar más detalles sobre lo que quiere decir con alineación o alias parcial y cómo eso podría afectar las cosas? ¿El caché L1 que se calienta debería hacerlo más rápido en lugar de más lento?

    – owagh

    4 de mayo de 2012 a las 1:43

  • @owagh Esta pregunta a la que me vinculé desde mi respuesta es probablemente el ejemplo más notorio en StackOverflow de dónde la alineación y el alias parcial pueden diezmar el rendimiento. Así que podría ser una buena lectura. No está claro cómo se aplica a su pregunta. Cualquier intento de probar una hipótesis requiere modificar el código, lo que cambiará la alineación de todo. Así que es un objetivo en movimiento que no puedo alcanzar. (como he mostrado comentando una línea de código irrelevante para invertir los números de rendimiento…)

    – Místico

    4 de mayo de 2012 a las 2:27

  • @owagh Mientras escribía un programa para probar el tiempo de acceso aleatorio de los cachés y la memoria, noté que al probar un patrón de acceso de exactamente 2 Mib en un Core2 con 6 MiB de caché de segundo nivel, la temperatura saltó cerca de la frecuencia del acelerador. Esto sucedió solo mientras se ejecutaba en uno de los cuatro núcleos y con exactamente 2 MiB, no 4, no 1. Esto casi sería una buena pregunta aquí 🙂

    -Gunther Piez

    4 de mayo de 2012 a las 9:08

  • Así que supongo que podemos suponer que tiene algo que ver con la alineación, pero no estamos exactamente seguros. qué

    – owagh

    4 mayo 2012 a las 15:20

avatar de usuario
ben voigt

Con su código actual, el compilador es libre de desvirtualizar las llamadas a obj->f()ya que obj no puede tener ningún tipo de dinámica que no sea class B.

yo sugeriría

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

Mi suposicion es class B : public dummy, public A tiene una alineación desfavorable en cuanto a A está preocupado Almohadilla dummy a 16 bytes y ver si hay una diferencia.

  • Creo que esa parte era la esperada. El problema es la diferencia de tiempo entre class B : public A y class B : public A, public dummy a favor de la herencia múltiple.

    – Ben Voigt

    3 mayo 2012 a las 20:53


  • Sí, esto se entendió: “como era de esperar gracias a los ajustes ‘thunk'”.

    – José

    3 mayo 2012 a las 20:54

  • @ Ben Voigt Eso es precisamente lo que esperaría en ambas situaciones.

    – owagh

    3 mayo 2012 a las 20:55

  • @Anycorn No hay problema.

    – José

    3 mayo 2012 a las 21:22


  • Creo que esa parte era la esperada. El problema es la diferencia de tiempo entre class B : public A y class B : public A, public dummy a favor de la herencia múltiple.

    – Ben Voigt

    3 mayo 2012 a las 20:53


  • Sí, esto se entendió: “como era de esperar gracias a los ajustes ‘thunk'”.

    – José

    3 mayo 2012 a las 20:54

  • @ Ben Voigt Eso es precisamente lo que esperaría en ambas situaciones.

    – owagh

    3 mayo 2012 a las 20:55

  • @Anycorn No hay problema.

    – José

    3 mayo 2012 a las 21:22


¿Ha sido útil esta solución?