There's all the instructions in the interpreter's main loop (which probably contains a bunch of call/returns on its own...), plus the cycles needed to read the instructions it's interpreting (including the manual management of the VM's call stack), then throw in a cache miss or two, and 400 cycles starts looking pretty good for an interpreted language.

I'm of the opinion that if call/return time is taking up a significant portion of the total running time of a program, then the problem is with the program's structure and nothing is going to solve it better than fixing the code itself (e.g. don't break it up into so many little pieces that most of the functions don't do much more than call others; but don't inline too much, since that'll increase cache misses.) All the clever trickery with stack/heap allocation to bring down the overhead is interesting, but it can't ever beat the zero cycles of not doing a call at all. As the saying goes, "the fastest way to do something is to not do it at all."

....or with the choice of the programming language. Some styles goes better together with some programming languages. CPython is possibly the worst offender in terms of function call overhead, amplified further by its lack of inlining / macro capabilities.

PyPy makes it better, but were they ever fighting an uphill task !

Python, on retrospect, seems to have been designed almost as a snarky challenge thrown at someone: "You think you are too smart, do you ? Let me see how you can make this go fast. No I want elide tail calls".

I'd say this is a pretty minor effect in every scenario I've dealt with. Haskell, in particular, lets you inline very easily (and so many people do if performance is important), and I've only heard of one time where that had a negative consequence, and that was mostly about a missing optimization that you had to fix in a non-removing-inlining kind of way (it had to do with polymorphic strings leading to code inlined at every single string literal, which is extremely silly).

Note, however, that, as a special case, inlining of a function only called in one place "should" always be faster.

Lest one think this is an idle warning, when I tried to verify his results on my machine I found that even when I prevented the inlining of the functions, "gcc-4.9 -O3" persistently optimized away the second function call by generating code like this:

  f2:
    callq  400700 <tree1>
    mov    %rax,%rdi
    jmpq   400700 <tree1>

So unless you carefully verify the generated assembly, you might end up measuring only half the calls you would expect. In this case it might not matter much (jmp and call are about equal in cost) but it's no longer actually measuring call/return overhead as the title says. Using '-O1' gave me the code closer to what one would expect.

From source code like this:

  COMPILER_NO_INLINE uint64_t f3( uint64_t x ) {
    return f2( f2( x ) ) + 1;
  }

  0000000000400720 <f2>:
  400720:       e8 db ff ff ff          callq  400700 <f1>
  400725:       48 89 c7                mov    %rax,%rdi
  400728:       e8 d3 ff ff ff          callq  400700 <f1>
  40072d:       48 83 c0 01             add    $0x1,%rax
  400731:       c3                      retq

  00000000004006f3 <f2>:
  4006f3:       e8 ea ff ff ff          callq  4006e2 <f1>
  4006f8:       48 89 c7                mov    %rax,%rdi
  4006fb:       e8 e2 ff ff ff          callq  4006e2 <f1>
  400700:       48 ff c0                inc    %rax
  400703:       c3                      retq

'icc -O3' produced strange code that ran slightly slower, at 4.5 cycles per call on Haswell, and 4.01 cycles on Sandy Bridge:

  0000000000400c90 <f2>:
  400c90:       56                      push   %rsi
  400c91:       e8 1a 00 00 00          callq  400cb0 <f1>
  400c96:       48 89 c7                mov    %rax,%rdi
  400c99:       e8 12 00 00 00          callq  400cb0 <f1>
  400c9e:       48 ff c0                inc    %rax
  400ca1:       59                      pop    %rcx
  400ca2:       c3                      retq

Clang also produces odd code with extra pushes and pops, but somehow achieves the same speed as GCC on Haswell despite this (3.67 cycles). Speed on Sandy Bridge was slow at 4.5 cycles:

  00000000004005c0 <f2>:
  4005c0:       50                      push   %rax
  4005c1:       e8 da ff ff ff          callq  4005a0 <f1>
  4005c6:       48 89 c7                mov    %rax,%rdi
  4005c9:       e8 d2 ff ff ff          callq  4005a0 <f1>
  4005ce:       48 ff c0                inc    %rax
  4005d1:       5a                      pop    %rdx
  4005d2:       c3                      retq

    void foo(int x) {
      char c[x]; 
      // . . .
    }

Would have loved a portable way to query how much stack space the process has left. The problem some architectures need not even have a stack.

@dbaupp Hey thanks ! and nice to know

  void foo(int x) {
    goto label;
    {
        char y[x];
  label:
        y[0] = 'a';
    }
  }

  alloca-goto.c: In function ‘foo’:
  alloca-goto.c:2:5: error: jump into scope of identifier with variably modified type
       goto label;
       ^
  alloca-goto.c:5:1: note: label ‘label’ defined here
   label:
   ^
  alloca-goto.c:4:14: note: ‘y’ declared here
           char y[x];
                ^

i tried it out in the browser, sum of fN(N) from [0..1000[ yields a ~2-3 times difference.