Reducing stack consumption through overlapping frames

[markshannon]

In #31 (comment) I discussed various frame layout options and came to the conclusion that the most compact form, option A, was not viable as it required 3 pointers.

However, this is incorrect as it assumes that the stack must grow upward. There is no reason for this, most hardware stacks grow down.
With the frame stack growing down the frame would look this:

+---------------+
|    locals     |
+---------------+
|    linkage    |
+---------------+    <--- Frame pointer points here
|     stack     |
+---------------+

The downside of this scheme is the extra care we need to take when initializing locals from the stack as they overlap and overlap in reverse order. E.g take the call g(a,b) from a function f:

Before the call:

+---------------+
|   f locals    |
+---------------+
|   f linkage   |
+---------------+    <--- Frame pointer for 'f'
|       g       |
|       a       |
|       b       |
+---------------+

Once frame for g has been created:

+---------------+
|   f locals    |
+---------------+
|   f linkage   |
+---------------+    <--- Frame pointer for 'f'
|       g       |
+---------------+
|       a       |
|       b       |      Unitialized g's locals, holding the arguments
|      ---      |
+---------------+
|   g linkage   |
+---------------+    <--- Frame pointer for 'g'
|    g stack    |
+---------------+

The local variables for g need to reordered in place:

+---------------+
|   f locals    |
+---------------+
|   f linkage   |
+---------------+    <--- Frame pointer for 'f'
|       g       |
+---------------+
|      ---      |
|       b       |     g's locals in correct order
|       a       |
+---------------+
|   g linkage   |
+---------------+    <--- Frame pointer for 'g'
|    g stack    |
+---------------+

[markshannon]

The problem with the above design is that we would need to flip all the arguments to call a C function.
Flipping the whole stack (so it grows up again, but the locals go down) would solve that problem:

+---------------+
|    stack      |
+---------------+
|    linkage    |
+---------------+    <--- Frame pointer points here
|     locals    |
|  (grow down)  |
+---------------+

[gvanrossum]

Doesn't it have the same problem that the locals and the stack grow in opposite directions, so you always have to flip the arguments?

[markshannon]

For Python functions, yes. But we need to move them anyway: if frames don't overlap, we bulk copy, if they do overlap we flip them.

[markshannon]

I'm closing this for two reasons:

• Any call sequences that need argument shuffling, packing, or unpacking are made considerably more complex by overlapping frames.
• We expect that the tier2 optimizer will eliminate a good fraction of leaf function calls, reducing any possible performance benefit.