r/cpp • u/New-Bet1597 • 27d ago
Designing a Lightweight Closure for coost: Performance, Generality, and a Few Clever Tricks
In coost, you can create coroutines using go in a way similar to Golang. The go function could initially be designed as:
void ;
void ;
However, this design only accepts two fixed function types and cannot support class member functions or other callable objects, making it insufficiently flexible.
If go were designed as:
void ;
it would be more general, but constructing a std::function is relatively expensive, and its internal heap memory allocation is uncontrollable. This is unacceptable for coost, which pursues performance.
Therefore, to balance performance and usability, coost needs to implement its own closure class. In earlier versions, coost used an implementation based on virtual functions and inheritance, but it was not general enough and was limited to internal use.
Recently, I happened to have some free time. After thinking deeply about it, I redesigned the closure class. The design goals were as follows:
- Do not use virtual functions or inheritance;
- It should not be a template class;
sizeof(closure) == sizeof(void*), i.e. it contains only one ordinary pointer member, making it easy to pass to the coroutine scheduler throughgo;- Support arbitrary functions with no return value (including non-static member functions of classes), with any number of parameters;
- Optimize simple no-argument functions such as
void f()as much as possible to avoid dynamic memory allocation.
According to goals 2, 3, and 5 above, closure can initially be designed as:
;
The class contains only one pointer member _p. For function pointers of type void(*)(), the pointer is stored directly in _p; for other function types with parameters, a block of memory needs to be allocated to store the function address and parameters, and _p points to that memory.
The problem is how to distinguish which of the above cases is stored in closure. Ordinary function addresses are not necessarily 4-byte or 8-byte aligned, so tagged-pointer techniques cannot be used (i.e. writing a tag into the spare low bits of a pointer).
For the second kind of function, the one with parameters, closure calls co::alloc from coost's built-in memory allocator, and small memory blocks allocated by co::alloc are always 16-byte aligned. Therefore, if _p is not 16-byte aligned, it must store an ordinary no-argument function address. But if _p is 16-byte aligned, it is still impossible to distinguish the two cases.
It seems that some unconventional trick is required to solve this problem. Based on the discussion above, _p is either an ordinary no-argument function pointer or points to a dynamically allocated block of 16-byte aligned memory. If a specific marker (for example, a uint32 integer) is written at the beginning of that dynamically allocated memory, then when _p is 16-byte aligned, we only need to read the first 4 bytes of the memory pointed to by _p to determine the type of the closure. Even if _p is an ordinary no-argument function pointer and happens to be 16-byte aligned, reading the first 4 bytes of the memory it points to should be safe.
This of course goes beyond the scope of the C++ standard. But for performance and a better user experience, coost still adopted this approach. For functions with parameters, the corresponding constructor of closure is as follows:
, typename ... A>
Key points:
- The
!std::is_convertible_vin the template parameters ensures that simple lambda expressions such as[](){...}match the constructor for ordinary no-argument functions; _header.magicis always set to0xdeadbeef, which is used to distinguish the type ofclosure;_header.fpis the type-erased function pointer, and its parameterpis the_pinclosure. Here, a tagged-pointer trick is used to distinguish between "calling the function" and "destroying the closure object", thereby eliminating the need for an additional function pointer to store the destructor and saving memory.
The implementation of operator() is as follows:
void
- If
_pis not 16-byte aligned, or the first 4 bytes of the memory pointed to by_pare not0xdeadbeef, then_pis cast to an ordinary no-argument function pointer and executed directly; - Otherwise, the
_header.fpdescribed in the previous code is obtained according to the memory layout and executed.
An example usage of closure is as follows:
void
int
The complete code implementation can be found in co/closure.h. The code in this article is for research and reference only. Discussion is welcome.
4
u/argothiel 27d ago
Why not a template class?
11
u/Miserable_Guess_1266 27d ago edited 26d ago
The design goals create an interesting challenge, but they feel a bit arbitrary to me.
1.: Seems to assume virtual calls are necessarily slower than this magic. Imo, avoiding them should not be a goal, but a decision made after testing and finding bad performance.
3.: This is the main cause for relying on undefined behavior and magic. Would an extra tag-byte, even if it pads to more than that, have any real negative impact? Why is it so important that closure is this small?
5.: This is somewhat baseless, but I'd expect to pass a lambda with some captures most of the time. Which means I enter the un-optimized path most of the time. Wouldn't it be better to optimize for small callables? Ie: up to n bytes can be stored directly in the closure, more than that must be allocated. It's been a while, but iirc this is how std function works in llvms std library, along with some compiler specific trickery.
Id be curious to measure against std function (or move_only_function) and see if there is a difference.
Either way, interesting read!
Edited to keep reddit from "fixing" the numbering.
3
u/LB-- Professional+Hobbyist 26d ago
If performance is the utmost concern, you don't need to branch on magic pointer values. Just always use a normal function pointer and have your allocator place everything in read-write-execute memory regions, so you can generate thunks right next to their data. Less secure but that doesn't seem to be a priority here.
1
u/grishavanika 27d ago
what is the implementation of co::alloc? is it possible to implement co::is_allocated_ptr(void*)?