[Performance]: Compile time scales with number of reachable functions, dominated by native backend (LLVM + tket passes)

[ss2165]

Issue found and generated with help of copilot, edited by me

Performance Issue

Compiling a Guppy program to native code (fn.emulator(...)) is slow and grows roughly linearly with the number of distinct reachable functions in the program, on top of a fixed ~1s backend floor.

This surfaced while reviewing the std.collections.BTreeMap PR (#2083). The BTreeMap is built from ~30 small, mutually-recursive generic helper functions, and this makes even trivial usages very slow to compile:

Program	Compile	Emulate (run)
Trivial main (loop + sum)	~1.0s	~0.35s
BTreeMap[int,int,4] — single insert	~4.9s	~0.5s
BTreeMap[int,int,4] — insert+remove	~10.6s	~0.5s
BTreeMap[int,int,20] — insert/get/remove/iterate	~11.8s	~0.5s

As a consequence the BTreeMap integration tests take ~90s wall-clock, versus ~15s for the comparable stack/queue/priority-queue tests.

This appears to be an underlying compiler/backend scaling property, independent of BTreeMap. The MWE below reproduces it with no dependency on that PR.

Steps to Reproduce

Self-contained MWE. It generates a program from N small functions, each of which constructs a one-element array and reads it back, chained so all are reachable from main. A chain of the same shape without the array does not scale, so array usage is the trigger:

"""
Run:
    uv run python compile_scaling_mwe.py
"""

from __future__ import annotations

import importlib.util
import time

# Number of distinct reachable functions to generate for the scaling sweep.
SIZES = (1, 20, 40, 60)


def _write_module(n: int) -> str:
    """Emit a module with `n` tiny functions, chained so all are reachable from
    `main`. Each builds a one-element `array` and reads it back; that single
    `array` use per function is what the backend is slow to compile in bulk."""
    lines = [
        "from guppylang import guppy",
        "from guppylang.std.array import array",
        "from typing import no_type_check",
        "",
    ]
    for i in range(n):
        call = "buf[0]" if i == n - 1 else f"_g{i + 1}(buf[0])"
        lines += [
            "@guppy",
            "@no_type_check",
            f"def _g{i}(x: int) -> int:",
            "    buf = array(x for _ in range(1))",
            f"    return {call}",
            "",
        ]
    lines += ["@guppy", "@no_type_check", "def main() -> int:", "    return _g0(1)", ""]
    path = f"/tmp/_guppy_compile_mwe_{n}.py"
    with open(path, "w") as fh:
        fh.write("\n".join(lines))
    return path


def _compile_seconds(path: str, name: str) -> float:
    spec = importlib.util.spec_from_file_location(name, path)
    assert spec and spec.loader
    mod = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(mod)
    start = time.perf_counter()
    mod.main.emulator(0)  # build the emulator == full compile to native code
    return time.perf_counter() - start


def main() -> None:
    print(f"{'reachable funcs':>16} | {'compile (s)':>11}")
    print("-" * 32)
    for n in SIZES:
        path = _write_module(n)
        secs = _compile_seconds(path, f"_guppy_compile_mwe_{n}")
        print(f"{n:>16} | {secs:>11.2f}")


if __name__ == "__main__":
    main()

Run with uv run python compile_scaling_mwe.py.

Performance Metrics

MWE output (macOS, arm64):

reachable funcs | compile (s)
--------------------------------
              1 |        0.96
             20 |        1.25
             40 |        2.32
             60 |        3.36

Roughly linear in the number of reachable functions above a ~1s fixed floor.

Where the time goes (cProfile of the 60-function MWE; identical hotspots to the BTreeMap case):

• selene_hugr_qis_compiler.compile_to_bitcode (LLVM lowering) — ~2.3s
• tket passes _normalize — ~1.4s
• HUGR serialization (to_model round-trip) — ~1.3s

What is NOT the driver (ruled out by measurement):

• Monomorphization count — 8 distinct Stack[int, K] instantiations stayed flat at ~1.3s.
• Array element size — a one-element array[int, 1] per function is enough to trigger the scaling; the element type/size is not what matters.
• Function body complexity per se — a bare recursion/arithmetic chain of the same length does not scale (~0.4s at N=30). Introducing a single array per function is what makes it scale.

Expected Performance

A program of a few dozen small functions should compile in ~1-2s, not 5-14s. Ideally compile time for a test-sized program is dominated by the fixed backend floor rather than growing per-function, so integration suites built on library data structures don't become compile-bound.

Component

• Guppy Compiler

Environment

- guppylang version: 9ef99cdfe8689d087c337479d4a8414bf6ea4479
- Python version: 3.14.3
- OS: macOS 26.5.2 (arm64)
- hugr: 0.18.2
- selene-hugr-qis-compiler: 0.4.2
- tket: 0.15.4

[acl-cqc]

I''m a little suspicious here. This table:

reachable funcs | compile (s)
--------------------------------
              1 |        0.96
             20 |        1.25
             40 |        2.32
             60 |        3.36

doesn't mention "hugr size". AFAICS the code example (generator) will generate hugrs whose size is linear in the number of functions, so might the compile-time increase be purely a result of hugr size? It is difficult to imagine compiling a Hugr to LLVM in less than linear time unless we are making heavy use of parallelism.

Some of the other data/experiments ("ablation studies") suggest that it is not just hugr size; this would suggest that a test case where dividing the same code up between more functions, would slow down compilation. That would be an interesting result and, if demonstrated, my first suspicion would be function inlining (does turning inlining off cure the problem? If so it might be because more functions, especially depending on structure, leads to a much bigger hugr after inlining - perhaps super-linear - but perhaps reducing back to size linear in size of input after removing dead functions?).