Будет ли разрушение большого списка переполнять мой стек?

12

Рассмотрим следующую реализацию односвязного списка:

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

Теперь предположим, что я перестал использовать некоторый std::unique_ptr<node> headэкземпляр, который затем выходит из области видимости, вызывая вызов его деструктора.

Будет ли это удар по моему стеку для достаточно больших списков? Справедливо ли предположить, что компилятор будет выполнять довольно сложную оптимизацию (встроенный unique_ptrдеструктор в node, а затем использовать хвостовую рекурсию), что будет намного сложнее, если я сделаю следующее (поскольку dataдеструктор будет запутывать next, делая его трудным чтобы компилятор заметил потенциальную возможность переупорядочения и возможности хвостового вызова):

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

Если dataкаким-то образом есть указатель на его, nodeтогда это может быть даже невозможно для хвостовой рекурсии (хотя, конечно, мы должны стремиться избегать таких нарушений инкапсуляции).

В общем, как можно иначе уничтожить этот список? Мы не можем просмотреть список и удалить «текущий» узел, потому что у общего указателя нет release! Единственный способ - с помощью пользовательского удалителя, который действительно воняет для меня.

VF1
источник
1
Для чего это стоит, даже без нарушения инкапсуляции, упомянутого во втором случае, gcc -O3не удалось оптимизировать хвостовую рекурсию (в сложном примере).
VF1
1
Вот ваш ответ: он может взорвать ваш стек, если компилятор не сможет оптимизировать рекурсию.
Барт ван Инген Шенау
@BartvanIngenSchenau Я думаю, это еще один пример этой проблемы . Это тоже позор, так как мне нравится чистота умных указателей.
VF1

Ответы:

7

Да, это в конечном итоге nodeразрушит ваш стек, если только компилятор не применяет оптимизацию хвостового вызова к деструктору и shared_ptr деструктору. Последнее чрезвычайно зависит от стандартной реализации библиотеки. Например, Microsoft STL никогда этого не сделает, потому что shared_ptrсначала уменьшает счетчик ссылок своего pointee (возможно, уничтожая объект), а затем уменьшает счетчик ссылок своего блока управления (слабый счетчик ссылок). Таким образом, внутренний деструктор не является хвостовым вызовом. Это также виртуальный вызов , который снижает вероятность его оптимизации.

Типичные списки решают эту проблему, не имея один узел, владеющий другим, а имея один контейнер, который владеет всеми узлами, и использует цикл для удаления всего в деструкторе.

Себастьян Редл
источник
Да, я реализовал «типичный» алгоритм удаления списка с пользовательским удалением для тех, кто shared_ptrв конце. Я не могу полностью избавиться от указателей, так как мне нужна была безопасность потоков.
VF1
Я не знал, что у объекта "counter" общего указателя будет также виртуальный деструктор, я всегда предполагал, что это просто POD, содержащий сильные ссылки + слабые ссылки + средство удаления ...
VF1
@ VF1 Вы уверены, что указатели обеспечивают необходимую вам безопасность потоков?
Себастьян Редл
Да - в этом весь смысл std::atomic_*перегрузок для них, нет?
VF1
Да, но с этим вы тоже ничего не добьетесь std::atomic<node*>и дешевле.
Себастьян Редл
5

Поздний ответ, но так как никто не предоставил его ... Я столкнулся с той же проблемой и решил ее, используя собственный деструктор:

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

Если у вас действительно есть список , т. Е. Каждому узлу предшествует один узел, и у него самое большее один подписчик, а ваш listуказатель на первый node, то вышеприведенное должно работать.

Если у вас есть нечеткая структура (например, ациклический граф), вы можете использовать следующее:

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

Идея в том, что когда вы делаете:

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

Старый общий указатель nextуничтожен (потому что use_countон сейчас 0), и вы указываете на следующее. Это делает то же самое, что деструктор по умолчанию, за исключением того, что он делает это итеративно, а не рекурсивно и, таким образом, избегает переполнения стека.

нора
источник
Интересная идея. Не уверен, что он отвечает требованиям OP по безопасности потоков, но, безусловно, является хорошим способом решения этой проблемы в других отношениях.
Жюль
Если вы не перегружаете оператор перемещения, я не уверен, как этот подход действительно что-то сохраняет - в реальном списке, в то время как условие будет оцениваться не более одного раза с рекурсивным next = std::move(next->next)вызовом next->~node().
VF1
1
@ VF1 Это работает, потому что next->nextстановится недействительным (оператором присваивания перемещения) до nextуничтожения указанного значения , тем самым "останавливая" рекурсию. Я на самом деле использую этот код и эту работу (протестировано с g++, clangи msvc), но теперь, когда вы это говорите, я не уверен, что это определено стандартом (тот факт, что перемещенный указатель является недействительным до уничтожения старого объекта, указанного по указателю цели).
Холт
@ VF1 Обновление: в соответствии со стандартом, operator=(std::shared_ptr&& r)эквивалентно std::shared_ptr(std::move(r)).swap(*this). Все еще из стандарта, конструктор перемещения std::shared_ptr(std::shared_ptr&& r)делает rпустым, следовательно r, пустым ( r.get() == nullptr) перед вызовом swap. В моем случае это средство next->nextпусто до того, как старый объект, на который указывает указатель, nextбудет уничтожен (при swapвызове).
Холт
1
@ VF1 Ваш код не тот же - вызов fвключен next, нет next->next, и, поскольку next->nextон нулевой, он немедленно останавливается.
Холт
1

Честно говоря, я не знаком с алгоритмом освобождения смарт-указателей любого компилятора C ++, но я могу представить простой нерекурсивный алгоритм, который это делает. Учти это:

  • У вас есть очередь умных указателей, ожидающих освобождения.
  • У вас есть функция, которая берет первый указатель и освобождает его, и повторяет это до тех пор, пока очередь не станет пустой.
  • Если умный указатель нуждается в освобождении, он помещается в очередь и вызывается вышеупомянутая функция.

Следовательно, у стека не было бы шансов переполниться, и это намного проще, чем оптимизировать рекурсивный алгоритм.

Я не уверен, вписывается ли это в философию «умных указателей с почти нулевой стоимостью».

Я полагаю, что то, что вы описали, не приведет к переполнению стека, но вы можете попытаться создать умный эксперимент, чтобы доказать, что я неправ.

ОБНОВИТЬ

Ну, это доказывает неправильность того, что я написал ранее:

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

Эта программа вечно строит и деконструирует цепочку узлов. Это вызывает переполнение стека.

Габор Ангьял
источник
1
Ах, вы хотите использовать стиль продолжения? По сути, это то, что вы описываете. Тем не менее, я бы скорее пожертвовал умными указателями, чем построил бы другой список в куче только для того, чтобы освободить старый.
VF1
Я был неправ. Я изменил свой ответ соответственно.
Габор Ангиал