Photo by Kaique Rocha Generator Functions are one of the coolest features of the Python programming language. There are numerous articles on the web describing the many benefits generator functions provide in terms of speed, scalability and memory efficiency of our python programs. However, there is not much material out there which sheds light on how generator functions actually work behind the scenes. This article attempts to fill this void by shedding light on some of the key features of the python programming language which make generator functions possible. The fundamental feature which gives generator functions their superpowers is the ability that a generator function can be and then at any time from any function. The local state of the generator function is kept intact after the function is paused and is available when the function is resumed again. How is that possible? How can a function be paused and then resumed with its local state kept intact? For all that we know, functions have a single and multiple points ( statements). Each time we call a function, the code executes beginning from the first line of the function until it encounters an exit point. At that juncture, control is returned to the caller of the function and the function’s stack of local variables is cleared and the associated memory reclaimed by the OS. paused resumed entry point exit return Generator functions however don’t behave this way. They have entry and exit points. Each statement in a generator function simultaneously defines an exit point and a re-entry point. Execution of a generator function continues until a statement is encountered. At that point, the local state of the function is preserved and the flow of control is yielded to the caller of the generator function. When the generator function is resumed (by calling , or by iterating through a it’s last known local state is conjured up and execution begins from the line following the statement at which the generator function was last paused. This behavior is quite mind boggling and does not conform to how functions normally behave. multiple yield yield next send for loop ), yield To try and understand the magic behind generator functions, let’s begin by taking a closer look at a normal function: Each time is called, we expect the CPython interpreter to create a new stack frame object and execute the function in the context of this object. We expect the local variable to get pushed onto this stack frame and remain there until the function exits. At function exit, we expect the associated stack frame to be cleared out and the corresponding memory to be reclaimed. Let’s confirm that this is the case: add_two_numbers add_two_numbers s We use the builtin module to capture the current frame of execution of the function. Towards the end , we print the stack frame object and any local variables associated with it. We would expect the stack frame to be empty and consequently have no local variables. Let’s go ahead and execute the above the code snippet: inspect add_two_numbers WHAT?! The stack frame and all its associated local variables are still hanging around after the call to the concludes! What is happening here? Have we stumbled across a memory leak in CPython? No, that is not the case. This observation leads us to one of the fundamental characteristics of Python stack frames: . What this essentially means is that python stack frames can outlive their respective function calls! Generator functions leverage this behavior to do their magic. add_two_numbers Python stack frames are not allocated on stack memory. Instead, they are allocated on heap memory When the CPython compiler encounters the statement in a function, it sets a flag on the compiled to tell the CPython interpreter that the function is a generator function. We can use the module to see this in action: yield code object dis When the CPython interpreter sees the flag on the code object associated with a function, it does not execute the function but instead returns a generator object. The generator object is an iterator. Which means that we can iterate through it using the next keyword or a for loop. GENERATOR As we iterate through the generator function, execution continues until a statement is encountered. At that point, the stack frame of the function is frozen and control is returned back to the caller of the generator function. yield As we continue advancing through the generator function by calling or via execution begins precisely from the point where it last left off ( the last statement). How does the CPython interpreter know where execution of an instance of a generator function was last stopped? It knows this via the stack frame object associated with the generator instance being executed. next for loop , yield We saw earlier that Python stack frames are allocated on heap memory and their state is preserved between subsequent calls to or on an instance of a generator function (Of Course each new instance of a generator function gets a new stack frame). Besides storing information about the local and global variables, a python stack frame encapsulates other useful bits of information. One such piece of information is the . next send last instruction pointer The is an index into the bytecode string of the code object associated with the body of the generator function and points to the last bytecode instruction that was run within the context of a stack frame. When an instance of a generator function is resumed, the CPython interpreter uses the on the associated stack frame to determine where to begin executing the code object of the generator function . We can see this interactively using the handy method provided by the module : last instruction pointer last instruction pointer disco dis We create a simple generator function that yields two numbers. Calling the generator function creates and returns a generator object. No code in the generator function’s body gets executed during this call and the is initialized to -1. As we begin executing the generator function by calling next, the advances from one yield statement to another (current position of the after each call to next denoted by → in the above code snippets), pausing and then resuming from the same point, until the generator function is exhausted and a StopIteration exception is thrown. last instruction pointer last instruction pointer last instruction pointer Wrapping it up, the key thing to remember is that python generators encapsulate a stack frame and a code object. The stack frame is allocated on heap memory and holds a pointer to the last bytecode instruction that was run on a code object within the context of the stack frame. It is the last instruction pointer which tells the CPython interpreter which line to execute next when a generator function is resumed. These are the core building blocks over which generator functions thrive. If you are feeling adventurous, you can take at the function in and the module in the CPython source to see the implementation details. This blog was written using the source for CPython 3.6. _PyEval_EvalCodeWithName Python/ceval.c Python/genobject.c If generator functions were a mystery to you, hopefully this post has helped offer some clarity on how generator functions work.
