SmallFun, an alternative to
std::function, which implements fixed-size capture optimization (a form of small buffer optimization). Whilst
SmallFun is a bit less generic than
std::function, it is 3–5x faster in some benchmarks.
You can view the code on GitHub.
std::function is a convenient way to store lambdas with closures (also known as captures), whilst providing a unified interface. If you are coming from the OOP world, then it might be helpful to understand them as a generalization of the strategy pattern.
std::function and lambdas, we would create a hand-crafted functor object like this:
This repository compares
std::function, the hand-crafted
SmallFun. We find that
SmallFun performs better then
std::function by being slighly less generic.
The Missed Opportunity of std::function
std::function uses a PImpl pattern to provide an unified interface aross all functors for a given signature.
For example, these two instances
g have the same size, despite having different captures:
This is because
std::function stores the capture on the heap. This unifies the size of all instances, but it is also an opportunity for optimization!
Instead of dynamically allocating memory on the heap, we can place the function object (including its virtual table) into a preallocated location on the stack.
This is how we implemented
SmallFun, which is used much like
To test how quickly we can allocate and call functors, we will be saving all the many instances in a vector and executing them in a loop. The results are saved into another vector to ensure that the optimizer does not optimize away what we are testing.
SmallFun Implementation Details
Type-erasure unifies many implementations into one interface. In our case, every lambda (or functor) has a custom call operator and destructor. We need to automatically generate an implementation for any type the API consumer will be using.
This shall be our public interface:
And for any callable type with a given signature:
Now we can use it the following way:
This is quite cumbersome and error prone. The next step will be a container.
PImpl seperates, hides, manages the lifetime of an actual implementation and exposes a limited public API.
A straightforward implementation could look like this:
This is more or less how
std::function is implemented.
So how do we remove the heap allocation?
Placement-new allocates memory at a given address. For example:
Putting it All Together
Now we only need to do minor changes to remove the heap allocation:
As you may noticed, if the
Model<...>’s size is greater than
SIZE, bad things will happen! An assert will only catch this at run-time, when it is to late… Luckily, this can be caught at compile-time using
But first, what about the copy constructor?
Unlike the implementation of
std::function, we cannot just copy or move a
std::shared_ptr. We also cannot just copy bitwise the memory, since the lambda may manage a resource that can only be released once due to a side-effect. Therefore, we need to make the model able to copy-construct itself for a given memory location.
We just need to add:
- As we saw, we can verify at compile-time if a Lambda will fit in our memory. If it does not, we could provide a fallback to heap allocation.
- A more generic implementation of
SmallFunwould take a generic allocator.
- We noticed that we cannot copy the memory just by copying the memory bitwise. However using type-traits, we could check if
the underlying data-type is POD and then copy bitwise.
Since You’re Here…
We created Buckaroo to make it easier to integrate C++ libraries. If you would like try it out, the best place to start is the documentation. You can browse the existing packages on Buckaroo.pm or request more over on the wishlist.
C++ is an unusual language in that it does not yet have a dominant package manager (we’re working on it!). As a result…hackernoon.com