[boost] [flyweight] Review summary

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 -