Quadratic `compile()` / `ast.parse()` time for modules with many f-strings (PEP 701 tokenizer `update_fstring_expr` rescans the whole remaining buffer per replacement field)

Bug report

Bug description:

Summary

Since the PEP 701 f-string tokenizer landed in 3.12, parsing/compiling a module that contains many f-string replacement fields is O(n²) in the total source size, where the constant is driven by the number of {...} fields. This is pure front-end (tokenizer) time — it reproduces with compile(src, "<x>", "exec") and ast.parse(src) and is unaffected by any optimization level.

It is not visible on ordinary hand-written code, but it is catastrophic for large machine-generated modules. A ~20 MB generated module in our codebase (~10k f-strings, up to ~230 plain {field}s each) compiles in:

Python	compile() of the 20 MB module
3.9.18	~2.3 s
3.12.4	~229 s
3.13.5	~376 s (worse)

Environment

• Reproduced on CPython 3.12.4 and 3.13.5 (Linux x86-64).
• Confirmed by source inspection to be present on main (3.14-dev) as well (see Root cause).

Minimal reproducer

Dependency-free. Run under 3.11 (or 3.9) vs 3.12+ and compare — the f-string compile time roughly quadruples each time the size doubles on 3.12+, but only doubles on ≤3.11.

import sys, time

def gen(n_fstrings, fields_each=100):
    # one module of `n_fstrings` f-strings, each with `fields_each` PLAIN replacement fields
    # (no format-spec, no conversion, no nesting). Names need not exist -- compile() only parses.
    field = "".join("{x%d}" % i for i in range(fields_each))
    return "\n".join('s%d = f"%s"' % (j, field) for j in range(n_fstrings))

print(sys.version)
prev = None
for n in (500, 1000, 2000, 4000):
    src = gen(n)
    t0 = time.perf_counter()
    compile(src, "<gen>", "exec")
    dt = time.perf_counter() - t0
    ratio = "" if prev is None else "  (%.1fx for 2x size)" % (dt / prev)
    print("%5d f-strings, %5.0f KB: %7.3f s%s" % (n, len(src) / 1024, dt, ratio))
    prev = dt

Observed output

Python 3.9.18 — linear (~2x per size doubling):

500 f-strings,   298 KB:   0.199 s
1000 f-strings,  595 KB:   0.404 s  (2.0x for 2x size)
2000 f-strings, 1190 KB:   0.787 s  (1.9x for 2x size)
4000 f-strings, 2382 KB:   1.573 s  (2.0x for 2x size)

Python 3.12.4 — quadratic (~4x per size doubling):

500 f-strings,   298 KB:   0.592 s
1000 f-strings,  595 KB:   2.109 s  (3.6x for 2x size)
2000 f-strings, 1190 KB:   8.484 s  (4.0x for 2x size)
4000 f-strings, 2382 KB:  32.497 s  (3.8x for 2x size)

So the same 2.4 MB source is ~21x slower on 3.12 than 3.9 (1.57 s → 32.5 s), and the gap keeps widening with size.

For comparison, rewriting the f-strings to str.format() (same source size) stays linear/fast on 3.12 (~0.78 s at the 4000 row) — i.e. the cost is specifically in the f-string tokenization path.

Root cause

The PEP 701 tokenizer buffers each f-string replacement-field expression by copying from the current cursor to the end of the remaining source buffer on every relevant token, using strlen(tok->cur) + strncpy(..., tok->cur, size):

3.12.4 — Parser/tokenizer.c, update_fstring_expr():

static int
update_fstring_expr(struct tok_state *tok, char cur)
{
    Py_ssize_t size = strlen(tok->cur);          // <-- length to END OF BUFFER, not end of expr
    tokenizer_mode *tok_mode = TOK_GET_MODE(tok);
    switch (cur) {
       case 0:
            ...
            strncpy(tok_mode->last_expr_buffer + tok_mode->last_expr_size, tok->cur, size);  // O(remaining)
            ...
        case '{':
            ...
            tok_mode->last_expr_buffer = PyMem_Malloc(size);
            ...
            strncpy(tok_mode->last_expr_buffer, tok->cur, size);   // O(remaining)
            ...
        case '}': case '!': case ':':
            if (tok_mode->last_expr_end == -1) {
                tok_mode->last_expr_end = strlen(tok->start);      // O(remaining)
            }
            ...
    }
}

It is called once per { / } / ! / : inside an f-string. Because size = strlen(tok->cur) is the distance to EOF, each replacement field near the top of a large module scans/copies almost the entire remaining file. Summed over all fields:

Σ_fields  remaining_bytes_after_field  ≈  O(source_size × num_fields)  ≈  O(n²)

A perf / gdb profile of the 20 MB case spends ~99% of time in __strlen_evex / __strncpy_evex reached from update_fstring_expr.

The same code (whole-remaining-buffer strlen(tok->cur) + strncpy) is still present, just relocated/renamed, in every current branch:

• 3.12: Parser/tokenizer.c:466 — update_fstring_expr (strlen(tok->cur) @470, strncpy @487/@500)
• 3.13: Parser/lexer/lexer.c:176 — _PyLexer_update_fstring_expr (strlen(tok->cur) @180)
• main (3.14-dev): Parser/lexer/string.c:124 — _PyLexer_update_ftstring_expr (strlen(tok->cur) @128, strncpy @145/@158)

Possible direction (for maintainers to evaluate)

update_fstring_expr runs unconditionally for every field, but the buffer it builds (last_expr_buffer) appears to be consumed only by set_fstring_expr() to produce the = self-documenting-expression debug metadata — and set_fstring_expr() early-returns unless tok_mode->f_string_debug is set. So:

1. In the common case (f_string_debug == 0, i.e. no = specifier — which is the vast majority of f-strings, and all of the generated code above), the whole per-field strlen/strncpy work is discarded. Gating update_fstring_expr on f_string_debug would make that case linear.
2. Even when debug is used, the copy is sized to strlen(tok->cur) (to EOF) rather than to the actual expression length; capturing only the expression span (start already known; end set on }/:/!) would remove the quadratic factor there too.

Not a duplicate of

• gh-97912 (quadratic in number of local variables / nlocals²) — different mechanism, in the compiler not the tokenizer, and fixed before 3.12.0. Setting optimize=2 does not help here.
• gh-119118 (tokenize.generate_tokens() performance regression in 3.12) — that is the pure-Python tokenize API and a different trigger (one huge single-line dict). This report is the C tokenizer used by compile() / ast.parse(), triggered by many f-string replacement fields via update_fstring_expr. (Similar "3.12 tokenizer change + generated input + repeated scan → superlinear" shape, hence worth cross-referencing as precedent, but a distinct code path.)

CPython versions tested on:

3.12

Operating systems tested on:

Linux

Linked PRs

• gh-156756

Beginne mit Parser/lexer/string.c auf main und vergleiche anschließend den entsprechenden Code in Parser/lexer/lexer.c und Parser/tokenizer.c für 3.12. Führe den reproduzierbaren Fall ohne Abhängigkeiten mit compile() und ast.parse() über die betroffenen Versionen hinweg aus. Als erledigt gilt die Aufgabe, wenn die gemeldete Workload für generierte Module keine quadratische Skalierung mehr zeigt und das Parsing-Verhalten von f-strings weiterhin durch die entsprechenden Parser-Tests abgedeckt ist.