python - Argumento Desembalaje de desechos Marcos de pila

recursion cpython

Question

Cuando se llama a una función desempacando argumentos, parece aumentar la profundidad de recursión dos veces. Me gustaría saber por qué sucede esto.

Normalmente:

depth = 0

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

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

#>>> 999

Con una llamada de desembalaje:

depth = 0

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

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

#>>> 500

En teoría, ambos deberían alcanzar alrededor de 1000:

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

Esto sucede en CPython 2.7 y CPython 3.3.

En PyPy 2.7 y PyPy 3.3 hay una diferencia, pero es mucho más pequeña (1480 vs 1395 y 1526 vs 1395).

Como puede ver en el desmontaje, hay poca diferencia entre los dos, además del tipo de llamada ( 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

El mensaje de excepción en realidad le ofrece una pista. Compare la opción de no desembalaje:

>>> 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

con:

>>> 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

Tenga en cuenta la adición de while calling a Python object . Esta excepción es específica de la función PyObject_CallObject() . No verá esta excepción cuando configure un límite de recursión impar :

>>> 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

porque esa es la excepción específica planteada en el código de evaluación de marcos PyEval_EvalFrameEx() dentro de PyEval_EvalFrameEx() :

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

Tenga en cuenta el mensaje vacío allí. Esta es una diferencia crucial.

Para su función ''regular'' (sin argumentos variables), lo que sucede es que se selecciona una ruta optimizada ; una función de Python que no necesita el argumento tuple o palabra clave desempaquetar soporte se maneja directamente en la función fast_function() del bucle de evaluación. Se crea un nuevo objeto de cuadro con el objeto bytecode de Python para la función y se ejecuta. Esta es una verificación de recursión.

Pero para una llamada de función con argumentos variables (tupla o diccionario o ambos), la llamada fast_function() no se puede usar. En su lugar, se ext_do_call() (llamada extendida) , que maneja el desempaquetado del argumento, luego usa PyObject_Call() para invocar la función. PyObject_Call() realiza una comprobación de límite de recursividad y ''llama'' al objeto de función. El objeto de función se invoca a través de la function_call() , que llama a PyEval_EvalCodeEx() , que llama a PyEval_EvalFrameEx() , que hace la segunda comprobación de límite de recursión.

TL; versión DR

Las funciones de Python que llaman a las funciones de Python están optimizadas y pasan por alto la función API API de PyObject_Call() , a menos que tenga lugar el desempaquetado de argumentos. Tanto la ejecución del marco de Python como PyObject_Call() realizan pruebas de límite de recursividad, por lo que eludir PyObject_Call() evita incrementar el control de límite de recursión por llamada.

Más lugares con controles de profundidad de recursividad ''adicionales''

Puede grep el código fuente de Python para Py_EnterRecursiveCall para otras ubicaciones donde se realizan comprobaciones de profundidad de recursión; varias bibliotecas, como json y pickle usan para evitar el análisis de estructuras que están demasiado anidadas o recursivas, por ejemplo. Se colocan otras comprobaciones en la list y en las implementaciones tuple __repr__ , en las comparaciones enriquecidas ( __gt__ , __lt__ , __eq__ , etc.), en el manejo del __call__ objeto invocable y en el manejo __str__ llamadas.

Como tal, puedes alcanzar el límite de recursión mucho más rápido aún :

>>> 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