Python Call Stack

Why function calls aren't free

4 January 2019

Tiago "Myhro" Ilieve

DevOps Engineer, Zalando SE

Python memory management

2

Stack frames

Also known as "activation records" or "activation frames", (basically) composed of:

3

PyFrameObject

Include/frameobject.h, lines 17 to 53:

Total: 129 bytes (on x86_64)

4

Factorial example

Loop: 

def factorial(n):
    r = 1
    while n > 0:
        r *= n
        n -= 1
    return r

Recursion: 

def rec_factorial(n):
    if n == 1:
        return 1
    return n * rec_factorial(n - 1)
5

Benchmark

Measured using IPython's %timeit built-in magic command: 

In [1]: %timeit factorial(5)
485 ns ± 1.85 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [2]: %timeit rec_factorial(5)
704 ns ± 2.49 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [3]: %timeit factorial(10)
902 ns ± 27.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: %timeit rec_factorial(10)
1.41 µs ± 6.95 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [5]: %timeit factorial(100)
10.4 µs ± 96 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [6]: %timeit rec_factorial(100)
15.9 µs ± 276 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
6

References

Python/C API Reference Manual - Memory Management
Python memory management - The Run-time stack and the Heap

7

Thank you

Tiago "Myhro" Ilieve

DevOps Engineer, Zalando SE

https://blog.myhro.info/

@myhro

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)