Boost logo

Boost Users :

Subject: Re: [Boost-users] boost serialize - stack overflow for largeproblems
From: Robert Ramey (ramey_at_[hidden])
Date: 2010-09-29 14:24:59


Dominique Devienne wrote:
> 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.

That's my suggestion.

>
> 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.

I'd have to think about this.

>
> #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.

If you can iterate along all the nodes, you can serialize them. Then
you use #1 above.

>> 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

I'm aware of the problem, it just seems to me that it's more general
than serialization and not addressable from within it. It would
come up on any nested recurssive algorithm.

Maybe just create a large stack and don't worry about it.
If memory commitment is a problem, then create a temporary stack
with a separate task or co-routine and use that for serialization.
Then the problem becomes temporary rather than permanent.

Robert Ramey


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net