Fri 05 Apr 2013 10:33:09 PM UTC, original submission:
Rik expressed concern about the loop introduced near the end of the changeset associated with bug 37297:
https://savannah.gnu.org/bugs/?37297
Jordi eliminated the loop in the repository.
I looked further at the whole algorithm and propose the following adjustments to make fftfilt a more userfriendly script.
After trying this fftfilt() routine a bit, what I don't like about it is if the user isn't completely familiar with the routine, the results could be misleading to the point where the conclusion is that the routine is very bad. It has to do with choosing an overlapandadd FFT length that is so short compared to the length of filter impulse response b. If the user does such a thing, the algorithm becomes absurdly slow.
First, I don't like when algorithms change the settings on the user:
n = 2 ^ nextpow2 (max ([n, l_b]));
especially without notification of doing so. Second, it would be nice if the algorithm would give some kind of hint to the user that what they are doing is wrong.
I've attached a patch to show the mods I'd like. The changes don't modify the FFT length. The mods allow the programmer to use, say, N=817 if he or she would like. Doing so wouldn't be as efficient as a power of two FFT, but the loss from that choice isn't that great and I've noted in the help that a power of two FFT is more efficient.
I've also attached a short script file for you to compare techniques. The first input is the length of b. The second input is the length N of the FFT. Try things like the following (I'll write a remark after each):
[Wow, that was slow. The block length L is one meaning that there is only a single element of the computation free of the wraparound effect of circular convolution. The FFT,FFT,mult,IFFT has to be done for every sample, and we know that the looping is somewhat slow.]
[Well, that's much better than the previous, but still much worse than just doing normal convolution.]
[Better still, not much compared to previous choice of N. No more warning message about potential slowness. At least it isn't dreaded slow.]
[Again getting better, but at this trend it doesn't seem like the fftfilt algorithm is worth much.]
[Same trend.]
[Not doing much.]
[OK, lets increase the filter length then. Now too much increase in the fftfilt cpu consumption. The reason is that 102496 isn't too much different from 102464. But the filter convolution is trending upward a bit.]
[Trending upward on the filter cpu consumption still.]
[Same trend.]
[OK, now normal convolution is starting to lose out in a big way.]
[Here there is a change to a non power of two FFT. You can see there is maybe a 20% hit. I don't think that is worth giving a warning about, so I just made mention of it in the documentation.]
[Again, non power of two but on the other side of 1024.]
I changed the internal fftfiltbenchmark routine to use "ones" instead of "rand".
[You can see that there is a cost of about 8% for that real/imaginary and rounding cleanup at the end, but it does make the discrepancy 0.]
Without going into great analysis of the algorithm, my conclusion is that the forloop does factor in a bit (for example, fftfiltbenchmark (64, 128) result could probably be a little better), but if N is chosen right it is tolerable. The integerization and real/imaginary clean up isn't too costly, but I'd still prefer an option to remove that.
