|
|
Boost : |
From: William Kempf (sirwillard_at_[hidden])
Date: 2000-12-05 10:25:22
--- In boost_at_[hidden], Karl Nelson <kenelson_at_e...> wrote:
> [...]
> > > 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.
This generality is just that, a generality. It's not always true.
> [...]
> > > 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.
We'll have to agree to disagree.
> [...]
> > > 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.
Taken most of what choice away? Of course they must pass a shared
copy, but that's *precisely* what I said previously that I was
illustrating when I gave the shared_ptr 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.
>
> 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.)
Why do you have to look at COW if COW isn't being used? The problems
with COW don't exist with ref-counting (though ref-counting may have
problems of it's own).
> > > 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.
The problem with benchmarking is that you don't know what to
benchmark. You don't know if a particular application is going to
require several function objects that are expensive to copy or not.
You simply can't predict this sort of thing. This is a poor place to
optimize, IMHO.
> [...]
> > > 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.
This sort of self assignment may be something you've run into in your
GUI applications of sigc++, but in general it's a corner case that
would have several work arounds and so would be best left as
undefined behavior IMHO. To me, this is akin to "delete this" in C++.
> class my_functor
> {
> A a; // some data
> operator()
> {
> do_something();
> a++;
> }
> };
>
> Functor f=my_functor();
>
> void do_something()
> {
> ...
// Simple fix outside of the library
Functor temp = f;
> 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.
Definately sounds like a "delete this" case to me. If the button is
destroyed during the "emit" you could have a lot more problems than
just the function object going away while it's running on the stack.
> 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.
I don't really buy this. "Patching over" may not, but wrapping in a
higher level concept should. Whether that's the best implementation
for this different concept is debatable, but claiming it's not
possible doesn't sound believable.
> 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.
I'm not sure I buy this either, though it's mostly based on my belief
that you can wrap a fast implementation into a new concept that's got
the safety you want.
> > 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.
That depends on the level of safety you're trying to achieve. You
need to be careful to not go too far with safety checks. In the
example you gave with the button I think you have. The function
being called has to know that once emitted the button will be
destroyed, other wise any use of references to the button will result
in undefined behavior. If the programmer knows this at that point,
it's trivial for him to insure the function object isn't destroyed
until afterwards, and that will increase efficiency for all other
cases.
The real danger here is that a programmer may not know that emitting
will cause destruction... but attempting to make the signal/slot
safer in this regard just makes it more likely that the programmer
won't realize this and will do something wrong.
> 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
I agree that it's tricky to manage this stuff. I just don't agree
you came up with the right solution by upping the ref-count during
execution of the signal.
> > > 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.'
> ;-)
Strategized locking is a pattern in which you factor out the locking
in either a polymorphic of parameterized idiom. So if the object is
used with out ever being passed between threads you can use a "null
lock" which does nothing. I wasn't thinking about "self-assignment"
here... but if you were to go to this length in your safety it would
still remove the expense of a "lock" around your ref-counting.
However, with atomic increment/decrement this is probably overkill.
> [...]
> > > 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.
The return value from an atomic decrement is what you'd check, so
it's thread safe. If the result is 0, there are no references left
and so you don't have to worry about clean up being synchronized
(beyond possible synchronization required by the wrapped function
object, but that's its responsibility). This bit of coding is thread
safe and lock free.
> 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)
I don't know what you mean by "commit to the next before giving up
the last", but if it means what I think it does, this too is a non-
issue. Because you're gauranteed there are no references left
on "the last" you can commit to "the next" while holding onto "the
last" for a while with out concerns for thread safety. (Now if you
can decipher what I just said... ;)
> [...]
> > > 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.
Thank you!
> Sharing just is a bigger can of
> worms unless there is a compelling reason to favor it over cloning.
One of the reason I agreed with for choosing cloning. It's just not
the reason we've been debating here.
> (Personally I prefer sharing over cloning, but I don't feel that
> it would meet the needs thus far described.)
The other reason to prefer cloning is that a sharing version can be
trivially built on top of the cloning version, or shared_ptr can be
used for simplicity.
> > > 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++. :-)
Well, if we move past the simpler callback type here and need a
sigc++ style concept it may be that there's people that can solve
these problems for you. I truly hope we can get to that point,
because sigc++ would be a great addition to Boost.
Bill Kempf
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk