BUG: spatial: long hangs using Qhull in SciPy 1.13.0, in Colour CI

[KelSolaar]

Describe your issue.

Hello,

We have seen our Windows Github Actions build times jumping from 15m to 4h15m after what seems an update from Scipy 1.12.0 to Scipy 1.13.0:

15m: https://github.com/colour-science/colour/actions/runs/8489605040/job/23259884769
4h15m: https://github.com/colour-science/colour/actions/runs/8845206377/job/24288653119

All the functions affected are touching Qhull via our colour.volume.is_within_mesh_volume definition:

2024-04-26T12:28:33.7956840Z ============================= slowest 5 durations =============================
2024-04-26T12:28:33.7957585Z 9020.65s call     colour/volume/tests/test_spectrum.py::TestIsWithinVisibleSpectrum::test_is_within_visible_spectrum
2024-04-26T12:28:33.7958454Z 8888.35s call     colour/volume/spectrum.py::colour.volume.spectrum.is_within_visible_spectrum
2024-04-26T12:28:33.7959562Z 4397.23s call     colour/volume/tests/test_rgb.py::TestRGB_colourspaceVisibleSpectrumCoverageMonteCarlo::test_RGB_colourspace_visible_spectrum_coverage_MonteCarlo
2024-04-26T12:28:33.7960670Z 3785.15s call     colour/volume/rgb.py::colour.volume.rgb.RGB_colourspace_visible_spectrum_coverage_MonteCarlo
2024-04-26T12:28:33.7961663Z 713.57s call     colour/volume/tests/test_pointer_gamut.py::TestIsWithinPointerGamut::test_is_within_pointer_gamut

def is_within_mesh_volume(
    points: ArrayLike, mesh: ArrayLike, tolerance: float = 100 * EPSILON
) -> NDArrayFloat:
    """
    Return whether given points are within given mesh volume using Delaunay
    triangulation.

    Parameters
    ----------
    points
        Points to check if they are within ``mesh`` volume.
    mesh
        Points of the volume used to generate the Delaunay triangulation.
    tolerance
        Tolerance allowed in the inside-triangle check.

    Returns
    -------
    :class:`numpy.ndarray`
        Whether given points are within given mesh volume.

    Examples
    --------
    >>> mesh = np.array(
    ...     [
    ...         [-1.0, -1.0, 1.0],
    ...         [1.0, -1.0, 1.0],
    ...         [1.0, -1.0, -1.0],
    ...         [-1.0, -1.0, -1.0],
    ...         [0.0, 1.0, 0.0],
    ...     ]
    ... )
    >>> is_within_mesh_volume(np.array([0.0005, 0.0031, 0.0010]), mesh)
    array(True, dtype=bool)
    >>> a = np.array([[0.0005, 0.0031, 0.0010], [0.3205, 0.4131, 0.5100]])
    >>> is_within_mesh_volume(a, mesh)
    array([ True, False], dtype=bool)
    """

    triangulation = Delaunay(mesh)

    simplex = triangulation.find_simplex(points, tol=tolerance)
    simplex = np.where(simplex >= 0, True, False)

    return simplex

I saw a reference to a Qhull related change in the mailing list here: https://mail.python.org/archives/list/scipy-dev@python.org/thread/V25I4CIN556ZKKBIA2Q2OLVFGVYVYDEB/ but not the release notes on Github.

Any pointers would be appreciated, we will probably ban this version.

Cheers,

Thomas

Reproducing Code Example

Hard to repro, would need to run Colour's above tests on Windows using 1.13.0.

Error message

N/A

SciPy/NumPy/Python version and system information

1.13.0 vs 1.12.0 on Windows

[lucascolley]

hmm, nothing obvious sticks out to me in the git history. Maybe gh-20337 @ev-br ?

[ev-br]

Maybe gh-20337?

No way it can explain the runtime change from 15min to 4 hrs.

Something else must have changed. I'd first verify the "new" run time is stable, then try to replicate locally. Then bisect.

[KelSolaar]

I will try to check if Github changed anything on their runners, I pointed to Scipy as the culprit because it is the obvious change and this happens in QHull by the looks of it but it could also be hardware related. Thomas Mansencal - colour-science.org <https://www.colour-science.org> - thomasmansencal.com <http://www.thomasmansencal.com>

…

On Tue, 30 Apr 2024 at 12:39 PM, Evgeni Burovski ***@***.***> wrote: Maybe gh-20337 <#20337>? No way it can explain the runtime change from 15min to 4 hrs. Something else must have changed. I'd first verify the "new" run time is stable, then try to replicate locally. Then bisect. — Reply to this email directly, view it on GitHub <#20613 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAYLQ57QVN4X3KAL3V6SUTY73R3XAVCNFSM6AAAAABG6542ZSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAOBTHE3DGOJYGQ> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[KelSolaar]

Confirming it is coming from 1.13.0, I banned the version and did a fresh build in ~15mins using 1.12.0: https://github.com/colour-science/colour/actions/runs/8890511725/job/24410682802

[ev-br]

1. Do you see it on other platforms, or can you confirm it's windows specific?

2. Can you reproduce this locally?

[KelSolaar]

Hey @ev-br,

It is Windows only and I cannot reproduce locally as I'm developing on macOs.

[ev-br]

Just to confirm: with scipy 1.13 the Windows CI run takes 4hrs and MacOS and Linux runs take 15 mins, correct?

Also, with scipy 1.12, all of them are 15 mins?

---

It's likely much faster to debug in a Windows VM. If only to see if the issue is specific to the GH runners or windows in general.

[KelSolaar]

Correct yes!

[ilayn]

Is this a wheel install or you are building it yourself in the CI?

[KelSolaar]

It is a wheel install, Scipy is one of our dependencies.

[lucascolley]

Right. To clarify, the installation is fast, but the test suite takes 4 hours.

[tylerjereddy]

There was a substantial bump in vendored OpenBLAS version between 1.12.0 and 1.13.0 of course. I suppose that's also worth considering, especially since the 0.3.26.dev version specifically addressed a concurrency issue on Windows. Having a way to bisect with a simple reproducer as Evgeni alluded to would of course be great.

[rgommers]

Agreed that OpenBLAS version is the prime candidate. We have nightlies that were just upgraded from 0.3.26.dev to 0.3.27, with a known regression that can cause this kind of performance regression fixed. Worth trying with those: https://anaconda.org/scientific-python-nightly-wheels/scipy