[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