Thread: How efficient is functional programming C++?

Hey guys,

So, I've been wondering... What if I started taking a more functional approach and started using std::function instead of just invoking functions. Like, if I started composing std::function objects and passing them around and other stuff like that (I know, such ambiguity), would I see a performance hit?

JavaScript is neat in the sense that everything is an object so functional programming is very highly encouraged. I've been trying to introduce the JS library Ramda into my code more and it got me thinking about designing my C++ in a similar matter.

For example, what if I wanted to design a function that would in essence be,

Code:

  std::atomic_flag lock = ATOMIC_FLAG_INIT;

  template <class R, class... Args> R&& spinLockExecutor(std::function<R(Args...)>& f)
  {
    while (lock.test_and_set(std::memory_order_acquire)) {
      
    }
    
     R r = f();
    
    lock.clear(std::memory_order_release);

    return std::move(r);
  }

or something like that.

Would I see a performance hit? I guess it depends on if I keep my function objects alive or create them before calling spinLockExecutor.

Hmm... Is this a good C++ design pattern? I really like the idea of having a function I can just throw another function at and it'll execute with a spinlock mutex. It's really up to the programmer but this is obviously meant for very short functions that need to be executed in an atomic manner and I'm wondering about design patterns and this was one that I like.

Std::function is not efficient, because it is always a call through a function pointer. If you want to pass functions or function objects around, it is more efficient to pass them as templated types. That way, the compiler can more easlily convert the function opbjects or pointers into raw function calls, or even inlined functions. std::function should only be used when you need to store the function object. It's main use is it's ability to store a lambda, function, or any function object within the same type, unlike a template class which has a different type for different template parameters.

EDIT: in your example you would simply do:

Code:

std::atomic_flag lock = ATOMIC_FLAG_INIT;
 
template <class F> auto spinLockExecutor(F& f) -> decltype(f())
{
  while (lock.test_and_set(std::memory_order_acquire)) {
     
  }
   
   auto r = f();
   
  lock.clear(std::memory_order_release);
 
  return std::move(r);
}

Hold on, I have to pick my mind up off the floor because you just blew my mind right out of my skull.

I wanna talk about your code because it's amazing and how it works.

Code:

template <class F> // using a type F, awesome
auto // the compiler resolve the return type
spinLockExecutor(F& f) -> decltype(f()) // our function takes a type F and I'm assuming this lambda-ish syntax is to help the compiler interept a return type, correct?{  
   auto r = f();
    
  lock.clear(std::memory_order_release);
  
  return std::move(r); // turns out, this is actually a no-no (dangling reference, I think [plus, it kills RVO {I think}])
}

But how is this different from the code posted as a solution here? c++ - Pass a function as an explicit template parameter - Stack Overflow

Code:

#include <iostream>


using namespace std;


int multiply(int x, int y)
{
    return x * y;
}


template <class F> // they do it the same way you do, King Mir
void foo(int x, int y, F f)
{
    cout << f(x, y) << endl;
}


template <int (*F)(int,int)> // this is what I'm referring to
void bar(int x, int y)
{
    cout << F(x, y) << endl;
}


int main()
{
    foo(3, 4, multiply); // works
    bar<multiply>(3, 4); //now it works!

   // so, what's the main difference between these two function calls? 
  // is it silly to ask if one is more "performant" than the other?


    return 0;
}

Edit: I'm so stupid. The way you did it is awesome for function objects, I think, while the second is awesome for function definitions, right? We can choose to pass function objects around or it seems like we can template our code with various function definitions.

Originally Posted by MutantJohn

auto // the compiler resolve the return type

It tells the compiler the return type comes after the function name (C++11). Or you could just omit the return type and just use "auto" to make the compiler decude the return type (C++14).

Originally Posted by MutantJohn

// our function takes a type F and I'm assuming this lambda-ish syntax is to help the compiler interept a return type, correct?

decltype() deduces the type of the expression inside without evaluating the expression. So even if f isn't actually callable, it still returns what f would return if it completed successfully. The "->" just says: here comes the return type.

Originally Posted by MutantJohn

// turns out, this is actually a no-no (dangling reference, I think [plus, it kills RVO {I think}])

No, this is okay. We're not returning a reference. The expression in the return statement is implicitly converted to the return type. So the compiler is going to do (let's called f's return type R) R(r) normally, but with this, the compiler is going to do R((R&&)r). Hence you get move semantics by moving a local variable. Although I will note that this is implicit anyway. Returning a local variable invokes move semantics in simple cases such as just one return statement. Hence, it should not interfere with RVO.

Originally Posted by MutantJohn

But how is this different from the code posted as a solution here? c++ - Pass a function as an explicit template parameter - Stack Overflow

template <class F> // they do it the same way you do, King Mir
template <int (*F)(int,int)> // this is what I'm referring to

The first works for any type, be it a function object or a free function. The second one only works for free functions that matches the signature. The first one also works if the arguments passed to the function can be implicitly converted to what the function expects. Example:

Code:

void foo1(int, int) {}
void foo2(double, double) {}

template<typename F> void caller(F f)
{
    f(1.0, 2.0);
}

template<void (*F)(int,int)> void caller2(F f)
{
    f(1.0, 2.0);
}

caller(&foo1); // Works
caller(&foo2); // Works
caller2<&foo1>(); // Works
caller2<&foo2>(); // Fails

Furthermore, as you can see, the second one only works with compile-time expressions. It must be a function known at compile-time.

Also, the function class DOES come with overhead, both when creating it and calling it. In my (non-scientific) tests with 100 million loop, the function call took 3 seconds, while the function object call took 4.2 seconds. But is it a lot? Probably not significant.

Originally Posted by Elysia

Also, the function class DOES come with overhead, both when creating it and calling it. In my (non-scientific) tests with 100 million loop, the function call took 3 seconds, while the function object call took 4.2 seconds. But is it a lot? Probably not significant.

Were you measuring the function call through the function pointer versus the function call through the function object only, or were you also measuring the callback mechanism, i.e., passing the function pointer versus creating and passing the function object? The former would dominate in cases where the callback is used repeatedly, e.g., the comparator in a sort algorithm.

Code:

int test() { return std::rand(); /* Prevent compiler optimization */ }

int main()
{
	std::function<void()> TestFnc(&test);
	
	const int Loops = 100'000'000;
	
	std::cout << "Testing function object...\n";

	for (int i = 0; i < Loops; i++)
		TestFnc();

	std::cout << "Testing direct call...\n";

	for (int i = 0; i < Loops; i++)
		test();
}

I just used the debugger's built-in functionality to measure the time it took. Nothing fancy.

What's the point of using std::function over a bare function pointer?

Originally Posted by Yarin

No.


False. The only overhead calling a function by a pointer has, is 1 MOV, and maybe 1 cache line.

It has the overhead of a function pointer, where as a function template will have the overhead of a direct function call, which is less. So that's the cost. Std::function may also allocate bound lambda variables on the heap. Furthermore, a direct function call may more easily be inlined, if the compiler deems it appropriate, further benefiting performance; this can be the greatest benefit.

Originally Posted by Yarin

What's the point of using std::function over a bare function pointer?

The point of std::function is that anything that works like a function can be past as the same type, be it function, function object, lambda, or pointer to member. (I may be forgetting another use case). In Elysia's example it was simply what she was testing. I would expect that a function pointer would be about the same as std::function, although it's possible that the compiler is better at optimizing it away.

Originally Posted by MutantJohn

Hold on, I have to pick my mind up off the floor because you just blew my mind right out of my skull.

I wanna talk about your code because it's amazing and how it works.

Code:

template <class F> // using a type F, awesome
auto // the compiler resolve the return type
spinLockExecutor(F& f) -> decltype(f()) // our function takes a type F and I'm assuming this lambda-ish syntax is to help the compiler interept a return type, correct?{  
   auto r = f();
    
  lock.clear(std::memory_order_release);
  
  return std::move(r); // turns out, this is actually a no-no (dangling reference, I think [plus, it kills RVO {I think}])
}

But how is this different from the code posted as a solution here? c++ - Pass a function as an explicit template parameter - Stack Overflow

Code:

#include <iostream>


using namespace std;


int multiply(int x, int y)
{
    return x * y;
}


template <class F> // they do it the same way you do, King Mir
void foo(int x, int y, F f)
{
    cout << f(x, y) << endl;
}


template <int (*F)(int,int)> // this is what I'm referring to
void bar(int x, int y)
{
    cout << F(x, y) << endl;
}


int main()
{
    foo(3, 4, multiply); // works
    bar<multiply>(3, 4); //now it works!

   // so, what's the main difference between these two function calls? 
  // is it silly to ask if one is more "performant" than the other?


    return 0;
}

Edit: I'm so stupid. The way you did it is awesome for function objects, I think, while the second is awesome for function definitions, right? We can choose to pass function objects around or it seems like we can template our code with various function definitions.

Elysia explained most of it. I left std::move in for your example, because it was fine as long as f returns a value. If f returns a reference, this code is actually broken. You can fix it like this:

Code:

std::atomic_flag lock = ATOMIC_FLAG_INIT;
  
template <class F> auto spinLockExecutor(F& f) -> decltype(f())
{
  while (lock.test_and_set(std::memory_order_acquire)) {
      
  }
    
   auto && r = f();
    
  lock.clear(std::memory_order_release);
  
  return r;
}

The difference is, "auto" will force the variable to be a value, whereas "auto &&" will match the return type exactly. "auto&&" has very special semantics, and has been called a "universal reference". If the return type of f is a value, the code will still work as before.

The function pointer template parameter is not as versatile because it does not allow lambdas, function object, or runtime function pointers to be passed. On the other hand, It does strictly enforce the type of the function, which might have some use. You won't accidentally be able to pass a function that uses long instead of int, or passes anything by reference. The type must match exactly.

You could also do this:

Code:

template <int F(int,int)> //not a pointer!
void baz(int x, int y)
{
    cout << F(x, y) << endl;
}

About the same as with the *. On one hand, this makes it easier for the compiler to see that you don't need to store a function pointer, but it probably sees that anyway. On the other hand, it so you can't use a compile time constant function pointer anymore, but there's not much point to those anyway.

In most cases, I would use the foo version, for maximum generality.

Originally Posted by Yarin

Yes, but he asked if he'd see a performance hit, and he wouldn't.

I guess that depends on what your baseline is. Using a raw template parameter as I showed is faster.

And actually, thinking about it more, std::function, should for a passed in ordinary function have the cost of a indirect call, followed by a direct call, so that's slightly worse than a function pointer. Essentially, std::function makes a virtual function call before calling the contained function object in whatever form it is.

I actually assumed this was the case until I actually saw neither John nor Elysia are doing that, so it doesn't look like his use case. But if this was happening, its overhead would be much much larger than an indirect function call.

You'd have to compare to a lambda or function object to be comparing apples to apples. These can, in general, be stored on the stack; std::function cannot do that unless the state is small.

Certainly. And to that end he'd be better making spinLockExecutor to be like std::lock_guard.

For performance reasons? I doubt it would make a difference with optimizations turned up. But it might be a good idea for stylistic reasons.

Maybe I'm missing something, but how is that useful (in the type-safe sense). It'll have to be called at some point, which means the callee will have to already be appropriately typed.

When it's called, the callee does not need to know the type of the function object that it was initialized with. He does not need to know at compile time the size of the state of the function object. He only needs to pass the correct arguments, and use the return type appropriately.

For example, std::function could be used for a callback routine, for a non-template library. That would allow for the callback to have state, without requiring the object that contains it to be a template. It also allows the use of std::bind and similar functions to be used, although a simple lambda may be preferred anyway.

If you return something from your operator (), then it will compile. This is essentially a lambda, the fastest function types of them all, provided you don't store them in std::functions.