
12

On 28 Oct 2014 04:07, "Matthew Brett" <[hidden email]> wrote:
>
> Hi,
>
> On Mon, Oct 27, 2014 at 8:07 PM, Sturla Molden <[hidden email]> wrote:
> > Sturla Molden <[hidden email]> wrote:
> >
> >> If we really need a
> >> kickass fast FFT we need to go to libraries like FFTW, Intel MKL or
> >> Apple's Accelerate Framework,
> >
> > I should perhaps also mention FFTS here, which claim to be faster than FFTW
> > and has a BSD licence:
> >
> > http://anthonix.com/ffts/index.html
>
> Nice. And a funny New Zealand name too.
>
> Is this an option for us? Aren't we a little behind the performance
> curve on FFT after we lost FFTW?
It's definitely attractive. Some potential issues that might need dealing with, based on a quick skim:
 seems to have a hard requirement for a processor supporting SSE, AVX, or NEON. No fallback for old CPUs or other architectures. (I'm not even sure whether it has x8632 support.)
 no runtime CPU detection, e.g. SSE vs AVX appears to be a compile time decision
 not sure if it can handle nonpoweroftwo problems at all, or at all efficiently. (FFTPACK isn't great here either but major regressions would be bad.)
 not sure if it supports all the modes we care about (e.g. rfft)
This stuff is all probably solveable though, so if someone has a hankering to make numpy (or scipy) fft dramatically faster then you should get in touch with the author and see what they think.
n
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On Tue, 28 Oct 2014 04:28:37 +0000
Nathaniel Smith < [hidden email]> wrote:
> It's definitely attractive. Some potential issues that might need dealing
> with, based on a quick skim:
In my tests, numpy's FFTPACK isn't that bad considering
* (virtually) no extra overhead for installation
* (virtually) no plan creation time
* not that slower for each transformation
Because the plan creation was taking ages with FFTw, numpy's FFTPACK was often faster (overall)
Cheers,

Jérôme Kieffer
tel +33 476 882 445
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 28/10/14 09:41, David Cournapeau wrote:
> The real issue with fftw (besides the license) is the need for plan
> computation, which are expensive (but are not needed for each
> transform). Handling this in a way that is user friendly while
> tweakable for advanced users is not easy, and IMO more appropriate for
> a separate package.
Just on this, I like to think I've largely solved the issue with:
https://github.com/hgomersall/pyFFTWIf you have suggestions on how it can be improved, I'm all ears (there
are a few things in the pipeline, like creating FFTW objects for
different types of transform more explicit, which is likely to be the
main difference for the next major version).
Cheers,
Henry
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 28/10/14 04:28, Nathaniel Smith wrote:
>
>  not sure if it can handle nonpoweroftwo problems at all, or at
> all efficiently. (FFTPACK isn't great here either but major
> regressions would be bad.)
>
From my reading, this seems to be the biggest issue with FFTS (from my
reading as well) and where FFTW really wins.
Having a faster algorithm used when it will work, with fallback to
fftpack (or something else) is a good solution IMO.
Henry
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


Jerome Kieffer < [hidden email]> wrote:
> Because the plan creation was taking ages with FFTw, numpy's FFTPACK was
> often faster (overall)
Matlab switched from FFTPACK to FFTW because the latter was faster in
general. If FFTW guesses a plan it does not take very long. Actual
measurements can be slow, however, but those are not needed.
Sturla
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


David Cournapeau < [hidden email]> wrote:
> The real issue with fftw (besides the license) is the need for plan
> computation, which are expensive (but are not needed for each transform).
This is not a problem if you thell FFTW to guess a plan instead of making
measurements. FFTPACK needs to set up a lookup table too.
> I made some experiments with the Bluestein transform to handle prime
> transforms on fftpack, but the precision seemed to be an issue. Maybe I
> should revive this work (if I still have it somewhere).
You have it in a branch on Github.
Sturla
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 28 Oct 2014 07:32, "Jerome Kieffer" <[hidden email]> wrote:
>
> On Tue, 28 Oct 2014 04:28:37 +0000
> Nathaniel Smith <[hidden email]> wrote:
>
> > It's definitely attractive. Some potential issues that might need dealing
> > with, based on a quick skim:
>
> In my tests, numpy's FFTPACK isn't that bad considering
> * (virtually) no extra overhead for installation
> * (virtually) no plan creation time
> * not that slower for each transformation
Well, this is what makes FFTS intriguing :). It's BSD licensed, so we could distribute it by default like we do fftpack, it uses cacheoblivious algorithms so it has no planning step, and even without planning it benchmarks as faster than FFTW's most expensive planning mode (in the cases that FFTS supports, i.e. poweroftwo transforms).
The paper has lots of benchmark graphs, including measurements of setup time:
http://anthonix.com/ffts/preprints/tsp2013.pdf
n
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


If I may 'hyjack' the discussion back to the metapoint:
should we be having this discussion on the numpy mailing list at all?
Perhaps the 'batteries included' philosophy made sense in the early days of numpy; but given that there are several fft libraries with their own pros and cons, and that most numpy projects will use none of them at all, why should numpy bundle any of them?
To have a scipy.linalg and scipy.fft makes sense to me, although import pyfftw or import pyFFTPACK would arguably be better still. Just as in the case of linear algebra, those different libraries represent meaningful differences, and if the user wants to paper over those differences with a named import they are always free to do so themselves, explicitly. To be sure, the maintenance of quality fft libraries should be part of the numpy/scipystack in some way or another. But I would argue that the core thing that numpy should do is ndarrays alone.
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 28 Oct 2014 14:48, "Eelco Hoogendoorn" <[hidden email]> wrote:
>
> If I may 'hyjack' the discussion back to the metapoint:
>
> should we be having this discussion on the numpy mailing list at all?
Of course we should.
> Perhaps the 'batteries included' philosophy made sense in the early days of numpy; but given that there are several fft libraries with their own pros and cons, and that most numpy projects will use none of them at all, why should numpy bundle any of them?
Certainly there's a place for fancy 3rdparty fft libraries. But fft is such a basic algorithm that it'd be silly to ask people who just need a quick oneoff fft to go evaluate a bunch of thirdparty libraries. For many users, downloading one of these libraries will take longer than just doing their Fourier transform with an O(N**2) algorithm :). And besides that there's tons of existing code that uses np.fft. So np.fft will continue to exist, and given that it exists we should make it as good as we can.
> To have a scipy.linalg and scipy.fft makes sense to me, although import pyfftw or import pyFFTPACK would arguably be better still. Just as in the case of linear algebra, those different libraries represent meaningful differences, and if the user wants to paper over those differences with a named import they are always free to do so themselves, explicitly. To be sure, the maintenance of quality fft libraries should be part of the numpy/scipystack in some way or another. But I would argue that the core thing that numpy should do is ndarrays alone.
According to some sort of abstract project planning aesthetics, perhaps. But I don't see how fractionating numpy into lots of projects would provide any benefit for users. (If we split numpy into 10 subprojects then probably 7 of them would never release, because we barely have the engineering to do release management now.)
CS courses often teach that more modular = more better. That's because they're desperate to stop newbies from creating balls of mush, though, not because it's the whole truth :). It's always true that an organized codebase is better than a ball of mush, but abstraction barriers, decoupling, etc. have real and important costs, and this needs to be taken into account. (See e.g. the Torvalds/Tenenbaum debate.)
And in any case, this ship sailed a long time ago.
n
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


Eelco Hoogendoorn < [hidden email]> wrote:
> Perhaps the 'batteries included' philosophy made sense in the early days of
> numpy; but given that there are several fft libraries with their own pros
> and cons, and that most numpy projects will use none of them at all, why
> should numpy bundle any of them?
Because sometimes we just need to compute a DFT, just like we sometimes
need to compute a sine or an exponential. It does that job perfectly well.
It is not always about speed. Just typing np.fft.fft(x) is convinient.
Sturla
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 28/10/14 18:44, Stefan van der Walt wrote:
> On 20141028 19:37:17, Daniele Nicolodi < [hidden email]> wrote:
>> On 28/10/14 16:50, David Cournapeau wrote:
>>> Nothing impossible (looks like Sony at least uses this code on windows:
>>> https://github.com/anthonix/ffts/issues/27#issuecomment40204403), but
>>> not a 2 hours thing either.
>>
>> One of the downsides of the BSD license :)
>
> Perhaps one of the upsides, as they may be willing to contribute back if
> asked nicely.
If it would be GPL or similar the would have to, and there would not be
need to ask nicely.
Cheers,
Daniele
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 20141028 19:55:57, Daniele Nicolodi < [hidden email]> wrote:
> On 28/10/14 18:44, Stefan van der Walt wrote:
>> On 20141028 19:37:17, Daniele Nicolodi < [hidden email]> wrote:
>>> On 28/10/14 16:50, David Cournapeau wrote:
>>>> Nothing impossible (looks like Sony at least uses this code on windows:
>>>> https://github.com/anthonix/ffts/issues/27#issuecomment40204403), but
>>>> not a 2 hours thing either.
>>>
>>> One of the downsides of the BSD license :)
>>
>> Perhaps one of the upsides, as they may be willing to contribute back if
>> asked nicely.
>
> If it would be GPL or similar the would have to, and there would not be
> need to ask nicely.
But then they would not have written the code to start off with, so that
point is moot.
Stéfan
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


My point isn't about speed; its about the scope of numpy. typing np.fft.fft isn't more or less convenient than using some other symbol from the scientific python stack.
Numerical algorithms should be part of the stack, for sure; but should they be part of numpy? I think its cleaner to have them in a separate package. Id rather have us discuss how to facilitate the integration of as many possible fft libraries with numpy behind a maximally uniform interface, rather than having us debate which fft library is 'best'.
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion


On 29 October 2014 10:48, Eelco Hoogendoorn < [hidden email]> wrote:
> My point isn't about speed; its about the scope of numpy. typing np.fft.fft
> isn't more or less convenient than using some other symbol from the
> scientific python stack.
The problem is in distribution. For many users, installing a new
library is not easy (computing cluster, company regulations...). And
this assuming the alternative library is held to the same quality
standards as Numpy.
Another argument is that this should only be living in Scipy, that is,
after all, quite standard; but it requires a FORTRAN compiler, that is
quite a big dependency.
/David.
_______________________________________________
NumPyDiscussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpydiscussion

12
