Slow recursive call of destructor in C ++

Question

I use C ++, represent large graphs using counted objects. Sort of:

// Public class class Pointer{ public: // Constructors Pointer(...){ node = ...; node->counter++;} // Copy constructor Pointer(Pointer& const other){ node = other.node; node->counter++;} // Destructor ~Point(){ if(--node->counter==0) delete node;} // Other methods ... Node* node; }; // Node base class class Node{ // Constructor Node():counter(0){} // Destructor virtual ~Node(){} // public: unsigned long counter; }; // Node derived class class NodeDerived : public Node{ // Constructors and other methods ... // Destructor virtual ~NodeDerived(){ ... } // Children Pointer children[2]; }; 

Thus, there is an open Pointer class that contains a pointer to a polymorphic Node class. Some classes derived from Node will contain new instances of Pointer . Note that multiple Pointer instances may point to the same Node instance.

I use this class to create very large graphs with millions of instances, and this works great. The problem arises when the graph needs to be deleted. Thanks to the default destructor implementation, this leads to a stack overflow, since child destructors are called in the node root destructor and child destructors of the children are called in the destructors of the children, etc.

I solved this by implementing a destructor for the NodeDerived class above, which avoids a recursive call using the stack instead. It works, but still very slow, and I'm looking for a way to speed it up. Is it possible to somehow avoid declaring a virtual destructor without causing a memory leak?

Answer 1

If you are dealing with millions of objects and stack overflow during destruction, then you might want to examine pointers to all your node objects in a container of some type that does not allow duplicate values ​​and supports iteration like a std::set or std::unordered_set . Then, only the connected nodes of the graph are stored in the graph nodes themselves. During deletion for a graph, do not re-read each pointer of the node graph to delete nodes ... instead, just go to the container containing pointers to many nodes on the entire graph, and iterate the container, destroying each node one by one. No recursion is required, since you do not need to “follow” each set of graph-node pointers to destroy all nodes to which the node graph is connected. You also do not need to worry about lack of space and time in std::shared_ptr .

Answer 2

If you are not deleting nodes individually, you might consider using a memory pool instead of link counting. The memory pool will allow you to quickly delete your entire graph at the expense of (depending on the type of pool), possibly unable to recover the memory used by individual deleted objects until the entire graph is destroyed.

Answer 3

Is it possible to somehow avoid declaring a virtual destructor without causing a memory leak?

I am afraid that, more precisely, you cannot avoid undefined behavior when calling delete p pointer with a dynamic pointer type that does not match the static pointer type.

but still very slow

I am afraid that it is so. Removing millions of objects will take some time. You can get around this, for example. while avoiding the destruction of individual objects, for example. putting them all in some pool (and dropping it altogether). Depending on your destruction needs.