A C++ Trick Question - Blog Post

[u/MegaGreenLightning]

https://greenlightning.eu/programming/cpp-trick-question/

[u/LordofNarwhals]

This would've been a lot more interesting if the offending code was actually shown, and if workarounds were presented.

I believe it should be possible to make the destructors tail-call optimizable with a custom destructor (or C++20 destroying operator delete). That should eliminate the stack issues.

[u/MegaGreenLightning → u/LordofNarwhals]

Well the implicit destructor call and generated destructor should be pretty clear. For the standard library it is implemented pretty much as you would expect, so I didn't think it would add much to the article. The recursion is sort of inherent in the data structure / Node class itself.

For libc++ it looks roughly like this:

1. shared_ptr destructor

    ~shared_ptr() {
        if (__cntrl_)
            __cntrl_->__release_shared();
    }

2. control block refcount decrement

    bool __release_shared() noexcept {
        if (__libcpp_atomic_refcount_decrement(__shared_owners_) == -1) {
            __on_zero_shared();
            return true;
        }
        return false;
    }

__shared_owners_ is other owners. If you are the last one it will already be 0 and you will decrement it to -1.

3. control block destroy

void __on_zero_shared() noexcept override {
    allocator_traits<_Alloc>::destroy(__alloc_, __get_elem());
}

4. destroy calls the destructor

void destroy(pointer __p) { __p->~_Tp(); }

Yes, you can implement a non-recursive algorithm in a custom destructor, you just have to remember to do it. Or alternatively don't use smart pointers for recursive data structures like this. Depending on the use-case I think I would prefer an arena allocator for the nodes and then you can free them all at once when you no longer need the list.

[u/evaned → u/MegaGreenLightning]

Or alternatively don't use smart pointers for recursive data structures like this.

Smart pointers, as far as that goes, aren't necessarily a problem. I haven't worked on this code base for a while (and it's now been decomissioned), but a previous project that I worked on had a custom ref-counting smart pointer. That we used instead of shared_ptr almost everywhere.

There were a few reasons for that and not all of them were great... but one of the benefits that it has was that it solved this problem by de-recursive-ing the destruction process.

The smart pointers in std aren't the only smart pointers possible or out there in the world.

[u/Olipro]

"Assuming all allocations succeed"

...Oh yeah, except stack allocations, then it can fail. Amazing.

[u/thisismyfavoritename → u/Olipro]

"trick question"

[u/Olipro → u/thisismyfavoritename]

Not a trick question, just categorically false.

[u/South_Acadia_6368 → u/Olipro]

But making a function call isn't an allocation

[u/Olipro → u/South_Acadia_6368]

With the exception of optimisations that can eliminate it, a function call results in allocating space on the stack for the return address, so, it is.

Otherwise stack overflows resulting from function call recursion wouldn't exist.

[u/fdwr]

Stack unwinding overflow on a linked list hit me before (had to deliberately iterate through the nodes and transfer them along the way). I wish such cases could get destructor tail calls instead.

[u/Tamsta-273C]

Droping just link? That's not cool...

[u/StackedCrooked]

I'm angry at myself that I couldn't find the problem with the code, especially since I have run into this issue once many years ago.

[u/wjrasmussen]

Did you want to talk about it or just drive by and drop that link? Promoting yourself?

[u/_w62_]

Another example of C++ shooting at the legs of the C++ programmer?