Re: [boost] [signal] performance

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-12-21 17:27:55

On Dec 21, 2005, at 6:43 AM, Dave Moore wrote:
> The bulk of the time seems to be spent in named_slot_map::iterator
> construction and equals().
>
> In both of those cases, nested calls to std::find_if are searching 
> other
> collections for things that are is_callable()...
>
> I see that some bookkeeping is required for handling groups and 
> disabled
> slots, etc., but it's not clear to me why find_if() needs to be called 
> just
> to compare two iterator values, or to construct an iterator...

Because you need to skip over any disabled or removed slots to properly 
compare two iterators. For instance, let's say that X is a callable 
slot and O is not. You might have a slot list that looks like this:

        O O O O O O O O O O

Now, you grab iterators "first" to the beginning of the sequence and 
"last" to the end of the sequence. If you just compare first and last 
directly, you'll think there are callable slots in the sequence... but 
there aren't! So, when you initialize first, you need to move it 
forward until you hit an X. In this case, you hit the end of the list 
first.

Now imagine we have this:

        O O X X X X X X X X

We skip over the first two O's, then hit an X. We call that slot, but 
it decides to disconnect all of the remaining slots:

        O O O O O O O O O O

Now when we compare "first != last" again, we need to move "first" to 
the end of the list to determine that there are no more callable slots. 
See, for instance, the filter_iterator adaptor from the iterator 
adaptors library.

Signals is much slower than vector<function<...> > because it has to do 
a lot more work than vector<function<...> >. Much of the problem comes 
from the fact that one can disconnect slots from a signal while that 
signal is invoking slots. A comparison against something like 
list<pair<function<...>, bool> >, where the bool tells us if we should 
skip the slot or not, would give us a much better bound on the 
performance that could be achieved by Signals.

That said, named_slot_map::iterator is horrible for performance. It was 
built that way to decrease the object-file size for programs using 
Signals, named slots are just plain expensive. I think we can build a 
data structure that allows the implementation of the slot list to be 
similar to list<pair<function<...>, bool> >, with the mappings from 
named slots to position in the list stored in a separate data 
structure... but nobody has implemented this yet. My attempts to kill 
named slots outright, thus improving the performance of Signals, have 
met much resistance.

We have to be realistic about the features that have been omitted in 
the simple, fast models against which Signals is being compared. For 
instance, the example program under discussion ignores several factors:
        1) function<>s/function pointers never call more than one target, so 
they have no internal iteration constructs. Any Signals implementation 
must have these iteration constructs (so we need to at least compare 
against a vector of function<>s or function pointers)
        2) target function objects can modify the iteration sequence during 
iteration. This results in additional iteration overhead that doesn't 
show up in the simple models, e.g., because one can add or remove slots 
while iterating through the list.
        3) named slots induce an ordering on slot invocations. This may or may 
not effect iteration overhead, but there's some non-trivial data 
structure code behind here that must be considered. Would you make 
iteration 2x faster if it meant that slot (dis)connection was linear 
time instead of logarithmic or constant time?

I'm not saying that it isn't useful to compare the performance of 
Signals against simpler models, but we need to compare apples to apples 
if the comparison is going to help us improve.

        Doug