Request for pre-review: std.serialization/orange

[Jacob Carlborg]

On 2011-10-03 15:57, Robert Jacques wrote:
> So, in essence, you are saying that by the time archiving occurs,
> isSliceOf will always return false? Then why is it part of the public API?

No, I'm not saying that. Example:

struct Array
{
	void* ptr;
	size_t length;
	size_t elementSize;
	
	bool isSliceOf (Array b)
	{
		return ptr >= b.ptr && ptr + length * elementSize <= b.ptr + b.length 
* b.elementSize;
	}
}

void main ()
{
	auto a = [0, 1, 2, 3, 4];
	auto b = a[2 .. 4];
	
	auto aArr = Array(a.ptr, a.length, 4);
	auto bArr = Array(b.ptr, b.length, 4);
	
	assert(bArr.isSliceOf(aArr));
	assert(!aArr.isSliceOf(bArr));
}

Both the asserts in the above code passes as expected. See, no 
serialization or archiving in sight. Is there something I'm missing?

Actually it does not need to be part of the public API when I think 
about it. I can move it into Serializer. Array would still need to be 
public since both Serailzer and Archive need access to it and the 
package attribute doesn't work very well.

>>> 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?
>
> Most of the time yes. But not all of the time. It would be fair to say
> that 'head' and 'tail' would be inside the GC memory region of the array
> and are <= or >= of the start/end of an array, respectively. More
> importantly, both objects and pointers would resolve to memory chunks as
> well and be included in the alias resolution algorithm.

Now I think I start to understand.

> I'm assuming you
> currently separate object and array alias resolution and don't handle
> pointers at all.

Yes. Pointers are handled as well. It's handled similar to 
arrays/slices. First it always serializes what the pointer points to. 
Then in a post process step, after all serialization is done, it 
replaces all serialized pointers, that points to a value that has been 
serialized, with a reference. If a given pointer doesn't point to a 
value that has be serialized it's left as is.

I can see if I this memory chunk approach can be used instead. How will 
this be used with the balanced tree, could you give a simple example?

-- 
/Jacob Carlborg