6

What do we call "stack" in Python? Is it the C stack of CPython? I read that Python stackframes are allocated in a heap. But I thought the goal of a stack was... to stack stackframes. What does the stack do then?

Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
usual me
  • 8,338
  • 10
  • 52
  • 95
  • The answers to that question don't answer this question. Maybe it's closely-related enough that the right thing to do is to add a third answer over there and leave this closed as a dup… but I'm not sure. Voting to reopen. – abarnert Aug 23 '14 at 01:15

2 Answers2

10

Python's stack frames are allocated on the heap. But they are linked one to another to form a stack. When function a calls function b, the b stack frame points to the a stack frame as the next frame (technically, a is the f_back attribute of the b frame.)

Having stack frames allocated on the heap is what makes generators possible: when a generator yields a value, rather than discarding its stack frame, it's simply removed from the linked list of current stack frames, and saved off to the side. Then when the generator needs to resume, its stack frame is relinked into the stack, and its execution continues.

Ned Batchelder
  • 364,293
  • 75
  • 561
  • 662
  • Hi Ned. May I kindly ask you to confirm this sentence?: So we have a call stack of "frame objects" which is implemented using a linked-list in heap memory, now inside each individual frame objects, there are two other stacks named *"evaluation stack"* and *"block stack"*. We're dealing with 3 stacks here. is that correct? – S.B Jul 11 '23 at 12:27
  • ...And in fact both `PUSH` and `POP` functions (in `ceval.c`) put/remove something from this "evaluation stack"(a.k.a value stack). – S.B Jul 11 '23 at 15:06
5

Oversimplifying slightly:

In CPython, when PyEval_EvalFrameEx is evaluating a Python stack frame's code, and comes to a direct function call, it allocates a new Python stack frame, links it up… and then recursively calls PyEval_EvalFrameEx on that new frame.

So, the C stack is a stack of recursive calls of the interpreter loop.

The Python stack is a stack of Python frame objects, implemented as a simple linked list of heap-allocated objects.

They're not completely unrelated, but they're not the same thing.

When you use generators, this gets slightly more confusing, because those Python stack frames can be unlinked and relinked in different places when they're resumed. Which is why the two stacks are separate. (See Ned's answer, which explains this better than I could.)

abarnert
  • 354,177
  • 51
  • 601
  • 671