Boost logo

Boost :

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-02-17 18:36:21


Hi to all,

I've just written a summary of the flyweight review that tries to point
out the main requests, questions and comments from reviewers and
Joaquin's replies to those. If someone thinks I've missed some important
point, please let me know.

Joaquín is already correcting the pointed issues and thinking about
alternatives on the keyed_flyweight issue. I hope we can definitely
solve them satisfactorily in a short period of time. Here we go:

--------------------------
      Beginning of summary
--------------------------

-------------------------
*Tim Blechmann’s review:*
-------------------------

Design: Good. Suggests using read-write locks to improve concurrency
since most operations will be searches.

Implementation: fine

Documentation: good

Usefulness: quite useful to reduce memory footprint.

Try to use the library: no

Effort: Read documentation and compare it with his own implementation

Knowledgeable about the problem domain: yes

Accept the library: yes

This reviews starts a thread about the correct read-write lock
implementation for flyweight:

1) Joaquín points out that the library is based on insert(x) so a good
candidate can be:

   readwrite_lock l(mutex);
   l.read_lock();
   if(h=find(x))return h;
   else{
     l.unlock();
     l.write_lock();
     h=insert(x);
   }

Unfortunately read-write locks were removed due to a bug so this issue
will be put under Future Work section for now.

2) Alberto Ganesh Barbati: suggests using hinted insert to improve
performance in cases where find(x) fails and try to get a O(1)
insertion. He also suggests using promotion or/and upgradable mutexes.

3) Joaquín thinks promotion/upgradable mutexes are not necessary.
Read-write locks/upgradability/hints will need more thinking to maintain
current policy orthogonality and the issue needs time. As mentioned, the
issue will be revised when rw locks are available in Boost.

Review manager note: I think that using “hint” needs atomic
convertibility, because the “hint” can be invalidated by an erasure
between unlock_sharable() and lock_sharable() and hint insertion does
not guard against invalidated hints, but only against non invalidated
but non-optimal hints.

-------------------------
*John Reid’s review:*
-------------------------

Design: Very good. Suggests intermodule_holder as the default holder.

Implementation: Ok.

Documentation: Clearly written and well thought out. He would like to
see more examples and the inclusion of test code.

Usefulness: High

Used the library: No

Effort: A quick read through the tutorial and the examples

Knowledgeable about the problem domain: Not a design patterns expert but
using C++ for 15 years.

Accept the library: yes

1) Joaquín replies that intermodule_holder performs a way more expensive
static initialization process than static_holder (needs shared memory).
Another reason for not including this is that Boost.Interprocess (on
which intermodule_holder depends) is not universally supported.

Agrees to improve examples.

2) John suggests documenting intermodule_holder limitations

3) Joaquín agrees documenting these limitations

-------------------------
*Marcus Lindblom’s review*
-------------------------

Design: Very nice. Comments: namespace should be boost::flyweight.
Factory should be called store

Implementation: Not looked at thoroughly.

Documentation: Great! Comments: the reference page, the first header
("boost/flyweight.hpp") doesn't link to anything? flyweight.hpp page
misses to mention the tag argument in the first list of parametrization.

Usefulness: High.

Used the library: Nope.

Effort: Quick reading. (1h)

Knowledgeable about the problem domain: Yes

Accept the library: Yes

1) Joaquín says that namespace issues are related to compiler bugs and
the namespace conforms Boost rules explained at "For those who are
really interested in namespaces" at http://tinyurl.com/ywb9n7

Factory name was chosen because most descriptions of the flyweight
design pattern use this same terminology: http://tinyurl.com/ys5k3q

Agrees to fix documentation problems with Firefox.

-------------------------
*Matias Capeletto’s review*
-------------------------

Design: Great.

Implementation: Quick look.

Documentation: Good. Typo spotted.

Usefulness: High

Used the library: gcc 4.1.3, under Linux

Effort: Followed the library progress from the beginning

Knowledgeable about the problem domain: Yes

Accept the library: Yes

1) Joaquín: Typo fixed

David Sankel’s review

Design: Very well designed. Suggests a configuration option for equality
segmantics.

Implementation: He hasn't looked at much code, so I have no opinion here

Documentation: Good

Usefulness: Good

Used the library: No

Effort: An in depth study of the documentation

Knowledgeable about the problem domain: Not until this review

Accept the library: Yes

1) Joaquín says it’s trivial to override the default equality on a per
case basis:

   typedef flyweight<whatever,...> fw_t;

   inline bool operator==(const fw_t& x,const fw_t& y)
   {
     return &x.get()==&y.get();
   }

-------------------------
*Vicente Botet’s review*
-------------------------

Design: Good.

Issues:

* The tests performed on example5 should be extended with a
intermodule_holder specifier.

Joaquín’s answer: there is no need for that since it’s only performed in
the initialization.

* On platforms on which static variables are unique inter DLL the
intermodule_holder specifier type can be a static_holder_class.

Joaquín’s answer: Ok.

* Holder specifier renaming. Maybe static_holder by module_holder, and
intermodule_holder by process_holder?

Joaquín’s answer: Agrees to revise names but he’s not found good
alternatives.

* Add an exclusive core specifier

Joaquín’s answer: Added to Future Work section.

Implementation: Quite good

* Minor correction
The documentation states that the ..._specifier must be a ..._marker,
but this is not needed for the ..._class

Joaquín’s anwswer: This ability used to be documented at the reference,
but I've just checked and it is no longer there, I'll restore that bit.

* refcounted_value is a class that could be public. Why it is declared
in the namespace detail.

Joaquín’s answer: It is an implementation detail, the user won't ever be
exposed to it.

* could you explain why detail::recursive_lightweight_mutex is needed
and boost::detail::lightweight_mutex is not used directly?

Joaquín’s answer: Recursive mutexes are needed when constructing
composite complexes with flyweight<>.

Documentation: Good. Issues:

* Some more elaborated examples suggested.

Joaquín’s answer: I'll try to extend the examples section.

* intermodule_holder specifier: A reference to a document explaining
the problem with platforms not ensuring the unicity of static variables
when DLL are used will be welcome.

Joaquín’s answer: I'm no expert here, but I'd say that platforms without
static var unicity across dynamic modules are the majority rather than
the exception.

* Reference section:
The reference section was much more hard to follow. I think that the
interactions between the different classes are very hard to describe
using the current style.

Joaquín’s answer: It tries to keep the level of formality you find at
the C++ standard. The idea is you go to the reference for exact,
authoritative information.

* An implementation section will help to understand how all this works,
describing the interactions between the core and the policies.

Joaquín’s answer: I'd much prefer to concentrate on improving the part
on extending the library without disclosing too much about how things
are assembled internally.

* Add performance section

Joaquín’s answer: Ok.

* Rational: Adding of the map versus set problem explanation.???

Usefulness: Good

Used the library: No.

Effort: In-depth reading of the docs and implementation

Knowledgeable about the problem domain: Yes

Accept the library: Yes

-------------------------
*Neil Hunt’s review*
-------------------------

Design: Good

Implementation: Good

Documentation: He didn't read it all closely.

* Some performance indicators or at least discussion of the tradeoff of
extra hashing vs reduced dynamic allocations would be useful.

Joaquín’s answer: ok

Usefulness: Useful

Used the library: No

Effort: A moderate investigation.

Knowledgeable about the problem domain: Yes

Accept the library: Yes

-------------------------
*Alberto Ganesh Barbati’s review*
-------------------------

Design: Very good. Issues:

* It doesn't fully grasp the essence of the flyweight pattern because of
a major flaw. The flaw is the fact that an object needs to be created in
order to check whether an equivalent flyweight exists or not.

Implementation: Well done. Issues:

* I strongly disagree with the choice of the term "factory" for a
component that actually only acts as a storage.

Documentation: Very well written. Issues:

* The policies are indeed properly described, but the bare description
is not very helpful in showing how to write a new policy

Usefulness: Useful if the flaw I described before could be addressed

Used the library: gcc 3.4.5 (mingw)

Effort: A couple of hours.

Knowledgeable about the problem domain: Yes.

Accept the library: Reluctantly, the answer is no. He encourages the
maintainer to consider addressing the issues I raised
here, in which case I am ready to change my opinion.

1) Joaquín’s answer:

* Instantiating a flyweight<T> will always create a temporary T (and
hopefully just one when we get rvalue refs and variadic templates). The
purpose of the library is *not* to avoid constructing expensive objects,
it is to reduce memory consumption through object sharing. Collateral
benefits include increased performance in object passing around.
* GoF introduces a key type K into the pattern that is used to retrieve
the actual values of T. So, we have a one-to-one relation KT, i.e.
there exists a stateless function f of the form “T f(const K&)”. My
analysis led me to conclude that the right approach is to assume that K==T.
* Joaquín will investigate the potencial of the LookupFactory (factories
that, additionally to the insert memfun, provide a find memfun) pattern,
described at http://lists.boost.org/Archives/boost/2008/01/132798.php
* 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.
* I’ll refine the reference section to make it easier write custom policies.

2) Alberto’s answer: 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.

3) Joaquín proposes the keyed_flyweight:

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');
}

4) Alberto proposes unifying keyed and non-keyd with just one flyweight
class template:

* we have two types: key_type for keys and value_type for values. The
two types can be coincident (non-keyed proposal)

* the constructor of flyweight semantically takes keys, not values

* keys (not values) are fed as-is to the factory insert() method: it's
up to the factory to determine whether the key is already present and if
it's not present to construct the corresponding value.

* the insert() method returns a handle

* the factory provides a way to extract values from handles

* The rest of the design would more or less stays exactly the same.

5) Joaquín’s answer to Alberto’s unified flyweight: I'd rather factories
remained dumber so that all this intelligence is implemented in the core
because:

* STL associative containers are either set-like
* (key_type=value_type) or map-like (T != value_type != key_type,
because T == mapped_type).

* The container would have to deal with a more general notion of key
extraction. Boost.MultiIndex can do that, but I don't want to tie
flyweight to that lib.

Review manager note: The discussion went a bit further but the essence
is that Joaquín has proposed alternatives and is ready to further
discuss the issue because flyweight won’t be ready until Boost 1.36. I
encourage Joaquín, Alberto and other contributors to discuss the issue
in the future again.

-------------------------
*John Torjo’s review*
-------------------------

Design: Ok.

Implementation: Ok.

http://svn.boost.org/svn/boost/sandbox/flyweight/libs/flyweight/doc/tutorial/technical.html

I think there could be a simpler way to do this:

http://www.entropygames.net/globals.htm

Documentation: Very nice

Usefulness: Very useful.

Used the library: No.

Effort: 1.5h

Knowledgeable about the problem domain: Yes

Accept the library: Yes.

-------------------------
*Markus Werle's review*
-------------------------

Design: Not reviewed

Implementation: Not reviewed

Documentation: Good

Usefulness: Yes

Used the library: No

Effort: Moderate

Knowledgeable about the problem domain: No

Accept the library: Yes

-------------------------
*Kevin Sopp’s review*
-------------------------

Design: Good. A way to get usage statistics about the
flyweights would be nice (Joaquín agrees)

Implementation: Good

Documentation: Good

Usefulness: Good

Used the library: Yes

Effort: Moderate

Knowledgeable about the problem domain: Yes

Accept the library: Yes

Other accepted suggestions coming from non-review posts:

Add assertions to catch static variables destruction ordering problems
with flyweight. The refcounted tracking policiy can detect such illegal
situations (an entry is destroyed with a refcount!=0).

--------------------------
      End of summary
--------------------------

Ion Gaztañaga
- Review Manager -


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk