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

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2008-01-28 12:51:42

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