Thread: How efficient is functional programming C++?

  1. #1
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665

    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.
    Last edited by MutantJohn; 01-16-2016 at 11:06 AM.

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    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);
    }
    Last edited by King Mir; 01-16-2016 at 06:38 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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.
    Last edited by MutantJohn; 01-17-2016 at 11:24 AM.

  4. #4
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Quote Originally Posted by MutantJohn View Post
    would I see a performance hit?
    No.


    Quote Originally Posted by King Mir View Post
    Std::function is not efficient, because it is always a call through a function pointer.
    False. The only overhead calling a function by a pointer has, is 1 MOV, and maybe 1 cache line.

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Huh.. So it seems like it's okay to use std::function and that's cool but part of me is really enjoying the idea of using templates to pass the functions around. It's incredibly easy to integrate using existing code. I dig it a lot.

    Man, I'm glad I made this thread now lol. I feel like I'm learning such cool C++ stuff.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by MutantJohn View Post
    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).

    Quote Originally Posted by MutantJohn View Post
    // 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.

    Quote Originally Posted by MutantJohn View Post
    // 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.

    Quote Originally Posted by MutantJohn View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,260
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    What's the point of using std::function over a bare function pointer?
    Last edited by Yarin; 01-19-2016 at 01:47 PM.

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Yarin View Post
    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.

    Quote Originally Posted by Yarin View Post
    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.
    Last edited by King Mir; 01-20-2016 at 12:28 AM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by MutantJohn View Post
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  12. #12
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Quote Originally Posted by King Mir View Post
    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.
    Yes, but he asked if he'd see a performance hit, and he wouldn't.


    Quote Originally Posted by King Mir View Post
    Std::function may also allocate bound lambda variables on the heap.
    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.


    Quote Originally Posted by King Mir View Post
    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.
    Certainly. And to that end he'd be better making spinLockExecutor to be like std::lock_guard.


    Quote Originally Posted by King Mir View Post
    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)
    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.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Yarin View Post
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Man, lots of stuff to read.

    I have another quick question though... What about the performance of a basic functor like this?
    Code:
    struct functor
    {
      auto operator() { /* definition }
    };
    if that'll even compile.

    You know, a callable object that's less fancy than std::function.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Functional testing
    By g4j31a5 in forum Tech Board
    Replies: 15
    Last Post: 03-22-2012, 01:54 AM
  2. My functional syllogism program
    By jeremy duncan in forum C Programming
    Replies: 3
    Last Post: 12-15-2011, 01:23 PM
  3. functional derivation better?
    By CodeMonkey in forum C++ Programming
    Replies: 3
    Last Post: 08-16-2007, 12:57 AM
  4. Functional programming languages... r they really functional?
    By code_mutant in forum C++ Programming
    Replies: 10
    Last Post: 02-25-2004, 05:29 AM
  5. functional dependencies
    By DMaxJ in forum C++ Programming
    Replies: 10
    Last Post: 10-23-2002, 07:07 AM