bugGNU Octave - Bugs: bug #61674, deconv much slower than conv

 
 

bug #61674: deconv much slower than conv

Submitted by:  None
Submitted on:  Tue 14 Dec 2021 10:41:01 PM UTC  
 
Category:  Interpreter Severity:  3 - Normal
Priority:  3 - Low Item Group:  Performance
Status:  Ready For Test Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  Open Release:  dev
Operating System:  Any

Add a New Comment (Rich Markup)
   

You are not logged in

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

 

( Jump to the original submission)

Fri 31 Dec 2021 06:31:57 PM UTC, comment #17: 

I pushed your change here:
https://hg.savannah.gnu.org/hgweb/octave/rev/d2cd9ead4c84

Marking as ready for test.

Markus Mützel <mmuetzel>
Project Member
Tue 28 Dec 2021 02:10:49 PM UTC, comment #16: 

Good points all. I've moved iidx inside the if-block but outside its for-loop. I removed the comment about setting num_inner based on CPU speed. I also added back quit.h -- in an earlier version I had removed it when removing octave_quit completely, but when I added back octave_quit it compiled without needing quit.h, so I didn't add it at the time, but yes, it needs to be self-contained in case the compilation order changes.

Updated patch attached.

(file #52575)

Arun Giridhar <arungiridhar>
Tue 28 Dec 2021 11:59:53 AM UTC, comment #15: 

Is there a reason why you removed including "quit.h"?

> +      // Can num_inner be set automatically at configure time based on actual
> +      // computer speed? Or is that too complicated?


Even if that was possible, that wouldn't help for distributions where Octave is built on different hardware than where it is executed. If at all, we'd need a runtime check. But I'm not sure if that check is worth the additional maintenance burden.

I might be missing something. But `iidx` is only used if `a_len > 1`. Would it make sense to move its scope to inside that branch of the `if` block?

Markus Mützel <mmuetzel>
Project Member
Thu 16 Dec 2021 11:14:31 PM UTC, comment #14: 

May be similar trick can apply to other places with
octave_quit.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 16 Dec 2021 05:41:23 PM UTC, comment #13: 

Cleaned up patch attached with a commit message.

Markus, I've listed you as a co-author for the loop-splitting idea.

Glad we could all speed up some code together!

(file #52517)

Arun Giridhar <arungiridhar>
Thu 16 Dec 2021 04:36:07 PM UTC, comment #12: 

This looks great.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 16 Dec 2021 04:09:41 PM UTC, comment #11: 

Patch 4 attached to split up the loop into outer and inner as mmuetzel suggested. Also moved some loop invariants out of their respective loops. Performance is almost as fast as Patch 1. Please test and see how interruptible this code is. I think the sweet spot for num_inner is somewhere between 30K and 300K and it can be tuned as needed. Passes BISTs.

(file #52515)

Arun Giridhar <arungiridhar>
Thu 16 Dec 2021 01:58:32 PM UTC, comment #10: 

Not sure if this will make a difference. But have you tried to create an inner loop without `if` conditionals and an outer loop that contains the octave_quit function call?
Something along the lines of

int some_big_number = 100000;
int n_inner_loop = 1000;
for (int i_outer = 0, i_outer < some_big_number/n_inner_loop, i_outer++)
{
  for (int i_inner = 0, i_inner < n_inner_loop, i_inner++)
  {
     do_the_actual_work
  }

  octave_quit ();
}

Obviously, we'd need to put a little bit more thought in to get the number of inner loop runs correct. But maybe that would allow the compiler to optimize the inner loop while still having the outer loop interruptible...

Markus Mützel <mmuetzel>
Project Member
Thu 16 Dec 2021 01:22:13 PM UTC, comment #9: 

I do not have a good sense of what a typical run-time for filter is, because it is used by multiple functions like deconv, fftfilt and others. If it typically takes 10 or 15 seconds currently, then Patch 1 will speed that up to no more than 2 or 3 seconds, so running without Ctrl-C for that long becomes very viable. But if typical run times are longer than a minute, then Patch 1 will reduce it to about 10 seconds without Ctrl-C, which may surprise the user if long run-times like that are normal in interactive mode.

Profiling indicates that more than 95% of the time in deconv is spent in filter.cc, and some 81% of the time inside the filter function is because of octave_quit. There does not seem to be much opportunity to speed up deconv other than focusing on octave_quit inside filter.cc. Thoughts?

Arun Giridhar <arungiridhar>
Thu 16 Dec 2021 03:20:33 AM UTC, comment #8: 

The signal handler runs in a separate thread.  To safely handle interrupts, all it can do is set a global variable to indicate that an interrupt signal has arrived.  It is up to the interpreter to check the status of that variable and throw an exception when it is safe to do so.  This problem is not specific to deconv, so it should probably be discussed separately from this bug report.  For deconv, is there something we can do to make it perform better in typical use cases?

John W. Eaton <jwe>
Project Administrator
Thu 16 Dec 2021 03:11:39 AM UTC, comment #7: 

Try patch 3, but this isn't fast. It's not as slow as the original code but it's 3 times slower than patch 1 or patch 2.

It turns out that even if octave_quit is never called based on the value of count, simply adding the code to call it prevents the compiler from optimizing the loop internals, and it slows by 3X compared to patch 1 and patch 2. Tuning the value of count does not help in this case: making it big or small gives the same slow performance.

Is there a better way to handle the conflicting goals of performance and interruption handling than to call a function from inside a for loop?

(file #52512)

Arun Giridhar <arungiridhar>
Thu 16 Dec 2021 01:07:46 AM UTC, comment #6: 

Here is the benchmark I tried (my scenario is that
I accidentally use length of the windows the same as lenfth the signal itself / 2):

wlen = 3*1e3
l = 2*wlen;
t = linspace(-100*pi,100*pi,300*1e5);
x = sin(t) + 0.25*rand(size(t));
b = (1/wlen)*ones(1,wlen);
a = 1;
tic;
y = filter(b,a,x);
toc

The speedup of patch2 is comparable to v1 (73 sec vs 13.6 sec).
But here is me realising something is wrong and hitting Chtrl-C:

octave:2> filt_benchl
wlen = 3000
Elapsed time is 13.6168 seconds.
octave:3> filt_benchl
wlen = 3000
^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C^C
octave:4>

I think delay of a couple sec is acceptable, but longer than that and you will get complains/bug reports etc...
The delay is pre predictable when there is  a simple arithmetic
expression in the loop and you check for interrupts every
N loops or something like that.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Thu 16 Dec 2021 12:26:39 AM UTC, comment #5: 

How about keeping it inside the outermost loop? New patch attached. Does this allow Ctrl-C?

I'm also seeing the structure of filter.cc has many if-else decisions inside for-loops but the variables for the if-else seem invariant in the loops. Would that be ordered better as for-inside-if instead of if-inside-for?

(file #52511)

Arun Giridhar <arungiridhar>
Wed 15 Dec 2021 11:55:01 PM UTC, comment #4: 

I tried your patch for some moving average filter on a very long signal. The speedup was substantial (~ 5 times), but I cannot
interrupt calculations with Ctrl-C.

Perhaps we should not eliminate octave_quit() but check for it every say 100 or 1000 cycles or so.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 15 Dec 2021 10:36:58 PM UTC, comment #3: 

Though I said in comment #2 that filter.cc could not be sped up, I had second thoughts and examined various sections of the filter function with std::chrono::high_resolution_clock. Ultimately it looks like the bulk of the execution time was taken by the several calls to octave_quit() inside the innermost for-loops. I removed them and the speed of filter and deconv both increased by 6 times! Passes BISTs and did not affect Ctrl-C operation. I suspect the calls to octave_quit() were added when computer speeds were such that frequent checking for interrupts made sense. but now it only seems to slow down execution without added benefit.

New benchmark data from the code in comment #2. It now takes only 6.1 seconds instead of 35 seconds. This is still slower than conv2 but not 10x slower, only some 1.8x slower. Some progress anyway.

octave:1> N = 40320; profile clear; tic; profile on; Q = cyclotomicpolynomial_deconv (N); profile off; toc, T = profile("info"); profshow (T)
Elapsed time is 6.10674 seconds.
   #                    Function Attr     Time (s)   Time (%)        Calls
--------------------------------------------------------------------------
  59                      filter             5.870      96.31         1844
   1 cyclotomicpolynomial_deconv    R        0.116       1.91           96
  55                      deconv             0.069       1.13         1844

(Other function calls are the same.)

Hg diff attached for filter.cc to get this 6x speedup. Please test and see if all is good. If it is, I'll upload a patch with a commit message.

(file #52510)

Arun Giridhar <arungiridhar>
Wed 15 Dec 2021 01:51:27 PM UTC, comment #2: 

I cannot replicate OP's test reliably, because those tests take only a millisecond or less, as Kai also saw.

It is known that deconv is roughly 10x slower than conv2 for large N though. But I do not consider this a bug, just the behavior of conv2 and filter, which is called by deconv.

Here is a demo with cyclotomic polynomials that I edited to highlight the difference (two functions attached).

If you are benchmarking these functions, you will need to run each with a fresh Octave session because they use memoization, so any subsequent calls with the same input from the same Octave session will be instant.

Only 4.3 seconds for the fast version that prefers conv2 over deconv:

octave:1> N = 40320; profile clear; tic; profile on; P = cyclotomicpolynomial_conv (N); profile off; toc, T = profile("info"); profshow (T)
Elapsed time is 4.31985 seconds.
   #                  Function Attr     Time (s)   Time (%)        Calls
------------------------------------------------------------------------
  52                     conv2             3.481      80.68         1844
  58                    filter             0.742      17.20           91
   1 cyclotomicpolynomial_conv    R        0.064       1.48           96
  11                   isprime             0.007       0.16           95
  51                      find             0.004       0.10         3779
  54                    deconv             0.003       0.08           91
  23                    primes             0.002       0.05           73
   9                 binary ==             0.002       0.04         3876
  29                      cast             0.002       0.04           73
  10                       any             0.001       0.03         2108
  41                     zeros             0.001       0.02          207
  47                       end             0.001       0.02         4163
  18                    lookup             0.000       0.01          168
  44                 binary ./             0.000       0.01           91
  49                      size             0.000       0.01          328
   3                  prefix !             0.000       0.00          889
  30                    strcmp             0.000       0.00          146
  46                 binary .*             0.000       0.00           91
  33                     feval             0.000       0.00           73
  45                     round             0.000       0.00           91

Compared with 34.8 seconds for the version that calls only deconv and not conv2:

octave:1> N = 40320; profile clear; tic; profile on; P = cyclotomicpolynomial_deconv (N); profile off; toc, T = profile("info"); profshow (T)
Elapsed time is 34.8092 seconds.
   #                    Function Attr     Time (s)   Time (%)        Calls
--------------------------------------------------------------------------
  59                      filter            34.586      99.39         1844
   1 cyclotomicpolynomial_deconv    R        0.104       0.30           96
  55                      deconv             0.067       0.19         1844
  11                     isprime             0.007       0.02           95
  54                        find             0.006       0.02         3688
  41                       zeros             0.003       0.01         1945
  23                      primes             0.002       0.01           73
  52                        size             0.002       0.01         3804
   9                   binary ==             0.002       0.01         3876
  29                        cast             0.002       0.00           73
  10                         any             0.001       0.00         2108
  60                    isargout             0.001       0.00         1844
  53                    binary -             0.001       0.00         3794
  56                    isvector             0.001       0.00         3688
  58                    iscolumn             0.001       0.00         3688
  47                         end             0.001       0.00         4163
  40                    binary +             0.001       0.00         4158
   3                    prefix !             0.001       0.00         2642
  51                      length             0.001       0.00         3890
  57                       isrow             0.001       0.00         1844

Both codes call either conv2 or filter the same 1844 times, but for conv2 it takes 3.5 seconds and for deconv it takes 35 seconds.

The only workaround I see is to reduce the number of polynomial divisions in one's code. This just seems to be the nature of those functions, not a bug necessarily.

(file #52505, file #52506)

Arun Giridhar <arungiridhar>
Wed 15 Dec 2021 07:28:29 AM UTC, comment #1: 

On my Linux system I cannot observe this difference with Octave 7.  deconv is marginal slower than conv.

>> N = 10; conv_t = nan(N,1); for j = 1:N; tic; num = 1; for i = 1:50; num = conv (num, [1 -1]); end; conv_t(j) = toc; end; mean(conv_t)
ans = 3.2459e-03

>> N = 10; deconv_t = nan(N,1); for j = 1:N; tic; den = num; for i = 1:50; den = deconv (den, [1 -1]); end; deconv_t(j) = toc; end; mean(deconv_t)
ans = 4.2221e-03

Did you overwrite one of those functions?  What is the output for

>> which conv
'conv' is a function from the file /usr/share/octave/7.0.1/m/polynomial/conv.m
>> which deconv
'deconv' is a function from the file /usr/share/octave/7.0.1/m/polynomial/deconv.m

If nobody else can confirm this issue, or a reason for this unique behavior can be identified, this issue is likely to be closed soon.

Kai Torben Ohlhus <siko1056>
Project Member
Tue 14 Dec 2021 10:41:01 PM UTC, original submission:  

tic
num = 1;
for i = 1:50
  num = conv (num, [1 -1]);
end
toc

tic
den = num;
for i = 1:50
  den = deconv (den, [1 -1]);
end
toc

 deconv takes 10 to 15 times as long as conv, for multiple polynomials and powers.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #52575:  filter_v6.patch added by arungiridhar (7KiB - text/x-patch)
file #52517:  filter_v5.patch added by arungiridhar (8KiB - text/x-patch)
file #52515:  filter_v4.patch added by arungiridhar (5KiB - text/x-patch)
file #52512:  filter_v3.patch added by arungiridhar (3KiB - text/x-patch)
file #52511:  filter_v2.patch added by arungiridhar (2KiB - text/x-patch)
file #52510:  filter.patch added by arungiridhar (2KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by arungiridhar (Updated the item)
  • -email is unavailable- added by siko1056 (Posted a comment)
  •  

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

    Only project members can vote.

     

     

     

    Follow 15 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-12-31 mmuetzel StatusPatch Submitted => Ready For Test
        Release7.0.90 => dev
    2021-12-28 arungiridhar Attached File- => Added filter_v6.patch, #52575
    2021-12-28 mmuetzel Operating SystemGNU/Linux => Any
    2021-12-21 siko1056 StatusNeed Info => Patch Submitted
    2021-12-16 arungiridhar Attached File- => Added filter_v5.patch, #52517
    2021-12-16 arungiridhar Attached File- => Added filter_v4.patch, #52515
    2021-12-16 arungiridhar Attached File- => Added filter_v3.patch, #52512
    2021-12-16 arungiridhar Attached File- => Added filter_v2.patch, #52511
    2021-12-15 arungiridhar Attached File- => Added filter.patch, #52510
    2021-12-15 arungiridhar Attached File- => Added cyclotomicpolynomial_conv.m, #52505
        Attached File- => Added cyclotomicpolynomial_deconv.m, #52506
    2021-12-15 siko1056 CategoryNone => Interpreter
        Priority5 - Normal => 3 - Low
        StatusNone => Need Info

    Back to the top


    Powered by Savane 3.7