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:

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

• Bytecode compile times are O(nlocals**2) #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.
• tokenize.generate_tokens() performance regression in 3.12 #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-155525: Cover quadratic f-string tokenization regression #156756
• [3.15] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157828
• [3.14] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157829
• [3.13] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157830