www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - FFT Lib?

reply dsimcha <dsimcha yahoo.com> writes:
I'm going to need an FFT library to perform some convolutions at some point
soon.  Two absolute, non-negotiable requirements are that it be written in
pure D and that it be Boost or compatibly (i.e. zlib or public domain)
licensed.  I also prefer "simple and good enough" over "has every
micro-optimization in the book but a PITA to maintain/modify/use", as long as
it's at least a true fft as opposed to an O(N^2) DFT.  A few questions:

1.  Does anyone already have such a lib?

2.  If noone has one I'll probably either write my own from scratch  or port
some code from C if I can find code that's under a suitable license and
written with a "simple and good enough" philosophy rather than an "every tiny
optimization in the book" philosophy.  Could anyone recommend one to port?

3.  If I do end up writing my own or porting, is there sufficient interest in
this that I should try to target it for std.numerics, or would I be better off
just making it good enough for my use case?
Jul 27 2010
next sibling parent reply "Mike James" <foo bar.com> writes:
"dsimcha" <dsimcha yahoo.com> wrote in message 
news:i2na5q$2kgi$1 digitalmars.com...

 I'm going to need an FFT library to perform some convolutions at some 
 point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use", as long 
 as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few questions:

 1.  Does anyone already have such a lib?

 2.  If noone has one I'll probably either write my own from scratch  or 
 port
 some code from C if I can find code that's under a suitable license and
 written with a "simple and good enough" philosophy rather than an "every 
 tiny
 optimization in the book" philosophy.  Could anyone recommend one to port?

 3.  If I do end up writing my own or porting, is there sufficient interest 
 in
 this that I should try to target it for std.numerics, or would I be better 
 off
 just making it good enough for my use case?


This is one of the best FFTs I've used...

http://www.fftw.org/

I don't know whether the licence is ok for you.

-=mike=-
Jul 27 2010
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Mike James (foo bar.com)'s article

 This is one of the best FFTs I've used...
 http://www.fftw.org/
 I don't know whether the licence is ok for you.
 -=mike=-


I was aware of this, but:

1.  GPL

2.  "every microoptimization", not "simple and good enough", so it would likely
be
a PITA to port.  This doesn't matter anyhow, though, because of (1).
Jul 27 2010
prev sibling next sibling parent reply Rory Mcguire <rjmcguire gm_no_ail.com> writes:
dsimcha wrote:


 I'm going to need an FFT library to perform some convolutions at some
 point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use", as long
 as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few questions:
 
 1.  Does anyone already have such a lib?
 
 2.  If noone has one I'll probably either write my own from scratch  or
 port some code from C if I can find code that's under a suitable license
 and written with a "simple and good enough" philosophy rather than an
 "every tiny
 optimization in the book" philosophy.  Could anyone recommend one to port?
 
 3.  If I do end up writing my own or porting, is there sufficient interest
 in this that I should try to target it for std.numerics, or would I be
 better off just making it good enough for my use case?



Hi,

I haven't used fft for anything before not sure what I'd use it for either,
here is public domain code claiming to be a fft:
	http://www.dsprelated.com/showmessage/36380/1.php
And here is a list of fft libs:
	http://fftw.org/benchfft/ffts.html

-Rory
Jul 27 2010
parent reply Fawzi Mohamed <fawzi gmx.ch> writes:
On 27-lug-10, at 21:47, Rory Mcguire wrote:


 dsimcha wrote:


 I'm going to need an FFT library to perform some convolutions at some
 point
 soon.  Two absolute, non-negotiable requirements are that it be  
 written in
 pure D and that it be Boost or compatibly (i.e. zlib or public  
 domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use",  
 as long
 as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few  
 questions:

 1.  Does anyone already have such a lib?

 2.  If noone has one I'll probably either write my own from  
 scratch  or
 port some code from C if I can find code that's under a suitable  
 license
 and written with a "simple and good enough" philosophy rather than an
 "every tiny
 optimization in the book" philosophy.  Could anyone recommend one  
 to port?

 3.  If I do end up writing my own or porting, is there sufficient  
 interest
 in this that I should try to target it for std.numerics, or would I  
 be
 better off just making it good enough for my use case?



 Hi,

 I haven't used fft for anything before not sure what I'd use it for  
 either,
 here is public domain code claiming to be a fft:
 	http://www.dsprelated.com/showmessage/36380/1.php
 And here is a list of fft libs:
 	http://fftw.org/benchfft/ffts.html

 -Rory


I was preceded, that is a good list. I can only say that FFTW is  
*really* good, and if you structure your code well you should be able  
to support more than one library.
I have wrappers for fftw, and it can be used with NArray (N  
dimensional dense arrays in blip), but is not directly there exactly  
due to the license.
So having a fallback FFT would be useful for me.

ciao
Fawzi
Jul 27 2010
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 I was preceded, that is a good list. I can only say that FFTW is
 *really* good, and if you structure your code well you should be able
 to support more than one library.
 I have wrappers for fftw, and it can be used with NArray (N
 dimensional dense arrays in blip), but is not directly there exactly
 due to the license.
 So having a fallback FFT would be useful for me.
 ciao
 Fawzi


This was kind of my point:  Does a "simple and good enough" FFT that's O(N log
N)
but not super optimized and maybe works on generic ranges and ranges of ranges
belong in Phobos?  The idea is that if you just need a few FFTs here and there,
convenience is important, and they're not a major bottleneck for you, you use
Phobos.  If you need the absolute best even if it has to be installed
separately,
is under a more restrictive license, is more of a PITA to use, etc., you use
FFTW
or something.

My use case, to give a little more detail as an example, is that I want to add
kernel density estimation to dstats.  I need a reasonably efficient way to
compute
a convolution, but not super-optimized pedal-to-the-metal ones, and I need to
not
have to add a dependency to dstats just for this and for the license to be
compatible.
Jul 27 2010
parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 27-lug-10, at 23:28, dsimcha wrote:


 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 I was preceded, that is a good list. I can only say that FFTW is
 *really* good, and if you structure your code well you should be able
 to support more than one library.
 I have wrappers for fftw, and it can be used with NArray (N
 dimensional dense arrays in blip), but is not directly there exactly
 due to the license.
 So having a fallback FFT would be useful for me.
 ciao
 Fawzi


 This was kind of my point:  Does a "simple and good enough" FFT  
 that's O(N log N)
 but not super optimized and maybe works on generic ranges and ranges  
 of ranges
 belong in Phobos?  The idea is that if you just need a few FFTs here  
 and there,
 convenience is important, and they're not a major bottleneck for  
 you, you use
 Phobos.  If you need the absolute best even if it has to be  
 installed separately,
 is under a more restrictive license, is more of a PITA to use, etc.,  
 you use FFTW
 or something.


about belonging to phobos I don't know, but it would be useful.
The program I am working on will be GPL, so I don't have problems with  
fftw,
still the fftw binding is one place where I know that I should work  
more...


 My use case, to give a little more detail as an example, is that I  
 want to add
 kernel density estimation to dstats.  I need a reasonably efficient  
 way to compute
 a convolution, but not super-optimized pedal-to-the-metal ones, and  
 I need to not
 have to add a dependency to dstats just for this and for the license  
 to be compatible.


I understand, I need more performance from the fft.

I know numpy  uses fftpack, but that is fortran, but it has a c  
version, probably not the best choice to have a maintanable code, but  
the .c version is small, see
http://www.netlib.org/fftpack/

fawzi
Jul 27 2010
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
dsimcha wrote:

 I'm going to need an FFT library to perform some convolutions at some point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough"


What does "simple" mean?
If you're happy with lengths being restricted to powers of 2, it's 
simple. Most of the complexity of something like FFTW comes from support 
for arbitrary lengths.


 3.  If I do end up writing my own or porting, is there sufficient interest in
 this that I should try to target it for std.numerics, or would I be better off
 just making it good enough for my use case?


I think that a basic power-of-2 FFT is simple enough, and sufficiently 
widely used to be worth including.
Jul 27 2010
next sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 28-lug-10, at 06:22, Don wrote:


 dsimcha wrote:

 I'm going to need an FFT library to perform some convolutions at  
 some point
 soon.  Two absolute, non-negotiable requirements are that it be  
 written in
 pure D and that it be Boost or compatibly (i.e. zlib or public  
 domain)
 licensed.  I also prefer "simple and good enough"


 What does "simple" mean?
 If you're happy with lengths being restricted to powers of 2, it's  
 simple. Most of the complexity of something like FFTW comes from  
 support for arbitrary lengths.


and cache awarness..., but yes efficiently supporting arbitrary  
lengths is difficult.


 3.  If I do end up writing my own or porting, is there sufficient  
 interest in
 this that I should try to target it for std.numerics, or would I be  
 better off
 just making it good enough for my use case?


 I think that a basic power-of-2 FFT is simple enough, and  
 sufficiently widely used to be worth including.


Note that the fft from fftpack support arbitrary lengths (the  
efficiency decreases, but not so drastically).
I would put something like that for "casual" use, so that one doesn't  
have to worry too much about sizes.
If he needs something better then he should start to worry about it.  
For example one could have a routine returning the next "good" size,  
always increasing.

Fawzi
Jul 28 2010
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam nospam.com)'s article

 dsimcha wrote:

 I'm going to need an FFT library to perform some convolutions at some point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough"


 What does "simple" mean?
 If you're happy with lengths being restricted to powers of 2, it's
 simple. Most of the complexity of something like FFTW comes from support
 for arbitrary lengths.


Yeh, I only need powers of two.  I realize this isn't very hard because I wrote
a
prototype of it a while back.  However, this prototype would basically need to
be
rewritten b/c:

1.  It only supports pure real inputs, meaning you can't use it to compute
inverse
FFTs.

2.  I tried to write it using strides instead of rearranging the elements of the
arrays, mostly because I was curious what effect this would have on performance.
It turned out to be disastrous, presumably because it killed cache efficiency.
Jul 28 2010
parent Don <nospam nospam.com> writes:
dsimcha wrote:

 == Quote from Don (nospam nospam.com)'s article

 dsimcha wrote:

 I'm going to need an FFT library to perform some convolutions at some point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough"


 What does "simple" mean?
 If you're happy with lengths being restricted to powers of 2, it's
 simple. Most of the complexity of something like FFTW comes from support
 for arbitrary lengths.


 
 Yeh, I only need powers of two.  I realize this isn't very hard because I
wrote a
 prototype of it a while back.  However, this prototype would basically need to
be
 rewritten b/c:
 
 1.  It only supports pure real inputs, meaning you can't use it to compute
inverse
 FFTs.
 
 2.  I tried to write it using strides instead of rearranging the elements of
the
 arrays, mostly because I was curious what effect this would have on
performance.
 It turned out to be disastrous, presumably because it killed cache efficiency.


I believe that a moderately efficient cache-aware FFT could be made 
using simple blocking with the info from core.cpuid.
Jul 28 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
  3.  If I do end up writing my own or porting, is there sufficient interest

 in
 this that I should try to target it for std.numerics, or would I be better
 off
 just making it good enough for my use case?


 I think that a basic power-of-2 FFT is simple enough, and sufficiently
 widely used to be worth including.


You have my vote, David. As long as it does 2D FFT, it'll cover the vast
majority of my own needs. And FFT is exactly the kind of things I need
regularly, but only a few times a year. Having it in std.numerics would be
excellent.


Philippe
Jul 28 2010
prev sibling parent reply jtravs <jtravs gmail.com> writes:
dsimcha Wrote:


 I'm going to need an FFT library to perform some convolutions at some point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use", as long as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few questions:
 
 1.  Does anyone already have such a lib?
 
 2.  If noone has one I'll probably either write my own from scratch  or port
 some code from C if I can find code that's under a suitable license and
 written with a "simple and good enough" philosophy rather than an "every tiny
 optimization in the book" philosophy.  Could anyone recommend one to port?
 


You should have a look at kissfft. It is very small (one short c file),
appropriately licensed and supports arbitrary sizes quite efficiently.

I have recently ported this to the go programming language in just a few hours
work. I'm willing to help with a D version too, if you want, as I might also
need this soon.

kissfft can be found at: http://kissfft.sourceforge.net

J
Jul 28 2010
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from jtravs (jtravs gmail.com)'s article

 dsimcha Wrote:

 I'm going to need an FFT library to perform some convolutions at some point
 soon.  Two absolute, non-negotiable requirements are that it be written in
 pure D and that it be Boost or compatibly (i.e. zlib or public domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use", as long as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few questions:

 1.  Does anyone already have such a lib?

 2.  If noone has one I'll probably either write my own from scratch  or port
 some code from C if I can find code that's under a suitable license and
 written with a "simple and good enough" philosophy rather than an "every tiny
 optimization in the book" philosophy.  Could anyone recommend one to port?


 You should have a look at kissfft. It is very small (one short c file),


appropriately licensed and supports arbitrary sizes quite efficiently.

 I have recently ported this to the go programming language in just a few hours


work. I'm willing to help with a D version too, if you want, as I might also
need
this soon.

 kissfft can be found at: http://kissfft.sourceforge.net
 J


This looks great except that the license requires binary attribution.  I've
emailed the author and asked him to waive the binary attribution requirement and
let me use it under the Boost license for the purpose of a D port.  If he goes
for
it, I'll probably just port this code to D for std.numeric, and then use it
where
I need to in dstats.  Otherwise, it's back to square 1.
Jul 28 2010
parent reply Fawzi Mohamed <fawzi gmx.ch> writes:
On 29-lug-10, at 00:01, dsimcha wrote:


 == Quote from jtravs (jtravs gmail.com)'s article

 dsimcha Wrote:

 I'm going to need an FFT library to perform some convolutions at  
 some point
 soon.  Two absolute, non-negotiable requirements are that it be  
 written in
 pure D and that it be Boost or compatibly (i.e. zlib or public  
 domain)
 licensed.  I also prefer "simple and good enough" over "has every
 micro-optimization in the book but a PITA to maintain/modify/use",  
 as long as
 it's at least a true fft as opposed to an O(N^2) DFT.  A few  
 questions:

 1.  Does anyone already have such a lib?

 2.  If noone has one I'll probably either write my own from  
 scratch  or port
 some code from C if I can find code that's under a suitable  
 license and
 written with a "simple and good enough" philosophy rather than an  
 "every tiny
 optimization in the book" philosophy.  Could anyone recommend one  
 to port?


 You should have a look at kissfft. It is very small (one short c  
 file),


 appropriately licensed and supports arbitrary sizes quite efficiently.

 I have recently ported this to the go programming language in just  
 a few hours


 work. I'm willing to help with a D version too, if you want, as I  
 might also need
 this soon.

 kissfft can be found at: http://kissfft.sourceforge.net
 J


 This looks great except that the license requires binary  
 attribution.  I've
 emailed the author and asked him to waive the binary attribution  
 requirement and
 let me use it under the Boost license for the purpose of a D port.   
 If he goes for
 it, I'll probably just port this code to D for std.numeric, and then  
 use it where
 I need to in dstats.  Otherwise, it's back to square 1.


otherwise, as I already said http://www.netlib.org/fftpack/fft.c is  
public domain, has reasonable performance, and supports all sizes.
It might not be the always beautiful, but it is stable and works well...

Fawzi
Jul 29 2010
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
 public domain, has reasonable performance, and supports all sizes.
 It might not be the always beautiful, but it is stable and works well...
 Fawzi


Yeah, I just looked at this code.  The problem is that I wouldn't do a straight,
mechanical port to D, I'd D-ify the code a little while I was at it (such as
making it work on generic random access ranges if it's an out of place
transform,
making real-only inputs vs. complex inputs DRYer with templates, etc.).  Since
this code seems to have been straight-up translated from FORTRAN, it scores
about
a -2 the readability scale, from 1 to 10.  In other words, I would probably be
able to translate it and make it run, but even the slightest modification would
be
near impossible.
Jul 29 2010
parent reply Fawzi Mohamed <fawzi gmx.ch> writes:
On 29-lug-10, at 15:31, dsimcha wrote:


 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
 public domain, has reasonable performance, and supports all sizes.
 It might not be the always beautiful, but it is stable and works  
 well...
 Fawzi


 Yeah, I just looked at this code.  The problem is that I wouldn't do  
 a straight,
 mechanical port to D, I'd D-ify the code a little while I was at it  
 (such as
 making it work on generic random access ranges if it's an out of  
 place transform,
 making real-only inputs vs. complex inputs DRYer with templates,  
 etc.).  Since
 this code seems to have been straight-up translated from FORTRAN, it  
 scores about
 a -2 the readability scale, from 1 to 10.  In other words, I would  
 probably be
 able to translate it and make it run, but even the slightest  
 modification would be
 near impossible.


eheh this must meant that too much fortran inured me, I did not find  
the code too bad, I classified it as a typical numerical intensive  
code (even rather clean where one can easily find the boundaries of  
the arrays, and without too many goto), and templating float, using  
slices as input seemed easy.
But yes probably it is not the best basis to develop your own thing.
Ahrg fortran ruined me ;).

ciao
Fawzi
Jul 30 2010
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 On 29-lug-10, at 15:31, dsimcha wrote:

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
 public domain, has reasonable performance, and supports all sizes.
 It might not be the always beautiful, but it is stable and works
 well...
 Fawzi


 Yeah, I just looked at this code.  The problem is that I wouldn't do
 a straight,
 mechanical port to D, I'd D-ify the code a little while I was at it
 (such as
 making it work on generic random access ranges if it's an out of
 place transform,
 making real-only inputs vs. complex inputs DRYer with templates,
 etc.).  Since
 this code seems to have been straight-up translated from FORTRAN, it
 scores about
 a -2 the readability scale, from 1 to 10.  In other words, I would
 probably be
 able to translate it and make it run, but even the slightest
 modification would be
 near impossible.


 eheh this must meant that too much fortran inured me, I did not find
 the code too bad, I classified it as a typical numerical intensive
 code (even rather clean where one can easily find the boundaries of
 the arrays, and without too many goto), and templating float, using
 slices as input seemed easy.


Yes, but typical numerics intensive code is basically unreadable.  I think D is
about the only language that has enough high-level stuff (templates, etc.) to
write readable numerics code with a nice interface, but is also efficient enough
to write efficient numerics code.  Unfortunately, we're basically starting from
scratch because C and Fortran numerics code is so crufty and unreadable that
it's
really, really hard to refactor it into readable D or even put a nice interface
on it.


 But yes probably it is not the best basis to develop your own thing.
 Ahrg fortran ruined me ;).
 ciao
 Fawzi


I got permission from Mark Borgerding to port kissfft and have the binary
attribution clause waived, but unfortunately this code is almost as difficult to
read due to its extreme preprocessor abuse.  (Basically he implements complex
numbers as a struct with an imaginary and real component and a bunch of
preprocessor macros.)  Part of the preprocessor abuse is necessary for
supporting
fixed point FFTs.  Does anyone care about these (I sure don't), or can I just
get
rid of them?

I'm hoping I can refactor this code into a nice D interface, but it may end up
being that I have to basically start from scratch.  One thing I will absolutely
not do is contribute code without a proper D-style (i.e. templated, works with
std.complex, etc.) interface.  If I can't understand kissfft well enough to do
this refactoring, then maybe I'll just start from scratch using the Wikipedia
FFT
article and a textbook.
Jul 30 2010
next sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 30-lug-10, at 16:14, dsimcha wrote:


 [...]
 Part of the preprocessor abuse is necessary for supporting
 fixed point FFTs.  Does anyone care about these (I sure don't), or  
 can I just get
 rid of them?


I don't care about them


 I'm hoping I can refactor this code into a nice D interface, but it  
 may end up
 being that I have to basically start from scratch.  One thing I will  
 absolutely
 not do is contribute code without a proper D-style (i.e. templated,  
 works with
 std.complex, etc.) interface.  If I can't understand kissfft well  
 enough to do
 this refactoring, then maybe I'll just start from scratch using the  
 Wikipedia FFT
 article and a textbook.


The main thing that you should probably do (apart documenting the  
factors and order that you assume/generate)
is splitting fft in initialization of a given size (creating a struct/ 
class environment) and executing an fft of that size (which might be a  
method of the environment (probably better) or a free function taking  
the env as parameter).
Both fftpack (http://www.netlib.org/fftpack/doc) and fftw (http://fftw.org/doc/ 
) have that structure.
This because you can prepare/precompute things to then do the actual  
fft in the optimal way.
Then you can still provide easy to use wrappers that call the two  
things in sequence.

ciao
Fawzi
Jul 30 2010
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
dsimcha wrote:

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 On 29-lug-10, at 15:31, dsimcha wrote:

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
 public domain, has reasonable performance, and supports all sizes.
 It might not be the always beautiful, but it is stable and works
 well...
 Fawzi


 Yeah, I just looked at this code.  The problem is that I wouldn't do
 a straight,
 mechanical port to D, I'd D-ify the code a little while I was at it
 (such as
 making it work on generic random access ranges if it's an out of
 place transform,
 making real-only inputs vs. complex inputs DRYer with templates,
 etc.).  Since
 this code seems to have been straight-up translated from FORTRAN, it
 scores about
 a -2 the readability scale, from 1 to 10.  In other words, I would
 probably be
 able to translate it and make it run, but even the slightest
 modification would be
 near impossible.


 eheh this must meant that too much fortran inured me, I did not find
 the code too bad, I classified it as a typical numerical intensive
 code (even rather clean where one can easily find the boundaries of
 the arrays, and without too many goto), and templating float, using
 slices as input seemed easy.


 
 Yes, but typical numerics intensive code is basically unreadable.  I think D is
 about the only language that has enough high-level stuff (templates, etc.) to
 write readable numerics code with a nice interface, but is also efficient
enough
 to write efficient numerics code.  Unfortunately, we're basically starting from
 scratch because C and Fortran numerics code is so crufty and unreadable that
it's
 really, really hard to refactor it into readable D or even put a nice
interface on it.
 

 But yes probably it is not the best basis to develop your own thing.
 Ahrg fortran ruined me ;).
 ciao
 Fawzi


 
 I got permission from Mark Borgerding to port kissfft and have the binary
 attribution clause waived, but unfortunately this code is almost as difficult
to
 read due to its extreme preprocessor abuse.  (Basically he implements complex
 numbers as a struct with an imaginary and real component and a bunch of
 preprocessor macros.)  Part of the preprocessor abuse is necessary for
supporting
 fixed point FFTs.  Does anyone care about these (I sure don't), or can I just
get
 rid of them?
 
 I'm hoping I can refactor this code into a nice D interface, but it may end up
 being that I have to basically start from scratch.  One thing I will absolutely
 not do is contribute code without a proper D-style (i.e. templated, works with
 std.complex, etc.) interface.  If I can't understand kissfft well enough to do
 this refactoring, then maybe I'll just start from scratch using the Wikipedia
FFT
 article and a textbook.


This is a useful read on FFT performance.
http://cnx.org/content/m16336/latest/
Jul 31 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Don:

 This is a useful read on FFT performance.
 http://cnx.org/content/m16336/latest/


That looks good, but it's also a large amount of information.
Register allocation (spilling strategy) is critical in not uber-optimized FFT
routines.
And GPUs can help :-)

Bye,
bearophile
Jul 31 2010
prev sibling parent "Mike James" <foo bar.com> writes:
"dsimcha" <dsimcha yahoo.com> wrote in message 
news:i2umov$2esa$1 digitalmars.com...

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 On 29-lug-10, at 15:31, dsimcha wrote:

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article

 otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
 public domain, has reasonable performance, and supports all sizes.
 It might not be the always beautiful, but it is stable and works
 well...
 Fawzi


 Yeah, I just looked at this code.  The problem is that I wouldn't do
 a straight,
 mechanical port to D, I'd D-ify the code a little while I was at it
 (such as
 making it work on generic random access ranges if it's an out of
 place transform,
 making real-only inputs vs. complex inputs DRYer with templates,
 etc.).  Since
 this code seems to have been straight-up translated from FORTRAN, it
 scores about
 a -2 the readability scale, from 1 to 10.  In other words, I would
 probably be
 able to translate it and make it run, but even the slightest
 modification would be
 near impossible.


 eheh this must meant that too much fortran inured me, I did not find
 the code too bad, I classified it as a typical numerical intensive
 code (even rather clean where one can easily find the boundaries of
 the arrays, and without too many goto), and templating float, using
 slices as input seemed easy.


 Yes, but typical numerics intensive code is basically unreadable.  I think 
 D is
 about the only language that has enough high-level stuff (templates, etc.) 
 to
 write readable numerics code with a nice interface, but is also efficient 
 enough
 to write efficient numerics code.  Unfortunately, we're basically starting 
 from
 scratch because C and Fortran numerics code is so crufty and unreadable 
 that it's
 really, really hard to refactor it into readable D or even put a nice 
 interface on it.


 But yes probably it is not the best basis to develop your own thing.
 Ahrg fortran ruined me ;).
 ciao
 Fawzi


 I got permission from Mark Borgerding to port kissfft and have the binary
 attribution clause waived, but unfortunately this code is almost as 
 difficult to
 read due to its extreme preprocessor abuse.  (Basically he implements 
 complex
 numbers as a struct with an imaginary and real component and a bunch of
 preprocessor macros.)  Part of the preprocessor abuse is necessary for 
 supporting
 fixed point FFTs.  Does anyone care about these (I sure don't), or can I 
 just get
 rid of them?


Fixed-point FFTs could be important if your number-crunching data that could 
have been collected by, say, a microcontroller-based system with 16-bit 
ADCs. Integer-only FFTs are useful.


 I'm hoping I can refactor this code into a nice D interface, but it may 
 end up
 being that I have to basically start from scratch.  One thing I will 
 absolutely
 not do is contribute code without a proper D-style (i.e. templated, works 
 with
 std.complex, etc.) interface.  If I can't understand kissfft well enough 
 to do
 this refactoring, then maybe I'll just start from scratch using the 
 Wikipedia FFT
 article and a textbook.
Aug 02 2010