Re: [boost] question about flyweight

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2008-02-04 13:35:24

Robert Ramey ha escrito:

[...]

>   template<
>     class Archive,
>     typename T,typename Arg1,typename Arg2,typename Arg3
>   >
>   void load(
>     Archive& ar,const ::boost::flyweights::flyweight<T,Arg1,Arg2,Arg3>& f,
>     const unsigned int version)
>   {
>     typedef ::boost::flyweights::flyweight<T,Arg1,Arg2,Arg3> flyweight;
>     T t;
>     ar >> t;
>     f = t;  // look up here
>     ar.reset_object_address(& f.get(), &t);
>   }
>
> vs.
>
> // from flyweight serialize
>
> template<
>     class Archive,
>     typename T,typename Arg1,typename Arg2,typename Arg3
> >
> void load(
>     Archive& ar,::boost::flyweights::flyweight<T,Arg1,Arg2,Arg3>& f,
>     const unsigned int version
> ){
>     typedef ::boost::flyweights::flyweight<T,Arg1,Arg2,Arg3> flyweight;
>     typedef ::boost::flyweights::detail::serialization_helper<flyweight>
> helper;
>     typedef typename helper::size_type size_type;
>     helper& hlp=
>     ::boost::flyweights::detail::get_serialization_helper<flyweight>(ar);
>     size_type n=0;
>     ar>>make_nvp("item",n);
>     if(n>hlp.size()){
>         throw_exception(
>         archive::archive_exception(archive::archive_exception::other_exception));
>     }
>     else if(n==hlp.size()){
>         ::boost::flyweights::detail::archive_constructed<T>
> v("value",ar,version);
>         hlp.push_back(flyweight(v.get())); // Doesn't push_back need to do a
> find?
>     }
>     f=hlp[n];
> }
>
> I've delved into the helper.  I kind of ran out of gas at multi-index.

:-) I know my code gets cryptic sometimes. Sorry for that. The helper is
just a table of flyweight objects with the following access methods:

  1. Given a flyweight f, it returns the position n of an equivalent object
  stored in the table (if there is any).
  2. Given a position n, it returns the flyweight at that position.

It's a kind of vector of flyweights with hash-based lookup.

> Doesn't this require a lookup to maintain the mult-indexed table?

Well, it turns push_back does indeed induces an insertion into the hashed index,
but this is an oversight from my part: we could do with a singly indexed container
and no lookup at all during the load phase, we need only use different helpers
for loading and saving. Either way, the actual measurements showed the helper
version outperformed the version based on T tracking, even with this unnecessary
lookup in place. Note that the non-helper version has an extra lookup lurking
inside reset_object_address.

For your reference, the helper-based loading algorithm reduces to:

  1. Load position n (constant time)
  2. If the table has size>=n, get flyweight at position n and assign to our
  loading object (constant time)
  3. Otherwise, load a T object, assign to our loading object (lookup needed)
  and store a copy on the table at position n (constant time).

It's hard to beat this up, it's as simple as it can get. In particular, when loading
a duplicate flyweight the executed code is extremely lean.

> Also using the helper entails a lot more generated code. It looks like a bunch more
> code generated for each type flyweight. I'm not convinced that there is a real saving
> here.

I've got nothing to say about the extra generated code except that I don't think
this is so important (others might differ), but there is definitely a high impact on
performance. It's not a theoretical analysis, I measured it.

> If you dropped the helper, then you're class would be serializable right now
> and it would entail a lot less code.  You could always make it more
> elaborate later.

If I released the library with serialization algorithm A and later on I migrated to
algorithm B, I'd have to maintain some legacy code to support old A-archives. This
is why I'd rather get it right at first shot.

IMHO we should shift our discussion focus to whether helpers make sense or
not in the first place, regardless of their particular applications. It's only on its general
merits that helpers should be included or not, of course. My particular application
at least shows they provide for much better performance.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo