A destruição de uma lista grande sobrecarregará minha pilha?

11

Considere a seguinte implementação de lista vinculada única:

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

Agora, suponha que eu pare de usar alguma std::unique_ptr<node> headinstância que fica fora do escopo, fazendo com que seu destruidor seja chamado.

Isso vai explodir minha pilha para listas suficientemente grandes? É justo supor que o compilador faça uma otimização bastante complicada ( unique_ptro destruidor do inline para o node's' e depois use a recursão da cauda), o que fica muito mais difícil se eu fizer o seguinte (já que o datadestruidor ofuscaria nexto do, tornando difícil para o compilador perceber as possíveis oportunidades de reordenação e chamada final):

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

Se de dataalguma forma tem um ponteiro para nodeisso, pode até ser impossível a recursão da cauda (embora, é claro, devamos nos esforçar para evitar tais violações do encapsulamento).

Em geral, como alguém deveria destruir essa lista, então? Não podemos percorrer a lista e excluir o nó "atual" porque o ponteiro compartilhado não possui um release! A única maneira é com um deleter personalizado, que é realmente fedorento para mim.

VF1
fonte
11
Pelo que vale a pena, mesmo sem a violação do encapsulamento mencionada no segundo caso, gcc -O3não foi possível otimizar uma recursão de cauda (em um exemplo complicado).
VF1 27/01
11
Aí você tem a sua resposta: pode explodir sua pilha, se o compilador não puder otimizar a recursão.
Bart van Ingen Schenau,
@BartvanIngenSchenau Acho que essa é outra instância desse problema . É uma pena também, já que gosto de limpeza inteligente de ponteiros.
VF1 27/01

Respostas:

6

Sim, isso acabará com sua pilha, a menos que o compilador aplique uma otimização de chamada de cauda ao nodedestruidor e shared_ptr destruidor. O último é extremamente dependente da implementação da biblioteca padrão. O STL da Microsoft, por exemplo, nunca fará isso, porque shared_ptrprimeiro diminui a contagem de referência de seu pontapé (possivelmente destruindo o objeto) e depois diminui a contagem de referência de seu bloco de controle (a contagem fraca de referência). Portanto, o destruidor interno não é um chamado final. Também é uma chamada virtual , o que torna ainda menos provável que ela seja otimizada.

As listas típicas resolvem esse problema por não ter um nó próprio no próximo, mas por um contêiner que possui todos os nós e usa um loop para excluir tudo no destruidor.

Sebastian Redl
fonte
Sim, implementei o algoritmo de exclusão de lista "típico" com um deleter personalizado para aqueles shared_ptrs no final. Não consigo me livrar completamente dos ponteiros, pois precisava da segurança do thread.
VF1 27/01
Eu não sabia o ponteiro objeto "counter" compartilhada teria um destrutor virtual seja, eu sempre assumiu que era apenas um POD segurando as refs fortes + refs fracos + deleter ...
VF1
@ VF1 Tem certeza de que os ponteiros estão lhe dando a segurança de thread que você deseja?
Sebastian Redl
Sim - esse é o objetivo das std::atomic_*sobrecargas para eles, não?
VF1 27/01
Sim, mas isso também não é algo que você não pode alcançar std::atomic<node*>, e mais barato.
Sebastian Redl
5

Resposta tardia, mas como ninguém a forneceu ... Encontrei o mesmo problema e o resolvi usando um destruidor personalizado:

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

Se você realmente tem uma lista , ou seja, todo nó é precedido por um nó e tem no máximo um seguidor, e você listé um ponteiro para o primeiro node, o que precede deve funcionar.

Se você possui alguma estrutura difusa (por exemplo, gráfico acíclico), pode usar o seguinte:

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

A ideia é que quando você faz:

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

O ponteiro compartilhado antigo nexté destruído (porque use_countagora é 0) e você aponta para o seguinte. Isso faz exatamente o mesmo que o destruidor padrão, exceto o iterativamente, em vez de recursivamente, evitando assim o estouro da pilha.

Holt
fonte
Idéia interessante. Não tenho certeza de que atende aos requisitos da OP para segurança de threads, mas certamente uma boa maneira de abordar a questão em outros aspectos.
Jules
A menos que você sobrecarregue o operador de movimentação, não tenho certeza de como essa abordagem realmente salva alguma coisa - em uma lista real, cada condição enquanto será avaliada no máximo uma vez, com next = std::move(next->next)chamadas next->~node()recursivas.
VF1
11
@ VF1 Isto funciona porque next->nexté invalidado (pelo operador de atribuição de movimentação) antes que o valor apontado por nextseja destruído, "interrompendo" a recursão. Eu realmente usar este código e este trabalho (testado com g++, clange msvc), mas agora que você diz isso, não estou certo de que esta é definida pelo padrão (o fato de que o ponteiro movido é invalidada antes da destruição do antigo objeto pontiagudo pelo ponteiro de destino).
Holt
@ Atualização VF1: De acordo com o padrão, operator=(std::shared_ptr&& r)é equivalente a std::shared_ptr(std::move(r)).swap(*this). Ainda a partir do padrão, o construtor movimento de std::shared_ptr(std::shared_ptr&& r)marcas resvaziar, assim restá vazio ( r.get() == nullptr) antes da chamada para swap. No meu caso, esse meio next->nextestá vazio antes que o objeto antigo apontado por nextseja destruído (pela swapchamada).
Holt
11
@ VF1 Seu código não é o mesmo - A chamada para festá ativada next, não next->nexte, como next->nexté nula, para imediatamente.
Holt
1

Para ser sincero, não estou familiarizado com o algoritmo de desalocação de ponteiros inteligentes de qualquer compilador C ++, mas posso imaginar um algoritmo simples e não recursivo que faz isso. Considere isto:

  • Você tem uma fila de ponteiros inteligentes aguardando a desalocação.
  • Você tem uma função que pega o primeiro ponteiro e o desaloca e repete isso até que a fila esteja vazia.
  • Se um ponteiro inteligente precisar de desalocação, ele será empurrado para a fila e a função acima será chamada.

Portanto, não haveria chance da pilha transbordar, e é muito mais simples otimizar um algoritmo recursivo.

Não tenho certeza se isso se encaixa na filosofia "quase zero custo de ponteiros inteligentes".

Eu acho que o que você descreveu não causaria estouro de pilha, mas você poderia tentar construir um experimento inteligente para provar que estava errado.

ATUALIZAR

Bem, isso prova errado o que escrevi 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;
}

Esse programa cria eternamente e desconstrói uma cadeia de nós. Isso causa excesso de pilha.

Gábor Angyal
fonte
11
Ah, você quer usar o estilo de passagem de continuação? Efetivamente, é isso que você está descrevendo. No entanto, antes sacrificaria indicadores inteligentes do que criaria outra lista na pilha apenas para desalocar uma antiga.
VF1 27/01
Eu estava errado. Eu mudei minha resposta de acordo.
Gábor Angyal 27/01