c++ - resueltos - ¿Por qué no es bueno usar herencia recursiva para implementaciones std:: tuple?

tipos de herencia en java

Question

En this pregunta, dijo Howard Hinnant

Algunas implementaciones de std :: tuple usan herencia recursiva. Pero los buenos no. ;-)

Por favor alguien puede arrojar algo de luz sobre eso?

Answer 1

No recuerdo exactamente la charla de GoingNative 2012 de Andrei Alexandrescu, pero él habló sobre este punto, y uno de los puntos que mencionó fue el diseño de la memoria. Si tengo un std::tuple<int, short, char, char> , estará en la memoria como char, short, int y este diseño tomará (en mi sistema) 4 bytes más que si se tendieran como int, short, char . R. Martinho Fernandes me ha recordado que lo mejor que se puede hacer es ordenarlos en la memoria en un orden que minimice el relleno, que no es el orden ni el orden inverso. (La herencia ingenua hace el orden inverso).

Si escribo std::tuple<int, char, short, char> , una tupla que funciona por herencia ingenua pondría estos en el orden char, short, int en la memoria, usando 3 bytes de relleno, cuando óptimo tiene cero bytes de relleno. (Ya sea int, short, char, char o char, char, short, int ).

Asumiendo que tengo razón de que se trata de relleno, entonces R. Martinho Fernandes said "[mi argumento] no excluye el uso de la herencia recursiva para la implementación real en el orden óptimo", así que es por eso que especifico esa herencia ingenua es malo.

(El orden en la memoria no significa que get<0> dará un objeto diferente, y R. Martinho Fernandes señala correctamente que el orden debe ser invisible para el usuario. Sin embargo, estos fueron los puntos que me ha recordado el GoingNative evento.)

El video está en http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Variadic-Templates-are-Funadic y las diapositivas están en http://ecn.channel9.msdn.com/events/GoingNative12/GN12VariadicTemplatesAreFunadic.pdf .

Answer 2

Una razón para no usar una cadena de clases base es que no hay una cadena de constructores involucrados: los argumentos se envían directamente al subobjeto apropiado. Además, parece que una implementación no recursiva ejerce mucha menos presión sobre el compilador y crea muchos menos símbolos [internos]. Sin mencionar que, en realidad, es más fácil no formar una cadena de clases base.

Answer 3

Una implementación no recursiva tiene un mejor rendimiento en tiempo de compilación. Créalo o no, en una instalación de biblioteca muy utilizada como std::tuple , cómo se implementa puede tener un impacto (para bien o para mal), los tiempos de compilación que ve el cliente. Las implementaciones recursivas tienden a producir tiempos de compilación que son lineales en la profundidad de la recursión (o pueden ser incluso peores).

Esto impacta más que solo la ejemplificación de la tupla misma. std::get<I>(tuple) por ejemplo, tomará una cantidad lineal de tiempo de compilación para una implementación y una cantidad constante de tiempo de compilación para otra implementación. Este impacto puede deteriorarse rápidamente (o no) al tratar con tuplas de tuplas. Es decir, la implementación recursiva podría dar como resultado O (N ^ 2) tiempo de compilación mientras que la implementación no recursiva sigue siendo O (1).

Fwiw, la implementación de libc ++ establece los objetos en el orden especificado por el cliente, pero optimiza el espacio libre para los componentes vacíos utilizando el recurso de optimización de la clase base vacía del compilador.