c++ - poo - polimorfismo programacion

¿Por qué no se puede resolver el polimorfismo en tiempo de ejecución en tiempo de compilación?

Question

Considerar:

#include<iostream>
using namespace std;

class Base
{
    public:
        virtual void show() { cout<<" In Base /n"; }
};

class Derived: public Base
{
    public:
       void show() { cout<<"In Derived /n"; }
};

int main(void)
{
    Base *bp = new Derived;
    bp->show();  // RUN-TIME POLYMORPHISM
    return 0;
}

¿Por qué este código causa polimorfismo en tiempo de ejecución y por qué no se puede resolver en tiempo de compilación?

Answer 1

¿Por qué este código causa polimorfismo en tiempo de ejecución y por qué no se puede resolver en tiempo de compilación?

¿Qué te hace pensar que sí?

Está haciendo una suposición común: el hecho de que el lenguaje identifique este caso como el uso del polimorfismo en tiempo de ejecución no significa que una implementación tenga que despacharse en tiempo de ejecución. El estándar C ++ tiene una regla llamada "como si": los efectos observables de las reglas del estándar C ++ se describen con respecto a una máquina abstracta, y las implementaciones son libres de lograr dichos efectos observables como lo deseen.

En realidad, la desvirtualización es la palabra general que se usa para hablar sobre las optimizaciones del compilador con el objetivo de resolver llamadas a métodos virtuales en tiempo de compilación.

El objetivo no es tanto reducir la sobrecarga de llamadas virtuales casi imperceptible (si la predicción de bifurcación funciona bien), se trata de eliminar un cuadro negro. Las mejores ganancias, en términos de optimizaciones, se basan en la inclusión de las llamadas: esto abre la propagación constante y una gran cantidad de optimización, y la integración solo se puede lograr cuando se conoce el cuerpo de la función que se llama en tiempo de compilación (ya que implicaba eliminar la llamada y reemplazarla por el cuerpo de la función).

Algunas oportunidades de desvirtualización:

• una llamada a un método final o un método virtual de una clase final se desvirtualiza trivialmente
• una llamada a un método virtual de una clase definida en un espacio de nombres anónimo se puede desvirtualizar si esa clase es una hoja en la jerarquía
• una llamada a un método virtual través de una clase base se puede desvirtualizar si el tipo dinámico del objeto se puede establecer en tiempo de compilación (que es el caso de su ejemplo, con la construcción en la misma función)

Sin embargo, por el estado del arte, querrás leer el blog de Honza Hubička. Honza es un desarrollador de gcc y el año pasado trabajó en la desvirtualización especulativa : el objetivo es calcular las probabilidades de que el tipo dinámico sea A, B o C y luego desvirtualizar especulativamente las llamadas de alguna manera como transformando:

Base& b = ...;
b.call();

dentro:

Base& b = ...;
if      (b.vptr == &VTableOfA) { static_cast<A&>(b).call(); }
else if (b.vptr == &VTableOfB) { static_cast<B&>(b).call(); }
else if (b.vptr == &VTableOfC) { static_cast<C&>(b).call(); }
else                           { b.call(); } // virtual call as last resort

Honza hizo una publicación de 5 partes:

• Desvirtualización en C ++, parte 1
• Desvirtualización en C ++, parte 2 (desvirtualización de nivel medio de bajo nivel reenviando tiendas a cargas)
• Desvirtualización en C ++, parte 3 (construcción de la jerarquía de tipos)
• Desvirtualización en C ++, parte 4 (análisis del gráfico de herencia de tipos por diversión y ganancias)
• Desvirtualización en C ++, parte 5 (desvirtualización impulsada por retroalimentación)

Answer 2

Básicamente, el compilador debería ser capaz de darse cuenta de que esto no debería resultar en un polimorfismo de tiempo de ejecución en su caso muy simple. Lo más probable es que haya compiladores que realmente lo hacen, pero eso es principalmente una conjetura.

El problema es el caso general cuando en realidad está construyendo un complejo, y aparte de los casos con dependencias de la biblioteca, o la complejidad de analizar las unidades de compilación múltiple posteriores a la compilación, lo que requeriría mantener múltiples versiones del mismo código, lo que eliminaría AST generación , el problema real se reduce a la capacidad de decisión y el problema de detención.

Este último no permite resolver el problema si se puede desvirtualizar una llamada en el caso general.

El problema de detención es decidir si un programa dado una entrada se detendrá ( decimos que el par de entrada de programa se detiene ). Se sabe que no existe un algoritmo general, por ejemplo, un compilador , que resuelva todos los pares posibles de entrada de programa.

Para que el compilador decida para cualquier programa si una llamada debe hacerse virtual o no, debe poder decidir eso para todos los pares posibles de entrada de programa.

Para hacer eso, el compilador necesitaría tener un algoritmo A que decida que dado el programa P1 y el programa P2 donde P2 hace una llamada virtual, luego programe P3 {while ({P1, I}! = {P2, I})} se detiene para cualquier entrada I.

Por lo tanto, el compilador para poder descubrir todas las posibles desvirtualizaciones debe poder decidir eso para cualquier par (P3, I) sobre todos los posibles P3 e I; lo cual es indecidible para todos porque A no existe. Sin embargo, se puede decidir para casos específicos que pueden ser desconcertantes.

Es por eso que en su caso la llamada puede ser descentralizada, pero no en ningún caso.

Answer 3

Eso podría resolverse fácilmente en tiempo de compilación si el optimizador decidiera hacerlo.

El estándar especifica el mismo comportamiento que si hubiera ocurrido el polimorfismo en tiempo de ejecución. No es específico que se logre a través del polimorfismo real en tiempo de ejecución.

Answer 4

Hay muchas razones por las cuales los compiladores en general no pueden reemplazar la decisión de tiempo de ejecución con llamadas estáticas, principalmente porque implica información que no está disponible en el momento de la compilación, por ejemplo, configuración o entrada del usuario. Aparte de eso, quiero señalar dos razones adicionales por las que esto no es posible en general.

Primero, el modelo de compilación de C ++ se basa en unidades de compilación separadas. Cuando se compila una unidad, el compilador solo sabe lo que se define en los archivos fuente que se compilan. Considere una unidad de compilación con una clase base y una función tomada como referencia a la clase base:

struct Base {
    virtual void polymorphic() = 0;
};
void foo(Base& b) {b.polymorphic();}

Cuando se compila por separado, el compilador no tiene conocimiento sobre los tipos que implementan Base y, por lo tanto, no puede eliminar el despacho dinámico. Tampoco es algo que queramos porque queremos poder extender el programa con una nueva funcionalidad mediante la implementación de la interfaz. Puede ser posible hacerlo en el momento del enlace , pero solo bajo el supuesto de que el programa está completamente completo. Las bibliotecas dinámicas pueden romper esta suposición, y como se puede ver a continuación, siempre habrá casos en los que no sea posible.

Una razón más fundamental proviene de la teoría de la computabilidad. Incluso con información completa, no es posible definir un algoritmo que calcule si se alcanzará o no una línea determinada en un programa. Si pudiera, podría resolver el problema de detención: para un programa P , creo un nuevo programa P'' agregando una línea adicional al final de P El algoritmo ahora podría decidir si se alcanza esa línea, lo que resuelve el problema de detención.

No poder decidir en general significa que los compiladores no pueden decidir qué valor se asigna a las variables en general, por ejemplo

bool someFunction( /* arbitrary parameters */ ) {
     // ...
}

// ...
Base* b = nullptr;
if (someFunction( ... ))
    b = new Derived1();
else
    b = new Derived2();

b->polymorphicFunction();

Incluso cuando se conocen todos los parámetros en tiempo de compilación, no es posible demostrar en general qué ruta se tomará a través del programa y qué tipo b estático tendrá. Las aproximaciones pueden y se hacen optimizando los compiladores, pero siempre hay casos en los que no funciona.

Dicho esto, los compiladores de C ++ se esfuerzan mucho por eliminar el despacho dinámico porque abre muchas otras posibilidades de optimización, principalmente de poder en línea y propagar el conocimiento a través del código. Si es interesante, puede encontrar una serie de publicaciones de blog interesantes para la implementación de la desvirtualización de GCC .

Answer 5

Los compiladores desvirtualizan rutinariamente tales llamadas, cuando se conoce el tipo estático del objeto. Pegar su código tal como está en el Explorador de compiladores produce el siguiente ensamblado:

main:                                   # @main
        pushq   %rax
        movl    std::cout, %edi
        movl    $.L.str, %esi
        movl    $12, %edx
        callq   std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        xorl    %eax, %eax
        popq    %rdx
        retq

        pushq   %rax
        movl    std::__ioinit, %edi
        callq   std::ios_base::Init::Init()
        movl    std::ios_base::Init::~Init(), %edi
        movl    std::__ioinit, %esi
        movl    $__dso_handle, %edx
        popq    %rax
        jmp     __cxa_atexit            # TAILCALL

.L.str:
        .asciz  "In Derived /n"

Incluso si no puede leer el ensamblado, puede ver que solo "In Derived /n" está presente en el ejecutable. No solo se ha optimizado el despacho dinámico, también se ha optimizado toda la clase base.

Answer 6

Porque en el caso general, es imposible en el momento de la compilación determinar qué tipo será en tiempo de ejecución. Su ejemplo se puede resolver en tiempo de compilación (vea la respuesta de @Quentin), pero se pueden construir casos que no pueden, como:

Base *bp;
if (rand() % 10 < 5)
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time

EDITAR: Gracias a @nwp, aquí hay un caso mucho mejor. Algo como:

Base *bp;
char c;
std::cin >> c;
if (c == ''d'')
    bp = new Derived;
else
    bp = new Base;
bp->show(); // only known at run time 

Además, por el corolario de la prueba de Turing , se puede demostrar que, en el caso general , es matemáticamente imposible para un compilador de C ++ saber a qué apunta un puntero de clase base en tiempo de ejecución.

Supongamos que tenemos una función similar a un compilador de C ++:

bool bp_points_to_base(const string& program_file);

Eso toma como su entrada program_file : el nombre de cualquier archivo de texto de código fuente C ++ donde un puntero bp (como en el OP) llama a su función miembro virtual show() . Y puede determinar en el caso general (en el punto de secuencia A donde la función miembro virtual show() se invoca primero a través de bp ): si el puntero bp apunta a una instancia de Base o no.

Considere el siguiente fragmento del programa C ++ "q.cpp":

Base *bp;
if (bp_points_to_base("q.cpp")) // invokes bp_points_to_base on itself
    bp = new Derived;
else
    bp = new Base;
bp->show();  // sequence point A

Ahora, si bp_points_to_base determina que en "q.cpp": bp apunta a una instancia de Base en A entonces "q.cpp" apunta bp a otra cosa en A Y si determina que en "q.cpp": bp no apunta a una instancia de Base en A , entonces "q.cpp" apunta bp a una instancia de Base en A Esto es una contradicción. Entonces nuestra suposición inicial es incorrecta. Entonces bp_points_to_base no se puede escribir para el caso general .