![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Hi, I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc... cheers, David
![](https://secure.gravatar.com/avatar/547665790a071bb74c66ff10cc3a378a.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 7:59 AM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc...
+1 I don't think I ever reported it, but I am pretty sure I have run into problems by just having it installed when building SciPy. I would be interested in whether anyone is able to successful use it. -- Jarrod Millman Computational Infrastructure for Research Labs 10 Giannini Hall, UC Berkeley phone: 510.643.4014 http://cirl.berkeley.edu/
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 11:30 AM, Jarrod Millman <millman@berkeley.edu> wrote:
On Mon, May 12, 2008 at 7:59 AM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc...
+1 I don't think I ever reported it, but I am pretty sure I have run into problems by just having it installed when building SciPy. I would be interested in whether anyone is able to successful use it.
I usually do have it installed and built into scipy, and I don't think I have had any problems with it. But I'm not averse to removing it if it causing problems for other people. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/547665790a071bb74c66ff10cc3a378a.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 9:36 AM, Robert Kern <robert.kern@gmail.com> wrote:
I usually do have it installed and built into scipy, and I don't think I have had any problems with it. But I'm not averse to removing it if it causing problems for other people.
If no one else has run into this problem, I will see if I can figure out what the exact issue I ran into was. -- Jarrod Millman Computational Infrastructure for Research Labs 10 Giannini Hall, UC Berkeley phone: 510.643.4014 http://cirl.berkeley.edu/
![](https://secure.gravatar.com/avatar/0b7d465c9e16b93623fd6926775b91eb.jpg?s=120&d=mm&r=g)
Robert Kern wrote:
On Mon, May 12, 2008 at 11:30 AM, Jarrod Millman <millman@berkeley.edu> wrote:
On Mon, May 12, 2008 at 7:59 AM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc...
+1 I don't think I ever reported it, but I am pretty sure I have run into problems by just having it installed when building SciPy. I would be interested in whether anyone is able to successful use it.
I usually do have it installed and built into scipy, and I don't think I have had any problems with it. But I'm not averse to removing it if it causing problems for other people.
fftw is great, but be aware it has a restricted license.
![](https://secure.gravatar.com/avatar/2a726b0de1ade0be11fb5bc5a383d71d.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 5:59 pm, David Cournapeau wrote:
Hi,
I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc...
djbfft is important for applications that need only the 2^n sizes support and here djbfft have speed advantage over other fft implementations. For some of these applications the fft speed can be crusial. Therefore my suggestion is not to drop the djbfft support but rather to move it from scipy to a standalone package. Then users, who need the fastest 2^n fft, can use it. This makes maintaining scipy.fft as well as djbfft wrappers easier. I have been using djbfft backend in scipy without problems. In my experience, most problems from using djbfft as a fft backend in scipy, are due to not installing djbfft according to its installation instructions. Somehow people tend to prefer their conventions but djbfft happens to be very sensitive to other conventions and then various problems follow easily. Regards, Pearu
![](https://secure.gravatar.com/avatar/af6c39d6943bd4b0e1fde23161e7bb8c.jpg?s=120&d=mm&r=g)
2008/5/12 Pearu Peterson <pearu@cens.ioc.ee>:
djbfft is important for applications that need only the 2^n sizes support and here djbfft have speed advantage over other fft implementations. For some of these applications the fft speed can be crusial.
I'm not so sure this is true any longer. From the FFTW discussion page on Wikipedia, by one of the authors of FFTW: """ Nowadays, both djbfft and pfftw are trounced on Intel processors by anything that uses SSE/SSE2 instructions, such as recent FFTW versions or the Intel Math Kernel Libraries. """ Here pfftw refers to their implementation of fixed size, out-of-order FFTs (what djbfft does). As for the licensing issue which someone else brought up: djbfft doesn't even have a license (not on its website, anyway). It is also no longer supported (last release 1999). That's extra ammo for the "release frequently" argument in the other thread: if you don't, then people think your project is dead! I'm of the opinion that, unless benchmarks show an advantage to keeping djbfft, keeping it around may be more trouble than it is worth. Regards Stéfan
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 3:17 PM, Stéfan van der Walt <stefan@sun.ac.za> wrote:
As for the licensing issue which someone else brought up: djbfft doesn't even have a license (not on its website, anyway).
D.J. Bernstein has released all of his code to the public domain. (One can quibble about the exact technicalities of this, a la Larry Rosen, but I think we're safe.) http://video.google.com/videoplay?docid=-3147768955127254412 -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/af6c39d6943bd4b0e1fde23161e7bb8c.jpg?s=120&d=mm&r=g)
2008/5/12 Robert Kern <robert.kern@gmail.com>:
On Mon, May 12, 2008 at 3:17 PM, Stéfan van der Walt <stefan@sun.ac.za> wrote:
As for the licensing issue which someone else brought up: djbfft doesn't even have a license (not on its website, anyway).
D.J. Bernstein has released all of his code to the public domain. (One can quibble about the exact technicalities of this, a la Larry Rosen, but I think we're safe.)
http://video.google.com/videoplay?docid=-3147768955127254412
Interestring that that conversation took place at Sage Days 6 (them using the GPL and all). I suppose D. Bernstein hadn't gotten around to changing the notices on his web page in the end. Thanks for the link! Stéfan
![](https://secure.gravatar.com/avatar/547665790a071bb74c66ff10cc3a378a.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 1:48 PM, Stéfan van der Walt <stefan@sun.ac.za> wrote:
Interestring that that conversation took place at Sage Days 6 (them using the GPL and all). I suppose D. Bernstein hadn't gotten around to changing the notices on his web page in the end.
He has the notice up on his FAQ: http://cr.yp.to/distributors.html -- Jarrod Millman Computational Infrastructure for Research Labs 10 Giannini Hall, UC Berkeley phone: 510.643.4014 http://cirl.berkeley.edu/
![](https://secure.gravatar.com/avatar/af6c39d6943bd4b0e1fde23161e7bb8c.jpg?s=120&d=mm&r=g)
2008/5/12 Jarrod Millman <millman@berkeley.edu>:
On Mon, May 12, 2008 at 1:48 PM, Stéfan van der Walt <stefan@sun.ac.za> wrote:
Interestring that that conversation took place at Sage Days 6 (them using the GPL and all). I suppose D. Bernstein hadn't gotten around to changing the notices on his web page in the end.
He has the notice up on his FAQ: http://cr.yp.to/distributors.html
And now I know why it is a FAQ! :) Thanks Stéfan
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Pearu Peterson wrote:
djbfft is important for applications that need only the 2^n sizes support and here djbfft have speed advantage over other fft implementations. For some of these applications the fft speed can be crusial.
Are you sure djbfft speed advantage is still true today ? When I run scipy.fftpack.bench, I hardly see any different between fftw3 and djbfft, and the current use of fftw3 is less than optimal (we can at least get a two fold increase with an improved design, because right now, we are using the worst possible plan method). When I run the benchmarks, the only backend significantly faster than the other ones is the MKL. cheers, David
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 8:26 PM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
Pearu Peterson wrote:
djbfft is important for applications that need only the 2^n sizes support and here djbfft have speed advantage over other fft implementations. For some of these applications the fft speed can be crusial.
Are you sure djbfft speed advantage is still true today ? When I run scipy.fftpack.bench, I hardly see any different between fftw3 and djbfft, and the current use of fftw3 is less than optimal (we can at least get a two fold increase with an improved design, because right now, we are using the worst possible plan method).
When I run the benchmarks, the only backend significantly faster than the other ones is the MKL.
Neither djbfft vs. fftw nor djbfft vs. MKL are definitive comparisons. Not everyone can use GPLed code or proprietary code. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Robert Kern wrote:
Neither djbfft vs. fftw nor djbfft vs. MKL are definitive comparisons. Not everyone can use GPLed code or proprietary code.
I understand that, I was merely answering to the fact that djbfft is the fastest. We have fftpack for people who do not care so much about speed, no ? IOW, I understand there are people who care about speed, people who care about open source, and people who care about not depending on both GPL and proprietary code. We support all this, and can still do it without depending on djbfft. But do we need to satisfy all the combinations of the above ? cheers, David
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 8:53 PM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
Robert Kern wrote:
Neither djbfft vs. fftw nor djbfft vs. MKL are definitive comparisons. Not everyone can use GPLed code or proprietary code.
I understand that, I was merely answering to the fact that djbfft is the fastest. We have fftpack for people who do not care so much about speed, no ? IOW, I understand there are people who care about speed, people who care about open source, and people who care about not depending on both GPL and proprietary code. We support all this, and can still do it without depending on djbfft. But do we need to satisfy all the combinations of the above ?
I'd drop FFTW and MKL support first before djbfft because they are not compatible with the scipy license. Perhaps this subsystem just needs to be redesigned. I think a lot of the complexity derives from the fact that we're doing the dispatching in C. If we moved the dispatching up to Python and just let external packages register themselves, we can probably save ourselves a substantial number of headaches. By separating the backend implementations, each can actually be unit-tested instead of integration-tested, and no one has to face a combinatorial explosion. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Robert Kern wrote:
I'd drop FFTW and MKL support first before djbfft because they are not compatible with the scipy license.
If we moved the dispatching up to Python and just let external packages register themselves, we can probably save ourselves a substantial number of headaches. By separating the backend implementations, each can actually be unit-tested instead of integration-tested, and no one has to face a combinatorial explosion. Yes, that's exactly what I wanted to do (fftpack by default, always, and dynamically changing the backend if wanted). I am trying to define fftpack as a C header, and each backend as an implementation of this API. But since no backend implements the same things (fftpack aside),
Ok. that's not easy. A lot of the complexities comes from this: for example, real to real fft is only implemented in fftpack right now; complex to complex and multi dimensional are available in fftw3 and mkl, complex to real available in fftw3. This makes refactoring fftpack as an API + different backends implementing this API wihout breaking anything tedious. The other approach could be to drop all backends but fftpack, and forcing a new backend to implement the whole api (I would be willing to implement a full backend for fftw3 because it is open source, as well as djbfft, but no other). cheers, David
![](https://secure.gravatar.com/avatar/ab7e74f2443b81e5175638d72be65e07.jpg?s=120&d=mm&r=g)
2008/5/12 David Cournapeau <david@ar.media.kyoto-u.ac.jp>:
If we moved the dispatching up to Python and just let external packages register themselves, we can probably save ourselves a substantial number of headaches. By separating the backend implementations, each can actually be unit-tested instead of integration-tested, and no one has to face a combinatorial explosion. Yes, that's exactly what I wanted to do (fftpack by default, always, and dynamically changing the backend if wanted). I am trying to define fftpack as a C header, and each backend as an implementation of this API. But since no backend implements the same things (fftpack aside),
Robert Kern wrote: that's not easy. A lot of the complexities comes from this: for example, real to real fft is only implemented in fftpack right now; complex to complex and multi dimensional are available in fftw3 and mkl, complex to real available in fftw3. This makes refactoring fftpack as an API + different backends implementing this API wihout breaking anything tedious.
The other approach could be to drop all backends but fftpack, and forcing a new backend to implement the whole api (I would be willing to implement a full backend for fftw3 because it is open source, as well as djbfft, but no other).
How about a third approach (which I think may be what Robert Kern was suggesting)? Simply SWIGify (or cythonify or f2pyify) each library, so that they each provide their own API to python. Then write the detection/wrapper code in python, where it's relatively easy to muck about with dispatching and API finagling. Would there be a big performance hit for operations that do many small FFTs? Is there much code that calls the FFTs at a C level? Anne
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Anne Archibald wrote:
How about a third approach (which I think may be what Robert Kern was suggesting)? Simply SWIGify (or cythonify or f2pyify) each library, so that they each provide their own API to python. Then write the detection/wrapper code in python, where it's relatively easy to muck about with dispatching and API finagling.
Yes, in my mind, that's the same thing: the complicated part is not the wrapping (it is already done through f2py anway), but the "libification", that is making sure that each backend is independant. Doing it from scratch is easy, doing it gradually while keeping compatibility is more work. But well, since dropping djbfft was not an option, I went forward, and I am almost done having one backend = one library in the refactor_fft branch. I still need to fight with distutils, but I know it well enough to win this time :) cheers, David
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Tue, May 13, 2008 at 12:06 AM, David Cournapeau <david@ar.media.kyoto-u.ac.jp> wrote:
Anne Archibald wrote:
How about a third approach (which I think may be what Robert Kern was suggesting)? Simply SWIGify (or cythonify or f2pyify) each library, so that they each provide their own API to python. Then write the detection/wrapper code in python, where it's relatively easy to muck about with dispatching and API finagling.
Yes, in my mind, that's the same thing: the complicated part is not the wrapping (it is already done through f2py anway), but the "libification", that is making sure that each backend is independant. Doing it from scratch is easy, doing it gradually while keeping compatibility is more work.
But well, since dropping djbfft was not an option, I went forward, and I am almost done having one backend = one library in the refactor_fft branch. I still need to fight with distutils, but I know it well enough to win this time :)
I think we're still talking past each other. What I was suggesting is that FFTW(3), MKL, etc. are moved to separate *packages* outside of scipy. Each would expose Python-level fft(), rfft(), ... whatever each library implements. Each package would have a registration function which would tell scipy.fftpack that these are optimized implementations that scipy.fftpack.fft(), etc. could call. scipy.fftpack.fft() and friends would be pure Python and check to see if an optimized version was registered (and possibly if the inputs are a power of 2 if the optimized version requires it). If not, it falls back to the FFTPACK implementation which comes with scipy.fftpack. If it were feasible to build the djbfft library in our build system, it would be nice if we could simply absorb the source into ours and make it a non-optional backend. Otherwise, it also gets kicked out into a scikit like the others. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Robert Kern wrote:
I think we're still talking past each other. What I was suggesting is that FFTW(3), MKL, etc. are moved to separate *packages* outside of scipy.
Yes, I understand that, but if we want to provide non broken packages for mkl and co, we need to separate the code in scipy.fftpack. Or did you mean just put the current code in scikits, even if not buildable, and people who want them just have to upgrade the code ? For djbfft, the problem is that its performances are dependent on the compiler options. IOW, building it should be easy, building it such as it is faster than fftpack maybe not so. cheers, David
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
David Cournapeau wrote:
Robert Kern wrote:
I think we're still talking past each other. What I was suggesting is that FFTW(3), MKL, etc. are moved to separate *packages* outside of scipy.
Robert, if you have a few minutes, would you be mind taking a look at the refactor_fft branch ? Basically, I tried to split as much as possible each backend (each one is a library, instead of the whole extensions being one big source file including other source files), so that we can remove them and put them into scikits without breaking them totally. As it is, the branch it is 100 % backward compatible with the trunk (I tried to test all possible combinations, but I may have missed some). So if you think the code is OK, I could then work on the registration thing, and put mkl, fftw and (djbfft ?) in scikits. cheers, David
![](https://secure.gravatar.com/avatar/3e3b4dff04d6c945d0f990ea8c362abb.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 9:44 PM, Robert Kern <robert.kern@gmail.com> wrote:
Neither djbfft vs. fftw nor djbfft vs. MKL are definitive comparisons. Not everyone can use GPLed code or proprietary code.
I understand that, I was merely answering to the fact that djbfft is the fastest. We have fftpack for people who do not care so much about speed, no ? IOW, I understand there are people who care about speed, people who care about open source, and people who care about not depending on both GPL and proprietary code. We support all this, and can still do it without depending on djbfft. But do we need to satisfy all the combinations of the above ?
I'd drop FFTW and MKL support first before djbfft because they are not compatible with the scipy license.
I don't see how this addresses David's argument. While being the "fastest BSD-compatible FFT for power of 2 problem sizes" achieves a certain Pareto optimality, wouldn't it be more productive to provide better support for actively maintained libraries that are faster and more general? How large is the djbfft + SciPy user base? -- Nathan Bell wnbell@gmail.com http://graphics.cs.uiuc.edu/~wnbell/
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
Nathan Bell wrote:
I don't see how this addresses David's argument.
I understand that Robert's position is if supporting too many backends is a burden, just drop mkl and fftw(2/3). Supporting fftpack and djbfft only would certainly be much easier. cheers, David
![](https://secure.gravatar.com/avatar/60e03bd1fd9f2dbc750e0899b9e7e71d.jpg?s=120&d=mm&r=g)
2008/5/13 David Cournapeau <david@ar.media.kyoto-u.ac.jp>:
Nathan Bell wrote:
I don't see how this addresses David's argument.
I understand that Robert's position is if supporting too many backends is a burden, just drop mkl and fftw(2/3). Supporting fftpack and djbfft only would certainly be much easier.
Well, for people that want Matlab-fast FFT (and those are the people you want to satisfy with the plug-in system with numpy), dropping the fastest libraries is not the best way to get them. Just my two cents. Matthieu -- French PhD student Website : http://matthieu-brucher.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92 LinkedIn : http://www.linkedin.com/in/matthieubrucher
![](https://secure.gravatar.com/avatar/764323a14e554c97ab74177e0bce51d4.jpg?s=120&d=mm&r=g)
On Mon, May 12, 2008 at 10:11 PM, Nathan Bell <wnbell@gmail.com> wrote:
On Mon, May 12, 2008 at 9:44 PM, Robert Kern <robert.kern@gmail.com> wrote:
I'd drop FFTW and MKL support first before djbfft because they are not compatible with the scipy license.
I don't see how this addresses David's argument.
Sure it does. He wants to reduce the number of combinations of optional libraries to support. Dropping any one of them reduces that number.
While being the "fastest BSD-compatible FFT for power of 2 problem sizes" achieves a certain Pareto optimality, wouldn't it be more productive to provide better support for actively maintained libraries that are faster and more general?
Not if their licenses conflict with scipy's, no. I think it's a waste of time to support optional backends instead of scipy itself. These optional backends will always be second-class citizens since official distributions won't (or shouldn't) include them. As with UMFPACK, I think that optional components, particularly incompatibly-licensed components, lead to more trouble than they are worth. I'd drop djbfft, too, if we can move to a system where external packages can register their implementations instead of having to build everything in. Or if we could absorb djbfft like we did FFTPACK so it is not an optional component.
How large is the djbfft + SciPy user base?
I don't think you'll ever get a confident answer to that question, for any combination of "foo" + scipy. Speculating will get us nowhere. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
![](https://secure.gravatar.com/avatar/1bc8694bf55c688b2aa2075eedf9b4c6.jpg?s=120&d=mm&r=g)
Hey David, When we put the fft library together back in 2001-2002, there wasn't a good alternative for a fast fft package that wasn't GPLed. fftw was reasonably fast and fully functioning, but GPLed. fftpack had the functionality, but not the speed. djbfft (at the time) was noticeably faster than either of these for its important subset of functionality (radix 2), but wasn't full featured. The combination of djbfft and fftpack gave us a BSD compatible and fast library for SciPy. This was the combination that we used to build the binaries that were available from the scipy.org website. Having been out of the building SciPy game for a while, my question would be, what fft libraries are used now to build the binaries for scipy.org? Are they using fftpack only? If so, they are likely much slower than they need to be. My guess is that the binaries are not linked to MKL or FFTW because of licensing issues. Is there another alternative that we can use now that is fast, BSD compatible, and simpler to build? I'm very sympathetic to build issues, so if getting rid of djbfft simplifies things, then it is well worth considering. If, on the other hand, it results in slow-ish fft algorithms in the SciPy provided binaries, this also needs to be weighed as a drawback. eric On May 12, 2008, at 9:59 AM, David Cournapeau wrote:
Hi,
I would like to ask again about dropping djbfft support. Djbfft is a fft implementation, which has not been updated since 1999, and is not packaged by most linux distributions (I quite doubt anyone on windows is using it). Also, because it only supports 2^n sizes, it has to be used simultaneously with another backend (fftpack, fftw, fftw3, etc....). The later is why I would like to drop it: it is quite a PITA to test all combinations, and it takes a lot of time for maybe one or two users out there. I would much prefer spending times on improving things like our fftw3 support, float support, etc...
cheers,
David _______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-dev
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
eric jones wrote:
Hey David,
When we put the fft library together back in 2001-2002, there wasn't a good alternative for a fast fft package that wasn't GPLed. fftw was reasonably fast and fully functioning, but GPLed. fftpack had the functionality, but not the speed. djbfft (at the time) was noticeably faster than either of these for its important subset of functionality (radix 2), but wasn't full featured. The combination of djbfft and fftpack gave us a BSD compatible and fast library for SciPy. This was the combination that we used to build the binaries that were available from the scipy.org website.
Having been out of the building SciPy game for a while, my question would be, what fft libraries are used now to build the binaries for scipy.org? Are they using fftpack only? Hi Eric,
My understanding is that, at least for the windows binaries, only fftpack is used. I would guess that on linux, people use fftw3, since it is packaged by most distributions. The problem is not a build issue per se. Because djbfft only supports 2^n, single dimension, we need to use another backend at the same time. Today, we support 4 backends (+ djbfft), which means I have to test 8 combinations (not 9 because when mkl is used, djbfft is not used at all). This, combined to the fact that every fft backend is different, makes moving forward more painful that I wished. I think the speed issue is a bit moot, in the sense that right now, we do not use the backends very efficiently anyway. I started working on fftpack to get more speed (in place and out of place, float support, fftw plan control), but instead of improving the code, I am spending most of my time checking that I am not breaking any possible environment combination. cheers, David
![](https://secure.gravatar.com/avatar/1bc8694bf55c688b2aa2075eedf9b4c6.jpg?s=120&d=mm&r=g)
On May 12, 2008, at 8:07 PM, David Cournapeau wrote:
eric jones wrote:
Hey David,
When we put the fft library together back in 2001-2002, there wasn't a good alternative for a fast fft package that wasn't GPLed. fftw was reasonably fast and fully functioning, but GPLed. fftpack had the functionality, but not the speed. djbfft (at the time) was noticeably faster than either of these for its important subset of functionality (radix 2), but wasn't full featured. The combination of djbfft and fftpack gave us a BSD compatible and fast library for SciPy. This was the combination that we used to build the binaries that were available from the scipy.org website.
Having been out of the building SciPy game for a while, my question would be, what fft libraries are used now to build the binaries for scipy.org? Are they using fftpack only? Hi Eric,
My understanding is that, at least for the windows binaries, only fftpack is used.
Ok. That is likely not optimal, but your other comments about speeding up the use of fftpack algorithms may ameliorate this issue while simplifying build.
I would guess that on linux, people use fftw3, since it is packaged by most distributions.
How do 3rd party Linux version packagers ( Redhat, Ubuntu, Suse, etc) package SciPy? Do they link against fftw or fftpack?
The problem is not a build issue per se. Because djbfft only supports 2^n, single dimension, we need to use another backend at the same time. Today, we support 4 backends (+ djbfft), which means I have to test 8 combinations (not 9 because when mkl is used, djbfft is not used at all). This, combined to the fact that every fft backend is different, makes moving forward more painful that I wished.
One option would be to just use djbfft with fftpack. This was the idea when it was added.
I think the speed issue is a bit moot, in the sense that right now, we do not use the backends very efficiently anyway. I started working on fftpack to get more speed (in place and out of place, float support, fftw plan control), but instead of improving the code, I am spending most of my time checking that I am not breaking any possible environment combination.
If it can be removed and we can keep the speed, that seems like a great win. If we loose the speed, I'd prefer just limiting djbfft to use with fftpack and disallowing the other combinations. eric
cheers,
David _______________________________________________ Scipy-dev mailing list Scipy-dev@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-dev
![](https://secure.gravatar.com/avatar/9820b5956634e5bbad7f4ed91a232822.jpg?s=120&d=mm&r=g)
eric jones wrote:
How do 3rd party Linux version packagers ( Redhat, Ubuntu, Suse, etc) package SciPy? Do they link against fftw or fftpack?
fftpack is always used (for real to real fft, for example), and integrated in scipy. Ubuntu and debian link against fftw2. I don't know about rpm-based distributions. The code in the refactor_fft branch is now ready to split fftpack into the parts which will stay in scipy (fftpack, djbfft ?) and the others, which will go into a scikits. I will then work on the registration system suggested by Robert, which should not be difficult to do. cheers, David
participants (10)
-
Anne Archibald
-
David Cournapeau
-
eric jones
-
Jarrod Millman
-
Matthieu Brucher
-
Nathan Bell
-
Neal Becker
-
Pearu Peterson
-
Robert Kern
-
Stéfan van der Walt