<div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Sep 26, 2019 at 10:43 PM Nathaniel Smith <<a href="mailto:njs@pobox.com">njs@pobox.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Thu, Sep 26, 2019 at 6:51 PM Todd <<a href="mailto:toddrjen@gmail.com" target="_blank">toddrjen@gmail.com</a>> wrote:<br>
> I have submitted a PR [1] for a new function, "oaconvolve", which is an implementation of the overlap-add algorithm for convolution.  This algorithm is much faster than conventional FFT-based > We previously discussed whether this should be its own function or part of fftconvolve.  The performance and memory characteristics of this function are significantly different than those of fftconvolve and would really be used in different situations, so the consensus seemed to be that this should be its own function.  I would ultimately like "convolve" to be able to use oaconvolve when it is the best choice, but that is an issue for later.<br>
><br>
> There is a "method" argument for choosing whether to automatically fall back on fftconvolve or raise an error.  Being able to prevent falling back on fftconvolve is essentially for testing.  We need to be able to make sure that oaconvolve is actually being tested and not the fftconvolve fallback.  But this may not be the best way to do that.<br>
<br>
It seems like there's some contradiction between the idea that it<br>
needs to be its own function so that users can control which algorithm<br>
they're using, but then it sometimes silently falls back to<br>
fftconvolve, so they can't – and then you need an argument to disable<br>
the fallback because you do need to control the choice of algorithm.<br>
<br>
What would be the consequences of removing the fallback entirely?<br>
<br>
-n<br></blockquote><div><br></div><div>You would get exceptions in specific, very hard-to-predict combinations of shapes.  Unless you have total control over the shapes of the inputs, the function couldn't be used safely on its own.  You would need to handle such cases somehow.  <br></div><div><div><br></div><div>To be clear, the situations where it falls back on fftconvolve are the situations where oaconvolve reduces to fftconvolve.  It would be possible to implement oaconvolve in these situations, and it would ultimately be the same algorithm as fftconvolve, but it would add unnecessary time and memory overhead compared to just using the fftconvolve fallback.  I didn't see the point in doing a numerically identical algorithm slower, hence the fallback.  Further, handling these situations in the oaconvolve function would slow down the oaconvolve function under all conditions, not just situations where oaconvolve reduces to fftconvolve.<br></div><div><br></div><div>I need the argument, or something like it, because I want to make sure the tests don't hit situations where oaconvolve reduces to fftconvolve.  Even if these situations where handled in oaconvolve itself rather than an fftconvolve fallback, I would still need to be able to raise an exception for these situations because I need to make sure the tests are actually testing the oaconvolve algorithm, not the fftconvolve one.<br></div></div><div><br></div><div>The reason there are two functions are situations where fftconvolve and oaconvolve are substantially different in their characteristics.  There is no fallback in such cases, even if fftconvolve is faster.  Picking the fastest algorithm for a given set of inputs should be handled by the "convolve" function, but adding support for oaconvolve to convolve will be a later pull request.  <br></div></div></div>