GeezerVison is showing github.com — test_implied_dirs_performance is flaky · Issue #102209 · python/cpython
test_implied_dirs_performance is flaky #102209DescriptionReported in discord, since #102018, the timing check was added to test_implied_dirs_performance and this check is frequently failing (example):
ERROR: test_implied_dirs_performance (test.test_zipfile.test_path.TestPath.test_implied_dirs_performance)
----------------------------------------------------------------------
Traceback (most recent call last):
File "D:\a\cpython\cpython\Lib\contextlib.py", line 80, in inner
with self._recreate_cm():
File "D:\a\cpython\cpython\Lib\test\test_zipfile\_context.py", line 30, in __exit__
raise DeadlineExceeded(duration, self.max_duration)
test.test_zipfile._context.DeadlineExceeded: (3.140999999999849, 3)
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:
|
zipfile.CompleteDirs._implied_dirs(data) |
That indicates that the flaky failures are due to the construction of test data:
|
data = ['/'.join(string.ascii_lowercase + str(n)) for n in range(10000)] |
Linked PRs
Activityjaraco commented on Feb 24, 2023 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. zooba commented on Feb 24, 2023 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. jaraco commented on Feb 24, 2023 jaraco commented on Feb 24, 2023 Turns out there already exists a sophisticated library to calculate a best-fit time complexity, big-O. That library does just what's needed. added 3 commits that reference this issue on Feb 25, 2023This issue will close once commit bd1904c is merged into the 'main' branch.bd1904c This issue will close once commit ccb0601 is merged into the 'main' branch.ccb0601 This issue will close once commit 8c0a745 is merged into the 'main' branch.8c0a745 jaraco commented on Feb 25, 2023 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_o is importable). The complexity constraint will have to be maintained in zipp. added a commit that references this issue on Feb 25, 2023gh-102209: Sync with zipp 3.15 moving complexity tests into dedicated…
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|