Are inline functions passed as argument, really executed inline in C/C++?

Question

I have a very long (in number of iterations) for loop, and I like to make it possible to personalize some of its parts. The code looks as following:

function expensive_loop( void (*do_true)(int),  void (*do_false)(int)){
    for(i=0; i<VeryLargeN; i++){
       element=elements[i]
       // long computation that produce a boolean condition
       if (condition){ 
         do_true(element); 
       }else{
         do_false(element);
       }
    }
}

Now, the problem is that every time do_true and do_false are called, there is an overhead due to the push/pop of the stack that ruins the high performance of the code.

To solve this I could simply create several copies of the expensive_loop function, each with its own do_true and do_false implementation. This will make impossible the code to mantain.

So, how does someone make the internal part of an iteration so it can be personalized, and still mantain high performance?

Answer 1

Note that the function accepts pointers to functions, so those get called through a pointer. The optimizer may inline those calls through the function pointers if the definitions of expensive_loop and those functions are available and the compiler inlining limits have not been breached.

Another option is to make this algorithm a function template that accepts callable objects (function pointers, objects with a call operator, lambdas), just like standard algorithms do. This way the compiler may have more optimization opportunities. E.g.:

template<class DoTrue, class DoFalse>
void expensive_loop(DoTrue do_true, DoFalse do_false) { 
    // Original function body here.
}

There is -Winline compiler switch for g++:

-Winline

Warn if a function can not be inlined and it was declared as inline. Even with this option, the compiler will not warn about failures to inline functions declared in system headers.

The compiler uses a variety of heuristics to determine whether or not to inline a function. For example, the compiler takes into account the size of the function being inlined and the the amount of inlining that has already been done in the current function. Therefore, seemingly insignificant changes in the source program can cause the warnings produced by -Winline to appear or disappear.

It probably does not warn about a function not being inlined when it is called through a pointer.

Answer 2

The problem is that the function address (what actually is set in do_true and do_false is not resolved until link time, where there are not many opportunities for optimization.

If you are explicitly setting both functions in the code (i.e., the functions themselves don't come from an external library, etc.), you can declare your function with C++ templates, so that the compiler knows exactly which functions you want to call at that time.

struct function_one {
  void operator()( int element ) {
  }
};

extern int elements[];
extern bool condition();

template < typename DoTrue, typename DoFalse >
void expensive_loop(){
  DoTrue do_true;
  DoFalse do_false;

  for(int i=0; i<50; i++){
    int element=elements[i];
    // long computation that produce a boolean condition
    if (condition()){ 
      do_true(element); // call DoTrue's operator()
    }else{
      do_false(element); // call DoFalse's operator()
    }
  }
}

int main( int argc, char* argv[] ) {
    expensive_loop<function_one,function_one>();

return 0;
}

The compiler will instantiate an expensive_loop function for each combination of DoTrue and DoFalse types you specify. It will increase the size of the executable if you use more than one combination, but each of them should do what you expect.

For the example I shown, note how the function is empty. The compiler just strips away the function call and leaves the loop:

main:
    push    rbx
    mov     ebx, 50
.L2:
    call    condition()
    sub     ebx, 1
    jne     .L2
    xor     eax, eax
    pop     rbx
    ret

See example in https://godbolt.org/g/hV52Nn

Using function pointers as in your example, may not inline the function calls. This is the produced assembler for main and expensive_loop in a program where expensive_loop

// File A.cpp
void foo( int arg );
void bar( int arg );

extern bool condition();
extern int elements[];

void expensive_loop( void (*do_true)(int),  void (*do_false)(int)){
    for(int i=0; i<50; i++){
       int element=elements[i];
       // long computation that produce a boolean condition
       if (condition()){
         do_true(element);
       }else{
         do_false(element);
       }
    }
}

int main( int argc, char* argv[] ) {
    expensive_loop( foo, bar );

    return 0;
}

and the functions passed by argument

// File B.cpp
#include <math.h>

int elements[50];

bool condition() {
    return elements[0] == 1;
}

inline int foo( int arg ) {
    return arg%3;
}

inline int bar( int arg ) {
    return 1234%arg;
}

are defined in different translation units.

0000000000400620 <expensive_loop(void (*)(int), void (*)(int))>:
  400620:       41 55                   push   %r13
  400622:       49 89 fd                mov    %rdi,%r13
  400625:       41 54                   push   %r12
  400627:       49 89 f4                mov    %rsi,%r12
  40062a:       55                      push   %rbp
  40062b:       53                      push   %rbx
  40062c:       bb 60 10 60 00          mov    $0x601060,%ebx
  400631:       48 83 ec 08             sub    $0x8,%rsp
  400635:       eb 19                   jmp    400650 <expensive_loop(void (*)(int), void (*)(int))+0x30>
  400637:       66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
  40063e:       00 00
  400640:       48 83 c3 04             add    $0x4,%rbx
  400644:       41 ff d5                callq  *%r13
  400647:       48 81 fb 28 11 60 00    cmp    $0x601128,%rbx
  40064e:       74 1d                   je     40066d <expensive_loop(void (*)(int), void (*)(int))+0x4d>
  400650:       8b 2b                   mov    (%rbx),%ebp
  400652:       e8 79 ff ff ff          callq  4005d0 <condition()>
  400657:       84 c0                   test   %al,%al
  400659:       89 ef                   mov    %ebp,%edi
  40065b:       75 e3                   jne    400640 <expensive_loop(void (*)(int), void (*)(int))+0x20>
  40065d:       48 83 c3 04             add    $0x4,%rbx
  400661:       41 ff d4                callq  *%r12
  400664:       48 81 fb 28 11 60 00    cmp    $0x601128,%rbx
  40066b:       75 e3                   jne    400650 <expensive_loop(void (*)(int), void (*)(int))+0x30>
  40066d:       48 83 c4 08             add    $0x8,%rsp
  400671:       5b                      pop    %rbx
  400672:       5d                      pop    %rbp
  400673:       41 5c                   pop    %r12
  400675:       41 5d                   pop    %r13
  400677:       c3                      retq
  400678:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
  40067f:       00

You can see how the calls are still performed even when using -O3 optimization level:

400644:       41 ff d5                callq  *%r13