On Aug 23, 2009, at 10:47 PM, Robert Dodier wrote:
> On 8/23/09, ?iga Lenar?i? <ziga.lenarcic at gmail.com> wrote:
>
>> myfft uses bordeaux-fft. I wrote a thin layer to convert maxima list
>> to a complex lisp array and back. The difference grows for bigger
>> sample sizer (for which the reason must be inefficient list
>> conversion of O(N^2) in current fft).
>
>> Any interest?
>
> Well, I suspect you're right about the list/array conversion
> being the bottleneck. If so, then just replacing that with
> faster code is going to get us most of the speed improvement
> with a tiny fraction of the effort. I can merge in a patch
> for the list/array conversion if you write it.
>
> Robert Dodier
Actually if you look at the source code - it's a real mess with a lot
of badly coded parts. The author also makes some very bad assumptions
about fft code which he has translated from a fortran version printed
in a book (not a good thing in my book) - like using two arrays, one
for real parts and one for imaginary is fast. It's never a good idea
to access two big arrays in a tight loop instead of just one -
processor has trouble caching two different memory locations which
effectively can mean a lot of unused processor cycles when waiting to
retrieve data. This is a very important factor when writing numerical
code...
Nevertheless I'll try to rewrite the parts that look problematic (one
only has to search 'nth' through source code) with 'coercing' to
lists and arrays as suggested by Fateman. I'll time the results and
report back, prepare diffs if it runs nicely..
Regards,
Ziga