BUG: signal.convolve takes longer than it needs to

[endolith]

While looking into #2651, I noticed that convolve takes longer if the first input is shorter than the second input, even though they are computing the same thing (convolution is commutative):

In [54]: a = rand(2)

In [55]: b = rand(500)

In [56]: timeit convolve(a, b, 'full')
100 loops, best of 3: 5.47 ms per loop

In [57]: timeit convolve(b, a, 'full')
10000 loops, best of 3: 67.9 us per loop

In [60]: allclose(convolve(a, b, 'full'), convolve(b, a, 'full'))
Out[60]: True

In [58]: timeit fftconvolve(a, b, 'full')
1000 loops, best of 3: 146 us per loop

In [59]: timeit fftconvolve(b, a, 'full')
10000 loops, best of 3: 147 us per loop

So the algorithm is taking 80 times as long as it needs to, and could be modified to take the same amount of time regardless of input order, maybe by just checking which input is longer and then internally rearranging them so that the shorter one comes last.

[endolith]

In [107]: short = rand(2)
In [112]: long = rand(500)

In [113]: timeit signal.convolve(short, long, 'full')  (SLOW)
100 loops, best of 3: 5.08 ms per loop

In [114]: timeit signal.convolve(long, short, 'full')
10000 loops, best of 3: 67.9 us per loop




In [115]: short = rand(2, 50)

In [116]: long = rand(50, 50)

In [117]: timeit signal.convolve(short, long, 'full')   (SLOW)
1 loops, best of 3: 333 ms per loop

In [118]: timeit signal.convolve(long, short, 'full')
100 loops, best of 3: 14 ms per loop


In [119]: short = rand(50, 2)

In [120]: timeit signal.convolve(short, long, 'full')  (SLOW)
1 loops, best of 3: 354 ms per loop

In [121]: timeit signal.convolve(long, short, 'full')
100 loops, best of 3: 14.3 ms per loop

So size(a) > size(b) is probably what it wants? len() won't work on ND arrays.

Maybe the underlying C code is optimized for the len(a) > len(b) case, since this was true 100% of the time with the "old behavior" that numpy.convolve still uses, where the inputs are internally swapped so the larger one is first?

[endolith]

Fixed by #3664