Re: [boost] Re: New New Callbacks Uploaded

From: Karl Nelson (kenelson_at_[hidden])
Date: 2000-12-04 19:52:35

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

I am simply pointing out that in general reference counting adds
one more piece of data which must be shared.  This in general means
more locks.  

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

In the threading case which shared objects you would use 
something like the code I presented above.  Since cloning doesn't
add extra data, it doesn't expose additional need for locks.  
Cloning seems like the clear win for multithread for me.  
Of course add in any of the other issues I have pointed out for
multicast, and cloning is bad.  

Basically, I disagree that cloning vs sharing is a wash for
multithread.   

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

Change that to shared_ptr<int> and you have no way to pass anything 
but a shared copy.  In other words you have taken most of the choice
away from the user.

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

I think if you interject sharing your really need to look at the 
COW issues.  (Just to note, sigc++ doesn't do COW but then once
created a slot is basically RO.)

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

This again depends on the frequency and the specifics of the system.
Potentially, cloning can be a malloc every copy which may be very
expensive.  But then if you end up paying for reference counting 
then potentially the cloning can be quite cheaper.  I generally
use benchmarking to determine tradeoffs like 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.  

This covers another signal thread case that is self assignment.  If
a callback calls something which causes that callback to change (
assignment) when the callback is still on the stack, it will 
cause the system to die when the stack unrolls.  

  class my_functor 
     { 
        A a;  // some data
        operator() 
          {
            do_something();
            a++;
          }
     };

  Functor f=my_functor();

  void do_something()
    {
      ...
      f.clear();
      ...
    }

  main()
    {
       f();
    }

This case turned out to be fairly common in GUI systems.  :-(

   A button in a dialog closes that dialog,  thus pressing the 
button emits a signal which kills the dialog which destroys the
button, which blanks the signal which is currently emitting, which
clears the slot which now has a reference count of zero, but
we will access that data again when we roll the stack back.

  A = we have a reference, so the execution doesn't need one
  B = the callback can be hooked back to effect the original object

conflict!
   A----><----B

Note, cloning doesn't help this problem and in fact makes it worse
because any assignment of the callback assures the current callback
is destroyed.  So cloning boost system would not be appropriate for
sigc++ style multi-cast.  Thus my rather long discussion on why
boost can't just hope to build the ideal simple system and then
patch it over to allow the dependency tracking and multi-cast.   It
just won't work.

Either we embrace large amounts of safety at cost of speed and
memory or you don't.  There really isn't a good in between.

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

I know the above case looks nasty, but this is what happens if you
really are trying to get safety with lifetime safe signals.   And under
that case it is necessary.

Consider what a chain of shared resources like look like in with
reverse dependencies...

WARNING ANSI ART * WARNING ANSI ART * WARNING ANSI ART * WARNING ANSI ART 
       __         ______________     ____      _______       ___
         |       |              |   |    |    |       |     |
   signal|----->*|  connection_ |*->|Adp*|*-->| slot_ |---->| object
         |       |              |   |    |    |       |     |
      ___|<------|              |*<-|    |*<--|       |<----|
                 |              |   |____|    |       |     |____ 
   connection *->|              |  slot *---->|       |
                 |______________|             |_______|

(* denotes multiplicity, signal points to many connection_, many
slots point to one slot_)

This is the typically sigc++ tree for a signal/slot.
  
  connection - iterator to connections in a signal (many of them)
  connection_ - instance binding a signal to a slot
  signal - multicast object
  slot   - pointer to a callback (many of them) 
  slot_  - actual callback
  adp*   - adaptors between the signal and the slot

Notice that we have rings here which can potentially lead to bad
something not going away.  So what should happen here if something gets
dropped.  We would like as much of this tree is possible to die
when one of the sides goes out, but then we still may have positive
reference counts on one branch of the tree.  To handle this we
must reference count all of the tree.

Further remember in the multicast case, you can't guarantee that only
the current item is removed from signal list.  Any item has
the potential to go away.  That is what makes multicast such a nasty problem.
Dtors of objects often trigger removal of multiple items on signal
lists which may in turn be executing at the time.  (button in dialog)
It is like having a list where every access to an item can cause 
other items to appear or disappear.  => royal mess

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

I am not up on most modern locking systems.  My system theory is about
10 years back.  'Jim, I am an electrical engineer, not a miracle worker.'  
;-)
 
[...]
> > 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.

People have recommended atomic operations for sigc++, but as
yet, I haven't found them to be much good.  Too often I have 
to decrement, check, then do some clean up in synchronized manner.
I also need to have things like commit to the next before giving
up the last where I can hold the lock for a bit of time.  Atomic
would make this harder to do (more suspect to optimization bugs)
   
[...]
> > 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.

There is never a clear winner.  Sharing just is a bigger can of 
worms unless there is a compelling reason to favor it over cloning.
(Personally I prefer sharing over cloning, but I don't feel that
it would meet the needs thus far described.)

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

If you get to implementing dependency tracking and lifespan issues
I would have a fair amount to say.  The most sensible solutions 
run into side effects when you realize that signals are blind.  
That is you can't see that the object on the other side needs a 
lock thus the user can't acquire the lock until the middle of the
list.  If the hold the lock for all the list they will deadlock.  
(If I could solve all these problems, I would be done with development 
of sigc++.  :-)

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

The goals at least to me seem to favor high speed and multi-thread
at the expense of the extreme safety and brain dead cases which sigc++
is attempting to address.  That would at least arguably favor 
cloning over sharing.  

Hope it helps.

--Karl