DeadlineExceeded failures in test_eye/test_linspace

[oleksandr-pavlyk]

Running array-api-tests suite on dpctl.tensor (https://github.com/IntelPython/dpctl):

ONEAPI_DEVICE_SELECTOR=*:cpu ARRAY_API_TESTS_MODULE=dpctl.tensor python -m pytest array_api_tests/test_creation_functions.py

two test new failures consistently occur (after updating from f82c7bc to recent tip of main, i.e. 9d7777b), e.g.:

FAILED array_api_tests/test_creation_functions.py::test_eye - hypothesis.errors.DeadlineExceeded: Test took 1470.80ms, which exceeds the deadline of 800.00ms
FAILED array_api_tests/test_creation_functions.py::test_linspace - hypothesis.errors.DeadlineExceeded: Test took 864.40ms, which exceeds the deadline of 800.00ms

Here is my understanding of what happens.

Hypothesis would generate a sufficiently large array, i.e. eye(47, 100) but testing of the output correctness is is done one element at the time (suboptimal usage for offloading libraries as it triggers 4700 submissions of small kernels) and this testing would take much longer than the creation of the array itself:

In [7]: import dpctl, dpctl.tensor as dpt

In [8]: %time eye_m = dpt.eye(47,100)
CPU times: user 3.23 ms, sys: 0 ns, total: 3.23 ms
Wall time: 2.76 ms

In [9]: %time all(eye_m[i, j] == (1 if i == j else 0) for i in range(eye_m.shape[0]) for j in range(eye_m.shape[1]))
CPU times: user 6.68 s, sys: 1.98 s, total: 8.67 s
Wall time: 2.09 s
Out[9]: True

The remedy would be to restrict the maximal dimension size.

[oleksandr-pavlyk]

This is the change I applied locally:

diff --git a/array_api_tests/test_creation_functions.py b/array_api_tests/test_creation_functions.py
index 94b6b0e..af86542 100644
--- a/array_api_tests/test_creation_functions.py
+++ b/array_api_tests/test_creation_functions.py
@@ -354,14 +354,25 @@ def test_eye(n_rows, n_cols, kw):
         ph.assert_kw_dtype("eye", kw_dtype=kw["dtype"], out_dtype=out.dtype)
     _n_cols = n_rows if n_cols is None else n_cols
     ph.assert_shape("eye", out_shape=out.shape, expected=(n_rows, _n_cols), kw=dict(n_rows=n_rows, n_cols=n_cols))
-    f_func = f"[eye({n_rows=}, {n_cols=})]"
+    expected_seq = []
     for i in range(n_rows):
+        row = []
         for j in range(_n_cols):
-            f_indexed_out = f"out[{i}, {j}]={out[i, j]}"
-            if j - i == kw.get("k", 0):
-                assert out[i, j] == 1, f"{f_indexed_out}, should be 1 {f_func}"
-            else:
-                assert out[i, j] == 0, f"{f_indexed_out}, should be 0 {f_func}"
+            value = 1 if j - i == kw.get("k", 0) else 0
+            row.append(value)
+        expected_seq.append(row)
+    expected_array = xp.asarray(expected_seq, dtype=out.dtype)
+    test = expected_array != out
+    if xp.any(test):
+        i_nz, j_nz, = xp.nonzero(test)
+        f_func = f"[eye({n_rows=}, {n_cols=})]"
+        for i in i_nz:
+            for j in j_nz:
+                f_indexed_out = f"out[{i}, {j}]={out[i, j]}"
+                if j - i == kw.get("k", 0):
+                    assert out[i, j] == 1, f"{f_indexed_out}, should be 1 {f_func}"
+                else:
+                    assert out[i, j] == 0, f"{f_indexed_out}, should be 0 {f_func}"

and it has helped with the timeout. I think a similar change needs to be applied to pytest_helpers.assert_array_elements.

If this looks OK, I will open a PR

[honno]

Just to say, what we (i.e. me) intend to do after resolving #221 is to review the test suites method of array comparison, because yes it's awfully slow right now.

Historical reasons (signed zero/NaN comparisons, masking being optional, and a mistrust of adopter's implementations of comparison functions) meant we've just iterated over arrays and casted elements one-by-one. But we probably can use vectorization everywhere at this point, with some clever use of xp.where, and some more trust/sanity-checking of adopter's own comparison functions.

Related discussions:

• Tests are too slow for libraries with eager-mode dispatch overhead #197
• Make test_eye more efficient #200 (comment)

[honno]

@oleksandr-pavlyk I wonder if this is fixed already? #236 and #246 might of solved this already.

I had trouble getting dpctl to work locally, although will have a serious go at it down the line as obviously it'll be useful. IntelPython/dpctl#1619 did help.