Re: [boost] [flyweight] Review period extended to February 3

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2008-02-03 18:20:27

----- Mensaje original -----
De: Alberto Ganesh Barbati <AlbertoBarbati_at_[hidden]>
Fecha: Domingo, Febrero 3, 2008 12:39 pm
Asunto: Re: [boost] [flyweight] Review period extended to February 3
Para: boost_at_[hidden]

> 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