FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

classic Classic list List threaded Threaded
38 messages Options
12
Reply | Threaded
Open this post in threaded view
|

FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Nathaniel Smith

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
> >> kick-ass 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 x86-32 support.)

-  no runtime CPU detection, e.g. SSE vs AVX appears to be a compile time decision

- not sure if it can handle non-power-of-two 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


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Jerome Kieffer
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
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Charles R Harris


On Tue, Oct 28, 2014 at 1:32 AM, 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

Because the plan creation was taking ages with FFTw, numpy's FFTPACK was often faster (overall)

Cheers,

Ondrej says that f90 fftpack (his mod) runs faster than fftw. The main thing missing from fftpack is the handling of transform sizes that are not products of 2,3,4,5.

Chuck


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

David Cournapeau


On Tue, Oct 28, 2014 at 9:19 AM, Charles R Harris <[hidden email]> wrote:


On Tue, Oct 28, 2014 at 1:32 AM, 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

Because the plan creation was taking ages with FFTw, numpy's FFTPACK was often faster (overall)

Cheers,

Ondrej says that f90 fftpack (his mod) runs faster than fftw.

I would be interested to see the benchmarks for this.

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.

The main thing missing from fftpack is the handling of transform sizes that are not products of 2,3,4,5.

Strickly speaking, it is handled, just not through an FFT (it goes back to the brute force O(N**2)).

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).

David


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Henry Gomersall-2
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/pyFFTW

If 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
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Henry Gomersall-2
In reply to this post by Nathaniel Smith
On 28/10/14 04:28, Nathaniel Smith wrote:
>
> - not sure if it can handle non-power-of-two 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
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Sturla Molden
In reply to this post by Jerome Kieffer
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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Sturla Molden
In reply to this post by David Cournapeau
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 look-up 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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Nathaniel Smith
In reply to this post by Jerome Kieffer

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 cache-oblivious 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. power-of-two transforms).

The paper has lots of benchmark graphs, including measurements of setup time:
  http://anthonix.com/ffts/preprints/tsp2013.pdf

-n


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Eelco Hoogendoorn
In reply to this post by Sturla Molden
If I may 'hyjack' the discussion back to the meta-point:

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/scipy-stack in some way or another. But I would argue that the core thing that numpy should do is ndarrays alone.

On Tue, Oct 28, 2014 at 11:11 AM, Sturla Molden <[hidden email]> wrote:
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 look-up 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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

David Cournapeau
In reply to this post by Nathaniel Smith
I

On Tue, Oct 28, 2014 at 2:31 PM, Nathaniel Smith <[hidden email]> wrote:

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 cache-oblivious 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. power-of-two transforms).

The paper has lots of benchmark graphs, including measurements of setup time:
  http://anthonix.com/ffts/preprints/tsp2013.pdf


Nice. In this case, the solution may be to implement the Bluestein transform to deal with prime/near-prime numbers on top of FFTS.

I did not look much, but it did not obviously support building on windows as well ?

David
 

-n


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion



_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Nathaniel Smith
In reply to this post by Eelco Hoogendoorn

On 28 Oct 2014 14:48, "Eelco Hoogendoorn" <[hidden email]> wrote:
>
> If I may 'hyjack' the discussion back to the meta-point:
>
> 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 3rd-party fft libraries. But fft is such a basic algorithm that it'd be silly to ask people who just need a quick one-off fft to go evaluate a bunch of third-party 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/scipy-stack 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


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

David Cournapeau
In reply to this post by David Cournapeau


On Tue, Oct 28, 2014 at 3:06 PM, David Cournapeau <[hidden email]> wrote:
I

On Tue, Oct 28, 2014 at 2:31 PM, Nathaniel Smith <[hidden email]> wrote:

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 cache-oblivious 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. power-of-two transforms).

The paper has lots of benchmark graphs, including measurements of setup time:
  http://anthonix.com/ffts/preprints/tsp2013.pdf


Nice. In this case, the solution may be to implement the Bluestein transform to deal with prime/near-prime numbers on top of FFTS.

I did not look much, but it did not obviously support building on windows as well ?

Ok, I took a quick look at it, and it will be a significant effort to be able to make FFTS work at all with MSVC on windows:

- the code is not C89 compatible
- it uses code generation using POSIX library. One would need to port that part to using Win32 API as well.
- the test suite looks really limited (roundtripping only).

The codebase does not seem particularly well written either (but neither is FFTPACK to be fair).

Nothing impossible (looks like Sony at least uses this code on windows: https://github.com/anthonix/ffts/issues/27#issuecomment-40204403), but not a 2 hours thing either.

David

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Sturla Molden
In reply to this post by Eelco Hoogendoorn
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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Daniele Nicolodi
In reply to this post by David Cournapeau
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#issuecomment-40204403), but
> not a 2 hours thing either.

One of the downsides of the BSD license :)

Cheers,
Daniele


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Stéfan van der Walt
On 2014-10-28 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#issuecomment-40204403), 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.

Stéfan
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Daniele Nicolodi
On 28/10/14 18:44, Stefan van der Walt wrote:

> On 2014-10-28 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#issuecomment-40204403), 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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Stéfan van der Walt
On 2014-10-28 19:55:57, Daniele Nicolodi <[hidden email]> wrote:

> On 28/10/14 18:44, Stefan van der Walt wrote:
>> On 2014-10-28 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#issuecomment-40204403), 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
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Eelco Hoogendoorn
In reply to this post by Sturla Molden
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'.

On Tue, Oct 28, 2014 at 6:21 PM, Sturla Molden <[hidden email]> wrote:
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

_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion


_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: FFTS for numpy's FFTs (was: Re: Choosing between NumPy and SciPy functions)

Daπid
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.
_______________________________________________
NumPy-Discussion mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/numpy-discussion
12