Estimating costs due to memory allocation in FFT
in [Matlab]
|
Prev: Gaussian Filter
Next: command "imagesc"
From: Matt J on 11 Jul 2010 08:27 darthshak <vishakadatta(a)gmail.com> wrote in message <493389247.59587.1278070392955.JavaMail.root(a)gallium.mathforum.org>... > Now, the net execution time for the statement containing the call to the fft() function was approximately 1080 seconds. However, in my experience with MEX-functions in general, there is usually a lot of overhead involved in making a large number of MEX function calls, in some cases, even 3x or 4x the actual execution time of the function. =================== Maybe that's true when the execution time of the function is very small in comparison to the time it takes for the MATLAB interpreter to do its job launching the function. I can't see why that would be true in general, though, and certainly wouldn't expect it in this case where your data sizes are 2^14. > Also, if memory allocation is genuinely an issue, is there a way to keep the memory persistent between function calls? This is possible with user-defined MEX function with the mexMakeArrayPersistent() function, but is there a similar such setting with the FFTW library set? ================ fft(X) acts columnwise on X when X is a matrix. If possible, you could shorten your loop and pass chunks of data in matrices to fft() rather than as individual vectors. I would imagine that when fft() is working in column-by-column mode, it is smart enough to know that it can keep the memory allocated during the processing of the previous column when moving on to the next one. Another way this might save you time is that by shortening the for-loop more execution is done in builtin code than M-code. > Also, I just have a nagging feeling that much of this time is being spent in memory allocation and reallocation. ============== Your nagging feeling could just be your imagination. According to this page http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Data_reordering.2C_bit_reversal.2C_and_in-place_algorithms some FFT implementations are in-place, with essentially no memory allocation overhead at all. I don't know if MATLAB's implementation is in-place, but since we don't know, there can be no firm basis to the feeling that it isn't.
From: darthshak on 11 Jul 2010 20:56 @Matt : The argument that passing a matrix instead of a vector makes sense. I'll give that a shot.
From: kk KKsingh on 23 Jul 2010 03:18
Rune Allnor <allnor(a)tele.ntnu.no> wrote in message <ef73c50e-33cd-4396-9790-463a9b3c7327(a)x21g2000yqa.googlegroups.com>... > On 2 Jul, 13:32, darthshak <vishakada...(a)gmail.com> wrote: > > Hi all > > > > I had recently written some code for intensive number crunching. In one of the test runs, I had to call the fft() function ~ 6.4 million times in a nested loop. The number of points of each vector being transformed is usually around 2^14. > > > > Now, the net execution time for the statement containing the call to the fft() function was approximately 1080 seconds. > > That's, what, some 17 minutes? Not too bad. A different way of > stating this is that you are executing some 6000 1684 pt DFTs > every second. > > > However, in my experience with MEX-functions in general, there is usually a lot of overhead involved in making a large number of MEX function calls, in some cases, even 3x or 4x the actual execution time of the function. Is this is a possibilty in this case, even though the fft() is a built-in function? > > That's nothing you need to worry about. Run-time speed is not, > and has never been, a prioritized aspect of matlab. > > > Also, I just have a nagging feeling that much of this time is being spent in memory allocation and reallocation. If so, is there any way, with or without MATLAB, that I can profile this fft() function and figure out how much time is spent on calculating *only* the Fourier transform itself? > > There is only *one* reason to use matlab for programming: > To save *coding* time. The time you save on getting something > up and running is paid for by poor run-time performance. > > If you really want speed, ditch matlab alltogether and > use one of the compiled languages. Of course, chances are > that you will spend a lot of time on numerical stuff that > comes canned with matlab (this si the case with C or C++), > or you will spend a lot of time coming up with flexible > control structures that is hard also in matlab (which is > the case with fortran). > > Rune Hi Rune! You have given me lot of replies regarding FFT. So looking forward for your comments on http://www.mathworks.com/matlabcentral/newsreader/view_thread/287549#764924 |