Re: New New Callbacks Uploaded

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-12-04 18:28:51

--- In boost_at_[hidden], Karl Nelson <kenelson_at_e...> wrote:
> > --- 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.

It can't be made thread safe internally for either approach (i.e. 
unless the wrapped object is thread safe the wrapper isn't thread 
safe).  So it's NOT a deciding factor.  Kevlin tried to make it a 
deciding factor and I disagreed with his conclusions, but honestly, 
since neither is thread safe it's a non-factor and should be dropped 
here.

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

Now you're discussing speed efficiency instead of thread safety.  Now 
we're left with a "take your pick Jenny" decision.  Neither factor is 
more important than the other generically, only for specific cases.  
In other words a legitimate case can be made for either idiom based 
on threading considerations.

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

Objects often include shared data via references to external objects 
that renders the above a bad thing to assume.  This was the basis of 
my arguments.
 
> 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.  

Change 'i' to be a shared_ptr<int> and you'll get a better picture of 
what I just said, even though it's a very simplistic and contrived 
example.

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

That is debatable, and several implementors are now going away from 
COW.  Regardless, this is a tangent from the original topic.
 
> 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. 

Copying isn't always small.  In fact, it can be much more expensive 
than the cost of a lock.  This shows that this level of micro-
management of optimizations may not be appropriate.  Not that I 
totally disagree with what you're saying here, I'm only pointing out 
that you've not got a clear case for choosing one idiom over the 
other here.
 
> > 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();
>       }

First, this does not invalidate what I said.  Second, this is 
overkill in your attempt to be thread safe.  The thread calling 
operator() should have a legitimate reference already so that you 
don't need to increment the ref-count here.  This code only protects 
against such cases where a reference or pointer to the callback is 
passed to a thread instead of passing the callback itself, which 
would be the norm for a ref-counted callback.  Do you ever pass a 
pointer to a shared_ptr<> object?  Even though this theoretically 
could occur I think it would be more appropriate to document this as 
undefined behavior instead of over coding like you've done above.  
After all, this is consistent with what you have for shared_ptr today.
 
> And we would need to do this whether the user was using this cross 
thread
> or not.

That's debatable as well.  There's ways around this, such as 
Strategized Locking (POSA 2).
 
> 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.

That's why I'd recommend Strategized Locking in that case (things 
will be slower even with out your ref-count hackery above).  After 
all, if you use the function object across thread boundaries you're 
going to have this overhead whether you ref-count or clone.  The 
difference is where the locks occur and who's responsible for doing 
them and when.  (Cloning does give you some opportunities to micro-
manage performance/locking here that ref-counting doesn't, 
admittedly.)
 
> > > >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.

Actually, we do have atomic actions.  They don't help much in the 
case of copying... you'll still need a lock there.  But the ref-
counting itself can be taken care of through atomic actions.  For 
example, your code above can be coded with out locks by using 
atomic_increment and atomic_decrement.  It's still not needed, but 
this would give you performance comparable to the cloned version of 
operator() since no locks would be used.
 
> > > 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.

Thread safety is still a must (though only gauranteed when the 
function object wrapped is thread safe, which is up to the programmer 
not the library) regardless of the implementation.  This simply 
doesn't effect the choice here, IMHO, between ref-counting and 
cloning.  Yes, there will be a speed hit for ref-counting, but the 
hit isn't as great as you claimed above, and can be reduced to 0 for 
many uses, while reducing the points of contention for thread safety 
over cloning.  I don't see a clear winner in that choice based on 
this criteria.
 
> 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.

I realize that you've addressed a lot of problem domain specific 
issues with sigc++ that we've not addressed yet.  Some are 
appropriate for general discussion about all callback concepts, while 
other's are specific only to sigc++.  This sounds like one of them.
 
> 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.

Again, that depends on the goals and the implementation.  I think 
that most of the problems you've discussed will disappear with 
cloning, which I think we've settled on for reasons other than thread 
safety.  I hope you can chime in where the issues haven't gone away 
based on your experience and the goals we've set and implementation 
we've used.  Your experience will be invaluable here.

Bill Kempf