Request for pre-review: std.serialization/orange

Jacob Carlborg doob at me.com
Sun Oct 2 23:38:22 PDT 2011


On 2011-10-02 00:52, Robert Jacques wrote:
> On Sat, 01 Oct 2011 07:18:59 -0400, Jacob Carlborg <doob at me.com> wrote:
> For the pre-review its okay. But you'll need it for the actual review.

Ok, it will be the same documentation as for Archive and Base. Ddoc 
really needs to get better at this, I mean, why can't it just inherit 
the documentation.

>>> Also by the time archiving is called, isSliceOf should always return
>>> false.
>>
>> Why is that?
>
> If isSliceOf can return true, then that means that the archive is
> responsible for alias detection, management, etc.

No, who says that. You can take this struct and use it outside of this 
library, it knows nothing about archiving or serialization. If the 
isSliceOf method should return false when archiving has been called I 
would need to add logic to detect when serialization and archiving has 
begun and ended.

> That means that every
> single archive format must implement an alias resolution algorithm.

No, the serializer performs this task.

> This  results in a lot of copy/paste boiler plate which has to be maintained.
> It also makes it more difficult to get extra formats supported. Worse if
> someone forgets to either include this functionality or to apply a
> patch, silent bugs and/or slowdowns are introduced. All and archiver
> should be responsible for is taking some decorated data structure and
> converting it to XML/JSON/YAML/etc and back again. Anything more complex
> than that should be shared functionality located in the serializer /
> de-serializer objects.

It's the only thing the archive does.

>> I do. How would I otherwise discover if an array is a slice of another
>> array or not?
>
> Okay, first some rational. Consider:
>
> assert(!a.isSliceOf(b));
> assert(!b.isSliceOf(a));
> assert( c.isSliceOf(a));
> assert( c.isSliceOf(b));
>
> and
>
> class Foo {
> float x;
> float[3] point;
> }
>
> void main() {
> auto foo = new Foo;
> auto ptr = &foo.x;
> auto slice = point[0..2];
> }
>
> In the first case, a, b and c are all slices of a common root array, but
> the root array may not be serialized. In the second case, first you have
> a pointer to the inside of an object and second you have a slice of a
> static array inside an object, all three of which may be serialized
> together. My impression from your API (so this might not be correct) is
> that currently, you can't handle the above use cases. Even if you can,
> an O(N^2) algorithm is rather inefficient.

This is how it works: As the first step all arrays are serialized as 
regular arrays and not slices. After all serialization is done I loop 
over all arrays and check if they are a slice of some other array. If I 
found a match I replace the serialized array with a slice instead.

These arrays are stored as an associative array with the type Array[Id]. 
I don't know if there's a better data structure for this.

> The solution, in my mind, is to think in terms of memory blocks/chucks.
> Every reference can be thought as pointing to a memory chunk defined by
> two pointers and a flag:
>
> {
> void* head; // Start of the memory chunk
> void* tail; // End of the memory chunk
> bool hasAliases; // True if there are more than one reference to this chunk
> }
>
> For alias detection / resolution, you build a balanced tree of memory
> chunks, widening the chunk and flagging hasAliases as appropriate. Which
> should give you O(N log(N)) performance.

I'm not sure I understand. That would require that the arrays are stored 
in a continues block of memory? Won't "head" and "tail" always point to 
start of the array and the end of the array?

> As an optimization, the user should be able to 'finalize' the
> serialization by pruning away all memory chunks without aliases. (i.e. a
> serializeAndClear method)


-- 
/Jacob Carlborg


More information about the Digitalmars-d mailing list