[phobos] FFT

[David Simcha]

Unfortunately I just downloaded the benchmark program for FFTW and my 
FFT is a ton slower, depending on how you look at it.  Using size 2^20 
as my benchmark, FFTW takes about 131 seconds to create its plan, even 
using -oestimate, the fastest planner.  However, the plan can be reused 
if performing multiple FFTs of the same size, and once the plan is 
created, it can do an FFT of size 2^20 in about 53 milliseconds (which I 
find almost unbelievable because even sorting an array of size 2^20 
using a well-optimized quick sort takes almost that long, and FFT seems 
like it should should have a much larger constant than quick sort), 
compared to my latest improvements to around 730 on the hardware I'm 
benchmarking on.

On the other hand, for one-off use cases, the lack of needing to create 
a plan is a big win, both from a speed and a simplicity of API point of 
view.  Benchmarking against R, which doesn't appear to use plans, making 
the comparison somewhat more relevant, things look better for my FFT:  R 
takes about 610 milliseconds for a size 2^20 pure real FFT.

On 8/2/2010 5:30 AM, Don Clugston wrote:
> On 2 August 2010 06:10, Andrei Alexandrescu<andrei at erdani.com>  wrote:
>    
>> It would be useful to compare this against the other FFTs that have been
>> talked about. I don't mean to discourage! I think the typical user of FFT
>> would put no price on readability and would be interested exclusively in
>> speed. If your implementation is within the ballpark, then great. If it's
>> considerably slower, then I think people won't say "well it's slower but I
>> like the elegance inside it".
>>
>> Andrei
>>      
> I agree with that, although I think there are FFT use cases which rate
> convenience over speed, especially if the speed is only a factor of
> three slower than worlds' best practice.
> We can assume that any usage of FFTs which is really speed critical
> will be using FFTW (or a similar library). So a Phobos FFT should not
> be aimed at power users. It might even be used for testing (do I need
> an FFT here?) which is basically what you've ended up doing.
> (My philosophy for std.bigint is the same; power users will use GMP,
> but for casual usage, GMP is overkill and a nuisance to set up).
> OTOH I think we need to be careful, it still needs to be much better
> than something which users could write themselves in a few hours...
>
>    
>> On 08/01/2010 06:31 PM, David Simcha wrote:
>>      
>>> Ok, here's the code, I've got it down to about 800 milliseconds for a
>>> 2^20 double[] ->  Complex!double[] transform. In comparison, the R
>>> statistics package, which is probably very heavily optimized and uses (I
>>> think) GCC as its compiler can do a similar transform in ~610
>>> milliseconds, so my code isn't blindingly fast, but it's not
>>> unreasonably slow.
>>>
>>> On 8/1/2010 5:21 PM, Jason Spencer wrote:
>>>        
>>>> I don't have much of an opinion on adding to Phobos, but I'd
>>>> definitely be
>>>> interested in seeing the code. I'm starting to do some scientific
>>>> computing
>>>> using D, and that would be a great learning reference for me.
>>>>
>>>> Jason
>>>>
>>>>
>>>> ----- Original Message ----
>>>>          
>>>>> From: David Simcha<dsimcha at gmail.com>
>>>>> To: Discuss the phobos library for D<phobos at puremagic.com>
>>>>> Sent: Sun, August 1, 2010 1:32:38 PM
>>>>> Subject: Re: [phobos] FFT
>>>>>
>>>>> Speed-wise, I've just been goofing around for the past hour or so and
>>>>> I've sped
>>>>> it up 2x. It now does 1 size 2 ^^ 20 double[] ->  Complex!double FFT
>>>>> in about
>>>>> 880 milliseconds.
>>>>>
>>>>> On 8/1/2010 3:36 PM, Walter Bright wrote:
>>>>>            
>>>>>> David Simcha wrote:
>>>>>>              
>>>>>>> As I am no longer going to use FFTs in my kernel density lib,
>>>>>>> improving
>>>>>>>                
>>>>> this FFT code will be bumped down my hacking to-do list. Does what I
>>>>> have now
>>>>> sound better than nothing by a large enough margin to warrant
>>>>> inclusion in
>>>>> std.numeric, or does it sound too primitive to be widely useful? If
>>>>> it sounds
>>>>> worth including I'll clean up/document the code and send it to the
>>>>> mailing list
>>>>> for review. If it sounds too primitive, I'll just scrap it.
>>>>>            
>>>>>> I don't know enough about FFT's to make any sort of informed comment.
>>>>>> _______________________________________________
>>>>>> phobos mailing list
>>>>>> phobos at puremagic.com
>>>>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>>>>
>>>>>>              
>>>>> _______________________________________________
>>>>> phobos mailing list
>>>>> phobos at puremagic.com
>>>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>>>
>>>>>            
>>>
>>>
>>> _______________________________________________
>>> phobos mailing list
>>> phobos at puremagic.com
>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>        
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>>      
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
>