¿Esquemas alternativos para implementar vptr?

Question

Esta pregunta no se trata del lenguaje C++ en sí mismo (es decir, no del estándar) sino de cómo llamar a un compilador para implementar esquemas alternativos para la función virtual.

El esquema general para implementar funciones virtuales es usar un puntero a una tabla de punteros.

class Base { 
    private: 
     int m; 
    public: 
     virtual metha(); 
}; 

equivalentemente en, digamos, C sería algo así como

struct Base { 
    void (**vtable)(); 
    int m; 
} 

el primer miembro es por lo general un puntero a una lista de funciones virtuales, etc. (un trozo de área de la memoria que la aplicación tiene sin control de). Y en la mayoría de los casos esto cuesta el tamaño de un puntero antes de considerar a los miembros, etc. Así que en un esquema de direccionamiento de 32 bits alrededor de 4 bytes, etc. Si creaste una lista de objetos polimórficos de 40k en tus aplicaciones, esto es alrededor de 40k x 4 bytes = 160k bytes antes de cualquier variable miembro, etc. También sé que esta es la implementación más rápida y común entre las compilaciones de C++.

Sé que esto es complicado por herencia múltiple (especialmente con clases virtuales en ellos, es decir, estructura de diamante, etc.).

Una manera alternativa de hacer lo mismo es tener la primera variable como un identificador de índice a una tabla de vptrs (equivalente en C como abajo)

struct Base { 
    char classid;  // the classid here is an index into an array of vtables 
    int  m; 
} 

Si el número total de clases en una aplicación es menos de 255 (incluidas todas las instancias de plantillas posibles, etc.), entonces una char es lo suficientemente buena como para contener un índice, lo que reduce el tamaño de todas las clases polimórficas en la aplicación (excluyo los problemas de alineación, etc.).

Mi pregunta es, ¿hay algún cambio en GNU C++, LLVM o cualquier otro compilador para hacer esto? o reducir el tamaño de los objetos polimórficos?

Editar: Entiendo acerca de los problemas de alineación señalados. También un punto adicional, si esto fuera en un sistema de 64 bits (suponiendo un vptr de 64bit) con cada miembro de objeto polimórfico que cuesta alrededor de 8 bytes, entonces el costo de vptr es el 50% de la memoria. Esto se relaciona principalmente con pequeños polimórficos creados en masa, por lo que me pregunto si este esquema es posible para al menos objetos virtuales específicos, si no toda la aplicación.

Answer 1

Su sugerencia es interesante, pero no funcionará si el ejecutable está compuesto de varios módulos, pasando objetos entre ellos. Dado que se compilan por separado (digamos DLL), si un módulo crea un objeto y lo pasa a otro, y el otro invoca un método virtual, ¿cómo sabe a qué tabla se refiere el classid? No podrá agregar otro moduleid porque es posible que los dos módulos no se conozcan entre sí cuando se compilan. Así que a menos que utilice punteros, creo que es un callejón sin salida ...

Answer 2

Un par de observaciones:

1. Sí, un valor más pequeño podría ser utilizado para representar a la clase, pero algunos procesadores requieren que los datos alinearse de manera que el ahorro en espacio se pierda por el requisito de alinear los valores de datos a, por ejemplo, 4 límites de bytes. Además, el ID de clase debe estar en un lugar bien definido para todos los miembros de un árbol de herencia polimórfica, por lo que es probable que esté por delante de otra fecha, por lo que los problemas de alineación no se pueden evitar.

2. El costo de almacenar el puntero se ha trasladado al código, donde cada uso de una función polimórfica requiere un código para traducir el identificador de clase a un puntero vtable o a una estructura de datos equivalente. Entonces no es gratis. Claramente, la compensación de costos depende del volumen de código frente al número de objetos.

3. Si los objetos se asignan desde el montón, generalmente hay espacio perdido en orer para asegurar que los objetos están alineados con el peor límite, por lo que incluso si hay una pequeña cantidad de código y una gran cantidad de objetos polimórficos, la administración de memoria puede ser significativamente mayor que la diferencia entre un puntero y un char.

4. Para permitir la compilación independiente de programas, debe conocerse el número de clases en el programa completo y, por lo tanto, el tamaño del id. De clase en tiempo de compilación; de lo contrario, no se puede compilar el código para acceder a él . Esto sería una sobrecarga significativa. Es más sencillo solucionarlo en el peor de los casos y simplificar la compilación y el enlace.

Por favor, no deje que me detenga tratando, pero hay mucho más para resolver problemas usando cualquier técnica que puede utilizar un identificador de tamaño variable para derivar la dirección de la función.

me animo encarecidamente a mirar Ian Piumarta's Cola también en Wikipedia Cola

De hecho se requiere un enfoque diferente, y utiliza el puntero de una manera mucho más flexible, a la construcción de la herencia, o basado en prototipos, o cualquier otro mecanismo que el desarrollador requiere.

Answer 3

La respuesta corta es que no, no conozco ningún cambio para hacer esto con cualquier compilador común de C++.

La respuesta más larga es que para hacer esto, tendría que crear la mayor parte de la inteligencia en el enlazador, por lo que podría coordinar la distribución de los ID en todos los archivos de objeto que se vinculan entre sí.

También me gustaría señalar que en general no sería muy útil. Al menos en un caso típico, quiere que cada elemento de una estructura/clase se encuentre en un límite "natural", lo que significa que su dirección inicial es un múltiplo de su tamaño. Utilizando su ejemplo de una clase que contiene una sola int, el compilador asignaría un byte para el índice vtable, seguido inmediatamente de tres byes de relleno para que el siguiente int aterrice en una dirección que era un múltiplo de cuatro. El resultado final sería que los objetos de la clase ocuparían precisamente la misma cantidad de almacenamiento que si usáramos un puntero.

Agregaría que esta tampoco es una excepción exagerada. Durante años, el consejo estándar para minimizar el relleno insertado en las estructuras/clases ha sido colocar los artículos que se espera sean más grandes al principio, y avanzar hacia los más pequeños. Eso significa que en código más, terminarías con esos mismos tres bytes de relleno antes del primer miembro explícitamente definido de la estructura.

Para obtener algo bueno de esto, debe tenerlo en cuenta, y tener una estructura con (por ejemplo) tres bytes de datos que podría mover donde quisiera. Luego movería esos para ser los primeros elementos explícitamente definidos en la estructura. Desafortunadamente, eso también significa que si apagas este interruptor para tener un puntero vtable, terminarás con el compilador insertando relleno que de otro modo podría ser innecesario.

En resumen: no está implementado, y si fuera así no lograría mucho.

Answer 4

No, no hay tal interruptor.

El código base LLVM/Clang evita tablas virtuales en las clases que se asignan por las decenas de miles: este trabajo bien en un cerrado jerarquía, porque un solo enum puede enumerar todas las clases posibles y luego cada clase está ligada a una valor de enum. El cerrado es obviamente debido a enum.

Luego, la virtualidad es implementada por un switch en el enum, y el casting apropiado antes de llamar al método. Una vez más, cerró. El switch tiene que ser modificado para cada clase nueva.

---

Una primera alternativa: vpointer externo.

Si se encuentra en una situación en la que el impuesto vpointer se paga con demasiada frecuencia, la mayoría de los objetos son del tipo conocido. Entonces puedes externalizarlo.

class Interface { 
public: 
    virtual ~Interface() {} 

    virtual Interface* clone() const = 0; // might be worth it 

    virtual void updateCount(int) = 0; 

protected: 
    Interface(Interface const&) {} 
    Interface& operator=(Interface const&) { return *this; } 
}; 

template <typename T> 
class InterfaceBridge: public Interface { 
public: 
    InterfaceBridge(T& t): t(t) {} 

    virtual InterfaceBridge* clone() const { return new InterfaceBridge(*this); } 

    virtual void updateCount(int i) { t.updateCount(i); } 

private: 
    T& t; // value or reference ? Choose... 
}; 

template <typename T> 
InterfaceBridge<T> interface(T& t) { return InterfaceBridge<T>(t); } 

Entonces, imaginando una clase simple:

class Counter { 
public: 
    int getCount() const { return c; } 
    void updateCount(int i) { c = i; } 
private: 
    int c; 
}; 

Puede almacenar los objetos en una matriz:

static Counter array[5]; 

assert(sizeof(array) == sizeof(int)*5); // no v-pointer 

Y todavía los utilizan con funciones polimórficas:

void five(Interface& i) { i.updateCount(5); } 

InterfaceBridge<Counter> ib(array[3]); // create *one* v-pointer 
five(ib); 

assert(array[3].getCount() == 5); 

El valor frente a referencia la verdad es una tensión de diseño. En general, si necesita clone, necesita almacenar por valor, y debe clonar cuando almacena por clase base (boost::ptr_vector, por ejemplo). Es posible proporcionar realidad tanto interfaces (y puentes):

Interface <--- ClonableInterface 
    |     | 
InterfaceB  ClonableInterfaceB 

Es simplemente escribiendo adicional.

---

Otra solución, mucho más complicada.

Un interruptor se puede implementar mediante una tabla de salto. Dicha tabla perfectamente se podría crear en tiempo de ejecución, en un std::vector por ejemplo:

class Base { 
public: 
    ~Base() { VTables()[vpointer].dispose(*this); } 

    void updateCount(int i) { 
    VTables()[vpointer].updateCount(*this, i); 
    } 

protected: 
    struct VTable { 
    typedef void (*Dispose)(Base&); 
    typedef void (*UpdateCount)(Base&, int); 

    Dispose dispose; 
    UpdateCount updateCount; 
    }; 

    static void NoDispose(Base&) {} 

    static unsigned RegisterTable(VTable t) { 
    std::vector<VTable>& v = VTables(); 
    v.push_back(t); 
    return v.size() - 1; 
    } 

    explicit Base(unsigned id): vpointer(id) { 
    assert(id < VTables.size()); 
    } 

private: 
    // Implement in .cpp or pay the cost of weak symbols. 
    static std::vector<VTable> VTables() { static std::vector<VTable> VT; return VT; } 

    unsigned vpointer; 
}; 

Y entonces, una clase Derived:

class Derived: public Base { 
public: 
    Derived(): Base(GetID()) {} 

private: 
    static void UpdateCount(Base& b, int i) { 
    static_cast<Derived&>(b).count = i; 
    } 

    static unsigned GetID() { 
    static unsigned ID = RegisterTable(VTable({&NoDispose, &UpdateCount})); 
    return ID; 
    } 

    unsigned count; 
}; 

Pues bien, ahora se dará cuenta de lo grande que es que la el compilador lo hace por usted, incluso a costa de algunos gastos generales.

Ah, y debido a la alineación, tan pronto como una clase Derived introduce un puntero, existe el riesgo de que se utilicen 4 bytes de relleno entre Base y el siguiente atributo. Puede usarlos seleccionando cuidadosamente los primeros atributos en Derived para evitar el relleno ...