Czy zniszczenie dużej listy przepełni mój stos?

12

Rozważ następującą pojedynczo połączoną implementację listy:

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

Załóżmy teraz, że przestałem używać std::unique_ptr<node> headinstancji, która następnie wykracza poza zakres, powodując wywołanie jej destruktora.

Czy to zniszczy mój stos na wystarczająco duże listy? Czy można założyć, że kompilator wykona dość skomplikowaną optymalizację (wbudowany unique_ptrdestruktor w node, a następnie użyje rekurencji ogona), co staje się znacznie trudniejsze, jeśli wykonam następujące czynności (ponieważ datadestruktor zaciemniłby next, co utrudnia aby kompilator zauważył potencjalną możliwość ponownego zamawiania i możliwość wywołania ogona):

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

Jeśli w datajakiś sposób ma do niego wskaźnik, nodewówczas rekurencja ogona może być nawet niemożliwa (choć oczywiście powinniśmy starać się unikać takich naruszeń hermetyzacji).

Ogólnie więc, w jaki sposób należy zniszczyć tę listę w inny sposób? Nie możemy przechodzić przez listę i usuwać „bieżącego” węzła, ponieważ wspólny wskaźnik nie ma release! Jedynym sposobem jest niestandardowy deleter, który jest dla mnie naprawdę śmierdzący.

VF1
źródło
1
Bo to, co jest warte, nawet bez naruszenia enkapsulacji wspomnianego w drugim przypadku, gcc -O3nie było w stanie zoptymalizować rekurencji ogona (w skomplikowanym przykładzie).
VF1
1
Tutaj masz odpowiedź: może to zniszczyć twój stos, jeśli kompilator nie będzie w stanie zoptymalizować rekurencji.
Bart van Ingen Schenau
@BartvanIngenSchenau Myślę, że to kolejny przypadek tego problemu . Szkoda też, ponieważ lubię sprytną czystość wskaźnika.
VF1

Odpowiedzi:

7

Tak, to ostatecznie nodezniszczy twój stos, chyba że kompilator po prostu zastosuje optymalizację wywołania ogona do destruktora i shared_ptr destruktora. Ten ostatni jest bardzo zależny od standardowej implementacji biblioteki. Na przykład STL Microsoftu nigdy tego nie zrobi, ponieważ shared_ptrnajpierw zmniejsza liczbę referencji swojego punktu (potencjalnie niszcząc obiekt), a następnie zmniejsza liczbę referencji bloku kontrolnego (liczba słabych referencji). Więc wewnętrzny destruktor nie jest wezwaniem do ogona. Jest to również połączenie wirtualne , co sprawia, że ​​jeszcze mniej prawdopodobne jest, że zostanie zoptymalizowane.

Typowe listy omijają ten problem, ponieważ jeden węzeł nie jest właścicielem drugiego, ale jeden kontener, który jest właścicielem wszystkich węzłów i używa pętli do usunięcia wszystkiego z destruktora.

Sebastian Redl
źródło
Tak, w końcu zaimplementowałem „typowy” algorytm usuwania listy z niestandardowym usuwaczem shared_ptr. Nie mogę całkowicie pozbyć się wskaźników, ponieważ potrzebowałem bezpieczeństwa wątku.
VF1
Nie wiedziałem też, że wspólny obiekt „licznika” wskaźnika miałby też wirtualny destruktor, zawsze zakładałem, że był to POD posiadający silne referencje + słabe referencje + deleter ...
VF1
@ VF1 Czy jesteś pewien, że wskaźniki dają ci bezpieczeństwo, którego potrzebujesz?
Sebastian Redl
Tak - to dla nich sedno std::atomic_*przeciążeń, nie?
VF1
Tak, ale to też nic, czego nie można osiągnąć std::atomic<node*>, i taniej.
Sebastian Redl
5

Późna odpowiedź, ale ponieważ nikt jej nie podał ... napotkałem ten sam problem i rozwiązałem go za pomocą niestandardowego destruktora:

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

Jeśli naprawdę masz listę , tzn. Każdy węzeł jest poprzedzony jednym węzłem i ma co najwyżej jednego obserwatora, a twój listwskaźnik jest wskaźnikiem do pierwszego node, powyższe powinno działać.

Jeśli masz rozmytą strukturę (np. Wykres acykliczny), możesz użyć następujących opcji:

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

Chodzi o to, że kiedy to robisz:

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

Stary wspólny wskaźnik nextjest zniszczony (ponieważ use_countjest teraz 0), a Ty wskazujesz na następujące. Robi to dokładnie to samo, co domyślny destruktor, tyle że robi to iteracyjnie zamiast rekurencyjnie, dzięki czemu unika się przepełnienia stosu.

Holt
źródło
Ciekawy pomysł. Nie jestem pewien, czy spełnia on wymagania OP dotyczące bezpieczeństwa wątków, ale z pewnością jest to dobry sposób podejścia do tego problemu pod innymi względami.
Jules
O ile nie przeciążyłeś operatora ruchu, nie jestem pewien, jak to podejście faktycznie cokolwiek oszczędza - na prawdziwej liście, każdy warunek zostanie oceniony najwyżej raz, z rekurencyjnym next = std::move(next->next)wywoływaniem next->~node().
VF1,
1
@ VF1 Działa next->nextto, ponieważ jest unieważniane (przez operatora przypisania ruchu), zanim wskazana wartość nextzostanie zniszczona, a tym samym „zatrzymanie” rekurencji. Właściwie używam tego kodu i tej pracy (przetestowanej z g++, clangi msvc), ale teraz, kiedy to mówisz, nie jestem pewien, czy jest to zdefiniowane przez standard (fakt, że przesunięty wskaźnik jest unieważniany przed zniszczeniem wskazanego starego obiektu wskaźnikiem docelowym).
Holt,
@ Aktualizacja VF1: Zgodnie ze standardem operator=(std::shared_ptr&& r)jest równoważna std::shared_ptr(std::move(r)).swap(*this). Wciąż ze standardu konstruktor ruchu make std::shared_ptr(std::shared_ptr&& r)czyni rpustym, dlatego rjest pusty ( r.get() == nullptr) przed wywołaniem swap. W moim przypadku środki te next->nextsą puste, zanim stary obiekt wskazywany przez nextzostanie zniszczony (przez swapwywołanie).
Holt,
1
@ VF1 Twój kod nie jest taki sam - połączenie z fjest włączone next, a nie next->next, a ponieważ next->nextjest puste, natychmiast się zatrzymuje.
Holt,
1

Szczerze mówiąc, nie jestem zaznajomiony z algorytmem inteligentnej dealokacji wskaźnika w żadnym kompilatorze C ++, ale mogę sobie wyobrazić prosty, nierekurencyjny algorytm, który to robi. Rozważ to:

  • Masz kolejkę inteligentnych wskaźników oczekujących na zwolnienie.
  • Masz funkcję, która pobiera pierwszy wskaźnik i zwalnia go, i powtarza to, aż kolejka będzie pusta.
  • Jeśli inteligentny wskaźnik wymaga zwolnienia, zostaje wypchnięty do kolejki i wywoływana jest powyższa funkcja.

Dlatego nie byłoby szansy na przepełnienie stosu, a optymalizacja algorytmu rekurencyjnego jest znacznie prostsza.

Nie jestem pewien, czy wpisuje się to w filozofię „prawie zerowych inteligentnych wskaźników”.

Sądzę, że to, co opisałeś, nie spowoduje przepełnienia stosu, ale możesz spróbować przeprowadzić sprytny eksperyment, aby udowodnić, że się mylę.

AKTUALIZACJA

Cóż, to okazuje się błędne, co napisałem wcześniej:

#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;
}

Ten program wiecznie buduje i dekonstruuje łańcuch węzłów. Powoduje to przepełnienie stosu.

Gábor Angyal
źródło
1
Ach, masz na myśli styl kontynuacji? Skutecznie to właśnie opisujesz. Jednak wcześniej poświęcę inteligentne wskaźniki, niż zbuduję kolejną listę na stosie, aby cofnąć przydział starej.
VF1,
Myliłem się. Odpowiednio zmieniłem swoją odpowiedź.
Gábor Angyal