[boost] Re: Proposal for Boost.Signals order of slots

From: Edward Diener (eddielee_at_[hidden])
Date: 2003-09-18 18:58:26

Douglas Gregor wrote:
> My apologies for the (very) late reply. Today is catch-up-with-Boost
> day, just in case nobody noticed :)
>
> On Sunday 14 September 2003 08:34 pm, Edward Diener wrote:
>> 1) Group values are stilled used and they are still 'int's.
>> 2) Group values can go from the greatest negative 'int' to the
>> greatest positive
>> 'int'.
>
> The Group type defaults to int, but it can be anything that models
> CopyConstructible. One can also override the GroupCompare type, which
> defaults to std::less<Group>. There are two questions that come to
> mind (and will be recurring in my response):
> 1) Can we just devise a better type for "Group" that gives us the same
> semantics you are proposing?
> 2) Can we get these semantics for any Group type, without imposing
> additional restrictions on the type?

Your group type is more flexible than I would have thought necessary, but is
in the spirit of Boost where such a type can be parameterized and is better
than just a hard-coded 'int' value.

>
>> 3) A group value of a given name, which let us call
>> SIGNALS_GROUP_TOP, specifies the greatest positive 'int' value and
>> may be passed. This value places that slot at the top of the list
>> for a given signal. 4) A group value of a given name, which let us
>> call SIGNALS_GROUP_BOTTOM, specifies the greatest negative 'int'
>> value and may be passed. This value places that slot at the bottom
>> of the list for a given signal.
>
> I like these, although I'd prefer to call them "front" and "back"
> (with appropriate syntactic modifications depending if they are
> constants/macros/types/etc.). I believe it's better to think of the
> slots as a queue (front/back terminology) than as a stack (top/bottom
> terminology).

That's fine, and the queue analogy is right.

>
> The answers to my questions #1 and #2 are "yes" and "yes".
>
>> 5) A slot which does not pass a group value automatically gets a
>> group value of 0, which places it in the middle of the list and not
>> at the end as the current implementation does.
>
> Yes, I can understand the reasoning behind this, and it seems like
> reasonable semantics to me. For my questions:
> 1) The answer is "yes": there are lots of types like 'int' for which
> there's an obvious middle value.
> 2) The answer is "mostly": what to do about types where we don't know
> the middle value? One easy fallback is to say that the
> default-constructed group value is given to any slot connection
> without specifying a group.

This does seem right. The burden is than placed on the end-user to
understand where the default-constructed value falls in the order of group
values for his type.

>> Slots for a given signal are called in the order of their group
>> value from highest 'int' to lowest 'int'.
>
> FWIW, this is the opposite of the current behavior (lowest groups are
> called first). Just passing GroupCompare = std::greater<Group> would
> switch the behavior, of course.

Yes, of course. No problem with that and, once again, template programming
proves more flexible than my line of thinking.

>
>> The interesting question, obviously, is in
>> what
>> order slots, which have the same group value, are called. What
>> follows is a design suggestion for that occurrence.
>>
>> 1) Ordering for a given signal for slots with the same group number
>> may be random, FIFO ( first in, first out ), LIFO ( last in, first
>> out ), and
>> user defined. This can be done with an enum with values such as
>> SIGNALS_ORDER_RANDOM, SIGNALS_ORDER_FIFO, SIGNALS_ORDER_LIFO, and
>> SIGNALS_ORDER_USER. A function of the connection can let the user
>> change this value from the default. The default should be
>> SIGNALS_ORDER_FIFO
>> and not SIGNALS_ORDER_RANDOM which is essentially the current
>> implementation.
>
> The current implementation should be at least deterministic, unless
> the underlying multimap implementation is truly crazy :)
>
> I don't see the point of random ordering. The current ordering is
> unspecified to give implementers (err, well, me) some freedom in the
> implementation. If we're going to take away that freedom with
> lifo/fifo/user ordering, there's no reason to leave random.

I was thinking of random ordering more along the lines of "I don't care what
order my slots are called." However you are completely right in that if the
user doesn't care, you might as well have the order be FIFO.

>
>> 2) If SIGNALS_ORDER_USER is specified the user should pass into the
>> connection
>> a Boost::Function as his callback which takes two const references to
>> the appropriate Boost::Function for the signal and returns a bool.
>>
>> Each time the Signals library has to decide in what order slots
>> should be called for a specific signal, when the slots have the same
>> group number, it starts with the first slot in its list for that
>> group number
>> and begins comparing it to every other slot after it using the above
>> Boost::function callback. If the callback returns true, it keeps the
>> order. If the callback returns false, it moves the other slot in
>> front of it
>> in the order but continues to compare the original slot in the same
>> way with all other uncompared slots.
>>
>> Then it goes to the next slot at the beginning of the list and does
>> the same, making sure not to compare again with any slot that has
>> already been previously compared. It follows this algorithm until
>> the final list order is determined and then calls each slot in that
>> order.
>
> This is an O(n^2) algorithm, and that's going to hurt at run-time
> more than we can justify. However, that doesn't really matter:
> implementing the suggested semantics amounts to changing the
> group-based ordering to a lexicographical ordering on (group,
> function object). But there is a caveat: boost::function<> objects
> cannot be compared, nor can the underlying object be queried. Because
> of this, I'm not sure how users could ever compare two slots, unless
> they replace boost::function<> with a different SlotFunction type
> (the last template parameter for the signal class).

The run-time slowness is justified, in my belief, in that the end-user
chooses to use a user-defined ordering in the first place. In other words
the time penalty which occurs is something the end_user will know about.

On the second issue: I acknowledge this at the bottom of my original post.
Ideally it would be nice for the end-user to know that a particular
connection refers to a particular handler. I am used to Borland's __closure
where the member function handler can actually have its __closure address
taken and compared against the actual address in the __closure pointer which
represents the signal. Of course this is a simpler, less flexible system
that does not do multi-cast events.

If the boost::function, boost::bind concept will never allow the end-user to
know what handler is actually bound to a boost::function after the fact,
then the idea of user-defined ordering, where the two const boost::function
references are passed at decision-making time, is worthless.

>
> So here's my question: where could the user get an ordering on slots
> that couldn't be done by using, e.g., std::pair<int, foo> instead of
> int as the Group type? I can't think of any instances.

Yes, ordering can always be done by group so that user-defined ordering
within the same group has much less value. I agree that my initial thoughts
about this went a bit overboard on this functionality. My initial thinking
is that the end-user might have to delay the decision of what order slots
are called until the signal actually occurred instead of when the slots are
connected. But I can think of no really practical examples of such usage
other than a theoretical invented one.

OTOH, your suggestion above makes me think that a user-defined ordering
might be at least conceivable if the lexigraphic function I originally
described actually passed back to the end-user the group type values instead
of const boost::function references. The group type values could also have,
as an example, C++ member function pointers which would enable the end-user
to determine which slot should be called first.

>
>> An obvious alternative to the above is to pass the entire list as a
>> vector of slots and let the end-user reorder it as he wants. However
>> I do prefer the previous method as being easier, from the end-user's
>> point of view,
>> to use, although obviously more iterative ( multiple calls versus a
>> single call ).
>
> This would seriously break the encapsulation of the Signals library,
> and put a huge burden on the user. If we're to do user ordering,
> using a lexicographical order is the right way.

Totally agreed, which is why I favored the original way.

>
> With respect to the in-group ordering, I think then the only two
> choices left are LIFO and FIFO, i.e., connect at either the beginning
> or the end of the group, respectively. We know we need:
> 1) Guaranteed ordering
> 2) A sensible default (FIFO)
>
> The question I can't adequately answer is: Does the usefulness of the
> option to use LIFO ordering within groups outweigh the cost of the
> extra interfaces we'll need to support it?

Will the extra interfaces really cost anything, or anything significant ? It
might make the implementation a little bigger or more complicated, but I
hardly think it would slow down the implementation.

>
> The benefit of allowing both LIFO and FIFO ordering is that users get
> more control over slot ordering. There may be uses where this is
> absolutely necessary; I'm not sure.

>From you perspective is it really difficult programming ? It seems that once
you have a FIFO queue for a given group, going backward through that queue
is easy.

>
> The cost is that we will need more connect() overloads, and we'll
> have some duplication in the slot interface: you can order slots via
> group names and with fifo/lifo subgroup ordering. One could argue
> that this completely redundant, because one can use a pair<group,
> foo> instead of group slot ordering to achieve the same thing.
>
> Here's a counter-proposal, that I think captures most of the
> semantics of your proposal. I'll note differences at the end:
> 1) Connecting a slot without specifying a group name uses a
> default-constructed group name.

Group "value" instead of group "name" ? Name implies to me that you are
specifying the group value as a literal.

> 2) There are two special values "at_front" and "at_back", located in
> namespace boost::signals, that connect to the front or back of the
> slot ordering. (We can spell these any way we want, of course, I just
> dislike ALL_CAPS if it's avoidable).

I dislike ALL_CAPS also.

> This will add one new connect( )
> overload: connection connect(front_or_back fob, const slot_type&
> slot); 3) Slots are connected at the back of their group (except when
> connecting at_front, of course), i.e., using FIFO ordering.

Total agreement.

>
> This (semantically) differs from your proposal in several ways:
> 1) at_front would go before, e.g., numeric_limits<int>::min() and
> at_back would go after numeric_limits<int>::max(), because they are
> part of an ordering applied before the group's ordering.

No problem.

> 2) "random"/"unspecified" in-group ordering doesn't exist (it isn't
> useful, nor does it give implementors any useful lattitude).

Agreed.

> 3) "user" in-group ordering doesn't exist (because I don't think it's
> feasible from an implementation perspective)

I think a theoretical case can still be made for deciding slot order also
when the signal occurs and not completely when the slot is connected.
Whether there is any real, practical value to this I don't know. But the
first time some programmer asks why he can't make the final decision just
before the signal occurs, we can both smile.

> 4) "lifo" ordering doesn't exist, because I'm guessing it isn't work
> the addition of more connect() overloads. This is the change for
> which I have the least rationale.

I agree with you on a practical level since I have never used a system,
other than your current implementation, where fifo wasn't the rule. I do
wonder if anyone has ever used a system where the last slot connected is the
first to be signalled. It does seem to me that the overhead for this is
merely a very slightly more complicated and less elegant interface.

>
> Thank you for starting this discussion. It's one we really need to
> have to improve Signals.

I like Signals and I especially like the idea of an modern event handling
C++ implementation which could become part of the C++ standard library.