Alternatives to std::function for collection of callables

Question

Is there any other way to store a homogeneous collection of callables than resorting to std::function? I.e., to replace type T in the following code

using T = std::function<void(int)>;
std::vector<T> v{some_lambda, some_fn_ptr, some_pmf, some_functor};

with something else?

When passing in individual callables as arguments to a higher-order function, I use template wherever possible to avoid the overhead of std::function. But for collections, I don't know if there is anything I can do.

Answer 1

The largest source of overhead reduction from a direct type is the ability to inline the function. In a tight loop with repeated application, an inlined function can sometimes be vectorized or otherwise get massive optimizations.

The second source of overhead from std::function is the fact that it uses a virtual function table. This causes two "random access" memory lookups -- one for the vtable, and one to follow the pointer on the vtable. If these are not in the cache from prior use, it is reasonably expensive. However, if they are in cache, this ends up being not at all expensive (a few instructions).

The last source of overhead from std::function is the memory allocation. If the object stored in the std::function is large (in MSVC as an example, larger than sizeof(std::string)*2, where std::string itself uses SBO so is modest in size), heap allocation occurs. So whenever the std::function is copied or created, there is a reasonably high cost.

Each of these can be mitigated.

A custom std::function clone can use a vtable-less invoke type erasure to reduce the cost of #2. This has size costs.

A function_ref type that does not store the callable can be written. These store a void* and the equivalent of the vtable (or a direct pointer to the methods). Alternatively, a std::function clone with custom storage size and refusal to heap allocate can be written. Either mitigates #3 reasonably well, at the cost of flexibility and/or lack of value semantics.

The first is the hardest to mitigate.

If you know what operations will be performed using your callable, instead of erasing down to generic invokation you can erase down to invokation in context.

As an example, suppose you have a per-pixel operation. Invoking a std::function on each pixel of an image is going to have lots of overhead.

However, if instead of erasing the per-pixel call (or as well), we erase the per-pixel-run call, we can now store our callable generically, and the overhead goes from per-pixel to per-scanline or per-image!

The callable is now visible in the tight loop, so it can be inlined and vectorized by the compiler, and the vtable following work is only done once per scanline.

You could get fancier and even have it erase scanline(s) with linestride. Or have a few erasures, one for scanlines with zero extra linestride, one for upside down scanlines, another for non-zero linestride, etc. And scanline lengths of powers of 2.

These all have costs, not the least at development time. Only go down this route if you have tested and confirmed that the std::function is actually causing problems.

Answer 2

The overhead of std::function exists because it is a value type. It stores a copy of the functor you give it (it can of course move from it) internally. It does type erasure, but since it could store an object of arbitrary side, it has to be able to allocate memory to do so.

So if your needs do not require the function to actually store an object, if it could only reference one which would continue to exist, then you would be fine. There are several implementations of such types that you can find, generally called something like function_ref. Such types never allocate memory; while their overhead is not zero, it's not as big as function.

However, these are references to an existing function. For functors, they therefore reference a real C++ object (rather than a function/member pointer). That creates a potential lifetime issue. For immediate callbacks (you pass them to a function that will call that callback only during its duration), it's not much of a problem. But in your case, it probably won't be useful.

Ultimately, if you can't work out the lifetime issue, then the overhead for using std::function is actually being useful to you. So best accept it.