Re: [Boost-users] boost serialize - stack overflow for large problems

Subject: Re: [Boost-users] boost serialize - stack overflow for large problems
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2010-09-29 12:12:12

On Wed, Sep 29, 2010 at 11:26 AM, Robert Ramey <ramey_at_[hidden]> wrote:
> question:How do you delete the graph?  You have to delete all the
> elements.  If you do it cursively, you'll have the same problem
> of deep nesting.  I doubt that the graph "own's" the objects pointed to.
> So you must have a way to list all the nodes without traveling through
> the graph.  Assumnig you do, serialize all the nodes this way - but
> DON'T include the pointers to adjacent nodes in your serialize function.

Having worked on similar things, I think you may be missing the point here.

Consider a triangulated surface, made up of nodes. Each node has an
ordered list of its neighbors (nodes) that implicitly defines all the
triangles having the node as an apex.

The surface "owns" the nodes (in a vector let's say). The neighboring
nodes of a node are not owned OTOH, yet the connectivity info (the
topology) they represent must still be persisted for each node. And
that info happens to be a vector of pointers of other nodes of the
same surface.

When you serialize the surface, you must serialize all its nodes, and
all those nodes' topology too.
If you do it depth first, you end up blowing up the stack indeed.

I see two possible solutions:

1) save all the nodes *without* their topology info on a first pass of
the vector, thus recording all the "tracked" pointers for them, then
write the topology info for each, since then you don't "recurse", you
only write a "ref" to an already serialized pointer.

2) have the possibility to write a "weak reference" to a pointer,
which only adds the pointer to the "tracking" map with a special flag
saying it wasn't "really" written yet, such that writing the topology
of a node that wasn't yet written is akin to "forward references" to
those neighboring nodes. Either the node will really be written later
on, or it never will, and I suppose serialization should handle that
gracefully.

#1 doesn't require changes in boost serialization, but puts the onus
on the client code. Especially since you have to "externally" save the
neighbors, so it's no longer well encapsulated, and writing a subset
of the surface's nodes become more complex.

#2 would require seeking ahead to read the actual object when
encountering a forward reference, and furthermore a separate map to
know where to seek for it. That may be incompatible with boost
serialization (I confess to be mostly ignorant about it).

But my point is that asking how you delete these nodes is not really a
fair question. The imagined code above (based on real code I've worked
on) knows the neighbors are just references to nodes from the same
surface, and doesn't delete them. Removing a node is an operation you
can do at the surface level only, and removing all nodes simply
iterates on the surface's nodes and deletes them, and the neighbors
are never deleted by the node itself.

> This should resolve your problem.

As I hope I've shown above, I don't think you've addressed the issue
actually. Don't get me wrong, I'm not barging in to this thread to
criticize you or boost serialization, I've just trying to make you see
the problem from a different angle based on my own experience, so you
can formulate a better answer since I'm interested in that answer. If
it comes out wrong, blame it on English not being my native language,
and I apologize in advance for it. Thanks, --DD