[Pharo-project] [GS/SS Beta] serializing object graphs / ordering graph anchors

Norbert Hartl norbert at hartl.name
Fri Jun 3 04:38:44 EDT 2011


Am 03.06.2011 um 10:20 schrieb Mariano Martinez Peck:

> 
> 
>> If I look at the serializers I know the mechanics are simple:
>> 
>> 1. take an object and look it up in a table.
>> 2. if the object is in the table it has already been serialized. We take a reference from the table and write it down
>> 3. if it isn't in the table it means the object has not been serialized and the contents need to be written. After that the object with a reference representation is written to the table
>> 4. while writing the content of an object (inst vars) I encounter simple objects (direct string representation) or complex objects (composite). In the latter case we start over from 1.
>> 
>> If the object graph is well interconnected than the odds are high that a stack will grow high until the first reference can be written. With a small pier kernel I already matched a stack size of 1000.
>> 
>> 
>> In Fuel we  traverse the graph but instead of using a recursion we use our own simple stack implementation where we push and pop objects. 
>> But Martin may explaint better than me. 
> 
> I'm interested in details how it works and if it avoids the deep stack. Is there additional information about that?
> 
> 
> In 4. you said "while writing the content of an object (inst vars) I encounter simple objects (direct string representation) or complex objects (composite). In the latter case we start over from 1.".
> So... Imagine object X with two instVars Y and Z. Imagine the method of the traverse is called #analye:.  So you do #analize: X.  Then, in such method you check whether X has regular pointers to regular objects, and if true, you analize them. So in this case you would send #analyze: Y and #analize: Z, generating the recursion. Right ?

yes, the time between analyse: Y and analyse: Z is dependent on the graph that is attached to Y. Y can have objects that have further objects etc. So leaving X aside, Y can be the first object to serialize and Z the last.
> 
> Ok, instead of sending #analyze: Y and #analize: Z  what we do is just to do a push on a stack:   #push: Y  and #push: Z. And then we are done with X, so we pop from the stack and we continue with the next object (at some point in the future we will pop Y and Z) When there are no more objects in the stack it means we are done. 

How do you write X? I can see that you turn a recursive trace into depth-by-depth trace but the difficult part is to write X. In X you need a reference representation of any sort. How do you derive that from the stack? 

> For performance (I think) we did FLSimpleStack. You can check also FLSimpleStackTest. Both are in Fuel repo. 
> 
> Would something like that help for the stack in GemStone?
> 
Yes. With this approach the resulting stack size is much smaller. To exceed the stack setting you need a graph containing an object which has a shortest route that is larger than the stack limit. And I think this is very unlikely :) 
I would need to change Sixx in order to have it work like this. I need to think about it.

Thanks,

Norbert
> 
>  
> Norbert
> 
>>  
>> One solution I can think of is to collect and order objects in the graph that cover smaller segments from the overall graph. This way I would construct a sorted collection that is sorted by stack depth (lowest first). The collection will then be serialized leading to a much smaller possible stack sizes. It might be there are cases it can't work but I think for most cases it will do its job. And it will be slow of course.
>> 
>> Does anybody know if such a tool exists?
>> 
>> Norbert
>> 
>> 
>> 
>> 
>> 
>> -- 
>> Mariano
>> http://marianopeck.wordpress.com
>> 
> 
> 
> 
> 
> -- 
> Mariano
> http://marianopeck.wordpress.com
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20110603/a1dfa297/attachment-0001.html>


More information about the Pharo-dev mailing list