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

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2008-01-30 14:54:15

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