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