Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Have the ideas behind the Fast Delegate (et al) been used to optimize std::function?

There have been proposals for C++ "delegates" which have lower overhead than boost::function:

  • Member Function Pointers and the Fastest Possible C++ Delegates
  • Fast C++ Delegate
  • The Impossibly Fast C++ Delegates

Have any of those ideas been used to implement std::function, resulting in better performance than boost::function? Has anyone compared the performance of std::function vs boost::function?

I want to know this specifically for the GCC compiler and libstdc++ on Intel 64-bit architectures, but information on other compilers is welcome (such as Clang).

like image 545
Emile Cormier Avatar asked Jun 20 '12 18:06

Emile Cormier


2 Answers

In libstdc++'s std::function we use a union type that is suitably sized and aligned to store pointers, function pointers or pointers to member functions. We avoid a heap allocation for any function object that can be stored in that size and alignment, but only if it is "location invariant"

/**
 *  Trait identifying "location-invariant" types, meaning that the
 *  address of the object (or any of its members) will not escape.
 *  Also implies a trivial copy constructor and assignment operator.
 */

The code is based on the std::tr1::function implementation and that part hasn't changed significantly. I think that could be simplified using std::aligned_storage and could be improved by specializing the trait so that more types are identified as location invariant.

Invoking the target object is done without any virtual function calls, the type erasure is done by storing a single function pointer in the std::function which is the address of a function template specialization. All operations are done by calling that function template through the stored pointer and passing in an enum identifying what operation it is being asked to perform. This means no vtable and only a single function pointer needs to be stored in the object.

This design was contributed by the original boost::function author and I believe it is close to the boost implementation. See the Performance docs for Boost.Function for some rationale. That means it's pretty unlikely that GCC's std::function is any faster than boost::function, because it's a similar design by the same person.

N.B. our std::function doesn't support construction with an allocator yet, any allocations it needs to do will be done using new.


In response to Emile's comment expressing a desire to avoid a heap allocation for a std::function which holds a pointer to member function and an object, here's a little hack to do it (but you didn't hear it from me ;-)

struct A {
  int i = 0;
  int foo() const { return 0; }
};

struct InvokeA
{
  int operator()() const { return a->foo(); }
  A* a;
};

namespace std
{
  template<> struct __is_location_invariant<InvokeA>
  { static const bool value = true; };
}

int main()
{
  A a;
  InvokeA inv{ &a };

  std::function<int()> f2(inv);

  return f2();
}

The trick is that InvokeA is small enough to fit in the function's small object buffer, and the trait specialization says it's safe to store in there, so the function holds a copy of that object directly, not on the heap. This requires a to persist as long as the pointer to it persists, but that would be the case anyway if the function's target was bind(&A::foo, &a).

like image 106
Jonathan Wakely Avatar answered Oct 03 '22 07:10

Jonathan Wakely


As noted in the comments, std::function is only an interface, and different implementations may do different things, but it's worth noting that the standard does actually have something to say about this matter. From 20.8.11.2.1/5 (which looks more like an IP address than a part of the standard):

Note: Implementations are encouraged to avoid the use of dynamically allocated memory for small callable objects, for example, where f’s target is an object holding only a pointer or reference to an object and a member function pointer. —end note

This is the standard's way of encouraging implementers to employ the "small function optimization," which was motivated by the cited articles on delegates. (The articles themselves don't actually talk about delegates in the .NET sense. Rather, they use the term "delegate" to mean bound member functions.)

like image 4
KnowItAllWannabe Avatar answered Oct 03 '22 06:10

KnowItAllWannabe