On Sat, 3 Apr 2004, David Roundy wrote:
On Sat, Apr 03, 2004 at 07:04:18PM +0200, Henning Thielemann wrote:
What is the most promising strategy to speed up the computation without loosing the elegance of Haskell's lists? 1. Upgrading GHC from 6.0 to the current version? 2. Use of simplification rules? How can I find out what new rules may be useful? The several dumps that GHC can generate are a bit hard to understand. :-( Is there some more detailed information about what rules GHC already applies than what one can get with -ddump-simpl-stats and -ddump-rules? 3. More strictness? Is a custom list structure with strict entries and maybe with only one constructor (thus always infinite) a considerable alternative? This would disallow the use of lots of functions that deal with lists, including State monad functions. 4. A list of arrays? Then signal processes with feedback like an echo are much more difficult.
Lists are slow, and laziness is slow, but on the other hand, computers are fast, so before trying any of 1-4 (all of which seem likely to uglify your code a bit)
For 1. a change wouldn't be necessary at all, for 2. the rules can be kept away from the actual implementation. Thus these variants would uglify the code only minimally.
I assume that if your highest priority was writing blindingly fast code, you'd be writing in C.
No, not _that_ ugly! :-) I have already coded some of the algorithms in Motorola DSP 56000 assembly language.
I guess one thing you could try (if you haven't already done so) is writing a simple program that just reads and writes and does nothing in between (except convert to a lazy list), to see how slow that is.
I have attached such an example together with the generated profile. It generates two signals: 1. 100000 zero samples, 2. 100000 samples of a saw oscillator with exponentially decaying frequency. Together it needs 1.0 seconds on my machine with 1.6 GHz which is very slow compared to the computational effort. The conversion from floating point numbers to 16 bit signed integers is quite cumbersome, maybe you know of a better one. Btw. is there a version of 'properFraction' that evaluates 'properFraction (-1.5)' to (-2,0.5) rather than (-1,-0.5) ?
Is laziness really an important issue? Are you interested in it mostly just for memory consumption reasons, to avoid holding an entire file in memory, or are you perhaps thinking to make the code work with real-time input?
I don't want to exclude real-time processing from the beginning. It's an unfortunate connection that laziness is perfectly suited for real-time processing but is much too slow for it. ;-)
On the other hand, with ForeignPtr's you leave yourself open to the possibility of calling an FFT program through the FFI, and you definitely *don't* want to write an FFT in haskell.
It's already done: http://haskelldsp.sourceforge.net/doc/Numeric.Transform.Fourier.FFT.html :-)