c++ - ¿Implementaciones alternativas de mecanismos virtuales?

dynamic vtable

Question

C ++ admite enlace dinámico a través de un mecanismo virtual. Pero como entiendo, el mecanismo virtual es un detalle de implementación del compilador y el estándar solo especifica los comportamientos de lo que debería suceder en escenarios específicos. La mayoría de los compiladores implementan el mecanismo virtual a través de la tabla virtual y el puntero virtual. Y sí, soy consciente de cómo funciona esto, así que mi pregunta no es acerca de los detalles de implementación de los punteros virtuales y la tabla. Mis preguntas son:

1. ¿Hay algún compilador que implemente el Mecanismo Virtual de otra manera que no sea el puntero virtual y el mecanismo de la tabla virtual? Por lo que he visto más (leer g ++, Microsoft visual studio) implementarlo a través de la tabla virtual, mecanismo de puntero. ¿Prácticamente hay alguna otra implementación de compilador?
2. El sizeof de cualquier clase con solo una función virtual será el tamaño de un puntero (vptr dentro de this ) en ese compilador . Entonces, dado que el mecanismo virtual ptr y tbl en sí mismo es la implementación del compilador, ¿será siempre verdadera esta afirmación que hice anteriormente?

Answer 1

¿Hay algún compilador que implemente el Mecanismo Virtual de otra manera que no sea el puntero virtual y el mecanismo de la tabla virtual? Por lo que he visto más (leer g ++, Microsoft visual studio) implementarlo a través de la tabla virtual, mecanismo de puntero. ¿Prácticamente hay alguna otra implementación de compilador?

Todos los compiladores actuales que conozco utilizan el mecanismo vtable.

Esta es una optimización que es posible porque C ++ está comprobado estáticamente.

En algunos lenguajes más dinámicos hay, en cambio, una búsqueda dinámica de la (s) cadena (s) de clase base, buscando una implementación de una función miembro que se llame virtualmente, comenzando en la clase más derivada del objeto. Por ejemplo, así es como funcionaba en Smalltalk original. Y el estándar de C ++ describe el efecto de una llamada virtual como si se hubiera usado dicha búsqueda.

En Borland / Turbo Pascal, en la década de 1990, se empleó esta búsqueda dinámica para encontrar manejadores de los "mensajes de ventana" de la API de Windows. Y creo que posiblemente lo mismo en Borland C ++. Era además del mecanismo vtable normal, utilizado únicamente para manejadores de mensajes.

Si se usó en Borland / Turbo C ++, no recuerdo, entonces era compatible con extensiones de idioma que permitían asociar identificadores de mensaje con funciones de manejo de mensajes.

El tamaño de cualquier clase con solo una función virtual será el tamaño de un puntero (vptr dentro del mismo) en ese compilador. Entonces, dado que el mecanismo ptr y tbl virtual es la implementación del compilador, ¿será siempre verdadera esta afirmación que hice anteriormente?

Formalmente no (incluso con la suposición de mecanismo vtable), depende del compilador. Como el estándar no requiere el mecanismo vtable, no dice nada sobre la ubicación del puntero vtable en cada objeto. Y otras reglas permiten que el compilador agregue libremente relleno, bytes no utilizados, al final.

Pero en la práctica tal vez. ;-)

Sin embargo, no es algo en lo que debe confiar o en lo que debe confiar. Pero en la otra dirección puede requerir esto, por ejemplo, si está definiendo un ABI. Entonces, cualquier compilador que no lo haga simplemente no cumple con sus requisitos.

Saludos y hth.,

Answer 2

¿Hay algún compilador que implemente el Mecanismo Virtual de otra manera que no sea el puntero virtual y el mecanismo de la tabla virtual? Por lo que he visto más (leer g ++, Microsoft visual studio) implementarlo a través de la tabla virtual, mecanismo de puntero. ¿Prácticamente hay alguna otra implementación de compilador?

Ninguno de los que conozco de los compiladores de C ++, aunque le puede resultar interesante leer sobre el envío de árboles binarios. Si está interesado en explotar la expectativa de tablas de despacho virtuales de alguna manera, debe tener en cuenta que los compiladores pueden, cuando los tipos son conocidos en tiempo de compilación, a veces resolver llamadas a funciones virtuales en tiempo de compilación, por lo que no pueden consultar la tabla.

El tamaño de cualquier clase con solo una función virtual será el tamaño de un puntero (vptr dentro del mismo) en ese compilador. Entonces, dado que el mecanismo ptr y tbl virtual es la implementación del compilador, ¿será siempre verdadera esta afirmación que hice anteriormente?

Suponiendo que no hay clases base con sus propios miembros virtuales, y sin clases base virtuales, es abrumadoramente probable que sea cierto. Se pueden prever alternativas, como el análisis de un programa completo que revela solo un miembro en la jerarquía de clases, y un cambio al despacho en tiempo de compilación. Si se requiere el envío en tiempo de ejecución, es difícil imaginar por qué cualquier compilador introduciría una indirección adicional. Aún así, el Estándar deliberadamente no estipula estas cosas precisamente para que las implementaciones puedan variar o variar en el futuro.

Answer 3

1. No creo que haya compiladores modernos con un enfoque que no sea vptr / vtable. De hecho, sería difícil descubrir algo más que no sea simplemente ineficiente.

   Sin embargo, todavía hay un espacio bastante grande para las concesiones de diseño dentro de ese enfoque. Tal vez especialmente con respecto a cómo se maneja la herencia virtual. Entonces tiene sentido hacer esta implementación definida.

   Si está interesado en este tipo de cosas, le sugiero leer Inside the C ++ Object Model .

2. sizeof class depende del compilador. Si desea un código portátil, no haga suposiciones.

Answer 4

1. Nunca he escuchado o visto ningún compilador que use una implementación alternativa. La razón por la cual los vtables son tan populares es porque no solo es la implementación más eficiente, sino que también es el diseño más fácil y la implementación más obvia.

2. En casi cualquier compilador que quieras usar, es casi seguro que sea cierto. Sin embargo, no está garantizado y no siempre es cierto; no se puede depender de él, aunque es casi siempre el caso. Su compilador favorito también podría alterar su alineación, aumentar su tamaño, para divertirse, sin decírselo. Desde la memoria, también puede insertar la información de depuración y lo que quiera.

Answer 5

Al tratar de imaginar un esquema alternativo, he encontrado lo siguiente, siguiendo la línea de la respuesta de Ytril . Que yo sepa, ¡ningún compilador lo usa!

Dado un espacio de direcciones virtuales suficientemente grande y rutinas flexibles de asignación de memoria de SO, sería posible que los new asignen objetos de diferentes tipos en rangos de direcciones fijos que no se superpongan. Entonces, el tipo de un objeto se puede deducir rápidamente de su dirección utilizando una operación de desplazamiento a la derecha , y el resultado se usa para indexar una tabla de tablas virtuales, ahorrando así 1 puntero vtable por objeto.

A primera vista, este esquema podría parecer tener problemas con los objetos asignados por la pila, pero esto se puede manejar limpiamente:

1. Para cada objeto asignado a la pila, el compilador agrega un código que agrega un registro a una matriz global de pares (address range, type) cuando se crea el objeto y elimina el registro cuando se destruye.
2. El rango de direcciones que comprende la pila se correlacionaría con un único vtable que contenga un gran número de thunks que lean this puntero, escanearán la matriz para encontrar el tipo correspondiente (vptr) para el objeto en esa dirección y llamarán al método correspondiente en el vtable apuntado a. (Es decir, el 42 thunk llamará al método 42 en el vtable; si la mayoría de las funciones virtuales utilizadas en cualquier clase es n , se requieren al menos n thunk).

Obviamente, este esquema incurre en una sobrecarga no trivial (al menos O (log n) para la búsqueda) para llamadas a métodos virtuales en objetos basados ​​en la pila. En ausencia de matrices o composición (contención dentro de otro objeto) de objetos basados ​​en pila, se puede usar un enfoque más simple y más rápido en el cual el vptr se coloca en la pila inmediatamente antes del objeto (tenga en cuenta que no se considera parte del objeto y no contribuye a su tamaño medido por sizeof ). En este caso, los thunk simplemente restan sizeof (vptr) de this para encontrar el vptr correcto a usar, y reenviarlo como antes.

Answer 6

En primer lugar, se mencionó la extensión patentada de Borland a C ++, tablas virtuales de envío dinámico (DDVT), y puede leer algo al respecto en un archivo llamado DDISPATC.ZIP . Borland Pascal tenía métodos virtual y dynamic , y Delphi introdujo otra sintaxis de "mensaje" , similar a la dinámica, pero para los mensajes. En este punto, no estoy seguro de si Borland C ++ tenía las mismas características. No hubo herencia múltiple en Pascal o Delphi, por lo que Borland C ++ DDVT podría ser diferente de Pascal o Delphi.

En segundo lugar, en la década de 1990 y un poco antes había experimentos con diferentes modelos de objetos, y Borland no era el más avanzado. Personalmente, creo que cerrar IBM SOMobjects hizo un daño al mundo del que todos todavía sufrimos. Antes de apagar SOM, hubo experimentos con compiladores Direct-to-SOM de C ++. Entonces, en lugar de la forma en que C ++ invoca los métodos, se usa SOM. Es en muchos aspectos similar a C ++ vtable, con varias excepciones. En primer lugar, para evitar el problema de la clase base frágil, los programas no usan desplazamientos dentro de vtable, porque no conocen este desplazamiento. Puede cambiar si la clase base introduce nuevos métodos. En cambio, los llamadores invocan un thunk creado en tiempo de ejecución que tiene este conocimiento en su código de ensamblado. Y hay una diferencia más. En C ++, cuando se usa herencia múltiple, un objeto puede contener varios VMTs IIRC. A diferencia de C ++, cada objeto SOM tiene solo un VMT, por lo que el código de envío debe ser diferente de "call dword ptr [VMT + offset]".

Hay un documento relacionado con SOM, Release-to-Release Binary Compatibility en SOM . Puede encontrar una comparación de SOM con otros proyectos de los que conozco poco, como Delta/C++ y Sun OBI . Resuelven un subconjunto de problemas que SOM resuelve, y al hacerlo también tienen un código de invocación algo ajustado.

Recientemente, encontré el fragmento del compilador de Visual Age C ++ v3.5 para Windows lo suficiente como para que las cosas funcionen y realmente lo toquen. La mayoría de los usuarios no es probable que obtengan VM OS / 2 solo para jugar con DTS C ++, pero tener el compilador de Windows es completamente otra cuestión. VAC v3.5 es la primera y la última versión compatible con la función Direct-to-SOM C ++. VAC v3.6.5 y v4.0 no son apropiados.

1. Descargue VAC 3.5 fixpak 9 de IBM FTP. Este fixpak contiene muchos archivos, por lo que ni siquiera necesita un compilador completo (tengo 3.5.7 distro, pero el fixpak 9 fue lo suficientemente grande como para hacer algunas pruebas).
2. Descomprimir para, por ejemplo, C: / home / OCTAGRAM / DTS
3. Comience la línea de comando y ejecute los comandos subsiguientes allí
4. Ejecutar: configure SOMBASE = C: / home / OCTAGRAM / DTS / ibmcppw
5. Ejecutar: C: / home / OCTAGRAM / DTS / ibmcppw / bin / SOMENV.BAT
6. Ejecutar: cd C: / home / OCTAGRAM / DTS / ibmcppw / samples / compiler / dts
7. Ejecutar: nmake clean
8. Ejecutar: nmake
9. hhmain.exe y su dll están en directorios diferentes, por lo que debemos hacer que se encuentren de alguna manera; ya que estaba haciendo varios experimentos, ejecuté "set PATH =% PATH%; C: / home / OCTAGRAM / DTS / ibmcppw / samples / compiler / dts / xhmain / dtsdll" una vez, pero puedes copiar dll cerca de hhmain. exe
10. Ejecutar: hhmain.exe

Tengo una salida de esta manera:

Local anInfo->x = 5
Local anInfo->_get_x() = 5
Local anInfo->y = A
Local anInfo->_get_y() = B
{An instance of class info at address 0092E318

}

Answer 7

IIRC Eiffel utiliza un enfoque diferente y todas las anulaciones de un método terminan fusionadas y compiladas en la misma dirección con un prólogo donde se verifica el tipo de objeto (por lo que cada objeto debe tener un ID de tipo, pero no un puntero a un VMT). Esto para C ++ requeriría, por supuesto, que la función final se cree en el momento del enlace. Sin embargo, no conozco ningún compilador de C ++ que use este enfoque.

Answer 8

No es cierto que los punteros vtable en los objetos sean siempre los más eficientes. Mi compilador de otro idioma solía usar punteros en el objeto por razones similares, pero ya no funciona: en su lugar utiliza una estructura de datos separada que asigna la dirección del objeto a los metadatos necesarios: en mi sistema, esta es información de forma para usar por el recolector de basura.

Esta implementación cuesta un poco más de almacenamiento para un único objeto simple, es más eficiente para objetos complejos con muchas bases, y es mucho más eficiente para matrices, ya que solo se requiere una entrada en la tabla de asignación para todos los objetos en la matriz. Mi implementación particular también puede encontrar metadatos dado un puntero a cualquier punto interior del objeto.

La búsqueda real es extremadamente rápida y los requisitos de almacenamiento son muy modestos, porque estoy usando la mejor estructura de datos del planeta: matrices Judy.

También conozco ningún compilador de C ++ que use otra cosa que no sean punteros vtable, pero no es la única. De hecho, la semántica de inicialización para las clases con bases hace que la implementación sea complicada. Esto se debe a que el tipo completo tiene que ver alrededor del objeto a medida que se construye. Como consecuencia de esta semántica, los objetos mixin complejos conducen a la generación de grandes conjuntos de tablas, objetos grandes y la inicialización lenta de objetos. Esto probablemente no es una consecuencia de la técnica vtable tanto como la necesidad de seguir servilmente el requisito de que el tipo de subobjeto en tiempo de ejecución sea correcto en todo momento. En realidad, no hay una buena razón para esto durante la construcción, ya que los constructores no son métodos y no pueden usar el despacho virtual con sensatez: esto no es tan claro para mí ya que los destructores son métodos reales.

Answer 9

Que yo sepa, todas las implementaciones de C ++ usan un puntero vtable, aunque sería bastante fácil (y tal vez no tan malo en cuanto a las cachés) mantener un pequeño índice de tipo en el objeto (1-2 B) y posteriormente obtenga la información vtable y escriba con una pequeña tabla de búsqueda.

Otro enfoque interesante podría ser BIBOP (http://foldoc.org/BIBOP) - gran cantidad de páginas - aunque tendría problemas para C ++. Idea: poner objetos del mismo tipo en una página. Obtenga un puntero al descriptor de tipo / vtable en la parte superior de la página simplemente seleccionando los bits menos significativos del puntero del objeto. (¡No funciona bien para objetos en la pila, por supuesto!)

Otro enfoque es codificar ciertas etiquetas / índices de tipo en los punteros del objeto. Por ejemplo, si por construcción todos los objetos están alineados en 16 bytes, puede usar los 4 LSB para colocar una etiqueta de tipo de 4 bits allí. (No es suficiente). O (especialmente para sistemas integrados) si ha garantizado bits más significativos no utilizados en las direcciones, puede poner más bits de etiquetas allí y recuperarlos con un cambio y una máscara.

Si bien ambos esquemas son interesantes (y algunas veces se usan) para otras implementaciones de lenguaje, son problemáticos para C ++. Ciertas semánticas de C ++, como las anulaciones de funciones virtuales de la clase base durante la construcción y destrucción de objetos (clase base), lo llevan a un modelo donde hay algún estado en el objeto que modifica al ingresar ctors / dtors de la clase base.

Puede encontrar interesante mi antiguo tutorial sobre la implementación del modelo de objetos de Microsoft C ++. http://www.openrce.org/articles/files/jangrayhood.pdf

¡Feliz hacking!

Answer 10

C++/CLI desvía de ambas suposiciones. Si define una clase de referencia, no se compila en absoluto en el código de máquina; en cambio, el compilador lo compila en el código administrado .NET. En el lenguaje intermedio, las clases son una característica incorporada, y el conjunto de métodos virtuales se define en los metadatos, en lugar de en una tabla de métodos.

La estrategia específica para implementar el diseño y el despacho del objeto depende de la máquina virtual. En Mono, un objeto que contiene solo un método virtual no tiene el tamaño de un puntero, pero necesita dos punteros en la estructura MonoObject ; el segundo para la sincronización del objeto. Como esto está definido por la implementación y tampoco es realmente útil saberlo, sizeof no es compatible con las clases de ref en C ++ / CLI.

Answer 11

La respuesta de Tony D'' señala correctamente que a los compiladores se les permite utilizar el análisis de programa completo para reemplazar una llamada de función virtual con una llamada estática a la implementación de función posible única; o para compilar obj->method() en el equivalente de

if (auto frobj = dynamic_cast<FrequentlyOccurringType>(obj)) {
    frobj->FrequentlyOccurringType::method();  // static dispatch on hot path
} else {
    obj->method();  // vtable dispatch on cold path
}

Karel Driesen y Urs Hölzle escribieron un papel realmente fascinante allá por 1996 en el que simularon el efecto de la optimización perfecta de todo el programa en aplicaciones típicas de C ++: "El costo directo de llamadas a funciones virtuales en C ++" . (El PDF está disponible de forma gratuita si busca en Google). Lamentablemente, solo compararon el despacho de vtable con el despacho estático perfecto; no lo compararon con el despacho de árbol binario.

Señalaron que en realidad hay dos tipos de tablas, cuando hablamos de idiomas (como C ++) que admiten herencia múltiple. Con la herencia múltiple, cuando llamas a un método virtual que se hereda de la segunda clase base, necesitas "reparar" el puntero del objeto para que apunte a una instancia de la segunda clase base. Este desplazamiento de corrección se puede almacenar como datos en el vtable, o se puede almacenar como código en un "thunk". (Vea el documento para más detalles).

Creo que todos los compiladores decentes en la actualidad utilizan los thunks, pero tardó 10 o 20 años para que esa penetración en el mercado alcanzara el 100%.