test_implied_dirs_performance is flaky

Reported 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:

cpython/Lib/test/test_zipfile/test_path.py

Line 336 in 9f3ecd1

zipfile.CompleteDirs._implied_dirs(data)

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

data = ['/'.join(string.ascii_lowercase + str(n)) for n in range(10000)]

Linked PRs

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.

Disable the timeout in test_implied_dirs_performance. Workaround for p…

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.

gh-102209: Disable the timeout in test_implied_dirs_performance. (#10…

Consume the _implied_dirs result, ensuring the algorithmic effect is …

Measure the complexity directly using the big-O library. Fixes python…

Turns out there already exists a sophisticated library to calculate a best-fit time complexity, big-O. That library does just what's needed.

Measure the complexity directly using the big-O library. Fixes python…

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.

gh-102209: Sync with zipp 3.15 moving complexity tests into dedicated…

pypi-zipp: Autospec creation for update from version 3.14.0 to versio…

python3-zipp: upgrade 3.14.0 -> 3.15.0

pythongh-102209: Disable the timeout in test_implied_dirs_performance. (

Navigation Menu

Repository navigation

test_implied_dirs_performance is flaky #102209

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

test_implied_dirs_performance is flaky #102209

Description

Linked PRs

Activity

jaraco commented on Feb 24, 2023

zooba commented on Feb 24, 2023

jaraco commented on Feb 24, 2023

jaraco commented on Feb 24, 2023

jaraco commented on Feb 25, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions