Segfault с использованием std:: shared_ptr во время уничтожения, вероятно, из-за слишком большого количества вызовов функций в стеке

Следующий код компилируется и работает нормально:

#include <memory>
struct MyTree {
    std::shared_ptr <MyTree> left;
    std::shared_ptr <MyTree> right;
    int val;
    MyTree(
        std::shared_ptr <MyTree> left_,
        std::shared_ptr <MyTree> right_,
        int val_
    ) : left(left_), right(right_), val(val_) {};
};
int main() {
    std::shared_ptr <MyTree> t(
        new MyTree( std::shared_ptr <MyTree>(),
                    std::shared_ptr <MyTree>(),
                    0)
    );  
    for(int i=0;i<10000;i++) {
        t.reset(new MyTree(t,t,0));
    }
}

Однако, когда цикл for изменяется с 10000 на 100000, я получаю segfault. Глядя на результат в gdb, похоже, что деструкторы, вызываемые в результате сборки мусора в std:: shared_ptr, создают обратную линию, которая имеет глубину тысяч. Таким образом, я думаю, что segfault из-за нехватки места в стеке из вызовов функций. У меня два вопроса. Во-первых, это правильная оценка segfault? Во-вторых, если это так, есть хороший способ управлять настраиваемыми структурами данных, такими как деревья, которые нужно собрать мусором, но может быть чрезвычайно большим. Спасибо.

Ответ 1

Это обычно не проблема, потому что обычно вы держите дерево сбалансированным, а глубина - O (lg N).

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

Настоящий односвязный список будет очень глубокой рекурсией, но может выиграть от оптимизации хвостового вызова и не исчерпать стек.

Проблема, с которой вы сталкиваетесь, действительно уникальна для вашего смешивания двух структур данных. У меня нет преимуществ, которые я могу видеть.

Ответ 2

Ваша оценка выглядит совершенно правильно для меня. Похоже, что рекурсивные вызовы для удаления дочерних поддеревьев превышают размер стека yoru. Это не связано с shared_ptr, хотя, как я ожидал бы, любые рекурсивные алгоритмы структуры данных также терпят неудачу одинаковым образом.

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

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

Ответ 3

Это выглядит как неправильное использование std::shared_ptr. И немного очень плохое имя: ваш класс MyTree не является деревом, а просто a node. Дерево должно быть отдельным классом и должно удалять все узлы в своем деструкторе.

Сказав это, это не сильно изменится в отношении проблема под рукой. Вы посещаете узлы на дереве рекурсивно (об единственном способе, который имеет смысл), и если вы пусть дерево становится слишком глубоким, стек будет переполняться, независимо о том, является ли посещение неявным (через деструктор вызывает в std::shared_ptr) или явно. Создание таких деревьев для начать с не имеет смысла, поскольку нет смысла создавать дерево, узлы которого вы не можете посетить, прежде чем начинать разрушая его.

EDIT:

Принять во внимание обсуждение сбора мусора в комментариях. Использование коллектора Boehm или другого сборщика мусора будет решать проблема освобождения элементов. Но он все равно не позволит вам посетить их до освобождения, поэтому такое дерево остается бесполезным. (Я думаю, что там являются очень сильными аргументами в пользу сбора мусора в С++, но это не один из них.)

Ответ 4

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

struct MyTree {
    MyTree *left;
    int val;
    MyTree()
    {
      left = 0;
    }
    MyTree(MyTree *left_)
     : left(left_) {};

    ~MyTree()
    {
      delete left;
    }
};
int main() {
    MyTree *t = new MyTree();
    for(int i=0;i<100000;i++) {
      t = new MyTree(t);
    }
    delete t;
}

Просто добавьте еще один нуль после 100000, и вы получите то же сообщение об ошибке