c++ - make_shared - shared_ptr example

Viabilidad del interruptor de ciclo automático para `std:: shared_ptr` (5)

Creo que la respuesta a su pregunta es que, contrariamente a lo que afirma, no existe una forma eficiente de manejar automáticamente las referencias cíclicas. La comprobación de ciclos debe llevarse a cabo cada vez que se destruye un "shared_ptr". Por otro lado, la introducción de cualquier mecanismo de aplazamiento inevitablemente dará como resultado un comportamiento indeterminado.

C ++ 11 introdujo punteros inteligentes contados por referencia, std::shared_ptr . Al ser contadas las referencias, estos punteros no pueden recuperar automáticamente las estructuras de datos cíclicos. Sin embargo, se demostró que era posible la recolección automática de ciclos de referencia, por ejemplo, mediante Python y PHP . Para distinguir esta técnica de la recolección de basura, el resto de la pregunta se referirá a ella como ciclo de ruptura .

Dado que parece que no hay propuestas para agregar funcionalidad equivalente a C ++, ¿hay alguna razón fundamental por la que un interruptor de ciclo similar a los que ya se implementaron en otros idiomas no funcione para std::shared_ptr ?

Tenga en cuenta que esta pregunta no se reduce a "por qué no hay un GC para C ++", que se ha pedido antes . Un C ++ GC normalmente se refiere a un sistema que administra automáticamente todos los objetos asignados dinámicamente, implementados típicamente utilizando alguna forma del recopilador conservador de Boehm. Se ha señalado que tal colector no es una buena opción para RAII. Como un recolector de basura maneja principalmente la memoria, y puede que ni siquiera se llame hasta que haya una falta de memoria, y los destructores de C ++ administran otros recursos, confiar en que el GC ejecutará los destructores introduciría no determinismo en el mejor de los casos y la falta de recursos en el peor. También se ha señalado que un GC completo es en gran medida innecesario en presencia de los punteros inteligentes más explícitos y predecibles.

Sin embargo, un interruptor de ciclo basado en la biblioteca para punteros inteligentes (análogo al utilizado por los intérpretes contados por referencia) tendría diferencias importantes con respecto a un GC de propósito general:

Solo se preocupa por los objetos administrados a través de shared_ptr . Dichos objetos ya participan en la propiedad compartida, y por lo tanto tienen que manejar la invocación del destructor diferido, cuyo tiempo exacto depende de la estructura de propiedad.
Debido a su alcance limitado, a un interruptor de ciclo no le preocupan los patrones que rompen o ralentizan el Boehm GC, como el enmascaramiento del puntero o los enormes bloques de montón opacos que contienen un puntero ocasional.
Puede ser opt-in, como std::enable_shared_from_this . Los objetos que no lo usan no tienen que pagar por el espacio adicional en el bloque de control para contener los metadatos del interruptor cíclico.
Un interruptor de ciclo no requiere una lista completa de objetos "raíz", que es difícil de obtener en C ++. A diferencia de un GC con marca de barrido que encuentra todos los objetos en vivo y descarta el resto, un interruptor de ciclo solo atraviesa objetos que pueden formar ciclos. En las implementaciones existentes, el tipo necesita proporcionar ayuda en forma de una función que enumera las referencias (directas o indirectas) a otros objetos que pueden participar en un ciclo.
Se basa en la semántica regular "destruir cuando el recuento de referencias cae a cero" para destruir la basura cíclica. Una vez que se identifica un ciclo, se solicita a los objetos que participan en él que borren sus referencias fuertemente retenidas, por ejemplo llamando al reset() . Esto es suficiente para romper el ciclo y destruiría automáticamente los objetos. Pedir a los objetos que proporcionen y eliminen sus referencias sólidas (a petición) garantiza que el interruptor automático no rompa la encapsulación.

La falta de propuestas para la interrupción automática del ciclo indica que la idea fue rechazada por razones prácticas o filosóficas. Tengo curiosidad por cuáles son las razones. Para completar, aquí hay algunas objeciones posibles:

"Introducirá la destrucción no determinística de objetos cíclicos shared_ptr ". Si el programador tuviera el control de la invocación del interruptor de ciclo, no sería no determinista. Además, una vez invocado, el comportamiento del interruptor de ciclismo sería predecible: destruiría todos los ciclos actualmente conocidos. Esto es similar a cómo el destructor de shared_ptr destruye el objeto subyacente una vez que su recuento de referencia cae a cero, a pesar de la posibilidad de que esto provoque una cascada "no determinista" de otras destrucciones.
"Un interruptor de ciclo, al igual que cualquier otra forma de recolección de basura, introduciría pausas en la ejecución del programa". La experiencia con los tiempos de ejecución que implementan esta función muestra que las pausas son mínimas porque el GC solo maneja la basura cíclica, y todos los demás objetos se recuperan mediante el recuento de referencias. Si el detector de ciclo nunca se invoca automáticamente, la "pausa" del interruptor de ciclo podría ser una consecuencia predecible de su funcionamiento, similar a la forma en que la destrucción de un std::vector grande puede ejecutar una gran cantidad de destructores. (En Python, el gc cíclico se ejecuta automáticamente, pero hay una API para desactivarlo temporalmente en las secciones de código donde no es necesario. Volver a habilitar el GC más tarde recogerá la basura cíclica creada mientras tanto).
"Un interruptor de ciclo es innecesario porque los ciclos no son tan frecuentes y se pueden evitar fácilmente usando std::weak_ptr ". De hecho, los ciclos aparecen fácilmente en muchas estructuras de datos simples, por ejemplo, un árbol donde los niños tienen un puntero hacia atrás para el padre o una lista doblemente vinculada. En algunos casos, los ciclos entre objetos heterogéneos en sistemas complejos se forman ocasionalmente con ciertos patrones de datos y son difíciles de predecir y evitar. En algunos casos, está lejos de ser obvio qué puntero reemplazar con la variante débil.

Hay una serie de problemas que se debatirán aquí, por lo que reescribí mi publicación para condensar mejor esta información.

Detección automática de ciclo

Tu idea es tener un puntero inteligente circle_ptr (sé que quieres agregarlo a shared_ptr , pero es más fácil hablar sobre un nuevo tipo para comparar los dos). La idea es que, si el tipo que el puntero inteligente está obligado a derivar de algún cycle_detector_mixin , esto activa la detección automática de ciclo.

Esta mezcla también requiere que el tipo implemente una interfaz. Debe proporcionar la capacidad de enumerar todas las instancias circle_ptr que pertenecen directamente a esa instancia. Y debe proporcionar los medios para invalidar uno de ellos.

Presento que esta es una solución muy poco práctica para este problema. Es excesivamente frágil y requiere inmensas cantidades de trabajo manual por parte del usuario. Y, por lo tanto, no es apropiado incluirlo en la biblioteca estándar. Y aquí hay algunas razones por qué.

Determinismo y costo

"Introducirá la destrucción no determinística de objetos cíclicos shared_ptr ". La detección de ciclo solo ocurre cuando el shared_ptr de referencia de un shared_ptr cae a cero, por lo que el programador tiene el control de cuándo sucede. Por lo tanto, no sería no determinista. Su comportamiento sería predecible: destruiría todos los ciclos actualmente conocidos de ese puntero. Esto es similar a cómo el destructor de shared_ptr destruye el objeto subyacente una vez que su recuento de referencia cae a cero, a pesar de la posibilidad de que esto provoque una cascada "no determinista" de otras destrucciones.

Esto es cierto, pero no de manera útil.

Existe una diferencia sustancial entre el determinismo de la destrucción regular de shared_ptr y el determinismo de lo que sugiere. A saber: shared_ptr es barato.

El destructor de shared_ptr hace una disminución atómica, seguida por una prueba condicional para ver si el valor se redujo a cero. Si es así, se llama a un destructor y se libera la memoria. Eso es.

Lo que sugieres hace esto más complicado. En el peor de los casos, cada vez que se destruye un circle_ptr , el código tendrá que recorrer las estructuras de datos para determinar si hay un ciclo. La mayoría de las veces, los ciclos no existirán. Pero aún tiene que buscarlos, solo para estar seguros. Y debe hacerlo cada vez que destruyas un circle_ptr .

Python et. Alabama. evitar este problema porque están integrados en el lenguaje. Ellos pueden ver todo lo que está pasando. Y, por lo tanto, pueden detectar cuándo se asigna un puntero en el momento en que se realizan esas asignaciones. De esta manera, tales sistemas constantemente están haciendo pequeñas cantidades de trabajo para construir cadenas cíclicas. Una vez que una referencia desaparece, puede observar sus estructuras de datos y tomar medidas si eso crea una cadena cíclica.

Pero lo que sugiere es una función de biblioteca , no una función de idioma. Y los tipos de bibliotecas realmente no pueden hacer eso. O más bien, pueden, pero solo con ayuda.

Recuerde: una instancia de circle_ptr no puede conocer el subobjeto del que es miembro. No puede transformar automáticamente un puntero a sí mismo en un puntero a su clase propietaria. Y sin esa capacidad, no puede actualizar las estructuras de datos en cycle_detector_mixin que posee si se reasigna.

Ahora, podría hacerlo manualmente , pero solo con la ayuda de su instancia propietaria. Lo que significa que circle_ptr necesitaría un conjunto de constructores a los que se les da un puntero a su instancia propietaria, que se deriva de cycle_detector_mixin . Y luego, su operator= podría informar a su propietario que se ha actualizado. Obviamente, la asignación copiar / mover no copiaría / movería el puntero de instancia propietaria.

Por supuesto, esto requiere que la instancia propietaria se circle_ptr un puntero a cada circle_ptr que crea. En cada constructor y función que crea instancias circle_ptr . Dentro de sí mismo y de las clases que posee, que tampoco son administradas por cycle_detection_mixin . Sin fallar. Esto crea un grado de fragilidad en el sistema; esfuerzo manual debe circle_ptr para cada instancia circle_ptr propiedad de un tipo.

Esto también requiere que circle_ptr contenga 3 tipos de punteros: un puntero al objeto que obtienes del operator* , un puntero al almacenamiento administrado real y un puntero al propietario de esa instancia. La razón por la que la instancia debe contener un puntero a su propietario es que se trata de datos por instancia, no información asociada con el bloque en sí. Es la instancia de circle_ptr que necesita poder decirle a su propietario cuando se recupera, por lo que la instancia necesita esa información.

Y esto debe ser una carga estática . No puede saber cuándo una instancia de circle_ptr está dentro de otro tipo y cuándo no. Por lo tanto, cada circle_ptr , incluso aquellos que no usan las características de detección de ciclo, deben soportar este costo de 3 punteros.

Por lo tanto, no solo requiere un alto grado de fragilidad, sino que también es costoso e hincha el tamaño del tipo en un 50%. Reemplazar shared_ptr con este tipo (o más al punto, aumentar shared_ptr con esta funcionalidad) simplemente no es viable.

En el lado positivo, ya no necesita usuarios que derivan de cycle_detector_mixin para implementar una forma de recuperar la lista de instancias circle_ptr . En cambio, tiene la clase registrarse en las instancias circle_ptr . Esto permite que las instancias circle_ptr que pueden ser cíclicas puedan hablar directamente con su propiedad cycle_detector_mixin .

Entonces hay algo.

Encapsulación e invariantes

La necesidad de poder decirle a una clase que invalide uno de sus objetos circle_ptr cambia fundamentalmente la forma en que la clase puede interactuar con cualquiera de sus miembros circle_ptr .

Un invariante es un estado que una parte del código supone que es verdadero porque debe ser lógicamente imposible que sea falso. Si comprueba que una variable const int es> 0, entonces ha establecido un invariante para código posterior que este valor es positivo.

La encapsulación existe para permitirle construir invariantes dentro de una clase. Los constructores solos no pueden hacerlo, porque el código externo puede modificar cualquier valor que almacene la clase. La encapsulación le permite evitar que el código externo haga tales modificaciones. Y por lo tanto, puede desarrollar invariantes para diversos datos almacenados por la clase.

Esto es para lo que es la encapsulación.

Con un shared_ptr , es posible construir un invariante alrededor de la existencia de dicho puntero. Puede diseñar su clase para que el puntero nunca sea nulo. Y, por lo tanto, nadie tiene que comprobar si es nulo.

Ese no es el caso con circle_ptr . Si implementa cycle_detector_mixin , su código debe ser capaz de manejar el caso de que cualquiera de esas instancias circle_ptr vuelva nula. Por lo tanto, su destructor no puede asumir que son válidos, ni ningún código que sus llamadas al destructor asuman.

Por lo tanto, su clase no puede establecer un invariante con el objeto al que apunta circle_ptr . Al menos, no si es parte de un cycle_detector_mixin con su registro asociado y otras cosas.

Puede argumentar que su diseño no rompe técnicamente la encapsulación, ya que las instancias circle_ptr aún pueden ser privadas. Pero la clase está voluntariamente abandonando la encapsulación al sistema de detección de ciclos. Y, por lo tanto, la clase ya no puede garantizar ciertos tipos de invariantes.

Eso suena como romper la encapsulación para mí.

Hilo de seguridad

Para acceder a un weak_ptr , el usuario debe lock . Esto devuelve un shared_ptr , que asegura que el objeto permanecerá vivo (si todavía existía). El bloqueo es una operación atómica, al igual que el incremento / decremento de referencia. Así que todo esto es seguro para subprocesos.

circle_ptr s puede no ser muy seguro para subprocesos. Es posible que un circle_ptr no sea válido desde otro hilo, si el otro hilo lanzó la última referencia no circular al mismo.

No estoy completamente seguro de esto. Es posible que tales circunstancias solo aparezcan si ya ha tenido una carrera de datos sobre la destrucción del objeto o está utilizando una referencia que no es de su propiedad. Pero no estoy seguro de que su diseño sea seguro para hilos.

Factores virulentos

Esta idea es increíblemente viral. Cualquier otro tipo en el que puedan aparecer referencias cíclicas debe implementar esta interfaz. No es algo que puedas poner en un tipo. Para obtener los beneficios, todo tipo que pueda participar en una referencia cíclica debe usarlo. Consistentemente y correctamente.

Si intentas hacer que circle_ptr requiera que el objeto que administra implemente cycle_detector_mixin , entonces haces imposible usar dicho puntero con cualquier otro tipo. No sería un reemplazo de (o aumento de) shared_ptr . Por lo tanto, no hay forma de que un compilador ayude a detectar el uso indebido accidental.

Claro, hay mal uso accidental de make_shared_from_this que los compiladores no pueden detectar. Sin embargo, eso no es una construcción viral. Por lo tanto, es solo un problema para quienes necesitan esta característica. Por el contrario, la única forma de obtener un beneficio de cycle_detector_mixin es usarlo lo más exhaustivamente posible.

Igualmente importante, porque esta idea es tan viral, la usarás mucho. Por lo tanto, es mucho más probable que encuentre el problema de herencia múltiple que los usuarios de make_shared_from_this . Y ese no es un problema menor. Especialmente dado que cycle_detector_mixin probablemente usará static_cast para acceder a la clase derivada, por lo que no podrá usar la herencia virtual.

Suma

Entonces, aquí está lo que debes hacer, sin falta, para detectar ciclos, ninguno de los cuales el compilador verificará:

Cada clase que participa en un ciclo debe derivarse de cycle_detector_mixin .
Cada vez que una clase cycle_detector_mixin construye una instancia de circle_ptr dentro de sí misma (ya sea directa o indirectamente, pero no dentro de una clase que deriva de cycle_detector_mixin ), pasa un puntero a ti mismo a ese cycle_ptr .
No asuma que cualquier subobjeto cycle_ptr de una clase es válido. Posiblemente incluso hasta el punto de convertirse en inválido dentro de una función de miembro gracias a problemas de enhebrado.

Y aquí están los costos:

Ciclo de detección de estructuras de datos dentro de cycle_detector_mixin .
Cada cycle_ptr debe ser un 50% más grande, incluso los que no se utilizan para la detección de ciclos.

Conceptos erróneos sobre la propiedad

En última instancia, creo que toda esta idea se reduce a una idea errónea acerca de para qué shared_ptr es en realidad.

"Un detector de ciclo es innecesario porque los ciclos no son tan frecuentes y se pueden evitar fácilmente usando std::weak_ptr ". De hecho, los ciclos aparecen fácilmente en muchas estructuras de datos simples, por ejemplo, un árbol donde los niños tienen un puntero hacia atrás para el padre o una lista doblemente vinculada. En algunos casos, los ciclos entre objetos heterogéneos en sistemas complejos se forman ocasionalmente con ciertos patrones de datos y son difíciles de predecir y evitar. En algunos casos, está lejos de ser obvio qué puntero reemplazar con la variante débil.

Este es un argumento muy común para GC de propósito general. El problema con este argumento es que generalmente hace una suposición sobre el uso de punteros inteligentes que simplemente no es válida.

Usar un shared_ptr significa algo . Si una clase almacena un shared_ptr , eso representa que la clase tiene propiedad de ese objeto.

Así que explique esto: ¿por qué un nodo en una lista enlazada necesita poseer los nodos siguiente y anterior? ¿Por qué un nodo secundario en un árbol necesita ser propietario de su nodo padre? Oh, necesitan poder hacer referencia a los otros nodos. Pero no necesitan controlar la vida de ellos.

Por ejemplo, implementaría un nodo de árbol como una matriz de unique_ptr para sus hijos, con un solo puntero al padre. Un puntero regular , no un puntero inteligente. Después de todo, si el árbol está construido correctamente, el padre será dueño de sus hijos. Entonces, si existe un nodo hijo, su nodo padre debe existir ; el niño no puede existir sin tener un padre válido.

Con una lista de doble unique_ptr , podría hacer que el puntero izquierdo sea un unique_ptr , con el derecho siendo un puntero regular. O viceversa; una forma no es mejor que la otra.

Su mentalidad parece ser que siempre deberíamos usar shared_ptr para las cosas, y simplemente dejar que el sistema automático resuelva cómo lidiar con los problemas. Ya sean referencias circulares o lo que sea, simplemente deje que el sistema lo resuelva.

Eso no es para lo que shared_ptr es. El objetivo de los indicadores inteligentes no es que ya no pienses en la propiedad; es que puedes expresar las relaciones de propiedad directamente en el código.

En general

¿Cómo es esto algo mejor que usar weak_ptr para romper ciclos? En lugar de reconocer cuándo pueden ocurrir los ciclos y hacer un trabajo extra, ahora hace un montón de trabajo extra en todas partes . Trabajo que es excesivamente fragante; si lo haces mal, no estarás mejor que si te perdieras un lugar donde deberías haber usado weak_ptr . Solo que es peor, porque probablemente pienses que tu código es seguro.

La ilusión de seguridad es peor que no tener seguridad en absoluto. Al menos esto último te hace tener cuidado.

¿Podrías implementar algo como esto? Posiblemente. ¿Es un tipo apropiado para la biblioteca estándar? No. Es demasiado frágil. Debe implementarlo correctamente, en todo momento, en todos los sentidos, en todos los lugares donde aparezcan los ciclos ... o no obtendrá nada.

Referencias autorizadas

No puede haber referencias autorizadas para algo que nunca fue propuesto, sugerido o incluso imaginado para la estandarización. Boost no tiene ese tipo, y tales construcciones nunca fueron consideradas para boost::shared_ptr . Incluso el primer papel de puntero inteligente (PDF) nunca consideró la posibilidad. El tema de expandir shared_ptr para que automáticamente pueda manejar los ciclos a través de un esfuerzo manual nunca se ha discutido, incluso en los foros de propuestas estándar donde se han deliberado las ideas más estúpidas.

Lo más cercano a una referencia que puedo proporcionar es este documento de 1994 sobre un puntero inteligente contado por referencia . Este documento básicamente habla sobre hacer que el equivalente de shared_ptr y weak_ptr parte del lenguaje (esto fue en los primeros días; ni siquiera pensaron que era posible escribir un shared_ptr que permitiera shared_ptr<T> un shared_ptr<T> en un shared_ptr<U> cuando U es una base de T ). Pero aun así, dice específicamente que los ciclos no se recogerán. No gasta mucho tiempo en por qué no, pero sí dice esto:

Sin embargo, los ciclos de objetos recolectados con funciones de limpieza son problemáticos. Si A y B son accesibles entre sí, la destrucción de cualquiera de los dos primeros violará la garantía de pedido y dejará un puntero colgando. Si el recolector rompe el ciclo arbitrariamente, los programadores no tendrían una garantía real de pedido, y podrían surgir errores sutiles y dependientes del tiempo. Hasta la fecha, nadie ha ideado una solución segura y general para este problema [Hayes 92].

Esto es esencialmente el problema de encapsulación / invariante que señalé: hacer que un puntero miembro de un tipo inválido rompa una invariante.

Así que, básicamente, pocas personas han considerado la posibilidad, y los pocos que la descartaron rápidamente por ser poco práctica. Si realmente crees que están equivocados, la mejor manera de probarlo es implementándolo tú mismo. Luego proponlo para la estandarización.

Por referencia, contar lo que pides es imposible. Para identificar un círculo, uno debería tener identificación de las referencias a su objeto. Eso es fácil en los lenguajes administrados por memoria ya que la máquina virtual sabe quién hace referencia a quién.

En c ++ solo puede hacer eso manteniendo una lista de referencias en el puntero circular de, por ejemplo, UUID que identifica el objeto que hace referencia a sus recursos. Esto implicaría que el uuid se pasa de alguna manera a la estructura cuando se adquiere el objeto, o que el puntero tiene acceso a los recursos internos.

Estos se convierten ahora en la aplicación específica, ya que requieren una interfaz de puntero por ejemplo, copia diferente y asignación no podría implementarse como punteros primas, y la demanda de todas las plataformas de tener una fuente UUID, que no puede ser el caso para todos los sistemas. Se podría, por supuesto, proporcionar la dirección de memoria como un UUID.

Aún así superar la copia, y la asignación adecuada sin tener una especializada assignmétodo, probablemente requeriría una sola fuente que asigna referencias. Esto no se puede incrustar en el lenguaje, pero se puede implementar para una aplicación específica como registro global.

Aparte de eso, la copia de un puntero compartidos tales incurr más grande sería mayor impacto en el rendimiento, ya que durante esas operaciones el tendría que realizar operaciones de búsqueda para añadir, eliminar o resolver ciclos. Dado que, haciendo la detección de ciclo en un gráfico, desde el punto de vista de la complejidad, sería necesario para atravesar el gráfico registrado y aplicar DFS con marcha atrás, que es al menos proporcional al tamaño de las referencias, no veo cómo todos estos no lo hacen gritar GC.

Shared_ptr no se hizo para la recuperación automática de referencias circulares. Existió en la biblioteca de impulso durante algún tiempo antes de copiarse en STL. Es una clase que asocia un contador de referencia a cualquier objeto de C ++, ya sea una matriz, una clase o un int. Es una clase relativamente ligera y autosuficiente. No sabe qué contiene, con la excepción de que conoce una función de eliminación para llamar cuando sea necesario.

Al esta resolución de ciclo requiere demasiado código pesado. Si le gusta GC, puede usar otro idioma, que fue diseñado para GC desde el principio. Encenderlo a través de STL se vería feo. Una extensión de lenguaje como en C ++ / CLI sería mucho más agradable.

std::weak_ptr es la solución a este problema. Tu preocupación por

un árbol donde los niños tienen un puntero hacia atrás al padre

puede resolverse utilizando punteros sin formato como puntero de retroceso. No se preocupe por las fugas si lo piensa.

y tu preocupación por

lista doblemente vinculada

es resuelto por std::weak_ptr o raw.