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, 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).
--Steffen