hi all,

The formal review of Flyweight library, proposed by Joaquín M. López Muñoz, begins today (sorry for the late announcement):

<snip>

* What is your evaluation of the design?

the flyweight class works quite similar to a class, that i am using in one of my c++ projects. from my point of view, the library is designed very well, there is only one issue, that i would like to see handled differently. the flyweight factory is a shared container, that can be configured to use one of the locking policies 'no_locking' and 'simple_locking'. simple_locking would guard the constructor/destructor by a mutually exclusive lock. while this is certainly correct, it is not actually necessary. the factory container needs only be locked exclusively by one thread, when the container is manipulated. instead of this 'simple_locking' policy, i would propose to guard the factory container by a reader-writer lock. if one object is used more than once, the ctors/dtors only need to acquire a reader lock for the container, only if new objects are inserted, a writer lock is required. this policy would make the library more scalable for multi-threaded applications ... i am not sure about the 'boost way' of implementing this, but afair a reader-writer lock was about to be added to boost.thread. this library would be the perfect use case for it ...

* What is your evaluation of the implementation?

i had only a brief look at the implementation ... looked fine for me ...

* What is your evaluation of the documentation?

looked good to me ...

* What is your evaluation of the potential usefulness of the library?

the library should be quite useful ... hopefully reduce the memory footprint of some applications ...

* Did you try to use the library? With what compiler? Did you have any problems?

no

* How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?

i was reading about the concept and compared it with my implementation ...

* Are you knowledgeable about the problem domain?

i have my own implementation of the same concept ...

And finally, every review should answer this question:

* Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion.

yes cheers, tim -- tim@klingt.org http://tim.klingt.org The price an artist pays for doing what he wants is that he has to do it. William S. Burroughs

so that we can follow this protocol:

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

that is similar to my implementation ...

An approach to convering both simple and read/write locks would be to extend the concepts "Locking Policy" (http://tinyurl.com/ypvy4l ) and "Factory" (http://tinyurl.com/2er6dl ) to "ReadWrite Locking Policy" and "Lookup Factory", respectively, and only when the components specified both conform to the extension concepts would we internally follow the readwrite protocol instead of the simple one. I think I can work this out, but I'd prefer to put this in the "Future work" section rather than trying to implement it immediately, so as to gain some more feedback and wait for read/write locks to be brought back into Boost (they were removed due to an implementation bug, see http://tinyurl.com/2clcr9 ).

that would be fine with me ... it would definitely make sense to wait for the reader-writer locks in boost.thread ...

...

...

* Did you try to use the library? With what compiler? Did you have any problems?

no

Given that you are already using a lib of your own around the same concept, I think it would be very interesting if you could try replacing that with my lib and report whether the experience is smooth enough --in particular, if you're using read/write locks you can measure whether thery make an actual diference wrt to candidate Boost.Flyweight simple locks.

since my class shares the same concept add the same interface, they can probably changed by changing a typedef ... i am not sure, whether at the moment rw-locks make a big performance difference for my application, mainly because most of the objects are allocated from a single thread ... that might change in the future, though ... cheers, tim -- tim@klingt.org http://tim.klingt.org Who need fossil fuel when the sun ain't goin' nowhere Amiri Baraka

Hello Alberto, Alberto Ganesh Barbati ha escrito:

Joaquín Mª López Muñoz ha scritto:

[...]

...

This idea is very interesting and I will definitely pursue it. A complication of using read/write locks is that these do not fit well in the current concept framework: a factory f is expected to have the following interface:

f.insert(x); f.erase(h);

where both expressions are *externally* guarded by a regular lock. The problem is that f.insert(x) does lookup and optional insertion in one fell swoop, and thus does not provide the necessary granularity to use a read/write lock. Instead, we'd need something like:

f.find(x); f.insert(x);

That would make the interface inefficient, because the search would be performed twice. I would go with:

f.find(x); f.insert(h, x);

where h is the value returned by f.find(x). This would exploit the two-parameter insert() provided by std::set (and even tr1::unordered_set, for what matters).

The interface would have to be a little more complicated than that, as find() does not return a useful handle (iterator) when the search was unsuccesful, it merely returns end(). We'd need to use something like lower_bound() for ordered associative containers. For unordered associative containers the situation would be even worse: although these containers formally accept a hint parameter, actually this is useless in containers with unique keys when it is known that no equivalent element exists (which is the case here). Furthermore, the only memfun usable to get a hint operator would be equal_range (no lower_bound in unordered associative containers), and this introduces a irregularity with the ordered case. All in all, I think using a hint is a lot of hassle for the small potential benefit it could bring. However, the only way to know for sure, of course, is measuring it.

...

so that we can follow this protocol:

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

which would become (using promote() instead of the very risky unlock/lock):

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

[promote() would be unlock_upgradable_and_lock() under the terminology of the current C++0x proposal, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2094.html , if I understand it right.] Why is unlock/lock risky? If I'm getting it right (although I admit to be no expert on threading issues), unlock_upgradable_and_lock() is equivalent to unlocking and then exclusively locking with some additional guarantees, namely that the thread will be the first to obtain exclusive access. The problem is that this can fail (if two threads request the privilege at the same time), hence unlock_upgradable_and_lock() may throw. Given that we don't require the kind of guarantees provided by unlock_upgradable_and_lock(), and since dealing with a throwing operation is always a mess, I'd rather go with simple unlock/lock. But then again I'm no threading expert, if there's some problem in my analysis I'd be glad to be told.

...

An approach to convering both simple and read/write locks would be to extend the concepts "Locking Policy" (http://tinyurl.com/ypvy4l ) and "Factory" (http://tinyurl.com/2er6dl ) to "ReadWrite Locking Policy" and "Lookup Factory", respectively, and only when the components specified both conform to the extension concepts would we internally follow the readwrite protocol instead of the simple one. I think I can work this out, but I'd prefer to put this in the "Future work" section rather than trying to implement it immediately, so as to gain some more feedback and wait for read/write locks to be brought back into Boost (they were removed due to an implementation bug, see http://tinyurl.com/2clcr9 ).

I believe you should consider using the find/insert approach immediately and not wait for readwrite locks. If you do so, you may upgrade to readwrite locks later once they become available, while sticking to the insert-only approach will make the upgrade more difficult because a change in the concept framework might break existing code (for example think about uses of assoc_container_factory with a user-provided container).

One way to implement this could be:

typename LockingPolicy::lock_type l(mutex); if(h=find(x))return h; else{ LockingPolicy::promote(l); h=insert(h, x); }

requiring the locking policy functions to provide *at least* read lock after the lock construction and to ensure write lock after a call to promote(). For regular mutexes promote() can simply be a no-op, of course. If the users had their own non-boost (and hopefully not buggy) read write mutex classes they could plug them in easily.

I don't think making the upgrade later on would be so difficult: the plan is not to *redefine* the concepts, but rather to provide extensions of them, so that older code will conform to the primitive concepts and new code can benefit of read/write stuff merely by appropriate tagging (for instance, marking a factory as a lookupfactory rather than a plain old factory, etc.) Your approach (making all mutexes look like read/write with promote a no-op where appropriate) is IMHO a little more inelegant than just having a hierarchy of concepts (just like, for instance, C++ does with iterator categories: non-random access iterators are not required to provide, say, a no-op operator[] just for conformity reasons).

Just my two eurocent,

Ganesh

Thank you for your elaborate comments. I'd be glad if you could submit a full review! Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Alberto Ganesh Barbati <AlbertoBarbati <at> libero.it> writes:

Joaquín Mª López Muñoz ha scritto:

[...]

...

All in all, I think using a hint is a lot of hassle for the small potential benefit it could bring. However, the only way to know for sure, of course, is measuring it.

I agree and the benefit could greatly depend on the actual container used. [...]

...

Why is unlock/lock risky? If I'm getting it right (although I admit to be no expert on threading issues), unlock_upgradable_and_lock() is equivalent to unlocking and then exclusively locking with some additional guarantees, namely that the thread will be the first to obtain exclusive access. The problem is that this can fail (if two threads request the privilege at the same time), hence unlock_upgradable_and_lock() may throw.

The fact is that if another thread gets write/exclusive access before "our" thread, the hint may become invalid and can no longer be used reliably.

(Assuming we're using a hint, which is debatable as discussed above.) Umm... I've been rereading N2094 and it proposes the following types of mutexes: * Exclusive: plain old mutexes * Shared: read/write * Convertible shared: read/write with non-blocking write->read and non-blocking tentative read->write * Upgradable: Convertible shared with possibly a unique designated thread holding a privilege to promote read->write atomically. As for upgradable mutexes, my understanding is that this makes sense only in scenarios where threads have two roles: "read only" and "read and maybe write", where the latter is much less likely than the former, thus making it worthwile for the latter to try to get upgradable status. In the case of my flyweight lib all threads behave the same, so I guess upgradable mutexes are no use here. If we devise our insertion algorithm to use convertible shared mutexes, it'd look like this (without unlocking or resorting to using RAII locks for brevity of exposition) mutex.lock_sharable(); if(h=find(x))return h; else{ if(mutex.try_unlock_sharable_and_lock()){ h=insert(h,x); } else{ // unlock and lock the non-atomic way mutex.unlock_sharable(); mutex.lock() // exclusive // using the hint does no harm, as it might // remain valid h.insert(h,x); } } Since the non-atomic branch finally carries out the same work as the atomic one, the following algorithm is equivalent AFAICS, and does not use convertibility: mutex.lock_sharable(); if(h=find(x))return h; else{ mutex.unlock_sharable(); mutex.lock() // exclusive h.insert(h,x); } My analysis might be wrong, but if it's not it seems to me mutex promotion is unneeded here. [...]

After reading your answer I realized that probably the best way to benefit from any complex locking strategy without compromising the general case is to leave both the decision and the actual algorithm to factory itself. Therefore I make a different proposal, much simpler, something in line with:

static handle_type insert(const Value& x) { lock_type lock(mutex()); return handle_type(factory().insert(entry_type(x), lock)); }

by passing the lock to the insert() function, the factory has the opportunity to ignore it, favoring a simple locking strategy, or to use it to perform some more complex strategy. By overloading insert() the factory could even provide different strategies according to the type of the lock.

Of course that would create problems with "simple" factories like hashed_factory_class and set_factory that don't expect the extra lock argument. This could solved by giving to class handle_factory_adaptor the responsibility to drop the lock argument unless explicitly requested by the user. How to let the user request the extra lock parameter is yet to be determined, one way might be to declare a new tag class advanced_factory_marker that derives from factory_marker.

Does it make sense?

It makes sense, but it seems to be against the orthogonality of the current design: the intention is that policies remain as little dependent from each other as possible, and your proposal works the other way around. If we accept that mutexes and factories can form concept hierarchies, then maybe we could simply accept * Mutexes, shared mutexes * Factories, factories with lookup, factories with lookup and hint and let the flyweight core deal with the combinations. I'll have to explore this when time permits. Sorry for the long post :) Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Hello John, thank you for submitting your review, John Reid ha escrito:

...

* What is your evaluation of the design? Very good. It seems everything is configurable if needed and works as expected out of the box.

Perhaps intermodule_holder should be the default holder specifier as there is an unpleasant potential gotcha otherwise? The docs do not state why not as far as I can see. An efficiency issue perhaps?

intermodule_holder performs a way more expensive static initialization process than static_holder (basically, it creates a shared memory area and interprocess mutex for communication between the different modules of the program. It only affects static initialization, though, the rest of operations (flyweight creation and passing around) are exactly the same as with static_holder. Another reason for not including this is that Boost.Interprocess (on which intermodule_holder depends) is not universally supported, so making intermodule_holder the default would complicate things for some compilers.

...

* What is your evaluation of the documentation? Extremely clearly written and well thought out. I would like to see more explanation of the examples. I like the inclusion of the test code.

Any particular example you wished you had more info about? I can try to improve that if you point me to the improvable parts. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

John Reid ha escrito:

Hello Joaquin,

Joaquín Mª López Muñoz wrote:

...

intermodule_holder performs a way more expensive static initialization process than static_holder (basically, it creates a shared memory area and interprocess mutex for communication between the different modules of the program. It only affects static initialization, though, the rest of operations (flyweight creation and passing around) are exactly the same as with static_holder. Another reason for not including this is that Boost.Interprocess (on which intermodule_holder depends) is not universally supported, so making intermodule_holder the default would complicate things for some compilers. Perhaps this is worth documenting.

I'll add a note on this on the docs.

...

...

...

* What is your evaluation of the documentation? Extremely clearly written and well thought out. I would like to see more explanation of the examples. I like the inclusion of the test code.

Any particular example you wished you had more info about? I can try to improve that if you point me to the improvable parts. All of them really, I was hoping to see some of the more important lines of code briefly explained in the documentation.

OK, I can try to revise this. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Hello Marcus, thank you for participating in the review. Marcus Lindblom ha escrito:

However, I'd like to nit-pick some naming:

* The namespace should be boost::flyweight, without the s, since that's what the lib & design pattern is called.

There is a reason for that spurious 's', namely that some compilers (VC6.0 --though this is probably of little relevance in 2008-- and some versions of GCC) have problems with using declarations where the namespace and class names are identical. This issue was raised originally in the context of Boost.Tuple, and indeed the namespace for that lib is boost::tuples: look up the section "For those who are really interested in namespaces"at http://tinyurl.com/ywb9n7 for more info.

* The factory not only creates objects, it also stores them. When I see 'Factory' I think creation only, not storage. How about naming it the 'store' instead, since it seems to be the primary function?

The main reason why the name "Factory" was picked is because most descriptions of the flyweight design pattern use this same terminology: http://tinyurl.com/ys5k3q . If there's an agreement that the name should be replaced by something more appropriate, I have no objection to do so, of course.

Does the factory even create objects? It doesn't seem like that. It just stores copies of them in Entrys?

Yep, factories stores copies of externally constructed values. In "classical" renditions of the pattern, the factory accepts some kind of key to get an associated flyweight object: here, the key is simply the value itself. It is likely that future extensions of the concept will allow for inplace construction of the values using perfect forwarding capabilities and variadic templates of C++0x. Along this line, look for "emplace" in the latest C++0x draft: http://open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf [...]

...

* What is your evaluation of the implementation?

Not looked at thoroughly.

However, there is a dependency on boost::hash<>. Could this be changed into conforming to a concept that just allows the value to be converted to size_t?

I'm not getting your suggestion. Do you mean that flyweight<T> should require that T be convertible to size_t? I don't know how this is better than relying on boost::hash<>. On the other hand, boost::hash<> is merely the default for providing the hashing of T. If you have an alternative you can use it like this: struct my_hash { std::size_t operator()(const T& x)const{...} }; typedef flyweight<T,hashed_factory<my_hash> > fw_t;

...

* What is your evaluation of the documentation?

Great!

However, on the reference page, the first header ("boost/flyweight.hpp") doesn't link to anything?

Do you mean the second bullet in the "Contents" section? If so, it links to somewhere below down the same page, maybe that's why it seemed to you to point nowhere. Or are you referring to some other link?

Also, the flyweight.hpp page misses to mention the tag argument in the first list of parametrization (above the code-block).

Oh, you're right. I'll fix that. [...]

...

* Do you think the library should be accepted as a Boost library?

Yup! But some names ought to be changed to avoid confusion.

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

Marcus Lindblom ha escrito:

Joaquín Mª López Muñoz wrote:

...

Hello Marcus, thank you for participating in the review.

Marcus Lindblom ha escrito:

[...]

...

...

However, on the reference page, the first header ("boost/flyweight.hpp") doesn't link to anything?

Do you mean the second bullet in the "Contents" section? If so, it links to somewhere below down the same page, maybe that's why it seemed to you to point nowhere. Or are you referring to some other link?

That one, and the first link under "header summary".

I retested, and it works in IE, but not in FireFox.

Oh, I looked again and it's indeed an HTML bug, I had the following destination anchor <a name="#flyweight_synopsis"> instead of <a name="flyweight_synopsis"> Seems like IE handled it right, but it's a bug nonetheless. I've corrected it in my local copy of the material. Thanks for spotting this! Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Hello Matías, excuse my late answering, I've been Internet deprived for the best part of the weekend. ----- Mensaje original ----- De: Matias Capeletto <matias.capeletto@gmail.com> Fecha: Viernes, Enero 25, 2008 6:45 pm Asunto: Re: [boost] [review] Review of Flyweight library begins today January 7 Para: boost@lists.boost.org

* What is your evaluation of the design?

Great. I specially like the simplicity of the out of the box version, that will surely cover most of the uses cases.

I like the current design of configuration parameters. With respect to Equality semantics, I have no strong opinion about this particular item. I think that the gain in using the &-version is too good to be discarded, but I do not like the fact of that small possibility of a user being surprised by it. A warning box can be put in the docs or this gain can be activated by the user overloading the operator== in a per class basis as Joaquin proposed in other thread (A section will be needed in the docs about this and maybe a macro to make it easy to activate it).

Another option would be to make the &-version the default and inform the user about the possibility to override operator== so as to implement the non-&-version... I'm very undecided about this. [...]

* What is your evaluation of the implementation?

I gave it a quick look. The code is very clean and is already bundle with the machinery to pass over compiler quirks. I think that is great how this library rest over the shoulders of other libraries of boost. It has a very nice test suit too.

Thank you. If you allow me a diversion , I think synergies between Boost libs are one of the best aspects of this project, and this is why (IMHO) we should resist the temptation to split the package in smaller units, even if some users request that from time to time: benefits in the long term compensate for the size of the distribution and nowadays several hundred MB are not that much of a problem, anyway.

* What is your evaluation of the documentation?

Good. It will be cool to have more info about when to use a set instead of a hashed container for the factory.

{{ Small typo in: tutorial/configuration.html Tracking policies > no_tracking > There is some _in some_ reduction in memory usage due to the absence of reference counters. }}

Thanks for spotting the typo! I'll fix it right away. Thank you for your review, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo