Will destructing a large list overflow my stack?

Question

Consider the following singly linked list implementation:

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

Now, suppose I stop using some std::unique_ptr<node> head instance that then goes out of scope, causing its destructor to be called.

Will this blow my stack for sufficiently large lists? Is it fair to assume that the compiler will do a pretty complicated optimization (inline unique_ptr's destructor into node's, then use tail recursion), which gets much harder if I do the following (since the data destructor would obfuscate next's, making it hard for the compiler to notice the potential reordering and tail call opportunity):

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

If data somehow has a pointer to its node then it might even be impossible for tail recursion (though of course we should strive to avoid such breaches of encapsulation).

In general, how is one supposed to destroy this list otherwise, then? We can't traverse through the list and delete the "current" node because shared pointer doesn't have a release! The only way is with a custom deleter, which is really smelly to me.

Answer 1

Late answer but since no one provided it... I ran into the same issue and solved it by using a custom destructor:

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

If you really have a list, i.e. every node is preceded by one node and has at most one follower, and your list is a pointer to the first node, the above should work.

If you have some fuzzy structure (e.g. acyclic graph), you could use the following:

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

The idea is that when you do:

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

The old shared pointer next is destroyed (because its use_count is now 0), and you point to the following. This does exactly the same that the default destructor, except it does it iteratively instead of recursively and thus avoid stack overflow.

Answer 2

Yes, this will eventually blow your stack, unless the compiler just happens to apply a tail call optimization to node's destructor and shared_ptr's destructor. The latter is extremely dependent on the standard library implementation. Microsoft's STL, for example, will never do that, because shared_ptr first decrements its pointee's reference count (possibly destroying the object) and then decrements its control block's reference count (the weak reference count). So the inner destructor is not a tail call. It's also a virtual call, which makes it even less likely that it will get optimized.

Typical lists get around that problem by not having one node own the next, but by having one container that owns all nodes, and uses a loop to delete everything in the destructor.

Answer 3

To be honest I am not familiar with the smart pointer deallocation algorithm of any C++ compiler, but I can imagine a simple, non-recursive algorithm that does this. Consider this:

• You have a queue of smart pointers waiting for deallocation.
• You have a function that takes the first pointer and deallocates it, and repeats this until the queue is empty.
• If a smart pointer needs deallocation, it gets pushed into the queue and the above function gets called.

Hence there would be no chance for the stack to overflow, and it is much simpler that optimizing a recursive algorithm.

I am not sure if this fits into the "almost zero cost smart pointers" philosophy.

I would guess that what you described would not cause stack overflow, but you could try to construct a clever experiment to prove me wrong.

UPDATE

Well, this proves wrong what I wrote previously:

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

This program eternally builds, and deconstructs a chain of nodes. It does cause stack overflow.

Answer 4

I would use

~node() noexcept {
  while (next) {
    std::shared_ptr<node> t;
    std::swap(t,next->next);
    next = t;
  }
}

The idea is to erase the list tail in a node destructor by holding  the pointer to the next node in temporary, then removing the pointer from the current node (by assigning to it next->next), and finally destroying temporary and so on.