{"id":103749,"date":"2020-05-14T07:00:00","date_gmt":"2020-05-14T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=103749"},"modified":"2020-05-14T10:17:45","modified_gmt":"2020-05-14T17:17:45","slug":"20200514-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20200514-00\/?p=103749","title":{"rendered":"Inside std::function<\/CODE>, part 2: Storage optimization"},"content":{"rendered":"

Last time<\/a>, we looked at the basic idea behind std::function<\/code>. For each callable type, it creates a custom callable<\/code> wrapper class that knows how to invoke the instance of that type. Each callable<\/code> derives from a common base interface, and the main std::function<\/code> holds a pointer to that interface.<\/p>\n

As I noted, the standard requires that if the callable is a plain function pointer or a reference_wrapper<\/code>, then no additional allocations are permitted.<\/p>\n

The way the optimization works is that the function<\/code> also carries with it a small buffer of raw bytes. If the callable<\/code> is small (as it will be for a function pointer or or a reference_wrapper<\/code>), then the callable<\/code> is stored directly in the buffer, avoiding an extra allocation. If the callable<\/code> is large, then a separate allocation is done as before.\u00b9<\/p>\n

The concept behind the optimization is simple, but the execution is rather complicated. Since the memory is now being partly managed by the class itself, we can’t use a unique_ptr<\/code> any more. Instead, we keep a raw pointer and do manual memory management.<\/p>\n

Let’s start with what we need in our function<\/code>:<\/p>\n

inline constexpr size_t storage_size =\r\n  std::max(sizeof(callable<void(*)()>),\r\n           sizeof(reference_wrapper<char>));\r\n\r\nusing storage_t = typename\r\n           aligned_storage<storage_size>::type;\r\n\r\nstruct function\r\n{\r\n  callable_base* m_callable = nullptr;\r\n\r\n  storage_t m_storage;\r\n\r\n  void* storage() { return addressof(m_storage); }\r\n\r\n  ...\r\n};\r\n<\/pre>\n
In addition to the callable_base<\/code> pointer, we also have some storage that we can use for small callables. In order to satisfy the standard, our storage needs to be large enough to hold a callable function pointer or a callable reference wrapper.<\/p>\n
There’s a bit of a trick here: Calculating the size of an arbitrary function pointer and an arbitrary reference wrapper. Fortunately, the standard requires that all function pointers have the same size,\u00b2 due to the rule that says that you can reinterpret_cast<\/code> among function pointers, and if you reinterpret_cast<\/code> back to where you started, the result is the same. A reference_wrapper<\/code> is a wrapper around a pointer, and the largest pointer is the void*<\/code>, which the standard requires to be the same size as a char*<\/code>.\u00b3<\/p>\n
The idea is that the m_callable<\/code> points either to a heap-allocated callable<T><\/code> (if it is large) or to a callable<T><\/code> constructed via placement new into the m_storage<\/code> (if it is small).<\/p>\n
It’s a simple idea, but the implementation gets kind of messy, because the callable<T><\/code>‘s clone<\/code> method has to do different things depending on whether it is a large or small object.<\/p>\n
struct function\r\n{\r\n  ...\r\n\r\n  template<typename T>\r\n  function(T&& t)\r\n  {\r\n    if constexpr (sizeof(*new callable(t)) <= storage_size) {\r\n      m_callable = new(storage()) callable(t);\r\n    } else {\r\n      m_callable = new callable(t);\r\n    }\r\n  }\r\n\r\n  ...\r\n};\r\n<\/pre>\n
To create a function<\/code>, we take the functor object and construct it either in-place (if it is small) or on the heap (if it is large).<\/p>\n
struct function\r\n{\r\n  ...\r\n\r\n  function(const function& other)\r\n  {\r\n    if (other.m_callable) {\r\n      m_callable = other.m_callable.clone(m_storage);\r\n    }\r\n  }\r\n\r\n  ...\r\n};\r\n<\/pre>\n
To copy a function<\/code>, we take the source’s m_callable<\/code> and ask it to clone itself, using our storage if it can.<\/p>\n
struct function\r\n{\r\n  ...\r\n\r\n  function(function&& other)\r\n  {\r\n    if (other.m_callable == other.storage()) {\r\n      m_callable = other.m_callable.move_to(m_storage);\r\n      exchange(other.m_callable, nullptr)->~callable();\r\n    } else if (other.m_callable) {\r\n      m_callable = exchange(other.m_callable, nullptr);\r\n    }\r\n  }\r\n\r\n  ...\r\n};\r\n<\/pre>\n
To move a function<\/code>, there are three cases.<\/p>\n