test_implied_dirs_performance is flaky

[jaraco]

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

• gh-102209: Disable the timeout in test_implied_dirs_performance. #102225
• gh-102209: Sync with zipp 3.15 moving complexity tests into dedicated module #102232

[jaraco]

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]

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]

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.

[jaraco]

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

[jaraco]

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.