patchGNU Octave - Patches: patch #7999, Further adjustments to fftfilt...

 
 

patch #7999: Further adjustments to fftfilt after changeset for bug 37297

Submitter:  Dan Sebald <sebald>
Submitted:  Fri 05 Apr 2013 10:33:09 PM UTC
   
 
Category:  None Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  mtmiller Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 21 Oct 2013 10:54:16 PM UTC, comment #6: 

Closing this patch tracker since there has been no activity and as I read it all issues that were raised have been addressed in the current version of the function. I just pushed a change to fix some minor problems with the docstring, but I don't think it needs much more work at this point.

Mike Miller <mtmiller>
Group Member
Fri 26 Jul 2013 06:38:31 AM UTC, comment #5: 

True, I should have kept that N for the FFT size to differentiate from the argument n.

Yes, we could address the performance tradeoff either in the docstring or with a warning, but do we know that some threshold that we identify will be the same across different hardware?

I'd be more inclined to add a note to the docstring with something general like "Certain values of @var{n} may result in much worse performance than others.  If you are unsure how to specify the value of @var{n}, use the two-argument form or use the filter function instead."

I saw the messages on the mailing list about the failing tests, feel free to open another patch tracker item about that one.

Mike Miller <mtmiller>
Group Member
Fri 26 Jul 2013 06:10:58 AM UTC, comment #4: 

Yes, that comment is good.  Typically capital N is used when referring to FFTs, but it's not critical.  That accounts for one of the issues.  Thanks.

The bulk of this patch concerned properly using the fftfilt() approach.  If I'm recalling correctly, someone had complained about the fftfilt being slow.  However, my conclusion was that there is a proper circumstance for choosing to use fftfilt compared to normal convolution.  Do we want to address that in some way?  E.g., make note in the documentation, or include the warning message that is part of the patch?  If not, let's close the entry.

I still need to tweak one of the tests, but that can be a separate bug/patch report.

Dan Sebald <sebald>
Fri 26 Jul 2013 05:48:47 AM UTC, comment #3: 

I checked in the following change to the fftfilt docstring:

http://hg.savannah.gnu.org/hgweb/octave/rev/641c47e8bcae

Does that take care of explaining the use of the N parameter?

Mike Miller <mtmiller>
Group Member
Sat 06 Apr 2013 08:00:14 AM UTC, comment #2: 

If the Octave documentation were to indicate that N is chosen as the next power of two above the maximum of N and the filter length, then no warning is fine.  There has to be something that indicates that.

I suggest still keeping the warning about inefficiency of over-lap add if the value of N is chosen unwisely short.

Dan Sebald <sebald>
Sat 06 Apr 2013 03:54:22 AM UTC, comment #1: 

I haven't had time to look at this in much detail, but keep in mind Matlab compatibility.

http://www.mathworks.com/help/signal/ref/fftfilt.html

The "Algorithms" section at the bottom of the page describes how the FFT size argument (or lack thereof) is handled by the routine. In particular it does explicitly say that it will round the user-specified value up to the next largest power of 2. Since this is part of the defined behavior of the function I don't think it warrants a warning message.

Mike Miller <mtmiller>
Group Member
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 user-friendly 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 overlap-and-add 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):


octave:10> fftfiltbenchmark (64, 64)
filter cpu (s): 0.111983
warning: fftfilt: N is small relative to length of filter, may run slowly
fftfilt cpu (s): 117.42
maximum discrepancy: 1.06581e-14

[Wow, that was slow.  The block length L is one meaning that there is only a single element of the computation free of the wrap-around 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.]


octave:11> fftfiltbenchmark (64, 96)
filter cpu (s): 0.111982
warning: fftfilt: N is small relative to length of filter, may run slowly
fftfilt cpu (s): 3.72343
maximum discrepancy: 2.4869e-14

[Well, that's much better than the previous, but still much worse than just doing normal convolution.]


octave:12> fftfiltbenchmark (64, 128)
filter cpu (s): 0.110984
fftfilt cpu (s): 2.04869
maximum discrepancy: 3.90799e-14

[Better still, not much compared to previous choice of N.  No more warning message about potential slowness.  At least it isn't dreaded slow.]


octave:13> fftfiltbenchmark (64, 256)
filter cpu (s): 0.110983
fftfilt cpu (s): 0.888865
maximum discrepancy: 3.90799e-14

[Again getting better, but at this trend it doesn't seem like the fftfilt algorithm is worth much.]


octave:14> fftfiltbenchmark (64, 512)
filter cpu (s): 0.110983
fftfilt cpu (s): 0.535919
maximum discrepancy: 4.61853e-14

[Same trend.]


octave:15> fftfiltbenchmark (64, 1024)
filter cpu (s): 0.110983
fftfilt cpu (s): 0.396939
maximum discrepancy: 5.32907e-14

[Not doing much.]


octave:16> fftfiltbenchmark (96, 1024)
filter cpu (s): 0.167975
fftfilt cpu (s): 0.406937
maximum discrepancy: 6.75016e-14

[OK, lets increase the filter length then.  Now too much increase in the fftfilt cpu consumption.  The reason is that 1024-96 isn't too much different from 1024-64.  But the filter convolution is trending upward a bit.]


octave:17> fftfiltbenchmark (128, 1024)
filter cpu (s): 0.217967
fftfilt cpu (s): 0.45893
maximum discrepancy: 9.23706e-14

[Trending upward on the filter cpu consumption still.]


octave:18> fftfiltbenchmark (256, 1024)
filter cpu (s): 0.419936
fftfilt cpu (s): 0.468929
maximum discrepancy: 2.27374e-13

[Same trend.]


octave:19> fftfiltbenchmark (512, 1024)
filter cpu (s): 3.41548
fftfilt cpu (s): 0.651901
maximum discrepancy: 4.83169e-13

[OK, now normal convolution is starting to lose out in a big way.]


octave:21> fftfiltbenchmark (512, 1023)
filter cpu (s): 3.41648
fftfilt cpu (s): 0.809876
maximum discrepancy: 3.97904e-13

[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.]


octave:22> fftfiltbenchmark (512, 1025)
filter cpu (s): 3.41848
fftfilt cpu (s): 0.823875
maximum discrepancy: 3.69482e-13

[Again, non power of two but on the other side of 1024.]


I changed the internal fftfiltbenchmark routine to use "ones" instead of "rand".


octave:23> fftfiltbenchmark (512, 1024)
filter cpu (s): 3.42048
fftfilt cpu (s): 0.697894
maximum discrepancy: 0

[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 for-loop 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.

Dan Sebald <sebald>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #27784:  octave-fftfilt-2013apr05.patch added by sebald (3KiB - application/octet-stream)
file #27783:  fftfiltbenchmark.m added by sebald (383B - application/vnd.wolfram.mathematica.package)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by sebald (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-10-21 mtmiller StatusIn Progress Done
        Open/ClosedOpen Closed
    2013-07-26 mtmiller StatusNone In Progress
        Assigned toNone mtmiller
    2013-04-05 sebald Attached File- Added octave-fftfilt-2013apr05.patch, #27784
    2013-04-05 sebald Attached File- Added fftfiltbenchmark.m, #27783

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code