9

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.

  • For what it's worth, even without the breach of encapsulation mentioned in the second case, gcc -O3 was unable to optimize a tail recursion (in a complicated example). – VF1 Jan 27 '15 at 3:29
  • 1
    There you have your answer: It might blow your stack, if the compiler can't optimize the recursion away. – Bart van Ingen Schenau Jan 27 '15 at 8:24
  • @BartvanIngenSchenau I guess that's another instance of this problem. It's a real shame, too, since I like smart pointer cleanliness. – VF1 Jan 27 '15 at 15:52
6

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.

  • Yeah, I implemented the "typical" list deletion algorithm with a custom deleter for those shared_ptrs in the end. I can't completely get rid of the pointers since I needed the thread safety. – VF1 Jan 27 '15 at 15:54
  • I didn't know the shared pointer "counter" object would have a virtual destructor either, I always assumed it was just a POD holding the strong refs + weak refs + deleter... – VF1 Jan 27 '15 at 15:56
  • @VF1 Are you sure the pointers are giving you the thread safety you want? – Sebastian Redl Jan 27 '15 at 16:08
  • Yes - that's the whole point of the std::atomic_* overloads for them, no? – VF1 Jan 27 '15 at 18:21
  • Yes, but that's nothing you can't achieve with std::atomic<node*> too, and cheaper. – Sebastian Redl Jan 28 '15 at 10:57
4

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

virtual ~node () throw () {
    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 () throw () {
    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.

  • Interesting idea. Not sure it meets OP's requirement for thread-safety, but certainly a good way of approaching the issue in other regards. – Jules Mar 15 '16 at 20:27
  • Unless you overloaded the move operator, I'm not sure how this approach actually saves anything - in a real list, each while condition will be evaluated at most once, with next = std::move(next->next) calling next->~node() recursively. – VF1 Mar 16 '16 at 4:37
  • @VF1 This works because next->next is invalidated (by the move assignment operator) before the value pointed by next is destroyed, thus "stopping" the recursion. I actually use this code and this work (tested with g++, clang and msvc), but now that you say it, I am not sure that this is defined by the standard (the fact that the moved pointer is invalidated before the destruction of the old object pointed by the target pointer). – Holt Mar 16 '16 at 7:29
  • @VF1 Update: According to the standard, operator=(std::shared_ptr&& r) is equivalent to std::shared_ptr(std::move(r)).swap(*this). Still from the standard, the move constructor of std::shared_ptr(std::shared_ptr&& r) makes r empty, thus r is empty (r.get() == nullptr) before the call to swap. In my case, this means next->next is empty before the old object pointed by next is destroyed (by the swap call). – Holt Mar 16 '16 at 7:38
  • 1
    @VF1 Your code is not the same - The call to f is on next, not next->next, and since next->next is null, it stops immediately. – Holt Mar 16 '16 at 18:27
1

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.

  • 1
    Ah, you mean to use continuation-passing style? Effectively, that's what you're describing. However, I'd sooner sacrifice smart pointers than build up another list on the heap just to deallocate an old one. – VF1 Jan 27 '15 at 15:51
  • I was wrong. I have changed my answer accordingly. – Gábor Angyal Jan 27 '15 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.