On 2005-05-03, David Roundy wrote:

An interesting challenge would be to rewrite fftw in haskell, and see how close one could come to the performance of the original... :)

What precisely do you mean by that? FFTW is C code generated by OCaml? Do you want to retarget ti so that Haskell is generated, or rewrite the generator in Haskell? (Or both?) -- Aaron Denney -><-

On Wed, May 04, 2005 at 07:20:20PM +0000, Aaron Denney wrote:

On 2005-05-03, David Roundy wrote:

...

An interesting challenge would be to rewrite fftw in haskell, and see how close one could come to the performance of the original... :)

What precisely do you mean by that? FFTW is C code generated by OCaml? Do you want to retarget ti so that Haskell is generated, or rewrite the generator in Haskell? (Or both?)

Both. I'd be curious to see how well one could do with pure haskell code. It may be possible to do reasonably well, and would certainly be instructive. FFTW is not simpley C code generated by OCaml, the C code also does runtime timing and optimization, generating new algorithms (by combining existing primitives) on the fly. This sort of code-generation-on-the-fly (or rather code-recombination) is what functional languages ought to be good at, if only there isn't too much overhead. I'd be interested if someone *else* did this. FFTW is an amazing piece of work, and I'd not want to bother duplicating their work. Another (also crazy) idea would be to implement a runtime-optimized version of ATLAS. That would be somewhat more practical, since I find it annoying that ATLAS is compile-time optimized, so you need to recompile it on each computer you use (or if you buy new RAM...). Of course, doing it all in haskell would still be silliness, but it'd be cool... :) And I think the algorithms involved in block matrix multiplies are much simpler than those involved in ffts. I don't know how it would work out in the real world, but it seems like one *ought* to be able to write truly beautiful auto-tuned code in haskell! Perhaps even some sort of a "time it as you go" mechanism could be used (if one had a clock with enough precision), which would eliminate the annoying feature of FFTW that one needs to create and keep track of plans. (Mostly I'm just daydreaming here... if only I were an undergrad again and had the time and energy for excessing hacking with very little hope of any practical benefit.) -- David Roundy