Argument Unpacking wastes Stack Frames

Question

When a function is called by unpacking arguments, it seems to increase the recursion depth twice. I would like to know why this happens.

Normally:

depth = 0

def f():
    global depth
    depth += 1
    f()

try:
    f()
except RuntimeError:
    print(depth)

#>>> 999

With an unpacking call:

depth = 0

def f():
    global depth
    depth += 1
    f(*())

try:
    f()
except RuntimeError:
    print(depth)

#>>> 500

In theory both should reach about 1000:

import sys
sys.getrecursionlimit()
#>>> 1000

This happens on CPython 2.7 and CPython 3.3.

On PyPy 2.7 and PyPy 3.3 there is a difference, but it is much smaller (1480 vs 1395 and 1526 vs 1395).

---

As you can see from the disassembly, there is little difference between the two, other than the type of call (CALL_FUNCTION vs CALL_FUNCTION_VAR):

import dis

def f():
    f()

dis.dis(f)
#>>>  34           0 LOAD_GLOBAL              0 (f)
#>>>               3 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
#>>>               6 POP_TOP
#>>>               7 LOAD_CONST               0 (None)
#>>>              10 RETURN_VALUE

def f():
    f(*())

dis.dis(f)
#>>>  47           0 LOAD_GLOBAL              0 (f)
#>>>               3 BUILD_TUPLE              0
#>>>               6 CALL_FUNCTION_VAR        0 (0 positional, 0 keyword pair)
#>>>               9 POP_TOP
#>>>              10 LOAD_CONST               0 (None)
#>>>              13 RETURN_VALUE

Answer 1

The exception message actually offers you a hint. Compare the non-unpacking option:

>>> import sys
>>> sys.setrecursionlimit(4)  # to get there faster
>>> def f(): f()
... 
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
RuntimeError: maximum recursion depth exceeded

with:

>>> def f(): f(*())
... 
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
RuntimeError: maximum recursion depth exceeded while calling a Python object

Note the addition of the while calling a Python object. This exception is specific to the PyObject_CallObject() function. You won't see this exception when you set an odd recursion limit:

>>> sys.setrecursionlimit(5)
>>> f()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in f
  File "<stdin>", line 1, in f
RuntimeError: maximum recursion depth exceeded

because that is the specific exception raised in the ceval.c frame evaluation code inside PyEval_EvalFrameEx():

/* push frame */
if (Py_EnterRecursiveCall(""))
    return NULL;

Note the empty message there. This is a crucial difference.

For your 'regular' function (no variable arguments), what happens is that an optimized path is picked; a Python function that doesn't need tuple or keyword argument unpacking support is handled directly in the fast_function() function of the evaluation loop. A new frameobject with the Python bytecode object for the function is created, and run. This is one recursion check.

But for a function call with variable arguments (tuple or dictionary or both), the fast_function() call cannot be used. Instead, ext_do_call() (extended call) is used, which handles the argument unpacking, then uses PyObject_Call() to invoke the function. PyObject_Call() does a recursion limit check, and 'calls' the function object. The function object is invoked via the function_call() function, which calls PyEval_EvalCodeEx(), which calls PyEval_EvalFrameEx(), which makes the second recursion limit check.

TL;DR version

Python functions calling Python functions are optimised and bypass the PyObject_Call() C-API function, unless argument unpacking takes place. Both Python frame execution and PyObject_Call() make recursion limit tests, so bypassing PyObject_Call() avoids incrementing the recursion limit check per call.

More places with 'extra' recursion depth checks

You can grep the Python source code for Py_EnterRecursiveCall for other locations where recursion depth checks are made; various libraries, such as json and pickle use it to avoid parsing structures that are too deeply nested or recursive, for example. Other checks are placed in the list and tuple __repr__ implementations, rich comparisons (__gt__, __lt__, __eq__, etc.), handling the __call__ callable object hook and handling __str__ calls.

As such, you can hit the recursion limit much faster still:

>>> class C:
...     def __str__(self):
...         global depth
...         depth += 1
...         return self()
...     def __call__(self):
...         global depth
...         depth += 1
...         return str(self)
... 
>>> depth = 0
>>> sys.setrecursionlimit(10)
>>> C()()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 9, in __call__
  File "<stdin>", line 5, in __str__
RuntimeError: maximum recursion depth exceeded while calling a Python object
>>> depth
2