Re: [flyweight] Review period extended to February 3

----- Mensaje original -----
De: Alberto Ganesh Barbati <AlbertoBarbati <at> libero.it>
Fecha: Domingo, Febrero 3, 2008 12:39 pm
Asunto: Re: [boost] [flyweight] Review period extended to February 3
Para: boost <at> lists.boost.org

> JOAQUIN LOPEZ MU?Z ha scritto:
[...]
> >   I am not plainly denying the existence of sensible K-->T
> >   scenarios, but I thought long and hard and couldn't find
> >   any. If you can come up with one I'll be happy to know.
> >   So, my analysis led me to conclude that the right approach
> >   is to assume that K==T, that is, the set approach, or at
> >   most than K and T are just different representations of the
> >   same information.
> 
> One such scenario is right there in the GoF book, the word-
> processing application that uses one flyweight object for each
> glyph in the document. I have another case in an project I am
> working on: in a 3D application, I have heavyweight 3D mesh
> objects that might be shared among several actors. The key of a
> 3D mesh is just its filename. I don't want to load 
> an entire mesh into memory just to find out that I have it 
> already. Yes, I could delay the actual loading of the mesh until
> the first time it is actually used, but that would be impractical
> for at least two reasons: 
> 1) any error encountered while loading the mesh would occur in the 
> wrong place and couldn't be handled properly, 2) the place where the 
> mesh is used is inside a tight rendering loop with strict real-time 
> requirements which can't be blocked by costly I/O operations.

OK, I'd classify these two examples as scenarios where K and
T contain esentially the same info but the translation
function f() is computationally expensive. This is a valid
context, just not the one I deem the most common. Maybe the
particular case K!=T could be solved by a different class
keyed_flyweight used like this (the example is similar to that
of GoF you referred to):

  struct character
  {
    character(char c):c(c){}
    char c;
  };

  int main()
  {
    // fw_t objects are constructed from chars but are convertible
    // to character.
    typedef keyed_flyweight<char,character> fw_t;

    // creates an internal character('a')
    fw_t x1('a');

    // same shared value as x1, zero temporary character's
    fw_t x2('a');

    // creates an internal character('b')
    fw_t x3('b');
  }

Is this approach more convincing to you? It turns out it can be
implemented with exactly the same machinery as flyweight (i.e.
holders, factories, locking and tracking policies), so it could
be provided as a companion to classic flyweight<> if there is
interest in it. The attached code shows the idea is viable, the
prototype keyed_flyweight implemented there has all their
aspects (holder, factory, etc.) fixed for simplicity, and lacks
some boilerplate features, but it proves its point. The idea
is that the factory keeps elements of type similar to

  entry = pair<K,T*>

So, only when a new entry is created need we equip it with a
new T, hence completely avoding T temporaries. This incurs a cost
in the form of additional storage and a slightly more expensive
creation process (when no duplicates are found), so we shouldn't
take flyweight<T> as shorthand for keyed_flyweight<T,T>,
both classes serve different scenarios and ought to be
provided separately.

Well, if you think this line of research is interesting I can
pursue it.

> >   3. That said, there is a natural evolution for the library that
> >   would eliminate T construction under some circumstances:
> >   C++0x containers will provide the emplace() member function 
> >   allowing for in-place construction of an inserted elements 
> >   given the ctor arguments, so eliminating the need to construct a
> >   temporary to pass to insert() and related memfuns. When this is
> >   available, the flyweight lib will take advantage of it, so that
> > 
> >     fw s2("foo");
> > 
> >   will create no temporary std::strings.
> 
> Actually it will always create one temporary. If the string is not 
> already present in the factory, the temporary is then moved into 
> the factory and so it is not created in vain. However, in the most 
> common case, the string is already present in the factor and the 
> temporary needs to be discarded.

Yes, you're right, one temporary is unavoidable. Sorry for
my mistake.

[...]
> > I decided to keep "factory" because this component is obviously
> > related to the element of the same name in GoF and oher 
descriptions
> > of the pattern. Incidentally, when point 3 above gets implemented
> > the factory will act more like a factory in the sense you describe.
> > That said, I'll be happy to use whatever other terminology 
reviewers
> > agree upon.
> 
> I would keep the "factory" term if you are considering the 
> find/insert approach as an alternative to the current
> insert-only approach. With that approach case, find() would
> be given a key, rather than an object. 
> If the object is not found, insert() would have to create an 
> object out of the information stored in the key and that
> would actually be what factories are expected to do.

Maybe keyed_flyweight is a better approch than find/insert,
despite the increase in storage consumption: as they're
designed, STL containers make it difficult to look up an
entry with a type other than the entry itself (although
Boost.MultiIndex has extensions to that effect.) I have to
think this over more thoroughly, but seems like find/insert
should be best exploited for read/write mutexes, while the
K!=T issue is best handled by keyed_flyweight.

Well, thank you for giving me plenty of food for thought :)

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

#include <boost/flyweight.hpp>
#include <iostream>

template<typename Key,typename Value>
struct key_value_pair
{
  key_value_pair(const Key& k_):k(k_),v(0){}
  ~key_value_pair(){delete v;}

  Key            k;
  mutable Value* v;
};

template<typename Key,typename Value,typename Entry>
struct adapted_entry:Entry
{
  adapted_entry(const key_value_pair<Key,Value>& x):Entry(x){}

  operator const Key&()const
  {
    return static_cast<const key_value_pair<Key,Value>&>(*this).k;
  }
};

template<typename Key,typename Value>
class keyed_flyweight_core;

template<typename Key,typename Value>
struct keyed_flyweight_core_tracking_helper
{
private:
  typedef keyed_flyweight_core<Key, Value> core;
  typedef typename core::handle_type  handle_type;
  typedef typename core::entry_type   entry_type;

public:
  static const entry_type& entry(const handle_type& h)
  {
    return core::factory().entry(h);
  }

  template<typename Checker>
  static void erase(const handle_type& h,Checker check)
  {
    typedef typename core::lock_type lock_type;
    lock_type lock(core::mutex());
    if(check(h))core::factory().erase(h);
  }
};

template<typename Key,typename Value>
class keyed_flyweight_core
{
public:
  typedef boost::flyweights::refcounted        tracking_policy;
  typedef key_value_pair<Key,Value>            key_value_pair_type;
  typedef typename boost::mpl::apply1<
    typename tracking_policy::entry_type,
    key_value_pair_type
  >::type                                      base_entry_type;
  typedef adapted_entry<
    Key,Value,base_entry_type
  >                                            entry_type;
  typedef boost::flyweights::hashed_factory<>  factory_specifier;
  typedef typename boost::mpl::apply2<
    factory_specifier,
    entry_type,
    Key
  >::type                                      base_factory_type;
  typedef typename boost::mpl::apply2<
    typename tracking_policy::handle_type,
    typename base_factory_type::handle_type,
    keyed_flyweight_core_tracking_helper<
      Key,Value
    >
  >::type                                      handle_type;  
  typedef boost::flyweights::detail::handle_factory_adaptor<
    base_factory_type,
    handle_type,entry_type
  >                                            factory_type;
  typedef boost::flyweights::simple_locking    locking_policy;
  typedef typename locking_policy::mutex_type  mutex_type;
  typedef typename locking_policy::lock_type   lock_type;

  static bool init(){return &(factory())!=0;}

  static handle_type insert(const Key& x)
  {
    lock_type lock(mutex());
    handle_type h=factory().insert(entry_type(x));
    if(!static_cast<const key_value_pair_type&>(factory().entry(h)).v){
      static_cast<const key_value_pair_type&>(factory().entry(h)).v=
        new Value(x);
    }
    return h;
  }

  static const Value& value(const handle_type& h)
  {
    return *(static_cast<const key_value_pair_type&>(factory().entry(h)).v);
  }

  static factory_type& factory()
  {
    (void)static_force_holder_get;
    return holder_type::get().factory;
  }

  static mutex_type& mutex()
  {
    (void)static_force_holder_get;
    return holder_type::get().mutex;
  }

private:
  struct                                   holder_arg
  {
    factory_type factory;
    mutex_type   mutex;
  };
  typedef boost::flyweights::static_holder holder_specifier;
  typedef typename boost::mpl::apply1<
    holder_specifier,
    holder_arg
  >::type                                  holder_type;

  static bool static_force_holder_get;
};

template<typename Key,typename Value>
bool keyed_flyweight_core<Key,Value>::static_force_holder_get=
  &(keyed_flyweight_core<Key,Value>::holder_type::get())!=0;

template<typename Key,typename T>
class keyed_flyweight
{
private:
  typedef keyed_flyweight_core<
    Key,T
  >                                            core;
  typedef typename core::handle_type           handle_type;

public:
  typedef T                                    value_type;

  keyed_flyweight():h(core::insert(Key())){}
  keyed_flyweight(const Key& k):h(core::insert(k)){}
  keyed_flyweight(const keyed_flyweight& x):h(x.h){}

  keyed_flyweight& operator=(const Key& k){return operator=(flyweight(k));}

  const T& get()const{return core::value(h);}
  operator const T&()const{return get();}

  void swap(keyed_flyweight& x){std::swap(h,x.h);}

private:
  handle_type h;
};

struct character
{
  character(char c):c(c){}
  char c;
};

int main()
{
  typedef keyed_flyweight<char,character> fw_t;
  fw_t x1('a');
  fw_t x2('a');
  fw_t x3('b');
  std::cout<<x1.get().c<<", "<<&x1.get()<<"\n";
  std::cout<<x2.get().c<<", "<<&x2.get()<<"\n";
  std::cout<<x3.get().c<<", "<<&x3.get()<<"\n";
}

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost