[clean-list] FFT with Clean

[John van Groningen]

Siegfried Gonzi wrote:

>so, would the following assumption hold: If Clean makes the
>matrix-matrix-multiplication of an array from the one-dimension 512*512 in 50sec, I
>can lay the base that Clean should take much fewer time for a FFT (Fast Fourier
>transform) of an array with only 512*512 members.
>
>...
>
>Huch, an array with 262144 (512*512) members and the FFT of that takes 90sec! >45sec is for calculating the FFT and 45sec is for garbage collection.
>
>So, there is something  not optimal. A first hint was, that the code takes 20sec
>for the bit-reversing alone (for an expected theoretical time-scaling of 2*N or so;
>my assumption).
>...
>Please could someone confrom or maybe reject my first paragraph of my message.
>Someone can believe Gonzi want to get the last from a programming language, but
>that is not so (I am to weak in computer sciences). But I think an expected
>calulation time from 7 or 10sec compared to 90sec is worth to bother.

On my G4 a 512x512 matrix multiplication takes about 7 seconds (10M heap).
A 262144 FFT of complex numbers take 1.88 seconds (10M heap). (This is not the same
FFT program as you used)

So the FFT is 3.7 times as fast.
Matrix multiplication performs 2 floating point computations per iteration, FFT 10.
So the matrix multiplication does (512/log2 262144)/5=5.7 times as many
floating point computations.

So your expected time of 7-10 seconds is probably too fast, but 90 seconds is too slow.

>[Can I study the above mentioned FFT code study with the time-profiling tool? I
>tried it, but I only get a window with a row. And this row has for all values a
>'0']

This should be possible. To find the cause try this: Open the profile file that
was generated by your application with a text editor, you should see lines starting
with a function name, followed by several numbers. If this is not the case,
make sure the "Never time profile" option in the Clean compiler dialog is disabled. If the profile file looks ok, there must be a problem with the ShowTimeProfile
application.

If you can't find the cause, report this as bug the clean@cs.kun.nl, and send
us the profile file, the project (.prj) file, the program and the .abc file
(only if it is small).

Regards,

John van Groningen