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

 
 

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

Submitted by:  Dan Sebald <sebald>
Submitted on:  Fri 05 Apr 2013 10:33:09 PM UTC  
 
Category: NonePriority: 5 - Normal
Status: DonePrivacy: Public
Assigned to: Mike Miller <mtmiller>Open/Closed: Closed

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project MemberIn charge of this item.
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>
Project MemberIn charge of this item.
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>
Project MemberIn charge of this item.
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>
Project MemberIn charge of this item.
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):

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

[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 1024-96 isn't too much different from 1024-64. 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 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 File(s):
   
   
Comment:
   

Attached Files
file #27784:  octave-fftfilt-2013apr05.patch added by sebald (3kB - 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
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by sebald (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 21 Oct 2013 10:54:16 PM UTCmtmillerStatusIn Progress=>Done
      Open/ClosedOpen=>Closed
    Fri 26 Jul 2013 06:38:31 AM UTCmtmillerStatusNone=>In Progress
      Assigned toNone=>mtmiller
    Fri 05 Apr 2013 10:36:47 PM UTCsebaldAttached File-=>Added octave-fftfilt-2013apr05.patch, #27784
    Fri 05 Apr 2013 10:33:09 PM UTCsebaldAttached File-=>Added fftfiltbenchmark.m, #27783

    Back to the top


    Powered by Savane 3.1-cleanup