Re: Are optimization for array_equal implementation welcome?

On Tue, 23 Dec 2025 at 12:18, Ralf Gommers via NumPy-Discussion
<[email protected]> wrote:
>
> On Sat, Dec 20, 2025 at 4:21 PM Mark Harfouche via NumPy-Discussion <[email protected]> wrote:
>>
>> this inevitably means that something like a full memory copy of your array is allocated for this equality check, which should only have a memory footprint of O(1) instead of O(n) which it has now.
>>
>> Are PRs welcome to implement optimize this?
>> https://github.com/numpy/numpy/blob/67fc5c311eea54b27e43c2c769b3b8f878ae43f9/numpy/_core/numeric.py#L2528
>
> PRs that make existing functionality faster are always welcome. The main criterion for acceptance is that extra complexity should be justified by the performance gains (e.g., adding hundreds of lines of C code to make it 20% faster is not okay, but if it'd be 3x faster than sure why not).

The speed difference can be much bigger than 3x:

In [17]: from array import array

In [18]: a1, a2 = [array('L', range(1_000_000)) for i in range(2)]

In [19]: a2[0] = 10

In [20]: %timeit a1 == a2
46.5 ns ± 0.204 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [21]: import numpy as np

In [22]: a1, a2 = [np.array(range(1_000_000)) for i in range(2)]

In [23]: a2[0] = 10

In [24]: %timeit np.array_equal(a1, a2)
2.04 ms ± 29.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

That is a 40000x speed difference.

For random arrays the comparison can be average O(1) in time and
space. For example if you have a uint8 array of uniform random
integers in the range 0-255 then 99.5% of the time it is sufficient
just to compare the first elements of the arrays. In practical
applications you may have reasons why it is much more likely that the
arrays actually are equal and the worst case is when they really are
but if the probability of them being not equal is 1/N then you can
basically have an average Nx speed up by short-circuiting.

--
Oscar
_______________________________________________
NumPy-Discussion mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/numpy-discussion.python.org
Member address: [email protected]