`[mypyc]` indexing fixed-length tuples is extremely slow and gets slower with increse in length

[Bobronium]

Bug Report

indexing fixed-length tuples is extremely slow and gets slower with increse in length

To Reproduce

cat reproduce.py

import timeit
from typing import Final

# fmt: off
FixedLength256 = tuple[
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int
]
FixedLength128 = tuple[
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int
]
FixedLength64 = tuple[
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int
]
FixedLength32 = tuple[
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int,
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int
]
FixedLength16 = tuple[
    int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int
]
FixedLength8 = tuple[int, int, int, int, int, int, int, int]
FixedLength4 = tuple[int, int, int, int]
FixedLength2 = tuple[int, int]
FixedLength1 = tuple[int]
# fmt: on
FIXED_LENGTH_256: Final[FixedLength256] = (0,) * 256
FIXED_LENGTH_128: Final[FixedLength128] = (0,) * 128
FIXED_LENGTH_64: Final[FixedLength64] = (0,) * 64
FIXED_LENGTH_32: Final[FixedLength32] = (0,) * 32
FIXED_LENGTH_16: Final[FixedLength16] = (0,) * 16
FIXED_LENGTH_8: Final[FixedLength8] = (0,) * 8
FIXED_LENGTH_4: Final[FixedLength4] = (0,) * 4
FIXED_LENGTH_2: Final[FixedLength2] = (0,) * 2
FIXED_LENGTH_1: Final[FixedLength1] = (0,) * 1

VARIABLE_LENGTH_256: Final[tuple[int, ...]] = (0,) * 256
VARIABLE_LENGTH_128: Final[tuple[int, ...]] = (0,) * 128
VARIABLE_LENGTH_64: Final[tuple[int, ...]] = (0,) * 64
VARIABLE_LENGTH_32: Final[tuple[int, ...]] = (0,) * 32
VARIABLE_LENGTH_16: Final[tuple[int, ...]] = (0,) * 16
VARIABLE_LENGTH_8: Final[tuple[int, ...]] = (0,) * 8
VARIABLE_LENGTH_4: Final[tuple[int, ...]] = (0,) * 4
VARIABLE_LENGTH_2: Final[tuple[int, ...]] = (0,) * 2
VARIABLE_LENGTH_1: Final[tuple[int, ...]] = (0,) * 1


def loop_fixed_length_256() -> None:
    for i in range(256):
        FIXED_LENGTH_256[i]


def loop_variable_length_256() -> None:
    for i in range(256):
        VARIABLE_LENGTH_256[i]


def loop_fixed_length_128() -> None:
    for _ in range(2):  # normalize against largest
        for i in range(128):
            FIXED_LENGTH_128[i]


def loop_variable_length_128() -> None:
    for _ in range(2):
        for i in range(128):
            VARIABLE_LENGTH_128[i]


def loop_fixed_length_64() -> None:
    for _ in range(4):
        for i in range(64):
            FIXED_LENGTH_64[i]


def loop_variable_length_64() -> None:
    for _ in range(4):
        for i in range(64):
            VARIABLE_LENGTH_64[i]


def loop_fixed_length_32() -> None:
    for _ in range(8):
        for i in range(32):
            FIXED_LENGTH_32[i]


def loop_variable_length_32() -> None:
    for _ in range(8):
        for i in range(32):
            VARIABLE_LENGTH_32[i]


def loop_fixed_length_16() -> None:
    for _ in range(16):
        for i in range(16):
            FIXED_LENGTH_16[i]


def loop_variable_length_16() -> None:
    for _ in range(16):
        for i in range(16):
            VARIABLE_LENGTH_16[i]


def loop_fixed_length_8() -> None:
    for _ in range(32):
        for i in range(8):
            FIXED_LENGTH_8[i]


def loop_variable_length_8() -> None:
    for _ in range(32):
        for i in range(8):
            VARIABLE_LENGTH_8[i]


def loop_fixed_length_4() -> None:
    for _ in range(64):
        for i in range(4):
            FIXED_LENGTH_4[i]


def loop_variable_length_4() -> None:
    for _ in range(64):
        for i in range(4):
            VARIABLE_LENGTH_4[i]


def loop_fixed_length_2() -> None:
    for _ in range(128):
        for i in range(2):
            FIXED_LENGTH_2[i]


def loop_variable_length_2() -> None:
    for _ in range(128):
        for i in range(2):
            VARIABLE_LENGTH_2[i]


def loop_fixed_length_1() -> None:
    for _ in range(256):
        FIXED_LENGTH_1[0]


def loop_variable_length_1() -> None:
    for _ in range(256):
        VARIABLE_LENGTH_1[0]


def bench() -> None:
    pairs = [
        ("256", loop_fixed_length_256, loop_variable_length_256),
        ("128", loop_fixed_length_128, loop_variable_length_128),
        ("64", loop_fixed_length_64, loop_variable_length_64),
        ("32", loop_fixed_length_32, loop_variable_length_32),
        ("16", loop_fixed_length_16, loop_variable_length_16),
        ("8", loop_fixed_length_8, loop_variable_length_8),
        ("4", loop_fixed_length_4, loop_variable_length_4),
        ("2", loop_fixed_length_2, loop_variable_length_2),
        ("1", loop_fixed_length_1, loop_variable_length_1),
    ]

    header = f"{'Length':<6} | {'Fixed (ms)':>12} | {'Variable (ms)':>14} | {'Ratio (V/F)':>10}"
    print(header)
    print("-" * len(header))

    for length, fixed_func, variable_func in pairs:
        fixed_time = timeit.timeit(fixed_func, number=10_000)
        variable_time = timeit.timeit(variable_func, number=10_000)
        ratio = variable_time / fixed_time if fixed_time != 0 else float("inf")
        print(
            f"{length:<6} | {fixed_time * 1000:12.3f} | {variable_time * 1000:14.3f} | {ratio:10.3f}"
        )

mypyc reproduce.py

running build_ext
building 'reproduce' extension
clang -fno-strict-overflow -Wsign-compare -Wunreachable-code -DNDEBUG -g -O3 -Wall -arch arm64 -mmacosx-version-min=11.0 -Wno-nullability-completeness -Wno-expansion-to-defined -Wno-undef-prefix -fPIC -Werror=unguarded-availability-new -I/Users/bobronium/dev/py/duper/.venv/lib/python3.12/site-packages/mypyc/lib-rt -I/Users/bobronium/dev/py/duper/.venv/include -I/Users/bobronium/.local/share/uv/python/cpython-3.12.5-macos-aarch64-none/include/python3.12 -c build/__native.c -o build/temp.macosx-11.0-arm64-cpython-312/build/__native.o -O3 -g1 -Werror -Wno-unused-function -Wno-unused-label -Wno-unreachable-code -Wno-unused-variable -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-but-set-variable -Wno-ignored-optimization-argument -Wno-cpp
clang -bundle -undefined dynamic_lookup -arch arm64 -mmacosx-version-min=11.0 -LModules/_hacl build/temp.macosx-11.0-arm64-cpython-312/build/__native.o -L/install/lib -o build/lib.macosx-11.0-arm64-cpython-312/reproduce.cpython-312-darwin.so
ld: warning: search path 'Modules/_hacl' not found
ld: warning: search path '/install/lib' not found
copying build/lib.macosx-11.0-arm64-cpython-312/reproduce.cpython-312-darwin.so -> 

python -c 'from reproduce import bench; bench()'

Length |   Fixed (ms) |  Variable (ms) | Ratio (F/V)
----------------------------------------------------
256    |     2625.639 |          6.894 |    380.847
128    |     1403.156 |          7.195 |    195.024
64     |      883.360 |          7.535 |    117.228
32     |      356.185 |          8.084 |     44.058
16     |      175.171 |          7.439 |     23.547
8      |      114.896 |          8.011 |     14.343
4      |      101.696 |          8.443 |     12.045
2      |       71.238 |          9.199 |      7.744
1      |        7.490 |         12.126 |      0.618

Expected Behavior
Fixed-length tuples behave faster or equal to variable-length tuples.

Actual Behavior
See output above: only case when fixed-length tuple is faster is when its length is 1. At length of 2, indexing fixed-length tuple is 7 times slower than variable-length one.

Your Environment

• Mypy version used: mypy 1.17.0 and 1.14.1
• Mypy command-line flags:
• Mypy configuration options from mypy.ini (and other config files):

pyproject.toml

[tool.mypy]
disallow_any_unimported = true
disallow_any_decorated = true
disallow_any_generics = true
disallow_subclassing_any = true

# Untyped definitions and calls
disallow_untyped_calls = true
disallow_untyped_defs = true
disallow_incomplete_defs = true
check_untyped_defs = true
disallow_untyped_decorators = true

# None and Optional handling
no_implicit_optional = true
strict_optional = true

# Configuring warnings
warn_redundant_casts = true
warn_unused_ignores = true
warn_no_return = true
warn_return_any = true
warn_unreachable = true
warn_incomplete_stub = true
warn_unused_configs = true

# Suppressing errors
ignore_errors = false
enable_error_code = "ignore-without-code"

# Miscellaneous strictness flags
allow_untyped_globals = false
allow_redefinition = false
local_partial_types = false
implicit_reexport = false
strict_equality = true
strict = true
# enable once this is resolved: https://github.com/python/mypy/issues/14796
# no_silence_site_packages = true

# Configuring error messages
show_error_context = false
show_column_numbers = false
show_error_codes = true
color_output = true
error_summary = true

• Python version used: 3.12.5

[sterliakov]

To add another datapoint. Py3.13, linux,

$ sudo lshw -C cpu
  *-cpu                     
       description: CPU
       product: Intel(R) Core(TM) i3-8145U CPU @ 2.10GHz
       vendor: Intel Corp.
       physical id: 4
       bus info: cpu@0
       version: 6.142.11
       serial: To Be Filled By O.E.M.
       slot: U3E1
       size: 3829MHz
       capacity: 4005MHz
       width: 64 bits
       clock: 100MHz
       capabilities: lm fpu fpu_exception wp vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp x86-64 constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi md_clear flush_l1d arch_capabilities cpufreq
       configuration: cores=2 enabledcores=2 microcode=246 threads=4

Compiled results:

$ MYPYC_OPT_LEVEL=3 mypyc rep.py
running build_ext
building 'rep' extension
creating build/temp.linux-x86_64-cpython-313/build
cc -pthread -fno-strict-overflow -Wsign-compare -Wunreachable-code -DNDEBUG -g -O3 -Wall -fPIC -fPIC -I/home/stas/Documents/Work/mypy/mypyc/lib-rt -I/tmp/tmp.itwiE4exHE/.venv/include -I/home/stas/.local/share/uv/python/cpython-3.13.3-linux-x86_64-gnu/include/python3.13 -c build/__native.c -o build/temp.linux-x86_64-cpython-313/build/__native.o -O3 -g1 -Werror -Wno-unused-function -Wno-unused-label -Wno-unreachable-code -Wno-unused-variable -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-but-set-variable -Wno-ignored-optimization-argument -Wno-cpp
creating build/lib.linux-x86_64-cpython-313
cc -pthread -shared -Wl,--exclude-libs,ALL -LModules/_hacl build/temp.linux-x86_64-cpython-313/build/__native.o -L/home/stas/.local/share/uv/python/cpython-3.13.3-linux-x86_64-gnu/lib -o build/lib.linux-x86_64-cpython-313/rep.cpython-313-x86_64-linux-gnu.so
copying build/lib.linux-x86_64-cpython-313/rep.cpython-313-x86_64-linux-gnu.so ->
$ python -c 'from rep import bench; bench()'
Length |   Fixed (ms) |  Variable (ms) | Ratio (V/F)
----------------------------------------------------
256    |     4349.421 |         11.004 |      0.003
128    |     2141.691 |         11.673 |      0.005
64     |     1114.604 |         12.027 |      0.011
32     |      564.822 |         11.725 |      0.021
16     |      276.040 |         13.144 |      0.048
8      |      170.304 |         12.554 |      0.074
4      |      115.018 |         17.597 |      0.153
2      |       86.066 |         18.153 |      0.211
1      |       16.974 |         22.325 |      1.315

interpreted results (the increase is due to double loop overhead, I suppose, indexing time should be ~ constant, as evidenced by 1-tuple with one loop which is at the same perf level as 256):

$ rm rep.*.so
$ python -c 'from rep import bench; bench()'
Length |   Fixed (ms) |  Variable (ms) | Ratio (V/F)
----------------------------------------------------
256    |       42.617 |         35.463 |      0.832
128    |       42.554 |         38.664 |      0.909
64     |       41.056 |         46.726 |      1.138
32     |       45.231 |         44.258 |      0.978
16     |       53.681 |         52.735 |      0.982
8      |       69.362 |         66.149 |      0.954
4      |       99.633 |        103.544 |      1.039
2      |      157.591 |        156.053 |      0.990
1      |       38.836 |         36.323 |      0.935

variance across runs is relatively big, but the performance trend is clear for 4 items and more: fixed compiled << interpreted < variadic compiled.