Re: [boost] [Boost-announce] [review] Review of Flyweight library begins today January 21

From: Alberto Ganesh Barbati (AlbertoBarbati_at_[hidden])
Date: 2008-01-29 18:20:40

Joaquín Mª López Muñoz ha scritto:
> Hello Alberto,
> 
> Alberto Ganesh Barbati ha escrito:
> 
>> 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.

That is indeed correct. I was too hasty in my proposal.

> 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.

>> 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.]

Yes, promote() was the name used in Boost.Thread. The new name is more 
verbose and much clearer.

> 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.

>> 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).

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?

Ganesh