Multicast function container

Question

I'd like to implement a multicast function. Currently, I'm in the design phase of this.

The basic idea is to have a class, to which std::function can be added, an interface like this:

template <typename ...PARAMETERS>
class MultiFunction {
    private:
        // some container to store functions
    public:
        // add a function into MultiFunction, return <something> as some id
        <something> add(std::function<PARAMETERS...>)

        // remove function, the <something> should be used as parameter, what add returned
        void remove(<something>);

        // call functions
        void operator()(PARAMETERS ...par);
};

So basically, there are:

• add functionality, which returns <something>, which somehow identifies the added function in the MultiFunction.
• remove: removes a function, which is identified by <something>
• operator(): calls the functions

This class can be implemented in two flavours: ordered and non-ordered. By this, I mean that if a MultiFunction is ordered, then it will call functions in the order that have been added. A non-ordered one can call functions in any order.

Here are my current ideas, how to implement this:

Non-ordered:

1. Implemented with array. If an element is removed, then the array will have a hole. The hole is added into a list, so next time at add, a list is used to find a free element. <something> is an index, so removal is O(1). Calls are slower, because there should be a check whether an element is a hole or not.
2. Implemented with array. If an element is removed, then the last element of the array moved into its place. <something> is some kind of token (token is stored in pair with std::function), so removal is O(n). Calls are fast, just an iteration through the array.

Ordered:

3. Basically, it is the same as 1., but elements in a list too. So calls can be made in order. Calls are slower then 2., because list iteration is needed.
4. Implemented with array. If an element is removed, then the array is shifted. <something> is a token. Removal is O(n) (because of token search, and because of shift needed). Calls are fast.
5. Implemented with list. <something> is a pointer to the added node. Removal is O(1). Calls are not that fast, because list iteration is slower than array iteration. The problem is, if I copy the MultiFunction, there is no way to remove elements in the copied MultiFunction (because <something> has a pointer to the original MultiFunction).

Are there any other sensible possibilities to implement this? Maybe using some kind of advanced data structure?

Basically, I'd like to decide, which way to go.

Currently, I think that 4. is the best for me: add/removal is usually rare, and I'd like to have fast calls. And it is ordered, which can be a bonus feature.

Answer 1

Okay, I'll try to answer this one again since the last time I got too wrapped up in thoughts about something I was working on and I missed a crucial detail that you have keys you return to clients to remove things.

Unordered

Implemented with array. If an element is removed, then the array will have a hole. The hole is added into a list, so next time at add, a list is used to find a free element. is an index, so removal is O(1).

This is actually one of my favorite solutions to these problems if the sequence isn't teeny. You can implement it very efficiently without even requiring a separate stack on the side like this for PODs:

template <class T>
struct Container
{
     union FreeElement
     {
         // Stores the element.
         T element;

         // Points to the next free element or -1 if the free
         // list is empty.
         int32_t next;
     };

     // Or whatever random-access sequence of your choice
     // (SmallVector, e.g., with SBO).
     std::vector<FreeElement> elements;

     // Points to the first free element.
     int32_t free_index;
};

It does get a little more involved in C++ for non-trivial UDTs (need placement new, manual dtor invocations, and aligned_storage). Or:

If you return an index to the client on inserting to the multifunction, you can do both insertion and removal in O(1).

Calls are slower, because there should be a check whether an element is a hole or not.

This is true, but it's not necessarily so bad if you use a parallel bitset (not necessarily std::bitset) on the side with FFS/FFZ. You'll be able to immediately spot holes using efficient bitwise instructions to skip over checking 64-bits at a time. I can actually almost rival std::vector sequential iteration using FFS/FFZ (just 2-3% slower for an array with a healthy number of holes in it), since a single 64-bit test for a packed array can then lead to iterating over 64 elements without doing another FFS/FFZ branch. And FFS/FFZ is often implemented very efficiently on our hardware.

Implemented with array. If an element is removed, then the last element of the array moved into its place. is some kind of token (token is stored in pair with std::function), so removal is O(n). Calls are fast, just an iteration through the array.

This kind of solution can be great as well but it does invalidate indices and naturally requires you to use something other than an index for a key with linear-time searches to remove things. It might be worth it though if your container isn't gigantic (more than worth it if it's teeny with, say, 32- elements), especially if your critical execution paths are skewed towards traversal.

If the index invalidation isn't a big deal (which it definitely won't be if your sequence is teeny), this solution is so ridiculously simple and nice.

Ordered

For ordered I actually recommend a totally different strategy, like this:

The diagram above shows:

1. List in basic form (the nodes are doubly-linked so the first node is pointing to -1 with the prev index).
2. The red node is about to be deleted. We update the links to skip the node.
3. We push the red node, now removed, to the free list by making the free head point to it and setting the red node's next index to the former free head (-1).
4. Inserting a new node. We reclaim a node by popping off the free list in constant time. Then we make the node at the back/tail of the list point to it with its next index, preserving traversal order to match insertion order.

I don't know what to call it except a "doubly-linked indexed free list" (or "doubly-linked array with free list" -- I keep changing the name every time I describe it to someone since I don't know if it has a name and I can't make up my mind if it doesn't). With that you can get constant-time removal through an index and reasonably fast iteration through the array unless the list starts to degrade after many removals and insertions to the point where you're zig-zagging all over the place in a huge array following these next/prev links around. If it's small, even zig-zagging isn't necessarily much of a problem since the former data might not get evicted from a cache line just yet.

You implement it like this:

template <class T>
struct Node
{
     // Stores the element.
     T element;

     // Points to the previous element in the list.
     int32_t prev;

     // Points to the next element in the list or the next free
     // element if the node has been removed.
     int32_t next;
};

template <class T>
struct List
{
     // Stores the nodes in the list.
     std::vector<Node<T>> nodes;

     // Stores the first node in the list or -1 if the list is empty.
     int32_t head;

     // Stores the last node in the list or -1 if the list is empty.
     int32_t tail;

     // Stores the first free node in the list of -1 if the free
     // list is empty.
     int32_t free_head;
};

Now linked lists have a notorious rep in C++ for being inefficient, but that's looking at things like std::list using default std::allocator which allocates one node at a time using a variable-length general-purpose allocator. Naturally if you do that, you get cache misses galore on list traversal. But if you use a linked list where all the nodes are stored contiguously in an array, you no longer have that problem much at all, and the size of the links can be halved on 64-bit down to 32-bit indices (unless you actually need billions of nodes).

So linked lists are super cool and can be really helpful in performance-critical areas! Just don't allocate one node at a time. Store them inside std::vector or something. You can think of the vector/array as the actual container. The integer (index) links are just there to let you skip over things that have been removed while allowing constant-time removals and insertions from/to anywhere in the container.

Crazy Idea: Just Don't Remove

And another one that sounds crazy for ordered is just don't remove the element. Keep it in the container but mark it as removed and just keep pushing to the back of the container on insertions, but eventually do a compaction pass to remove all the holes (maybe when the number of holes reaches a certain number).

This can work a lot better than it sounds. You get to keep constant-time insertion (always pushing back) and removal from the middle, but occasionally you do an amortized linear-time compaction pass. A big downside is that when you do these compaction passes, it invalidates indices, so you have to update the indices stored on the side of your clients in these cases for this solution to be beneficial, and that may or may not be a huge PITA. I wouldn't bother if it is.

A Layer of Indirection

Another strategy is to use an added layer of indirection. Instead of your clients storing, say, an int for the index as the key, have them store an index to an index to a key.

That allows your ordered container to store a list of indices. The indices of indices have to be stable, but you're free to update the values of each index as elements get shuffled around (ex: using swap with back and pop_back) to maintain constant-time insertions and removals while still allowing reasonably cache-friendly traversal when you call all the functions in your container (you'd access the elements using the indices you store). Like the doubly-linked indexed free list, it suffers from zig-zagging through the array after you remove and insert a lot on traversal and you have to maintain two parallel sequences.

I can't comment on this solution so much in detail and I'm not 100% sure I described it perfectly since I never really cared for it and have never implemented it. I'm currently a bit sleepy but was trying to work out how to maintain insertion order with these and can't figure it out, so I'm not even perfectly sure if it can maintain insertion order with constant-time removals and insertions (if it can't, I really don't like it since it's really wasteful if it doesn't at least do that). It's popular in game studios though, but I never liked that it requires maintaining a separate parallel array of indices with clients pointing to indices of indices (or sometimes pointers to pointers). However, it does have the upside of storing half the indices over the "doubly-linked indexed free list" that I prefer instead if it can at least maintain insertion order on traversal somehow without a linear-time cost. The only way I can think of to do that is to always add indices to the back of the list (though we can swap/pop elements from the back), like this:

a  b  c  d  e
0, 1, 2, 3, 4

If we remove b, we can swap and pop:

a  e  c  d 
0, x, 2, 3

But now what? How do we keep the insertion order in constant-time without shuffling the whole list? Only way I can think of is to push back 1 to the index list and keep the hole (x or -1), like so:

a  e  c  d 
0, x, 2, 3, 1

At which point we have to deal with holes on traversal and maybe a compaction pass, which is kind of the worst of both worlds. So unless there's something I'm overlooking, this seems like the worst solution for both unordered and ordered. But it's really popular with game studios for some reason, so maybe I'm overlooking a benefit.

Externalizing Storage

This is a strategy that can apply to both unordered and ordered if your multifunctions typically store a small number of elements (functions) each. The temptation in those cases might be to store a boatload of teeny sequences, and that can get explosive in memory use and cache misses.

Generally containers are very efficiently implemented for storing a non-trivial number of elements, but you don't necessarily want to instantiate hundreds of thousands or millions of instances of std::vector with 3 elements each, e.g.

So if you have a case like that, it can help to store all the functions in one big array with holes, for example, like so (where each cell in the grid wants to store its own full-blown container of elements, but we don't and instead just store a 32-bit integer to a first element in a big array stored once for the entire grid):

And you can combine that with the free list strategy. That comes with the cons of potentially requiring a bigger stride to get from one element to the next in one of these teeny sequences as well as thread syncs to insert/remove for thread-safety, but can be better when you're accessing a boatload of teeny multifunctions than storing a full-blown container for each one.