¿Destruir una lista grande desbordará mi pila?

12

Considere la siguiente implementación de lista vinculada individualmente:

struct node {
    std::unique_ptr<node> next;
    ComplicatedDestructorClass data;
}

Ahora, supongamos que dejo de usar alguna std::unique_ptr<node> headinstancia que luego se sale del alcance y hace que se llame a su destructor.

¿Esto volará mi pila de listas lo suficientemente grandes? ¿Es justo suponer que el compilador hará una optimización bastante complicada ( unique_ptrdestructor en línea en nodeel, luego usará la recursión de cola), que se vuelve mucho más difícil si hago lo siguiente (ya que el datadestructor ofuscaría nextel de él, lo que lo dificultaría para que el compilador note la posible oportunidad de reordenamiento y llamada de cola):

struct node {
    std::shared_ptr<node> next;
    ComplicatedDestructorClass data;
}

Si de dataalguna manera tiene un puntero, nodeentonces podría ser imposible para la recursión de la cola (aunque, por supuesto, deberíamos esforzarnos por evitar tales brechas de encapsulación).

En general, ¿cómo se supone que se debe destruir esta lista de otra manera, entonces? No podemos atravesar la lista y eliminar el nodo "actual" porque el puntero compartido no tiene un release! La única forma es con un eliminador personalizado, lo cual es realmente maloliente para mí.

VF1
fuente
1
Por lo que vale, incluso sin la violación de la encapsulación mencionada en el segundo caso, gcc -O3no fue posible optimizar una recursión de la cola (en un ejemplo complicado).
VF1
1
Ahí tienes tu respuesta: podría volar tu pila, si el compilador no puede optimizar la recursión.
Bart van Ingen Schenau
@BartvanIngenSchenau Supongo que esa es otra instancia de este problema . También es una verdadera lástima, ya que me gusta la limpieza del puntero inteligente.
VF1

Respuestas:

7

Sí, esto eventualmente volará tu pila, a menos que el compilador simplemente aplique una optimización de llamada de cola al nodedestructor y shared_ptr al destructor. Este último es extremadamente dependiente de la implementación estándar de la biblioteca. El STL de Microsoft, por ejemplo, nunca hará eso, porque shared_ptrprimero disminuye el recuento de referencia de su destinatario (posiblemente destruyendo el objeto) y luego disminuye el recuento de referencia de su bloque de control (el recuento de referencia débil). Entonces el destructor interno no es una llamada de cola. También es una llamada virtual , lo que hace que sea aún menos probable que se optimice.

Las listas típicas resuelven ese problema al no tener un nodo propio al siguiente, sino al tener un contenedor que posee todos los nodos y usa un bucle para eliminar todo en el destructor.

Sebastian Redl
fuente
Sí, implementé el algoritmo de eliminación de listas "típico" con un eliminador personalizado para esos shared_ptral final. No puedo deshacerme por completo de los punteros ya que necesitaba la seguridad del hilo.
VF1
Tampoco sabía que el objeto "contador" de puntero compartido tendría un destructor virtual, siempre supuse que era solo un POD que contenía las referencias fuertes + referencias débiles + deletor ...
VF1
@ VF1 ¿Está seguro de que los punteros le brindan la seguridad de hilo que desea?
Sebastian Redl
Sí, ese es el objetivo de las std::atomic_*sobrecargas para ellos, ¿no?
VF1
Sí, pero eso no es nada con lo que no puedas lograr std::atomic<node*>también, y más barato.
Sebastian Redl
5

Respuesta tardía pero como nadie me la proporcionó ... Me encontré con el mismo problema y lo resolví usando un destructor personalizado:

virtual ~node () throw () {
    while (next) {
        next = std::move(next->next);
    }
}

Si realmente tiene una lista , es decir, cada nodo está precedido por un nodo y tiene como máximo un seguidor, y su listpuntero es el primero node, lo anterior debería funcionar.

Si tiene alguna estructura difusa (por ejemplo, un gráfico acíclico), puede usar lo siguiente:

virtual ~node () throw () {
    while (next && next.use_count() < 2) {
        next = std::move(next->next);
    }
}

La idea es que cuando lo haces:

next = std::move(next->next);

El puntero compartido anterior nextse destruye (porque use_countes ahora 0), y señala lo siguiente. Esto hace exactamente lo mismo que el destructor predeterminado, excepto que lo hace de forma iterativa en lugar de recursiva y, por lo tanto, evita el desbordamiento de la pila.

Bosquecillo
fuente
Idea interesante. No estoy seguro de que cumpla con los requisitos de OP para la seguridad de subprocesos, pero sin duda es una buena forma de abordar el problema en otros aspectos.
Jules
A menos que haya sobrecargado el operador de movimiento, no estoy seguro de cómo este enfoque realmente guarda algo: en una lista real, cada una de las condiciones se evaluará como máximo una vez, con next = std::move(next->next)llamadas next->~node()recursivas.
VF1
1
@ VF1 Esto funciona porque next->nextes invalidado (por el operador de asignación de movimiento) antes de que nextse destruya el valor señalado por , "deteniendo" la recursión. De hecho, utilizo este código y este trabajo (probado con g++, clangy msvc), pero ahora que lo dice, no estoy seguro de que esto esté definido por el estándar (el hecho de que el puntero movido se invalida antes de la destrucción del antiguo objeto señalado por el puntero de destino).
Holt
@ Actualización VF1: de acuerdo con el estándar, operator=(std::shared_ptr&& r)es equivalente a std::shared_ptr(std::move(r)).swap(*this). Todavía desde el estándar, el constructor de movimiento de std::shared_ptr(std::shared_ptr&& r)make rempty, por lo tanto, restá vacío ( r.get() == nullptr) antes de la llamada a swap. En mi caso, esto significa que next->nextestá vacío antes de que el viejo objeto señalado nextsea ​​destruido (por la swapllamada).
Holt
1
@ VF1 Su código no es el mismo: la llamada a festá activada next, no next->next, y como next->nextes nula, se detiene de inmediato.
Holt
1

Para ser honesto, no estoy familiarizado con el algoritmo de desasignación de puntero inteligente de ningún compilador de C ++, pero puedo imaginar un algoritmo simple y no recursivo que hace esto. Considera esto:

  • Tiene una cola de punteros inteligentes esperando la desasignación.
  • Tiene una función que toma el primer puntero y lo desasigna, y lo repite hasta que la cola esté vacía.
  • Si un puntero inteligente necesita desasignación, se inserta en la cola y se llama a la función anterior.

Por lo tanto, no habría posibilidad de que la pila se desbordara, y es mucho más simple que optimizar un algoritmo recursivo.

No estoy seguro de si esto encaja en la filosofía de "punteros inteligentes de costo casi cero".

Supongo que lo que describiste no provocaría un desbordamiento de la pila, pero podrías intentar construir un experimento inteligente para demostrar que estoy equivocado.

ACTUALIZAR

Bueno, esto prueba mal lo que escribí anteriormente:

#include <iostream>
#include <memory>

using namespace std;

class Node;

Node *last;
long i;

class Node
{
public:
   unique_ptr<Node> next;
   ~Node()
   {
     last->next.reset(new Node);
     last = last->next.get();
     cout << i++ << endl;
   }
};

void ignite()
{
    Node n;
    n.next.reset(new Node);
    last = n.next.get();
}

int main()
{
    i = 0;
    ignite();
    return 0;
}

Este programa construye eternamente y deconstruye una cadena de nodos. Causa desbordamiento de pila.

Gábor Angyal
fuente
1
Ah, ¿te refieres a usar el estilo de paso continuo? Efectivamente, eso es lo que estás describiendo. Sin embargo, preferiría sacrificar punteros inteligentes que crear otra lista en el montón solo para desasignar una antigua.
VF1
Estaba equivocado. He cambiado mi respuesta en consecuencia.
Gábor Angyal