Running the following test using pytest 9.0.0 in python 3.10 leads to a quadratic blowup:
from unittest import TestCase
N = 1 # 1, 2, 3, 4, ...
class TestQuadraticBlowup(TestCase):
def test_quadratic_blowup(self) -> None:
for i in range(1000 * N): # multiplying by 1000 to make bigger steps
with self.subTest():
pass
For a given N, it takes O(N^2) time to complete. Here are a few samples:
N=10 -> 10s
N=20 -> 35s
N=30 -> 73s
N=40 -> 130s
When running this test using python -m unittest test.py, it takes less than 0.5s for N=40.
I traced this test a little:
TestCaseFunction.runtest() is called (unittest.py#360)
- it calls
testcase(result=self) (unittest.py#389) which is TestCase.run() (case.py#557)
- it constructs
outcome = _Outcome(result) (case.py#582) and assigns to self a line later
- the actual test is executed with
self._callTestMethod(testMethod) (case.py#591)
- the test repeatedly calls
with self.subTest() which is TestCase.subTest() (case.py#480)
TestCase.subTest() constructs _SubTest (case.py#495)
- it enters that subtest with
with self._outcome.testPartExecutor(self._subtest, isTest=True): yield (case.py#497) which is _Outcome.testPartExecutor() (case.py#55)
- when the subtest finishes successfully, that
_Subtest instance is appended to the _Outcome.errors list with None as error (case.py#79)
- after all subtests finish,
TestCase.run() calls self._feedErrorsToResult(result, outcome.errors) (case.py#599)
- note that
outcome.errors has 1000 * N elements
TestCase._feedErrorsToResult() iterates over all those errors (case.py#511)
- this gives the first, outer
O(N)
- for each error, it calls
result.addSubTest(test.test_case, test, exc_info) (case.py#513) which is TestCaseFunction.addSubTest() (unittest.py#404)
TestCaseFunction.addSubTest() eventually iterates over self.instance._outcome.errors (unittest.py#455) which is the same list as outcome.errors above (1000 * N elements)
- this gives us the second, nested
O(N), which in total gives us O(N^2) for the entire test
There might be similar issues with skipped tests (unittest.py#450). Another potential hot spot is unittest.py#318.
pip list output:
Package Version
----------------- -------
exceptiongroup 1.3.0
iniconfig 2.3.0
packaging 25.0
pip 23.0.1
pluggy 1.6.0
Pygments 2.19.2
pytest 9.0.1
setuptools 65.5.0
tomli 2.3.0
typing_extensions 4.15.0
Python: 3.10.17
Running the following test using pytest 9.0.0 in python 3.10 leads to a quadratic blowup:
For a given
N, it takesO(N^2)time to complete. Here are a few samples:N=10-> 10sN=20-> 35sN=30-> 73sN=40-> 130sWhen running this test using
python -m unittest test.py, it takes less than 0.5s forN=40.I traced this test a little:
TestCaseFunction.runtest()is called (unittest.py#360)testcase(result=self)(unittest.py#389) which isTestCase.run()(case.py#557)outcome = _Outcome(result)(case.py#582) and assigns toselfa line laterself._callTestMethod(testMethod)(case.py#591)with self.subTest()which isTestCase.subTest()(case.py#480)TestCase.subTest()constructs_SubTest(case.py#495)with self._outcome.testPartExecutor(self._subtest, isTest=True): yield(case.py#497) which is_Outcome.testPartExecutor()(case.py#55)_Subtestinstance is appended to the_Outcome.errorslist withNoneas error (case.py#79)TestCase.run()callsself._feedErrorsToResult(result, outcome.errors)(case.py#599)outcome.errorshas1000 * NelementsTestCase._feedErrorsToResult()iterates over all those errors (case.py#511)O(N)result.addSubTest(test.test_case, test, exc_info)(case.py#513) which isTestCaseFunction.addSubTest()(unittest.py#404)TestCaseFunction.addSubTest()eventually iterates overself.instance._outcome.errors(unittest.py#455) which is the same list asoutcome.errorsabove (1000 * Nelements)O(N), which in total gives usO(N^2)for the entire testThere might be similar issues with skipped tests (unittest.py#450). Another potential hot spot is unittest.py#318.
pip listoutput:Python:
3.10.17