"Collecting" hangs forever if mark.parametrize is used with scope session or module

[adaasch]

• a detailed description of the bug or problem you are having

If you parametrize a test function with several parameters with @mark.parametrize and set scope to "session" or "module" the collection step will take forever*. Debugging shows that _pytest/fixtures.py:fix_cache_order() is called repeatedly:

__hash__ (/usr/lib/python3.11/enum.py:1230)
fix_cache_order (.venv/lib/python3.11/site-packages/_pytest/fixtures.py:233)
reorder_items_atscope (.venv/lib/python3.11/site-packages/_pytest/fixtures.py:269)
reorder_items (.venv/lib/python3.11/site-packages/_pytest/fixtures.py:222)
pytest_collection_modifyitems (.venv/lib/python3.11/site-packages/_pytest/fixtures.py:1617)
_multicall (.venv/lib/python3.11/site-packages/pluggy/_callers.py:103)
_hookexec (.venv/lib/python3.11/site-packages/pluggy/_manager.py:120)
__call__ (.venv/lib/python3.11/site-packages/pluggy/_hooks.py:513)
perform_collect (.venv/lib/python3.11/site-packages/_pytest/main.py:814)
pytest_collection (.venv/lib/python3.11/site-packages/_pytest/main.py:349)
_multicall (.venv/lib/python3.11/site-packages/pluggy/_callers.py:103)
_hookexec (.venv/lib/python3.11/site-packages/pluggy/_manager.py:120)
__call__ (.venv/lib/python3.11/site-packages/pluggy/_hooks.py:513)
_main (.venv/lib/python3.11/site-packages/_pytest/main.py:338)
wrap_session (.venv/lib/python3.11/site-packages/_pytest/main.py:285)
pytest_cmdline_main (.venv/lib/python3.11/site-packages/_pytest/main.py:332)
_multicall (.venv/lib/python3.11/site-packages/pluggy/_callers.py:103)
_hookexec (.venv/lib/python3.11/site-packages/pluggy/_manager.py:120)
__call__ (.venv/lib/python3.11/site-packages/pluggy/_hooks.py:513)
main (.venv/lib/python3.11/site-packages/_pytest/config/__init__.py:178)
console_main (.venv/lib/python3.11/site-packages/_pytest/config/__init__.py:206)
<module> (.venv/lib/python3.11/site-packages/pytest/__main__.py:7)
_run_code (/usr/lib/python3.11/runpy.py:88)
_run_module_as_main (/usr/lib/python3.11/runpy.py:198)

*forever scales with the number of parameters.

• output of pip list from the virtual environment you are using

Package                        Version   Editable project location
------------------------------ --------- ------------------------------------
aenum                          3.1.15
aiohttp                        3.9.3
aiosignal                      1.3.1
alabaster                      0.7.16
astroid                        3.1.0
attrs                          23.2.0
Babel                          2.14.0
bcrypt                         4.1.2
beautifulsoup4                 4.12.3
black                          23.12.1
build                          1.2.1
CacheControl                   0.14.0
certifi                        2024.2.2
cffi                           1.16.0
cfgv                           3.4.0
charset-normalizer             3.3.2
cleo                           2.1.0
click                          8.1.7
construct                      2.10.70
crashtest                      0.4.1
cryptography                   42.0.5
dill                           0.3.8
distlib                        0.3.8
docutils                       0.20.1
dulwich                        0.21.7
fastjsonschema                 2.19.1
filelock                       3.13.3
frozenlist                     1.4.1
furo                           2024.5.6
grpcio                         1.62.1
grpcio-tools                   1.62.1
identify                       2.5.35
idna                           3.6
imagesize                      1.4.1
importlib_metadata             7.1.0
iniconfig                      2.0.0
installer                      0.7.0
isort                          5.13.2
iterators                      0.2.0
jaraco.classes                 3.4.0
jeepney                        0.8.0
Jinja2                         3.1.3
keyring                        24.3.1
MarkupSafe                     2.1.5
mccabe                         0.7.0
more-itertools                 10.2.0
msgpack                        1.0.8
multidict                      6.0.5
mypy-extensions                1.0.0
nodeenv                        1.8.0
numpy                          1.26.4
opencv-contrib-python-headless 4.9.0.80
packaging                      24.0
paramiko                       3.4.0
paramiko-expect                0.3.5
pastel                         0.2.1
pathspec                       0.12.1
pexpect                        4.9.0
pip                            24.0
pkginfo                        1.10.0
platformdirs                   4.2.0
pluggy                         1.5.0
poethepoet                     0.25.1
poetry                         1.8.3
poetry-core                    1.9.0
poetry-plugin-export           1.8.0
pooch                          1.8.1
pre-commit                     3.7.0
protobuf                       4.25.3
ptyprocess                     0.7.0
pycparser                      2.22
pydocstyle                     6.3.0
Pygments                       2.17.2
pylint                         3.1.0
PyNaCl                         1.5.0
pyproject_hooks                1.1.0
pyright                        1.1.362
pytest                         8.2.1
pytest-reportportal            5.4.1
PyYAML                         6.0.1
rapidfuzz                      3.9.1
reportportal-client            5.5.6
requests                       2.31.0
requests-toolbelt              1.0.0
rstr                           3.2.2
SecretStorage                  3.3.3
setuptools                     69.2.0
shellingham                    1.5.4
snowballstemmer                2.2.0
soupsieve                      2.5
Sphinx                         7.3.7
sphinx-basic-ng                1.0.0b2
sphinx-rtd-theme               2.0.0
sphinxcontrib-applehelp        1.0.8
sphinxcontrib-devhelp          1.0.6
sphinxcontrib-htmlhelp         2.0.5
sphinxcontrib-jquery           4.1
sphinxcontrib-jsmath           1.0.1
sphinxcontrib-qthelp           1.0.7
sphinxcontrib-serializinghtml  1.1.10
timecode                       1.4.0
tomli                          2.0.1
tomlkit                        0.12.4
trove-classifiers              2024.5.17
urllib3                        2.2.1
virtualenv                     20.25.1
yarl                           1.9.4
zipp                           3.18.2

• pytest and operating system versions

  • Linux 03b812391caf 5.10.0-29-amd64 SMP Debian 5.10.216-1 (2024-05-03) x86_64 GNU/Linux
  • Python 3.11.2
  • pytest 8.2.1
  • pytest 7.4.0

• minimal example if possible

The issue is reproducible with pytest 7.4.0 and 8.2.1 with the following minimal example.

from pytest import mark

params = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')

@mark.parametrize(argnames=params, argvalues=[range(len(params))] * 3, scope="module")
def test_parametrize(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z):
    pass

[bluetech]

Thanks for the report.

By gradually increasing the number of parameters, this looks like an "accidentally quadratic" (or worse...) situation.

A (not so...) quick profile run puts the blame on _pytest/fixtures.py:238(reorder_items_atscope) which calls _pytest/fixtures.py:228(fix_cache_order).

Profile output

         225490710 function calls (225482776 primitive calls) in 79.889 seconds

   Ordered by: cumulative time
   List reduced from 3530 to 30 due to restriction <30>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    501/1    0.022    0.000   79.891   79.891 {built-in method builtins.exec}
        1    0.000    0.000   79.891   79.891 <string>:1(<module>)
        1    0.000    0.000   79.891   79.891 <frozen runpy>:201(run_module)
        1    0.000    0.000   79.703   79.703 <frozen runpy>:65(_run_code)
        1    0.000    0.000   79.703   79.703 pytest/src/pytest/__main__.py:1(<module>)
        1    0.000    0.000   79.703   79.703 pytest/src/_pytest/config/__init__.py:199(console_main)
        1    0.000    0.000   79.703   79.703 pytest/src/_pytest/config/__init__.py:142(main)
   475/71    0.001    0.000   79.672    1.122 pytest/.tox/venv/lib/python3.12/site-packages/pluggy/_manager.py:111(_hookexec)
   475/71    0.004    0.000   79.672    1.122 pytest/.tox/venv/lib/python3.12/site-packages/pluggy/_callers.py:53(_multicall)
    291/2    0.001    0.000   79.670   39.835 pytest/.tox/venv/lib/python3.12/site-packages/pluggy/_hooks.py:498(__call__)
        1    0.000    0.000   79.550   79.550 pytest/src/_pytest/main.py:331(pytest_cmdline_main)
        1    0.000    0.000   79.550   79.550 pytest/src/_pytest/main.py:272(wrap_session)
        1    0.000    0.000   79.219   79.219 pytest/src/_pytest/main.py:335(_main)
        1    0.000    0.000   79.201   79.201 pytest/src/_pytest/main.py:348(pytest_collection)
        1    0.000    0.000   79.201   79.201 pytest/src/_pytest/main.py:746(perform_collect)
        1    0.139    0.139   79.165   79.165 pytest/src/_pytest/fixtures.py:1617(pytest_collection_modifyitems)
        1    0.000    0.000   79.025   79.025 pytest/src/_pytest/fixtures.py:210(reorder_items)
      6/1    2.334    0.389   79.025   79.025 pytest/src/_pytest/fixtures.py:238(reorder_items_atscope)
  1572861   27.109    0.000   74.492    0.000 pytest/src/_pytest/fixtures.py:228(fix_cache_order)
 29886354    8.917    0.000   23.305    0.000 <string>:2(__hash__)
77074144/77073790   17.417    0.000   20.581    0.000 {built-in method builtins.hash}
 36175863    8.681    0.000   13.444    0.000 /usr/lib/python3.12/enum.py:1267(__hash__)
 31457220    5.894    0.000    5.894    0.000 {method 'appendleft' of 'collections.deque' objects}
  6298142    2.611    0.000    5.103    0.000 {method 'get' of 'dict' objects}
 11010191    2.636    0.000    4.066    0.000 pytest/src/_pytest/nodes.py:289(__hash__)
 29886863    3.164    0.000    3.166    0.000 /usr/lib/python3.12/pathlib.py:524(__hash__)

I don't have time to look into it right now and will look at it later, but this looks like a fun issue if someone else would like to try to figure it out. There are probably some python-level optimizations which could bring down the processing time, and algorithmic-level optimizations which could eliminate it entirely. Both are welcome.