[Haskell-cafe] Re: fftw bindings
Magnus Therning wrote: On Thu, Apr 19, 2007 at 09:20:36 -0700, David Roundy wrote: On Thu, Apr 19, 2007 at 05:37:05PM +0200, Fawzi Mohamed wrote: I was wondering if someone had fftw bindings for haskell, or if I should roll my own. Not that I'm aware of, but if you roll your own, please make them public, as I'll be interested in fftw bindings before long. For us less knowledgable, what's fftw? "Fastest Fourier Transform in the West." http://www.fftw.org/ Its cool, they use generative programming: an OCaml program generates "codlets" in C that can be composed and tuned to the specifics of your machine, then compiled into a blazingly fast FFT/DFT library. /M (curious) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
On Thu, Apr 19, 2007 at 05:46:49PM -0400, Al Falloon wrote: > >For us less knowledgable, what's fftw? > > "Fastest Fourier Transform in the West." http://www.fftw.org/ > > Its cool, they use generative programming: an OCaml program generates > "codlets" in C that can be composed and tuned to the specifics of your > machine, then compiled into a blazingly fast FFT/DFT library. But that's only the beginning of the coolness! fftw uses runtime timings to optimize each fourier transform based on the behavior of the computer on which it is being run--its cache, memory speed, CPU, etc. The result being that fftw using portable C can beat out most hand-optimized fftw libraries written in assembly! Steven (one of fftw's two authors) has done some incredible work on optimizations. The most unbelievable (to me) was that by eliminating negative constants from the generated code (using subtraction instead) they sped up the library on a particular architecture by some some significant margin (I think I recall 20%). -- David Roundy http://www.darcs.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
Are you aware of Dan J. Bernstein's library?: http://cr.yp.to/djbfft.html According to his benchmarks (from 1999?) it is faster than FFTW. I don't know whether that's still the case, a quick search did turn up http://projects.scipy.org/pipermail/scipy-dev/2002-August/001107.html which suggests that this was still the case in 2002. Support for djbfft seems to have been integrated into scipy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: fftw bindings
> On Thu, Apr 19, 2007 at 05:46:49PM -0400, Al Falloon wrote: > > >For us less knowledgable, what's fftw? > > > > "Fastest Fourier Transform in the West." http://www.fftw.org/ > > > > Its cool, they use generative programming: an OCaml program > generates > > "codlets" in C that can be composed and tuned to the > specifics of your > > machine, then compiled into a blazingly fast FFT/DFT library. > > But that's only the beginning of the coolness! fftw uses > runtime timings to > optimize each fourier transform based on the behavior of the > computer on > which it is being run--its cache, memory speed, CPU, etc. > The result being > that fftw using portable C can beat out most hand-optimized > fftw libraries > written in assembly! Steven (one of fftw's two authors) has done some > incredible work on optimizations. The most unbelievable (to > me) was that > by eliminating negative constants from the generated code (using > subtraction instead) they sped up the library on a particular > architecture > by some some significant margin (I think I recall 20%). > -- > David Roundy Oleg has some related work http://okmij.org/ftp/Computation/Generative.html#framework "... The papers discuss in detail the generation of a straight-line C, Fortran, etc. code for the power-of-two FFT. The papers show that with the help of Abstract Interpretation we can exactly match the quality of code generated by the well-known system FFTW. The second paper demonstrates that our generated power-of-two FFT code has exactly the same number of floating-point operations as that in codelets of FFTW. The significant difference from FFTW is that we do not do any intensional code analysis ... " I don't know how useful this is. Alistair * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
Christian Jaeger wrote: > Are you aware of Dan J. Bernstein's library?: http://cr.yp.to/djbfft.html > > According to his benchmarks (from 1999?) it is faster than FFTW. Quite possibly faster, but restricted to Intel and AMD CPUs. FFTW compiles and runs on anything with a C compiler. Erik -- +---+ Erik de Castro Lopo +---+ "Every time an American goes to a gas station, he is sending money to America's enemies." -- http://www.meforum.org/article/653 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
Erik de Castro Lopo wrote: > but restricted to Intel and AMD CPUs. This is wrong. I've just successfully compiled and run it on a PPC G3. > FFTW > compiles and runs on anything with a C compiler. > There is no PPC specific code in the sources, so djbfft did compile and run on PPC just by virtue of a C compiler. http://cr.yp.to/djbfft/install.html: "The djbfft installation procedure assumes that you have a UNIX system with gcc." That probably means that it won't build on Windows without cygwin or maybe MinGW; but likely that's just an issue of the build process (which is depending on make and sh), which isn't a big deal. Possibly it doesn't run competitively on architectures he hasn't optimized for. If you have valuable information about this, please provide it. Christian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
Thanks to everybody for the answers, For the moment I think that I will try to slightly expand http://ofb.net/~wnoise/haskell/FFTW/ that was pointed out to me by Patrik Sellin with respect to Dan J. Bernstein's library http://cr.yp.to/djbfft.html I was not aware of it, but I would like to have also non power of 2 grids... so FFTW. Fawzi ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fftw bindings
Christian Jaeger wrote: > There is no PPC specific code in the sources, so djbfft did compile and > run on PPC just by virtue of a C compiler. I stand corrected. I must admit it was many years ago that I last looked at djbfft. Erik -- +---+ Erik de Castro Lopo +---+ "A mouse is a device used to point at the xterm you want to type in." -- Kim Alm, a.s.r ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
