[Haskell-cafe] Benchmark of DFT libraries in Haskell

[Scott Michel]

Ertugrul:

I might be missing something in translation, but if I understand Takayuki's
message's intent, everything needs to be calculated because the C-based
FFTW library is called (eventually). Laziness doesn't really have an impact.

The choice of underlying data structure and whether FFTW wisdom is used
clearly has a significant impact.

FFTW and Intel's MKL libraries are the acknowledged "state of the art"
libraries for performing discrete Fourier transforms. I'm not sure there's
anything better or faster for CPU implementations (I know there's a O(1)
implementation for map-reduce systems and NVIDIA's CUDA-FFT. Note that the
map-reduce approach has a preprocessing step that isn't O(1).) Interesting
to note that much of the code for FFTW was initially generated using OCaml
to find optimal versions of code for particular problem sizes.


-scooter

On Sun, Aug 5, 2012 at 6:37 PM, Ertugrul Söylemez <es at ertes.de> wrote:

> Takayuki Muranushi <muranushi at gmail.com> wrote:
>
> > * vector-fftw with wisdom was more than 1/2 times faster than fftw in
> > C with wisdom (and with communication overhead.)
> > * vector-fftw without wisdom was significantly _faster_ than fftw in C
> > without wisdom. I wonder why.
> > * vector-fftw over vector was faster than fft over CArray.
> > * any library that doesn't use fftw is much slower than those that
> > does.
>
> I have no experience with FFTW, but in general a result like this often
> means that you may not have actually calculated the values themselves.
> One easy way to ensure this is to print out the whole result.  If you
> feel like printing takes too much CPU time for comparison, you need to
> force deeply like with deepseq.
>
> Notably Data.Vector is a lazy data structure.  If you force the vector
> itself, you are not forcing the individual values.  For FFT I would
> assume that the length of the resulting vector does not depend on any
> values.
>
>
> Greets,
> Ertugrul
>
> --
> Not to be or to be and (not to be or to be and (not to be or to be and
> (not to be or to be and ... that is the list monad.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120805/0bd87faf/attachment.htm>