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
> collections for things that are is_callable()...
> I see that some bookkeeping is required for handling groups and
> slots, etc., but it's not clear to me why find_if() needs to be called
> 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
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk