Block stack size for frame objects should be dynamically sizable

[tomkpz]

BPO	42917
Nosy	@gvanrossum, @gpshead, @markshannon, @serhiy-storchaka, @tomKPZ
PRs	bpo-42917: Made block stack for frame objects dynamically sizable #24204 bpo-42197: Don't create f_locals dictionary unless we actually need it. #32055

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2022-03-25.11:32:43.977>
created_at = <Date 2021-01-13.01:54:09.764>
labels = ['interpreter-core', 'type-feature', '3.10']
title = 'Block stack size for frame objects should be dynamically sizable'
updated_at = <Date 2022-03-25.11:32:43.976>
user = 'https://github.com/tomkpz'

bugs.python.org fields:

activity = <Date 2022-03-25.11:32:43.976>
actor = 'Mark.Shannon'
assignee = 'none'
closed = True
closed_date = <Date 2022-03-25.11:32:43.977>
closer = 'Mark.Shannon'
components = ['Interpreter Core']
creation = <Date 2021-01-13.01:54:09.764>
creator = 'tomkpz'
dependencies = []
files = []
hgrepos = []
issue_num = 42917
keywords = ['patch']
message_count = 10.0
messages = ['384991', '385111', '385120', '385125', '385409', '388697', '388698', '388715', '388747', '415993']
nosy_count = 6.0
nosy_names = ['gvanrossum', 'gregory.p.smith', 'Mark.Shannon', 'python-dev', 'serhiy.storchaka', 'tomkpz']
pr_nums = ['24204', '32055']
priority = 'normal'
resolution = 'out of date'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue42917'
versions = ['Python 3.10']

[tomkpz]

Currently the block stack size is hardcoded to 20. Similar to how the value stack is dynamically sizable, we should make the block stack dynamically sizable. This will reduce space on average (since the typical number of blocks for a function is well below 20) and allow code generators to generate code with more deep nesting. Note: the motivation is not necessarily to reduce memory usage, but to make L1 cache misses less likely for stack objects.

[markshannon]

Reducing the size of the frame object seems like a worthwhile goal, but what's the point in increasing the maximum block stack?

[serhiy-storchaka]

Getting rid of hardcoded limits is good. And at first look the proposed PR looks good (some minor details can be discussed).

Although there is different approach to solve the same problem. The stack of blocks is used to set handlers for exceptions. For example, when enter the try block, it pushes the handler that points to except and/or finally clauses, when enter the with block, it pushes the handler that calls __exit__, etc. The stack of handlers is changed at run time, and it was the only solution to this problem. But after reorganizes of bytecode in latest Python versions (mainly by Mark) it is now possible to determine handlers for every instruction statically, at compile time. Instead of stack of blocks we would have a table of addresses of handlers. It is more efficient approach and it is used in modern C++ compilers. The only technical issue is compact and platform-independent representation of the table (because the size of the uncompressed table would be larger than the size of the code, but most of entries are repeated and usually are small integers).

It would make PR 24204 unneeded, so I suggest to wait some time before reviewing it.

[tomkpz]

Reducing the size of the frame object seems like a worthwhile goal, but what's the point in increasing the maximum block stack?

No point for humans, but it may be useful for code generators.

[markshannon]

I see no advantage of getting rid of the limit of 20.

No one ever gets near 20 deep in practice.
Given the limit has been there for so long, it is likely that some tooling that expects the depth of try-statements to be limited.

Why would a code generator need to nest try statements so deeply? I'm curious.

[tomkpz]

IIRC, some transpilers for functional languages create deeply nested code. In particular for things like haskell's do notation.

Anyway, when I wrote the PR, it was initially to reduce the frame size. Then once I had dynamic block stack sizing working, I realized there was no longer a need to keep the limit of 20 blocks. It was just compile.c that had the artificial limit, so I removed it. I can add the limit back in the PR, but I'm not sure what benefit that would give.

[gvanrossum]

I don't see what putting the limit back in this PR would give, but I do question that we need more block nesting, and this PR causes a lot of code churn (including a new API to create frames). It would be more convincing if you could actually point to a code generator that would benefit, rather than hand-waving "code generators might use it."

I'm also not sure that we'll see measurable benefits in terms of memory access locality. Have you tried to benchmark this? Even a micro-benchmark aiming to show there is *some* effect would be helpful.

At the same time I'm intrigued by Serhiy's idea, which could well reduce the size of the bytecode and the cost of instruction decoding by avoiding all dynamic block stack manipulation.

There are also other ideas floating about for improving memory locality related to the frame stack, e.g. putting the stack frames in an array instead of a linked list.

[serhiy-storchaka]

There are also other ideas floating about for improving memory locality related to the frame stack, e.g. putting the stack frames in an array instead of a linked list.

Would it work with generators and coroutines?

[gvanrossum]

Yes, if we keep the top of the stack and the current frame in separate
variables.--
--Guido (mobile)