Re: [boost] Re: New New Callbacks Uploaded

From: Karl Nelson (kenelson_at_[hidden])
Date: 2000-12-04 17:39:36

> --- In boost_at_[hidden], Kevlin Henney <kevlin_at_c...> wrote:
> > In message <90gbnn+104i5_at_e...>, William Kempf <sirwillard_at_my-
> > deja.com> writes
> > >Think about a string that's shared 
> > >across threads.  
> > 
> > No, think of a string that's not shared across threads. As I said, 
> there
> > are many subtleties to programming with threads and objects, and if 
> you
> > are going to share mutable, sequential value types between threads 
> you
> > have just fallen into one of them. Sorry, but that's just the way 
> it is
> > :-(
> 
> Sharing data is a fundamental *need* of MT applications.  You even go 
> so far as to illustrate this with your next argument here.

Data sharing is still possible in the cloned case so I don't see how
this should be a deciding factor.  When data is shared it must be 
locked, however, in the cases of shared objects this means during the
use of that object it must be locked, thus calling the callback means
locking.  This is a very slow and tedious result.  The alternative
is to use cloning and then only deal with the shared data in the context
of a threaded program....  ie.

  class my_functor
    {
       A* a; // data shared between threads
       void operator ()(void)
         {
             MutexLock m(mutex);
             // deal with access to A
         }
    };
 
 void start_thread(function<void> f); // this is a copy

 main()
   {
     A a;
     function<void> f=my_functor(&a);
     ....
     start_thread(f);
     ...
     f();
   }
  
Now if we had a reference counter here (ie, threads share) then
access to that reference counter is a shared object and thus
the library would need its own locks.  While the above requires no
locks except in the user code.

> > This discussion does not simply apply to the function wrapper, it 
> is a
> > multi-threading design consideration in general. Consider it for any
> > type T that has non-atomic copying and assignment semantics. Using a
> > common classification, we can treat objects as being passive (only
> > execute when called, have no thread of their own) or active (having
> > their own thread). There are different ways of classifying passive
> > objects, but for the sake of argument here is the way that UML
> > classifies operation synchronisation:
> > 
> > sequential: Safe in a single thread only. Needs external locking to 
> be
> > used across threads. This includes value objects, such as strings.
> > 
> > guarded: Monitor-like and can be accessed across multiple threads.
> > Synchronisation is self managed and access is serialised.
> > 
> > concurrent: Multiple thread accesses without explicit locking are
> > possible. This is the case with access to immutable data and for 
> lock-
> > free change operations, eg InterlockedIncrement.
> 
> The shared string I mentioned fits category 1, sequential.  The 
> problem is that external synchronization wasn't applied.  It wasn't 
> applied because of a claim that the function_object wrapper was 
> thread safe internally so the programmer used it to wrap the string 
> figuring the library would take care of threading issues from there.  
> In other words, back to what I originally said, you can't gaurantee 
> thread safety unless the wrapped object is thread safe, which is 
> outside of the ability for the library to do.

When the user copies an object they consider that separate data and
thus it should not require any locking between the two copies.  If
you do like strings, you force the used to place serial access even
when the objects themselves appear as separate and distinct objects.

Consider the simplest case, what does the user expect?

  void foo(int i)
    { i=1; }

  main() {
    int i=2;
    foo(i);
    cout << i << endl;
  }

What did the user expect there?  The expected that the copies of the
object were distinct.  That is that changing the local didn't affect the
global.  

If they wanted the other the would have written...

  void foo(int& i)
    { i=1; }

Thus they can specify they want the same object or an new copy.

What sharing with a reference counter is takes away the first option
unless copy on write is allowed.  This is done with strings because 
the cost of copying a string is high compared to the work of copy on
write.  

The cost of copying a functor is small generally and the cost 
of implementing the locks for thread safety is very high.  Thus
cloning is best. 

> > If T does not deep copy then it must refer to either immutable 
> objects
> > or to objects with self-managed safety for the above examples to be
> > safe. If T refers indirectly to something that does not satisfy 
> these,
> > then the user of T must be responsible for its synchronisation. Deep
> > copying objects that can be deep copied unasks the questions raised 
> by
> > such issues.
> 
> A ref-counted idiom wrapping a thread safe object (i.e. the call to 
> operator() is gauranteed thread safe by the programmer) is just as 
> safe as a cloning idiom wrapping a thread safe object.  If the object 
> is not gauranteed thread safe then deep copying has more points of 
> failure (cloning has both operator() call as well as copy operations, 
> while ref-counting only has one point of failure in operator()).

This is not true.  Ref-counting requires that the object disappear
only after the last user of the object goes away.  This means the 
pointers and the execution stack need to count as accesses.  Thus 
you will need to access the reference counter on every operator(),
and thus you would end up doing this....

   void operator() ()
      {
        mutex.lock();
        rc++;
        mutex.unlock(); // we can't hold the lock through a user callback
                        // or we can deadlock
        call();
        mutex.lock();
        if (!--rc) delete object;
        mutex.unlock();
      }

And we would need to do this whether the user was using this cross thread
or not.

In sigc++ I have studied the various cases of callbacks and threading
extensively.  The conclusion I have had is that ref counting works, it is
just very slow.

> > >So, discussing thread safety as a reason to choose one over the 
> other 
> > >is a red herring, but if you insist going down that path it leads 
> to 
> > >ref-counting not cloning.
> > 
> > Threading came up as a topic for discussion. I merely demonstrated 
> that
> > both threading and the sequential value-based approach lead to the 
> same
> > conclusion: cloning.
> 
> Which I disagree with.  Since ref-counting reduces the points of 
> failure it would be preferred when thread safety is brought into the 
> picture.  However, since neither can be gauranteed thread safe this 
> is a pointless argument to make.  Threading makes no difference, 
> IMHO, on the choice here.

Reference counting adds a common point with must be shared across threads
that is the flags and counter itself.  Since we do not have atomic actions
these flags and counters must be protected and since we are fundamentally
hiding the sharing from the users, they can't be expected to do
it themselves or they will end up with brutal deadlocks.   Threading
makes a big difference in the context of this argument.

 
> > When a design decision can be made for two
> > different reasons this makes a very strong case for it and its
> > stability. If you are still unhappy with the threading case, I 
> suggest
> > we drop it and just focus on the one we can agree on.
> 
> That much sounds like a good idea at this point.

If you drop threading than I once again resubmit that sigc++ is the 
best design because it handles the plethora of cases which hasn't
even been discussed here.  The only reason I dropped the argument is
that it was clear the goal of the current boost discussion is 
for a non-lifetime safe, quick and thread-safe callback system, something
which sigc++ is not.

Consider the cases like someone sets an callback to within the calling
of that same callback and then access a parameter which was stored in
the old version of the callback.  Sigc++ 1.1 handles this case by extending
the life of that data container until the end of all executions in the
stack.  These sorts of problems haven't even been touched here!  You
don't even need multi-thread to get some really nasty data lifetime issues.

You should either make a system for the specific function of fast
and clean threading issues or you will find yourself doing what I did:
write a system, discover a new data dependency case, rewrite system,
repeat for 2 years.  I am on my 7th rewrite of sigc++, where the first
5 went straight from my fingers to the trash because of failures on
one of the more exotic tests.

--Karl