Repository navigation
test_implied_dirs_performance is flaky #102209
Description
Activity
Some have suggested to replace the check with something that asserts the algorithmic complexity.
I've confirmed that after addressing the correctness of the check, the tests fail if I apply this diff:
diff --git a/zipp/__init__.py b/zipp/__init__.py index f06e9fcc..6a60fc0a 100644 --- a/zipp/__init__.py +++ b/zipp/__init__.py @@ -63,7 +63,7 @@ def _difference(minuend, subtrahend): Return items in minuend not in subtrahend, retaining order with O(1) lookup. """ - return itertools.filterfalse(set(subtrahend).__contains__, minuend) + return (item for item in minuend if item not in subtrahend) class InitializedState:
I'm struggling to think how one could test the algorithmic complexity of
_difference. In fact, the complexity differs based on the inputs. In the slower, generator-based version, if a set is passed as the subtrahend, the performance is comparable to the faster version. It's only when a non-set is passed does the algorithm experience quadratic time.I think I see how one can experimentally verify linear time:
(a) measure the performance at n=5, n=10, ... n=100.
(b) test that the difference between each increment is about the same.Experimentally verifying linear time is probably fine.
I suspect the reason it's failing now is because we run a lot of our CI tests against debug builds, rather than the fully optimised builds that were being used externally. So even measuring once for a small N and extrapolating a suitable timeout for a larger N is probably going to be fine - it's just the fixed 3 seconds is based on a different baseline.
- added a commit that references this issue
on Feb 24, 2023 I've started work in https://github.com/jaraco/jaraco.test/blob/main/jaraco/test/complexity.py to attempt to test for linear time complexity of a function, but I'm finding the test is very flaky (failing 10-20%, especially in CI).
So rather than leave CPython CI in a flaky state, I've proposed #102225 to disable the flaky check for now.
Annoyingly, the fix in zipp isn't portable to CPython (because it depends on numpy), so the solution here will be just to skip the test (unless
big_ois importable). The complexity constraint will have to be maintained in zipp.Reacted by Steve Dower- added a commit that references this issue
on Feb 25, 2023 - added a commit that references this issue
on Feb 28, 2023 - added a commit that references this issue
on Mar 1, 2023 - added a commit that references this issue
on Mar 1, 2023 - added a commit that references this issue
on Mar 2, 2023
Reported in discord, since #102018, the timing check was added to
test_implied_dirs_performanceand this check is frequently failing (example):These failures aren't occurring on zipp, where the check has been running for years without fail.
Furthermore, the check is currently not capturing the failure case because the invocation fails to consume the generator:
cpython/Lib/test/test_zipfile/test_path.py
Line 336 in 9f3ecd1
That indicates that the flaky failures are due to the construction of test data:
cpython/Lib/test/test_zipfile/test_path.py
Line 335 in 9f3ecd1
Linked PRs