Re: Cannot write serialization code without access to Perl_hv_backreferences_p

On 22 December 2014 at 17:56, Steffen Mueller <smue...@cpan.org> wrote:

> On 12/22/2014 03:51 PM, demerphq wrote:>>> Now, if Sereal were a two pass serializer like DDS we could do one>> traversal over the data structure, and use the bookkeeping for that to>> control the second pass. But that would obviously be inefficient as well.>>>> Technically, Sereal can have sort of a second pass, specifically in the> face of weakrefs: If encountered had weakrefs which are not otherwise> referenced in the structure,


The point I was trying to make was to even know this at all one would have
to track every item serialized. Consider something like this:

my $hash= { foo => "foo"};
$hash->{fooref}= \$hash->{foo};
weaken $hash->{fooref};

How would we know that $hash->{foo} was referenced without tracking it?


> we erase the "weaken" tags from the output at the end of the normal> serialization pass (by replacing the tag with a padding entry instead of> memmove'ing what might be a large amount of data).> But as for introducing a full O(inputsize) or rather O(outputsize) pass,> see below:>>  So all together this is a performance issue. If a serialization tool>> wants to handle weakrefs properly and efficiently it needs something>> like hv_backreferences_p(). Having said that I have a patch that>> introduces a new API call in yves/backrefs. I think probably>> hv_backreferences_p() can be made internal again, and the use case>> replaced by the proposed new sv_get_backrefs().>>>> I'd phrase it as "it's a performance issue in terms of having a wide range> of features that users should only pay for if they use them". So the cost> of supporting weakrefs is O(n_weakrefs_used) instead of O(input) or> O(output).


Indeed. With a tiny O(input) overhead due to the check to see if an item is
a weak-referent.

So i think its something like O(k1*input) + O(k2*n_weakrefs_used) versus
O(k3*input) + O(k4*input) where k1 < k2 <= k3 <= k4.

Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"